How to design Hashing function when the distribution for the bits that will be set are known before hand? Given that the number of bits to be set is constant. The intention is to minimize the hash collisions and resizing of the hash table.
Mentioned query is more of an open-ended question. What I am interested is in the known existing approach for such scenarios?
More description: Design a hashing function where the keys are formed from 64 bits. The number of bits $(l)$ that will be set is fixed which is $3 \leq l \leq 15$ of the 64 bits in the key. Further clarification, any $l$ bits in of the given 64 bit will be set.
Approximate distribution for the respective bit to be set is also known beforehand. The approximate probability of the $k^{th}$ bit will be set in the keys that will be inserted is known. In other words, for most keys that will be inserted in the hash table $k^{th}$ bit will not be set.
Implementation is to be done in C++ if this information helps in anyway.
I have tried with bit mixing from link which has the following function:
UInt64 MurmurHash3Mixer( UInt64 key )
{
key ^= (key >> 33);
key *= 0xff51afd7ed558ccd;
key ^= (key >> 33);
key *= 0xc4ceb9fe1a85ec53;
key ^= (key >> 33);
return key;
}
But the number of key collisions wasn't much affected. Also, the execution time worsened in comparison to hashing scheme that comes with std::ordered_map
.
For my case, most of the keys have the property that last certain will never be set and the probability of initial bits will be set is lower than the bits in the middle section.
std::ordered_map
- I believe uses the initial bits to map to a memory location. Since, many of keys share the property more time is spent in re-hashing.
std::ordered_map
. It has astd::map
, which is ordered (and therefore not a hash table), andstd::unordered_map
, which uses an implementation-specific hashing function, so there is no definite statement you can make about how the hash is computed. $\endgroup$