Question: do all minecraft maps have villages?
Answer: Since the world is infinite: yes, as long as you didn't disable structures during worldgen. They seem to only/mostly spawn in deserts and plains, so concentrate your searches there.