Perfect hashing in CLRS relies on universal hashing functions. How can the full

Question

Perfect hashing in CLRS relies on universal hashing functions. How can the full strength be relaxed, so that it can have the weaker condition prob(h(x) = h(y)) = O(1/n)? where x!=y? Explain

Explanation / Answer

Definition: H is a 2-universal family (set) of hash functions from M to N if: for all x,y in M (x != y), Prob[h(x) = h(y)] given this value of a, we must have b = r-ax (mod p). So, this probability is 1/[p(p-1)]. (What is the probability for r=s? Ans: 0) Now, how many pairs r!=s are there in {0,...,p-1} such that r = s (mod n)? -> have p choices for r, and then at most ceiling(p/n)-1 choices for s ("-1" since we disallow s=r). The product is at most p(p-1)/n Putting this all together, Pr[(a*x + b mod p) mod n = (a*y + b mod p) mod n] Perfect hashing. (h is perfect for S if it causes no collisions). 1 way: Say O(|S|^2) space is OK. Then, just do a universal hash function into table of size n=|S|^2. For any x!=y, we have Pr[h(x)=h(y)]

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.