Hash Functions

Flashcards by msladey, updated more than 1 year ago
Created by msladey almost 6 years ago



Resource summary

Question Answer
What 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)
What does a hash function do?
What data structure is used, when collisions are resolved by chaining? Linked Lists
When 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)
If h(x) and h(y) are chosen uniformly and independantly from [m], what is Pr(h(x) = h(y))? 1/m
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? We need ulogm bits, which is a ridiculous amount of space
Why 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!
Define Weakly Universal Hashing
Explain why this scheme is weakly universal ax + 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
What is the lemma for the longest chain in true randomness hashing?
What is the lemma for the longest chain in weakly universal hashing?
Show full summary Hide full summary


Static Perfect Hashing
Cuckoo Hashing
Lowest Common Ancestor
Data Structures & Algorithms
Reuben Caruana
Data Structures & Algorithms
Martyn Haigh
Computer science unit 2
Somto Ibeme
Algorithms ♡
lauren ♥
Computational Thinking ♡
lauren ♥
Searching and Sorting Algorithms
Josh Calvert
Systems Software Revision
Grafy I.
Michal Roch