Relativistic hash tables, part 1: Algorithms

In addition to the overhead of copying all the elements, you'd break any code that holds references to those elements. In quite a few hash tables in the kernel, other code holds long-running references to hash nodes and expects them to stay alive.

When I first started working on hash table algorithms, years ago, I started out by developing an algorithm to move a single node between buckets because the key changed. My first attempt involved making a copy of the node. That works fine in a standalone hash table, but it won't work in many real kernel data structures (for instance, dcache), because it breaks other pointers to the (reference-counted) node.

That's why the algorithm shown here does *not* copy any nodes.