search

martinus / unordered_dense

A fast & densely stored hashmap and hashset based on robin-hood backward shift deletion
MIT License
898 stars 72 forks source link

some optimization #2

Closed ktprime closed 2 years ago

ktprime commented 2 years ago

**

A fingerprint; 1 byte of the hash (lowest significant byte in dist_and_fingerprint)

** why not use the main (32-3) bits as hash code in dist_and_fingerprint which can reduces collision rate(improving find hit) I do it in my emhash8.

martinus commented 2 years ago

I use 3 bytes to store the distance from the original bucket, 1 byte for the fingerprint, and 4 bytes for the index into the vector. There's no place left any more

ktprime commented 2 years ago

I use 3 bytes to store the distance from the original bucket, 1 byte for the fingerprint, and 4 bytes for the index into the vector. There's no place left any more

if the map size is less than 1 << 24 , no need 3 bytes. just statisfy distance bit+ fingerprint bit= 32 bit.