Flashcards
Hash Functions
Cards in this deck (12)
- 1What do we store in a dictionary data structure? What three operations should we be able to perform?We store (key,value) pairs. We want to perform add(x,v), lookup(x) and delete(x)
- 2What does a hash function do?
- 3What data structure is used, when collisions are resolved by chaining?Linked Lists
- 4When building a linked list with chaining, what are the time complexities for add, lookup and delete?O(1), O(length of chain containing x), O(length of chain containing x)
- 5If h(x) and h(y) are chosen uniformly and independantly from [m], what is Pr(h(x) = h(y))?1/m
- 6What is the expected run time per operation if we use a random hash function with chaining?
- 7For each key in U, we specify an arbitrary position in T. Why is this a bad choice for a random hash function?We need ulogm bits, which is a ridiculous amount of space
- 8Why can we not just pick the hash function when we first see x?We would need to recall the hash function we use, therefore needing a dictionary to solve the dictionary problem!
- 9Define Weakly Universal Hashing
- 10Explain why this scheme is weakly universalax + b is a linear transformation which spreads the keys over p values when taken modulo p. This causes no collisions. Only when taken modulo m do we get colliisions
- 11What is the lemma for the longest chain in true randomness hashing?
- 12What is the lemma for the longest chain in weakly universal hashing?
