All Questions
Tagged with hash-tables randomized-algorithms
4 questions
1
vote
1
answer
79
views
Number of unique values in array in $\theta(n)$ average expected time
My idea is to initialize a hash table (with chaining) with $n$ cells, having load factor $\alpha = 1$ hence having $\theta(1)$ expected number of values in each cell in the hash table, then go cell by ...
- 243
3
votes
1
answer
677
views
Does hashing under the Simple Uniform Hashing Assumption battle worst-case adversaries the same way quick sort does?
One common way for algorithms to battle adversarial inputs is by acting randomly. One popular example is quicksort and choosing pivots randomly (this sort of notions is explained well in section 5.3 ...
- 3,090
1
vote
1
answer
1k
views
How would you implement truly random hash functions in practice?
Suppose that $[U] = [0,...,U-1]$ is the universe from which all elements will be taken, and $A$ a hash table of size $m$.
A hash function $h:[U]\rightarrow[m]$ is truly random if
For any set of ...
- 639
2
votes
0
answers
81
views
Tradoff between space and false positive rate when using bloom filters
Bloom Filters have false positive rate of $\epsilon = 2^{-k}$ with a data structure of size $m = n\log (\frac{1}{\epsilon})\ln 2$. Suppose you fix the number of hash functions at $k \le 3$. What is ...
- 109