First, we refer to a hash of a name as a nickname. Second, my method involves hashing to a linked list.
We will have two methods of assigning nicknames, one that gives fairly short nicknames, and one that gives medium-length nicknames. We assume the medium nicknames are long enough that one wouldn’t want to store them for all the elves. For each type of nickname we have an index sheet and an address book.
The first index sheet stores all the short nicknames and next to each it has the number of elves with that nickname so far. If that number is exactly 1 then it has the line number in the first address book holding that elf’s address. A simple hash lookup.
The second index sheet stores all the medium nicknames of those elves whose short nicknames are not unique. Next to each of those, it has the number of elves with that medium nickname, and the line number in the second address book holding the address of the first of those elves. In that second address book, next to each address there is space to write the line number of the address of the next elf with that same medium nickname. A hash to a linked list.
By choosing a well-designed method of assigning short nicknames, we ensure that we rarely need to store any medium nicknames. And by choosing a well-designed method of assigning medium nicknames, we ensure that the linked lists almost never have more than one element each.
When a particular short nickname is given to a second elf, you will have to go to the address of the first elf with that short nickname, and give that elf a medium nickname. Then transcribe that elf’s address to the second address book.
When a particular medium nickname is given to an nth elf, you go to the line in the second address book with the address of the most recently added one of those elves, and next to it write the line number where the newest elf’s address will go. Or, if you like, you can build the linked list “backwards”, and have each address point to the previous, with the index page pointing to the most recent. That way you don’t have to traverse the whole list just to find its end, and you don’t have to add stuff to any existing address entry.
When a visitor comes looking for someone by name, you turn that name into a short nickname. If it’s unique, you look up the address and give it to the visitor. If not, you turn that name into a medium nickname, and write out a list of addresses of all elves with that medium nickname (which should be only one, or very few) and give that list to the visitor. If the list has more than one address, the visitor will have to compare full names at each one, but that should be extremely rare.
We could, of course, do away with the first address book, and just have a single hash to linked lists. That works too, but the tradeoff is that it requires a longer hash to get the same performance, so you have to store more information yourself as gatekeeper.
Whereas mward uses arbitrarily-many hash functions, I’m stopping at 2. There should be so few collisions that performance is barely reduced, and with mward’s method there is no upper bound on the number of hash functions that might be required—it’s not even bounded by the population of the village, because you don’t know if a given hash function actually distinguishes among any of the names until you try it.