4
$\begingroup$

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.)

$\endgroup$
  • 1
    $\begingroup$ I'm confused. If you want to store all the possible keys, why do you want a hash table? Hash tables are there for the case where you only want to store a fraction of the keys and the total number of keys is too big to just use an array. $\endgroup$ – David Richerby Feb 21 '15 at 23:40
  • $\begingroup$ Perhaps you could explain why you want to use a hash for this? You want 362,880 keys, but if you're willing to use 100,000,000 slots (just 300x more), arrays will do very well at most every task I can think of. If you're storing lots of data on each node, this would be trouble, but on modern machines, handling 100 million values is a piece of cake. $\endgroup$ – Cort Ammon Feb 22 '15 at 4:22
  • $\begingroup$ @CortAmmon My algorithm needs to run under memory constraints, which is why I can't use much more than exactly 362,880 item array for the hash table. $\endgroup$ – Jakub Arnold Feb 22 '15 at 8:15
  • $\begingroup$ Maybe B-trees of suitable degree would be a better choice. $\endgroup$ – Raphael Feb 22 '15 at 10:47
  • $\begingroup$ @JakubArnold does that means you need to not only find a perfect hash (everything gets its own bin), but a minimal perfect hash (no empty bins)? The latter is a much harder task. $\endgroup$ – Cort Ammon Feb 22 '15 at 13:50
9
$\begingroup$

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
$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks! I've updated the question with more details. I guess I'll need to look into perfect hashing. $\endgroup$ – Jakub Arnold Feb 21 '15 at 22:07
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.