In a place like central New Mexico, where this mushroom-shaped hoodoo stands, erosion commonly leaves bits of resistant rock protecting the weaker rock layer beneath it.
The big geologic dictionary says that only a tall formation should be called a hoodoo; any other shape—a camel, say—is called a hoodoo rock. The defining feature of either one of these is that its shape is bizarre or fantastic. And a proper hoodoo (the word is the same as voodoo), it seems, must look like an image of the spirits that populate the voodoo cosmology—that is, it needs to be spooky. That's a curious eruption of folklore in a scientific glossary, and just another reason to love geology.