0
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ By "number of bits that will be set", are you saying that you want 64-bit outputs from the hash function that always have between 3 and 15 bits set (and no more)? Or are you saying that the number of bits that will be set in the input to the hash function is between 3 and 15? Or something else? Also, what do you mean by "distribution for the bits that will be set"? Can you elaborate on that? Are there any approaches you've already considered and rejected? $\endgroup$
    – D.W.
    Feb 24, 2017 at 3:24
  • $\begingroup$ @D.W. I tried to elaborate more. Please do let me know if I still left some room for ambiguity. $\endgroup$ Feb 24, 2017 at 4:53
  • $\begingroup$ What is meant by "setting the bits"? $\endgroup$
    – kennytm
    Feb 24, 2017 at 5:14
  • $\begingroup$ @kennytm I meant making the respective bit set to $1$ instead of the default $0$ $\endgroup$ Feb 24, 2017 at 5:27
  • $\begingroup$ C++ doesn't have a std::ordered_map. It has a std::map, which is ordered (and therefore not a hash table), and std::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$
    – rici
    Feb 24, 2017 at 6:17

2 Answers 2

1
$\begingroup$

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 247.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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Was that really the wikipedia entry you intended to link to? en.wikipedia.org/wiki/K-independent_hashing seems more relevant to the link text. Also, both of those end up pointing at en.wikipedia.org/wiki/Tabulation_hashing which is both practical and theoretically sound (given a good source of random numbers) although without knowing more about OP's practical needs, it is hard to know which tradeoffs are appropriate. $\endgroup$
    – rici
    Feb 24, 2017 at 14:59
  • $\begingroup$ @rici, you're right. I updated the first link. Now I think they point to what I intended. Nice answer, by the way -- I don't know I didn't see it before. $\endgroup$
    – D.W.
    Apr 26, 2017 at 0:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.