Metadata

Metadata for a slot. It can be in three states: empty, used or tombstone. Tombstones indicate that an entry was previously used, they are a simple way to handle removal. To this state, we add 7 bits from the slot's key hash. These are used as a fast way to disambiguate between entries without having to use the equality function. If two fingerprints are different, we know that we don't have to compare the keys at all. The 7 bits are the highest ones from a 64 bit hash. This way, not only we use the log2(capacity) lowest bits from the hash to determine a slot index, but we use 7 more bits to quickly resolve collisions when multiple elements with different hashes end up wanting to be in the same slot. Not using the equality function means we don't have to read into the entries array, likely avoiding a cache miss and a potentially costly function call.