0
$\begingroup$

The question popped up in my head. The hash function used is Murmur3.

$\endgroup$
0

2 Answers 2

1
$\begingroup$

Making keys the same size doesn't make a huge amount of sense, but fixed-sized keys for key-value stores and database indexes are an important use case. In the real-world, people do sometimes want to search on integers, or IP addresses, or DNA $k$-mers.

If your keys are naturally the same size, then this enables an interesting optimisation, and unlike most uses of the word "optimisation", this one actually is "optimal".

For the sake of exposition, we'll assume a few things:

  • You are using a hash table that is a power of two in size, $2^n$ slots.
  • The hash function returns $m$ bits, and $m>n$.
  • This hash table is a set, so we don't need to consider the "value" part of a key-value store. This is easy to add in later, but I'm only doing this so I don't have to keep talking about it.

What you typically do hash the key, and take the (say) lowest-order $n$ bits from the hash value, and this determines the hash slot. Within each hash slot, you then store the key in full.

One common technique, if keys are large, is also to store the hash value in each entry, because that comparison is cheap. It only costs $m$ extra bits per entry.

The first observation is that you don't need to store all $m$ bits, because $n$ of those bits are implied by the hash slot. So to support this technique, you only need to store $n-m$ bits in each entry.

So, in summary, each entry needs two things:

  • $m-n$ bits of hash value, and
  • a copy of the key.

Now here's the clever bit. Suppose that your keys are also $m$ bits in size, and suppose, furthermore, that your hash function is invertible. Then the key is completely recoverable from the hash value, which in turn is recoverable from the hash slot number and the additional $m-n$ bits of information stored in the entry.

So the key need not be stored at all.

(Constructing invertible hash functions is not difficult; given a non-invertible hash function using, you could use something like a Feistel network.)

Now, let's look at the space usage as a whole.

If the hash table is full, with a load factor of 1, then you need to represent a subset of $2^n$ items from a universe of $2^m$ possible items. There are ${ 2^m \choose 2^n}$ possible subsets, and so any representation must use at least $\log { 2^m \choose 2^n}$ bits (all logarithms are base 2).

By Stirling's approximation:

$$\begin{eqnarray*}& & \log { 2^m \choose 2^n} \\ & = & \log \left(2^m\right)! - \log \left(2^n\right)! - \log \left(2^m - 2^n\right)! \\ & = & \left( m 2^m - 2^m \log e\right) - \left(n 2^n - 2^n \log e\right) - \left( (2^m - 2^n) \log \left( 2^m - 2^n \right) - (2^m - 2^n) \log e \right) + O(m) \\ & = & m 2^m - n 2^n - (2^m - 2^n) \log \left( 2^m - 2^n \right) + O(m) \\ & = & m 2^m - n 2^n - (2^m - 2^n) \left( n + \log (2^{m-n} - 1) \right) + O(m) \\ & = & m 2^m - n 2^n - (2^m - 2^n) ( n + m - n ) + O(m) \\ & = & (m - n) 2^n + O(m) \end{eqnarray*}$$

The second-last step introduces the assumption that $2^m \gg 2^n$, so $\log(2^{m-n}-1) = m - n + O(m)$.

In other words, the minimum number of bits required is, under these assumptions, exactly the same as storing $2^n$ records of $m-n$ bits each! So the only overhead required is whatever is needed to maintain the structure of the hash table itself (e.g. the overhead of storing multiple records in a bucket).

If this were a minimal perfect hash function, or a low-overhead technique such as cuckoo hashing, this representation is asymptotically optimal.

$\endgroup$
0
$\begingroup$

It makes the hash table unusable if I can’t have x and yz and abc as keys.

$\endgroup$
2
  • 2
    $\begingroup$ This doesn't answer the question. You can easily achieve keys of equal length by padding. $\endgroup$ May 16, 2020 at 10:31
  • $\begingroup$ The hash table can do whatever it wants with the keys, nobody mind. Forcing the user to modify the keys makes the table unusable. $\endgroup$
    – gnasher729
    Oct 14, 2020 at 12:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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