0
$\begingroup$

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?

$\endgroup$

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.