How do humans find their way in new environments, so quickly and efficiently? Humans reuse old knowledge to build new concepts in many non-spatial domains, such as language and drawing. Could people learn maps by a similar process, that extracts common structure to speed up learning, and generalize across maps? Understanding the computational cognitive mechanisms that support this efficiency can advance the study of the human mind and enable more efficient exploration algorithms. We hypothesize that human map learning relies on inferences over the structure of unobserved spaces, based on spatial priors informed by previous experience. We model this by combining Program Induction with a Hierarchical Bayesian framework that explicitly reasons about uncertainty through strong spatial priors. Using a new behavioral Map Induction Task, we demonstrate that this computational framework explains human exploration behavior better than non-inductive models and outperforms state-of-the-art planning algorithms in a realistic spatial navigation domain.