BPHT -- A bitpacked hopscotch hash table
Computing address and remainder (fingerprint; fp) from keys:
key: 32-bit | 32 - fp_len address-bits | floor(log2(|ht|)) fingerprint-bits | | power of 2 of the address space | |
Bitpacking hash table entries:
| 32 bit payload | ~24 bit fingerprint |~ 8 hop bits| |pppppppppppppppppppppppppppppppp|ffffffffffffffffffffffff...<|>...hhhhhhhh|
Hop bits: 0 means free, 1 means filled Hop bits are read from left to right 1011 means, this position is filled (_1), as is the next (1) and the one with offset 3 (1)
The number of fingerprint bits depends on the size of the hash table.