3
$\begingroup$

In real-world programming, we frequently need to compute hash codes for complicated objects. The main desired properties are that the values should

  • be deterministic and
  • have few collisions.

Let's assume we have access to robust hashing for basic data types such as integers, strings, etc. How do we combine multiple such hash codes to a single one, say for an array or a struct with several properties?

I immediately went for XOR-ing all "child" codes, figuring that the "spread" of the original hash function should be maintained, roughly. Apparently, I'm not alone.

However, if you google around, you find other approaches.

  • Here an answerer proposes adding hash codes after perturbing them by some multiplication.
  • This asker uses XOR but multiplies the individual codes with some numbers, apparently consciously choosing "large" primes.
  • Here, the author states that "[things] have low values (favour the lower bits), so they should be combined with a multiplication to spread them across a wider bit range of the hash code".

The reasons given, if any, seem vacuous to me. Does multiplying already "random" values with a (small) constant really serve any purpose? Does it matter if the factor is a prime (which everybody seems to assume)?

$\endgroup$
6
$\begingroup$

XOR is not a good method, because then the hash of $(a,b)$ will be equal to the hash of $(b,a)$. Also, the hash of $(a,a,c)$ will be equal to the hash of $(b,b,c)$ and to the hash of just $c$. That's not good.

A better method is to make the hash of $(a,b)$ be equal to $H(H(a) || H(b))$, where $H$ is your hash function on basic objects (ints, strings, etc.) and where I am using $||$ to represent concatenation of bit strings. This avoids all of those degeneracies.

The particular constructions you mention can be viewed as instances of that approach:

  • The first link basically proposes using $H(a) + 37 \times H(b) \bmod 2^{64}$. That's equivalent to the construction $H'(H(a) || H(b))$ where $H'$ is a standard Rabin-Karp hash function.

  • The second link is $1013 \times H(a) \oplus 1009 \times H(b) \bmod 2^{64}$. That has the form $H''(H(a) || H(b))$ where $H''(x||y) = c_1x \oplus c_2y$, which is also a reasonable hash function (though it takes a little bit of algebra to prove it).

  • The third link is $(c \times H(a)) \oplus H(b) \bmod 2^{64}$ where $c$ is a prime. That's the same as the previous one, but with $c_2=1$. It also turns out to be a reasonable hash function.

Does the constant multiplier (e.g., 37) need to be prime? No, it only needs to be relatively prime to the modulus. If the modulus is a power of two (as in these cases), it only needs to be odd. A prime is sufficient but not necessary. To obtain provably good results, the constant multiplier should be chosen at random; in practice, we fix a particular value and hope that will be close enough for practical purposes.

Another reasonable method is to use $H_1(a) + H_2(b)$ or $H_1(a) \oplus H_2(b)$ as the hash of $(a,b)$, where $H_1,H_2$ are two independently chosen hash functions. This also works.. but is a little more annoying to implement, because it requires us to have multiple hash functions.

Is there some theory here? Yes, you can prove that if $H_1,H_2$ are drawn uniformly at random from a 2-universal hash family, and $+$ is a group operator, then $H_1(a)+H_2(b)$ will be a 2-universal. The same is true for $H_1(H_2(a)||H_2(b))$. I am not sure about what one can prove about $H(H(a)||H(b))$; I suspect it's not provably good in a generic sense, but is normally fine in practice.

$\endgroup$
  • $\begingroup$ Comments are not for extended discussion; this conversation has been moved to chat. $\endgroup$ – Raphael Jul 10 '17 at 15:54
0
$\begingroup$

You want to make sure that each distinct change to the data has a different effect.

This also means avoiding that changes in multiple fields can cancel each other out. If you simply summed the fields then {3,5} will be equal to {2,6}, if you add a factor of 7 to the second field then it's {9,5} that collides with {2,6} and everything in between won't collide.

Using factors that are mutually prime will reduce the number of collisions between objects that differ very little. Prime numbers are all mutually prime.

$\endgroup$
  • $\begingroup$ "Using factors that are mutually prime will reduce the number of collisions between objects that differ very little. Prime numbers are all mutually prime." -- can you elaborate on that? $\endgroup$ – Raphael Jul 5 '17 at 22:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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