Sorted Storage

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!

Bucket Sort

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.

Hash Tables to the Rescue

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.