How should I design a hash table where all the keys are permutations?
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