Design Hashing function from known distribution of bits to be set

Question

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.

Answer 1

There are 224,723,513,575,448 possible 64-bit bit-strings which satisfy the constraint that there are between 3 and 15 one-bits (inclusive). That number is approximately 2^47.675, so it could be represented in 48 bits. This compression is not particularly difficult, but it is much slower than the Murmur3 mixing algorithm you cite, whose speed seems to be a concern.

In any event, the compression won't really help you much (if at all). A good hash function will produced unbiased distribution of hash values for any subset of possible inputs; such hash functions are theoretically possible and, with appropriate caveats, practically achievable. (Tabulation hashing is a simple and effective technique, which is provably independent provided you have an appropriate source of randomness. But unless you have special requirements, you are probably better off using an existing hash library which has been tested and found to be unbiased.)

In practice, the C++ standard does not prescribe any particular hashing algorithm nor does it prescribe any particular mapping from hash values to buckets for unordered associative containers (there is no such thing as a std::ordered_map; there are std::map, which is ordered and therefore not a hash table, and std::unordered_map, which is a hash table). The implementations of the C++ standard library I know of use the identity function for hashes of all integer types. (Hash values are of type size_t, which means that values larger than the capacity of a size_t will be reduced modulo the size of a size_t; that will be the case for a 64-bit key on most 32-bit architectures.) Since that is likely to produce biased results in your case regardless of how the hash values are mapped to buckets, you probably are well-advised to use a specialized hash function, at least if you expect the hash tables to be large.

Answer 2

The theoretical answer

Use a 2-universal hash function (see also here). It is provably good, regardless of the input distribution.

The pragmatic answer

Use any good, standard hash function that mixes the bits well. You don't need a special hash function for this situation -- any standard one should be fine. The fact that you happen to know that the inputs will only have 3..15 bits set doesn't change that.

For instance, the following should all be fine: MurmurHash, Pearson hash (though it only outputs a 8-bit hash value, which might not be enough). FNV hash might be OK. I'd worry a bit more about Jenkins hash. I haven't looked at CityHash, SpookyHash, or FarmHash but they sound promising.

There are standard hash functions that don't mix the bits very well (perhaps on the assumption that the inputs will be random enough that this isn't needed). Don't use one of those.

You might be interested in SMHasher, a toolkit for testing candidate hash functions.