How should I design a hash table where all the keys are permutations?

Question

I need to create a hash table to store values for (possibly all) permutations of 123456789, which is exactly 362 880 keys.

Given that I know how all the keys look up front, it seems I that there should be an optimal hashing function, and an optimal size of the table to store the values in.

Is this true? If so, how can I create the perfect hashing function? And also, how can I determine the optimal size for the hash table?

update: I'm looking to store all of the possible permutations, where each will be stored only once, which means the table should in the end contain exactly all 362 880 keys (since I have a hard limit on my algorithm for which I need to optimize my worst case scenario.)

Answer 1

Simply compute the index of the permutation into the sorted list of all permutations and use that as your hash key. This can be achieved with a relatively simple algorithm: https://stackoverflow.com/questions/5131497/find-the-index-of-a-given-permutation-in-the-sorted-list-of-the-permutations-of

Once you have that index, you can make a table with exactly 9! slots - you have a perfect hash over your input domain.

For example, for n=3, the hash function produces

123 -> 0
132 -> 1
213 -> 2
231 -> 3
312 -> 4
321 -> 5

Answer 2

Since you have only 362,880 possible keys, you can uniquely represent every key with just 19 bits. (Where a really naïve representation of the key might take 9*4 = 36 bits).

I can't see a way to have this help you with hashing.

The size of the hash table is determined by how many keys you need to store, not by the size of the space of possible keys.

The size of the output of the hash function is determined by the size of the hash table.

Perfect hashing is a technical term meaning that every key maps to a different hash bucket. It is only possible to construct a perfect hash if you know the exact elements you are going to be storing before you start.

I guess if you really are going to store all possible permutations then you can make a table of 362,880 bits, map each permutation to a unique key in the range [0, 362,879], and then use the key as an index into the table, but that's hardly perfect or optimal if you usually only need to store a few thousand permutations.

Answer 3

If you want to optimize for memory usage, use an array instead of a hash table.

For example, suppose I'd like to store the following keys/values: {123456789: "alpha", 123456798: "beta", 123456879: "gamma", 987654321: "omega"}

We could instead store these in an array: [123456789, 123456798, 123456879, ..., 987654321]

To do this, you'll need a function that will take a permutation, and return a unique number between 0 and 362879 inclusive. This unique number is your array index.

Whether this is a better solution depends on what your optimisation goals are:

• lookup performance
• memory usage
• programmer time/effort
• iteration performance

Lookup performance might be better, or it might be worse. This depends on how fast your permutation->index function runs.

Memory usage will be better than a hash table -- there's no extra padding space, no hash collisions, and the keys don't need to be stored in the data structure.

Programmer time/effort will be worse than a hash table.

Iteration performance [ie, how quickly it can visit all entries in the hash table] will be greatly improved. However, since you're looking for a hash table, this is likely irrelevant.