New open addressing hash table algorithm #2
Reference in GitHub. Contains Zig code.
I have been working on some interesting stuff and out of necessity had to extend my earlier work with incremental resizing to significantly reduce memory waste. The end result is a novel algorithm that the literature has not seen before. I trust that many of you will find the unique properties of the hash table interesting but useless in practice - it has a very specific use case.
The new thing is extending it with an open addressing variant of Linear Hashing. Linear hashing is a technique which enables incremental adjustments to the capacity of the hash table. It enables each individual insert() to also grow the hash table by a little and for each remove() to also shrink the hash table by a little. This means:
- No
O(table_size)grow/resize/shrink operations. - Ability to maintain the target load factor at ALL times - not just resize at some max load factor.
- Significantly reduced tail latency for all operations.
The combined algorithm is now starting to be full of subtle invariants to maintain. I provide a "simplified" reference implementation of it which limits itself to the essence of the algorithm. I won't bother explaining the new algorithm in detail because it's too hard. Read the code and play around with it.
Hoping that many of you find this interesting. Happy 250th birthday USA!