Fechar
What do we store in a dictionary data structure? What three operations should we be able to perform?
What does a hash function do?
What data structure is used, when collisions are resolved by chaining?
When building a linked list with chaining, what are the time complexities for add, lookup and delete?
If h(x) and h(y) are chosen uniformly and independantly from [m], what is
Pr(h(x) = h(y))?
What is the expected run time per operation if we use a random hash function with chaining?
For each key in U, we specify an arbitrary position in T. Why is this a bad choice for a random hash function?
Why can we not just pick the hash function when we first see x?
Define Weakly Universal Hashing
Explain why this scheme is weakly universal
What is the lemma for the longest chain in true randomness hashing?
What is the lemma for the longest chain in weakly universal hashing?
