New answers tagged hashing
1
Let $h:[U]\to[m]$ be a uniform hash function, and $x_1,\dots,x_n\in[U]$ be the elements currently stored in the hash table, and we want to look up the query $q\in[U]$. Finally let $X_i$ be the indicator variable for the event that $x_i$ collides with $q$:
$$X_i = \begin{cases}1 && h(x_i)=h(q)\\0 &&h(x_i)\ne h(q)\end{cases}
\Rightarrow P(X_i=1)...
Top 50 recent answers are included
