Wegman-Carter on their seminal Universal classes of hash functions uses the term universal for their definition. They gave this definition as:

Let $H$ be a class of functions from $A$ to $B$. We say that $H$ is $universal_2$ if for all $x,y$ in $A$, $\delta_h(x,y) \leq \frac{\vert H\vert}{\vert B\vert}.$ That is, $H$ is $universal_2$ if no pair of distinct keys are mapped into the same index by more than one $\vert B\vert^{\text{th}}$ of the functions.

Is there a rational reason for the naming of this hash functions as universal?


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.