How should I design a hash table where all the keys are permutations? 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.)
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 -&gt; 0
132 -&gt; 1
213 -&gt; 2
231 -&gt; 3
312 -&gt; 4
321 -&gt; 5