14
$\begingroup$

A family $H$ of hash functions $h: U \rightarrow \{0,\ldots,M-1\}$ is universal if $$\forall x,y \in U, x \neq y \Rightarrow \Pr_{h \in H}[h(x) = h(y)] \leq \frac{1}{M}$$ You can find more about universal hashing this wikipedia article.

The concept of universal hashing is now a standard part of undergraduate data structure courses. It would be nice to be able to motivate students about the importance of universal hashing in industrial applications. So my question is:

Are constructions of universal family of hash functions important in practice? If the answer is yes, would you please share some interesting industrial applications that you've seen?

$\endgroup$
  • $\begingroup$ I expect that all implementations of generic hash structures that want to reach (amortized/expected/real) constant time cost for insert, lookup and remove (which is the only reason why we bother to hash in the first place) need a reliable way to construct "good" hashing functions. Universal hashing is a (successful) attempt at formalizing what a "good" hashing function is, and it also gives us tools to generate such functions efficiently for arbitrary keys. Since I don't have any industry experience, this is all from a theoretical point of view, but I very much expect them to be the go-to way. $\endgroup$ – G. Bach Oct 16 '13 at 10:55
  • $\begingroup$ @G.Bach Thanks for your comments. But I do want to hear opinions from an industrial point of view. $\endgroup$ – Dai Oct 21 '13 at 14:31
  • $\begingroup$ @Dai This is probably not the right place for get statements from industry, though. $\endgroup$ – Raphael Nov 14 '14 at 11:16
4
$\begingroup$

Universal hashing (or near-universal) is a key ingredient in defending against algorithmic complexity attacks that engineer hash table collisions from user input.

See Scott A. Crosby and Dan S. Wallach's "Denial of Service via Algorithmic Complexity Attacks".

$\endgroup$
  • $\begingroup$ That is very useful. I went through a similar paper as the link was broken. Will have a look at this one as well. Thanks $\endgroup$ – Rishi Dua Nov 14 '14 at 8:51

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.