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
Related Tags
hashing × 95hash × 40
hash-tables × 21
probability-theory × 17
algorithms × 15
algorithm-analysis × 8
data-structures × 8
time-complexity × 6
cryptography × 5
sorting × 3
linear-algebra × 3
probabilistic-algorithms × 3
bloom-filters × 3
complexity-theory × 2
terminology × 2
computational-geometry × 2
proof-techniques × 2
search-algorithms × 2
strings × 2
data-compression × 2
mathematical-foundations × 2
check-my-answer × 2
encryption × 2
rolling-hash × 2
optimization × 1