0
$\begingroup$

Suppose I have integers that follows a power distribution:

$P(n) \propto 1/(n + 1)^\alpha, n \geq 0$

What hash function is a good choice to avoid collisions. The usecase is keys in an std::unordered_map. Thus, it should be fast as opposed to cryptographic hash functions which are constructed to be slow.

$\endgroup$
1
  • $\begingroup$ @D.W. 1. Because if keys have a non-suitable distribution, we will get collisions. 2. They should be slow, because it should be hard to brute-force its inverse. $\endgroup$
    – user877329
    Commented May 12 at 6:50

1 Answer 1

1
$\begingroup$

Use any standard hash function. It will work fine. You don't need a special hash function just for this distribution of data.

An imbalanced distribution does not cause an increase in collisions. If you see the same value twice, they will both hash to the same bucket, but that is not a collision - a collision occurs when two different values hash to the same value.

Let's consider a simplified scenario to make this easier to think about. Consider hashing a distribution on keys, where each key can only take the value 0 or 1. Consider an extreme case: a distribution of values that are 1 with probability $0.999$ or 0 with probability $0.001$. Does this have more collisions than a uniform distribution? No, it has fewer. A collision occurs only if $h(0)=h(1)$. ($h(1)=h(1)$ is not a collision.) Suppose you pick a hash function $h$ from a family of hash functions, such that the probability of $h(0)=h(1)$ is $1/3$. Then suppose you draw two values from some distribution, hash them, and ask whether this yields a collision. For the uniform distribution, the probability of a collision is $1/6$ (first you have to choose a hash function such that $h(0)=h(1)$, which happens with probability $1/3$, then the second value has to be different from the first, which for the uniform distribution happens with probability $1/2$). For the aforementioned distribution with probability $0.999$ vs $0.001$, the probability of a collision is $1/3 \times 2 \times 0.999 \times 0.001$, which is far smaller than $1/6$. So an imbalanced distribution does not increase the number of collisions; it might even reduce it.

If you wanted to ask for a function $f$ such that $f(X)$ is as close to uniformly distributed as possible, when $X$ has the random variable you mentioned, that is a different question, and I suggest asking it separately.


I suspect you might have a few misunderstandings.

Collisions are always possible, no matter what hash function you use. That is not a reason to pick one hash function over another. Collisions are expected to be rare/unlikely, with any decent hash function.

Your statements about cryptographic hash functions seem to be based on a faulty premise. Cryptographic hash functions are not designed to be slow. (Some are -- e.g., password-based key derivation functions -- but standard cryptographic hash functions are not designed to be slow. They are designed to be cryptographically secure, and to be as fast as possible given that requirement. Hardness of inversion does not come from them being slow to compute in the forward direction, but from their design.)

$\endgroup$
2
  • $\begingroup$ I thought the input distribution would affect the likelyhood of collisions. In this case, wouldn't a higher alpha increase the risk of collisions, since expected values are more concentrated. So the ideal hash function would turn the distribution into a uniform distribution. $\endgroup$
    – user877329
    Commented May 12 at 9:01
  • $\begingroup$ @user877329, Nope. See revised answer. $\endgroup$
    – D.W.
    Commented May 12 at 19:03

Your Answer

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

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