2
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.