# How do the following Hash Functions compare?

Consider the two hash functions used to map IP addresses. $x_i$ represents a octave (or "bit field") of the address.

Hash Function 1: $$h_a(x_1, x_2, x_3, x_4) = \sum^{4}_{i=1} a_ix_i \bmod n$$

Where $n$ is a prime number closest to the total number of IP addresses being mapped. The probability of two IP addresses being mapped to the same bucket is $\frac{1}{n}$ using this hash function.

Hash Function 2:

$$h_a(x_1, x_2, x_3, x_4) = \sum^{4}_{i=1} x_i \bmod n$$

What would the probability to two IP addresses being mapped to the same bucket be using the second hashing function?

## 1 Answer

Your question is a bit confusing. These two "hashes" are incomparable.

The reason is that your second function is a specific hash function, while the first formulation is a family of hash functions (indexed by $a$).

How can you compare the two? Choose $a$ in random and compare the two instances? Compare for the best/worst $a$, maybe? Compare on average (for a uniform $a$)?

Remark: Just to complete the details: Usually (at least, within the crypto-community), when people say "hash function" they actually mean a family of hash function, out of which you pick one instance uniformly. The properties of the hash function is (also) over the probability of selecting the specific function out of the family

As for your other question, the answer is no, in the second hash, the probability is not equal $1/n$ to be in each bucket. Assume that each $x_i$ is uniform in [0..255], then $x_1+x_2$ is not uniform in [0..510]. For instance $P(0)=1/256^2$ (both are 0) while $P(4) = P(0,4) + P(1,3) + P(2,2) + P(3,1) + P(4,0) = 5/256^2$. There's no reason that the sum will be uniform $\mod n$.

Last comment: As explained above, for the first hash, a probability of $1/n$ is over the choice of $a$.