_U_urga·Dec 8, 2018
This is a fantastic explanation of developments in hash tables in general.
If anyone is interested, I recently released a scalable hash table for Node.js (@ronomon/hash-table), designed to store literally billions of elements without stressing the GC.
At first, I tried writing a native addon module for Node.js in C (using SIMD), but the Javascript-to-C call cost was just too high, and doubled latency. In the end, I was surprised to find that writing directly in Javascript proved faster than the C module with SIMD, simply by avoiding the bridging cost.
Also, instead of linear or quadratic probing (or double hashing or triangular probing), I used cuckoo hashing, but with a twist. Normally, in the case of a naive cuckoo hash table, if an element is not in its first bucket, then its second bucket must be fetched from memory, causing a cache m
Read the rest
iss, which for a hash table is embarrassingly slow. This is why SwissTable and F14 tend to avoid naive cuckoo hashing.
However, in our design, the first bucket includes an 8-byte coarse-grained bloom filter (k=1, or a single bit per element). If the element is not in this bloom filter, the element is guaranteed not to be in either of its first or second buckets, and a cache miss can be avoided nearly 90% of the time. Using cuckoo hashing in this way then starts to produce major advantages over linear probing: no tombstones, higher load factor (which has knock-on implications for resize latency), and constant time worst-case lookups.
More design details are here:
https://github.com/ronomon/hash-table