0
$\begingroup$

Given the following family of hash functions:

$$ \mathbb{H} = \{h_c(x) = (12x + c) \bmod m \mid c \in \mathbb{N} \}, $$ where $m$ is the key size.

Prove that $\mathbb{H}$ is not a universal family of hash functions.

So I got the following idea:

If $m = 12 $ then $H$ is not an universal family of hash functions. But is this enough or have I to prove it for every/random m?

This leads to the question: Is a universal family of hash functions dependent on the hash table size?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ Is this enough? You should ask whoever set you the exercise to clarify this point. $\endgroup$
    – Yuval Filmus
    May 21, 2022 at 20:49
  • 1
    $\begingroup$ Since the hash is used to index an index in a hash table, the range of the hash function should match the size of the hash table. In practice, this is accomplished by computing a long hash and reducing it modulo the size of the hash table. $\endgroup$
    – Yuval Filmus
    May 21, 2022 at 20:50

1 Answer 1

Reset to default
2
$\begingroup$

Ultimately this is a question for the person who posed the exercise. They need to specify if they are asking "Is H non-universal for all m?" or if they are asking "Is H universal for all m?"

If they're asking the former, then you proving H is non-universal for m = 12 is not enough. If they're asking the latter, it is.

Improve this answer
$\endgroup$

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.