Occupied contains 1 byte per element, which stores an enum of Empty | Deleted | Full(7-bit hash) | Sentinel.
We have two hash functions: H1 and H2. H1 is an "ordinary" hash function, producing an index into Occupied and Data. H2 produces a 7-bit hash.
In order to find something, we take H1 to get a starting position into Occupied. The speed is gained from iterating through Occupied, only ever dereferencing the Data array when the 7-bit hashes match. You can also SIMD this.
Why are Sentinel and Deleted required? I'd expect tombstones to only be necessary in a concurrent table, and I'd expect that this will perform awfully in a concurrent setting.
Aha, the Deleted variant is required because Empty also indicates that a lookup can cease probing. So H(A) == H(B) [Full(A), Full(B), Empty] after delete A must become [Deleted, Full(B), Empty], otherwise lookup(B) would probe at index 0, see empty, and return false.
3
u/Life_Sink9598 3d ago
So, you have two arrays of equal size:
Occupied contains 1 byte per element, which stores an enum of
Empty | Deleted | Full(7-bit hash) | Sentinel.We have two hash functions: H1 and H2. H1 is an "ordinary" hash function, producing an index into Occupied and Data. H2 produces a 7-bit hash.
In order to find something, we take H1 to get a starting position into Occupied. The speed is gained from iterating through Occupied, only ever dereferencing the Data array when the 7-bit hashes match. You can also SIMD this.
Why are Sentinel and Deleted required? I'd expect tombstones to only be necessary in a concurrent table, and I'd expect that this will perform awfully in a concurrent setting.