Hash Tables are an efficient way to store and retrieve information. To understand how they work, and why they work well, we'll consider alternative ways to store things. To concretely illustrate these methods, let's suppose you are managing a valet service. You are given keys (with numbered tags attached), store them on a key rack, and when someone arrives with a certain tag number, it's your job to find the right keys quickly. You have a board with nails on it to hang the keys on.
As you get each key, you hang it on a nail on the rack. Any nail. When it comes time to find the right key, you have to look at the tag of each key until you find the right one. (If you're smart, you look at them in a certain order, so you'll know which keys you've looked at so far.) This solution might work for 10 cars or so, but the amount of keys you have to look at to find the right one increases as more cars come in. At 20 cars it starts to become annoying, and at 100 you know this solution needs to be improved.
As you get each key, you re-hang all the keys on the pegs to keep them sorted by their tag number. When it comes time to find the right set of keys, you can quickly narrow down where the key is by comparing its value to its neighbors. If you're a computer, you keep chopping the number of keys left to look at in half using a binary search tree algorithm (less complicated than it sounds), or if you're a human you less efficiently scan the keys until you get into the right range. (Less efficient if a computer were to do it, but you can make good guesses at where it's going to be and start off pretty well.)
The problem with this technique is twofold. It still does take longer to find the right key as you get more keys (though the search goes more quickly than the linear, check-'em-all approach), but moreover it's a problem to store the keys. You have to find the right spot for the new key, and move all the other keys after that one to make room. Bleh!
If you know ahead of time how many different kinds of numbers you might get, you could set up the board ahead of time to make room for them all, and when a new key comes in you drop it on the associated peg. That way you're sorting the keys as they come in, while leaving space for new keys to be inserted into the middle of the system without having to do the jingle-jangle shuffle. Problems: 1) there are many cases when you don't know ahead of time what numbers you might have to sort (maybe the owners write down a number themselves) and 2) Even if you do know the range ahead of time, it may be wildly inefficient to create a space for every possibility. What if you know that the numbers can be from 1 to 1000? Do you create 1000 nail spots for your 10-cars-a-night-business? Foolish.
In the ideal world, what we want is a way to almost instantly know where to put a key (a way that doesn't take longer as we get more keys per night), and which also allows us to almost instantly find the key we're looking for, and one which doesn't waste too much space.
In a hash table, you store and retrieve items based on a hash key, generated by a hash function. (I may be messing up some terms--it's been a while since I took computer science. The principal is the same, regardless.) The hash function takes whatever information you are trying to store (in our example, the number on the tag) and creates a number based from it, within the range of available spaces. So let's pretend that we only have 9 nails to store items on. Our hash function might be to take the digits in the tag's number and add them up (and if the result has more than 1 digit, to add those up, and so on) until we get a 1-digit number which tells us which nail that key will be on. For example, tag number 2541 would be put on nail number 3 (2+5+4+1=12; 1+2=3). Now, whenever it's time to place a set of keys, a simple calculation tells us which nail to put the keys on, and when it comes time to find them, we know which nail to pick them up from. In the unsorted approach, we had to look through all the keys until we found the right one. With this 9-nail approach, we've now divided the number of keys to look through by 9! If we have to store 1000 keys, this helps some but not enough, and so choosing the size of your hash table (the number of available nails to store things on) is important. There's a tradeoff between trying to give each key its own nail (so you don't have to hunt through a lot of keys on a single nail) and trying to not have too many resources wasted. 10,000 nails (along with a hash function that ended up with a number between 1 and 10,000) would come close to ensuring a unique nail for each set of keys, but it would also waste a lot of board space, with many nails left empty. 2 nails (perhaps your function is to check whether the tag number is even or odd) makes certain that no nails are left empty ('wasted') but doesn't really solve the problem.
Note that this is my own suspicion at how information is stored, and should not be construed as Known Fact.
I believe that when you remember something, your brain generates a bunch of key attributes derived from the information, and uses this to store the information. Consider songs and faces.
When you hear a song, your ear is receiving a stream of pressure waves, ups and downs, vibrating your ear drum in and out. This 'waveform' of sound can be viewed on an oscilloscope, or a computer, as a jagged line going up and down. This is how sound is often stored on a computer, as a series of pieces of information describing how high the wave is at any point in time. Suppose you stored 50 songs (for you surely can recognize at least that many different songs) in a computer like this. Suppose you then gave it a 2-second sound clip from the middle of some song, and asked it whether it knew that song. It would have to compare that waveform, the squiggly lines, to each part of each song, trying to see if they matched up. What if you slowed down the sound clip a little bit--then the waveform wouldn't match what was stored in the computer, even though the computer might have stored that song. I think it's obvious that this is not how we remember songs. It would be too slow, too inefficient, too inaccurate.
I think that when your brain stores a song, you don't remember the waveform. Instead, your brain analyzes the song and finds things like "Male singer, brass instruments, tempo about this fast, a harmony which meshes like this" etc. and uses these to store the song. When you hear a sound clip, your brain has enough information to quickly analyze the clip, find the storage/retrieval keys that it uses, and to find the corresponding song.
As an aside, I think that your brain accesses the information as part of a multi-dimensional array. For the non-computer scientist, no, I'm not talking about physical dimensions, like time and space, but rather about the idea of storing and retrieving information by finding the intersection of several key values. A two-dimensional array would be a grid, like rectangular layout of nails, where you would store/retrieve items based on the row they were in and the column. [Just as you might do with a spreadsheet like Excel.] In a multi-dimensional array, you could say "Show me all the songs I know which are sung by men, have a saxophone, and have a beat which goes pit-ta-tsh pit-ta-tsh pit-ta-tsh".
When we remember what someone looks like, I think that we remember key attributes about their face. These could be a large variety of discernible keys (perhaps the separation of the eyebrows, the angle of the nose, the depth of their nasal-labial trough, the angle and sharpness of their cheekbones, etc.) and they vary from person to person. This explains why you may say "that person looks just like Uma Thurman" and your friend says to you "What, her? Not at all!" You may recognize people's faces regardless of their eyebrow shape, but to your friend the shape of the eyebrows is a large part of their storage system, and the Uma Thurman look-alike lacks a similar feature which their brain uses to discern between faces.
Caricatures work along a similar principal. There are some features which many people recognize about a particular person (Jay Leno's chin, Richard Nixon's nose) and the cartoonist accentuates and exaggerates those features, causing the cartoon's face to be even more recognizable than might be an attempt to draw them accurately.
Beyond just songs and faces, I believe that everything we remember is stored and accessed by certain key attributes which we distill out of the memory. When items are stored and retrieved based on a subset of their actual properties, it likely that some differing items will result in the same key properties. The likelihood of such a 'collision' increases as the more you try to distill down the items into fewer and fewer key properties. Remember the valet-service? If you were to store the keys based only on whether their number was odd or even, you would have a lot of collisions, as all the keys hung on only one nail or the other. Conversely, if you found a way to make 10,000 different differentiations between keys, then the chance that two would land on the same nail is quite small indeed.
They say that a large portion of the brain is 'unused', wasted. Perhaps (not integral to my theory, but wouldn't-it-be-neat-if) this is because there's a large portion of it saved as available, making certain that there are a lot of distinct spaces to store memories in. So much space, in fact, that your brain assumes, when it searches for a memory and finds one, that there are no other memories on that nail.
True memory--you're driving down a street, and suddenly you say "Hey, I'm not lost anymore! I recognize this place." Your brain has been watching everything, generating key information and running it through your memories, trying to see if anything matches a stored memory. Once it finds one you are able to retrieve that memory, and other related ones, to figure out where to go.
Dejá vu--you're sitting in a room, talking with people, and your brain (ever alert) is analyzing the situation. "I'm happy right now, a little confident, I'm seeing a large crowd of people from slightly above, on an escalator" and as it processes all the key elements of your situation, it suddenly says "Whoa! This must have happened before, because all these key elements match something else! I felt like this, I was seeing this, I was moving like this...I've been here before!" In reality, you haven't been there. You've been somewhere when you felt similar, and saw similar things. There are differences in the situation, but these differences happen to lie in areas that your brain doesn't use to store or retrieve situations.
Have you ever turned on the radio and been listening to a song, thought you knew what song it was, and then it suddenly turned out to be a different song? Same thing, in my opinion--your brain was analyzing the song into its key elements, found a song which matched, and said "I've found it! I know what song this is!" And then suddenly a woman starts singing, and your brain says "Whoops! This isn't that song. Apparently there are several songs I know which all sound similar in that middle bit, but now that I have an additional key, this woman's voice, I see that it's a different song."
When you, the crafty valet servant, use your hash function and go searching for a key, and you find several on the nail, you say "Hrm...better look at all of these and see which is right." Your brain, on the other hand, is so used to having tons of space, is so used to always having only one memory per nail, that when it finds a memory on a nail it says "Found It!" Because your brain has found that it's easier and better to assume that it found the right memory and very, very rarely be wrong than it is to double-check itself every time it remembers something. In fact, I believe that evolution long ago decided that the usually-right, sometimes wrong technique is much better, and so your brain doesn't even have the ability to "double-check" itself, except insofar as your rational mind can catch it being wrong when it says "You've been here before" and you say "Nope…never been in this mall before in my life. Wow...dejá vu!"