Expand description
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.