New answers tagged hashing
0
In the second paragraph:
"In other words, with a hash function randomly chosen from $\mathscr{H}$, the chance of a collision between distinct keys $k$ and $l$ is no more than the chance $1/m$ of a collision if $h(k)$ and $h(l)$ were randomly and independently chosen from the set $\{0,1,...,m-1\}$."
Here, "the chance of a collision between ...
0
Both definitions are equivalent, and I think you have almost specified the reason behind it.
The below equivalence work in both ways.
From Definition 2:
"the chance of a collision between distinct keys $k$ and $l$" $\le$ $1/m$
$\Leftrightarrow$
{note that the "chance" here is about the process of picking $h$ from the class $\mathscr{H}$}
(...
0
If $n_j$ keys hash to slot $j$ of the first-level hashtable, and if $n_j > 1$, we will need to use a second-level hashtable for that slot. Theorem 11.9 helps us in the sense that, if we keep this second hashtable size as $n_j^2$, then atleast 1/2 of the hash-functions in any universal-class (which all hash to range 0 to $n_j^2-1$) must give no collisions ...
1
... collisions are still possible in this second level
For each slot of the first-level hash table (which contains more than 1 keys), we will need to decide a hash-function. Since we want perfect-hashing, we want this function to give no collision. Theorem 11.9 (quoted below) guides us that it is in-fact possible to find such a function in a universal-class, ...
0
Probing doesn’t find an empty slot if all probed slots are full. If less than half the slots are full, and half the slots or more are probed, then you are probing more than the full slots, so the probed slots cannot all be full.
1
Suppose that $t=11$, $i=5$, $j=6$. Then $i+j \bmod t = 0$, and there is no contradiction. However, in this example $i < t/2$ while $j > t/2$. This sort of example cannot happen if $i,j < t/2$, since then $i+j < t$.
Top 50 recent answers are included
