A hash table you don't need to rehash
=====================================

[Published 2022-05-07]

Let's make a small hash table that has four slots and that we
index using two bits of a hash value.

    [ _ , _ , _ , _ ]
      00, 01, 10, 11

Now we add some items to it, A (hash 00) and B (hash 10) and C
(hash 01):

    [ A , C , B , _ ]
      00, 01, 10, 11

Let's say that we want to add D (hash 10).  The problem is that
it would collide with B.  Now when the hash table is getting
pretty full, you would normally create a bigger hash table,
recalculate the hashes for all values and add them again in the
bigger table.  That can be pretty slow.  Let's instead allocate a
new small hash table that we link to slot 10 where B is.

    [ A , C , B , _ ]
      00, 01, 10, 11
              |
              [ _ , _ , _ , _ ]
                00, 01, 10, 11

Now we can add D to that second table but first we need more bits
from the hash value.  Let's say the hash of D ends with 0110.
The lowest two bits were already used for the index in the first
table (10).  Now let's use the next two bits (01) as index in the
second table.

    [ A , C , B , _ ]
      00, 01, 10, 11
              |
              [ _ , D , _ , _ ]
                00, 01, 10, 11

If we continue like this, we can add as many values as we like
without needing to rehash or do any other expensive operation,
other than allocating some memory.  To find a value, we first
calculate the hash (0110 for D).  Then we first look at the
lowest two bits (10) and go to the root table where we find B at
that position.  That's not the value we were looking for so we
continue with the next two bits (01) in the second table.  Here
we find the value D that we are looking for.

Removing a value is really easy too.  We can just remove it and
optionally find any leaf node that has its path through the
removed node and put that leaf node in the place of the removed
node.  The vertical order of the nodes doesn't matter as long as
they are on the same hash path.

This data structure is like a combination of a hash table and a
tree.  It's called a Hash Array Mapped Trie.