0
$\begingroup$

Why can't we pick just $x + b$ for example? I know that for universal hashing the Pr[$h(x) == h(y)$] $\leq 1/|n|$

But with the same hash function, just without the $a$ we can get $h(k) = (($k$ + b$ mod $p$) mod $n$).

I've run through a million examples and I can't find a single reason why I might be wrong.

$\endgroup$
0
$\begingroup$

You pick $p\ge n$ and your family consists of $h_b(x)=(x+b\bmod p)\bmod n$, where $b$ ranges over $0,\ldots, b-1$. To show that this family is universal, we need that for any $0\le x<y<n$, the probability that $h_b(x)=h_b(y)$ for a uniform choice of $b$, is $\le \frac 1n$. Note that if $p=2k+1>n+1$ and $n>k+1$, then $h_k(k+1)=0$ and $h_k(n-k)=0$. Also, $h_{k+1}(k+1)=1$ and $h_{k+1}(n-k)=1$. Thus for $x=k+1\ne n-k=y$, the probability of $h_b(x)=h_b(y)$ is at least $\frac 2{p}$. Unfortunately, this may well be $>\frac 1n$.

You'd be better of to consider $h_b(x)=x+b\bmod n$. But that would not really be hash-y after all

$\endgroup$
  • $\begingroup$ Yep, that works. Can you run me through why you chose $p = 2k + 1 > n+1$ and $n > k+1$ and how you got $x = k+1$ and $y = n-k$. I want to learn how you reached these numbers. Thanks $\endgroup$ – QuantumHoneybees Feb 15 '17 at 2:34

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.