2
$\begingroup$

Can somebody explain the following:

image

U is a universe of keys, and H is a finite collection of hash functions mapping U to {0, 1, … , m-1}.

I do not understand definition 2, and thus why amount of funtions that map x and y to the same location is given by |H|/m.

$\endgroup$

migrated from stackoverflow.com Jun 15 at 23:47

This question came from our site for professional and enthusiast programmers.

3
$\begingroup$

Let’s begin by talking about the intuition for universal hash families. Intuitively, a family of hash functions is universal if for any distinct objects x and y that you’d like to hash, if you select a random hash function from the hash family, the probability that you get a collision between those two elements is at most 1/m, where m is the number of buckets. In other words, universal hash families tend to spread elements out in a way where the probability of a pair colliding is the same as if the elements were distributed randomly.

Let’s see how the definition accomplishes this. Here’s the definition from your question:

H is universal if ∀ x, y ∈ U where x ≠ y | { h in H : h(x) = h(y) } | = |H| / m.

For starters, I’m assuming that we’re talking about hash functions that map from some set U to the integers 1 through m or 0 through m-1. With that in mind, let’s unpack some of this notation.

If we replace the universal quantifier (∀) with the plain English “for all,” this definition says “H is universal if for every choice of two different items x and y to hash, some inequality is true.” So let’s look at that inequality. First, what is this bit?

| { h in H : h(x) = h(y) } |

The vertical bars here represent the size of a set, and the set in question is this one:

{ h in H : h(x) = h(y) }

Read literally, this is the set of all hash functions h in the family H where h(x) = h(y). Keeping in mind that we’re talking about hash collisions here, we can think of h(x) = h(y) as saying that hash function h causes x and y to collide with one another (have the same hash code). With that in mind, the complex expression

| { h in H : h(x) = h(y) } |

means “the number of hash functions in H where x and y collide.” Combining that with our earlier bit, we can rewrite the entire definition as

H is universal if for any two distinct elements x and y that we want to hash, the number of hash functions in H where x and y collide is at most |H| / m.

So what’s |H| / m? That’s the total number of hash functions (|H|) divided by the number of possible outputs for any one single hash function (m). It might help to divide the entire expression through by |H|, which would then give this final definition:

H is universal if for any two distinct elements x and y that we want to hash, the probability of picking a hash function h where x and y collide (that is, the total number of hash functions where x and y collide divided by the total number of hash functions) is at most 1/m.

Hope this helps!

$\endgroup$
  • $\begingroup$ Ye, it helps a lot, but I actually do not understand why is the amount of the functions, where h(x) = h(y), equal to |H|/m. $\endgroup$ – coolchock Jun 15 at 23:10
  • $\begingroup$ Think of it as like a probability. Divide both sides by |H| to get a left-hand side of “the fraction of functions where x and y collide,” which we can interpret as “the probability of a collision between x and y if you sample a random hash function.” Now, what would that quantity be if the functions are truly random? If there are m possible choices for a hash code for x and m choices for a hash code for y, the collision probability would be 1/m - the chance that they end up in the same slot. So for universal hashing, we want that same probability, 1/m, which is the right-hand side. $\endgroup$ – templatetypedef Jun 15 at 23:39
  • $\begingroup$ it's all clear now, thank you very much for your professional help! $\endgroup$ – coolchock Jun 16 at 0:05
0
$\begingroup$

As you found it is just a definition. You can ask about what is the meaning of the definition. It means the set of function H is universal if for every two different members of U, has exactly the same number of hash function exists in H and that number is |H|/m.

The intuition behind this definition comes from the application over this definition. As a set of function is universal (satisfy the definition), the probability of choosing a function from H to have the same value over two different members of U is 1/m, and it means this probability depends uniformly on the size of m (the range space of those hash functions).

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