# Universal Hashing in Practice

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?

• 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. – G. Bach Oct 16 '13 at 10:55
• @G.Bach Thanks for your comments. But I do want to hear opinions from an industrial point of view. – Dai Oct 21 '13 at 14:31
• @Dai This is probably not the right place for get statements from industry, though. – Raphael Nov 14 '14 at 11:16