# Hash Functions

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

Hashing

## 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?

### Similar

Static Perfect Hashing
Cuckoo Hashing
Lowest Common Ancestor
Data Structures & Algorithms
Data Structures & Algorithms
Computer science unit 2
Algorithms ♡
Computational Thinking ♡
Searching and Sorting Algorithms
Systems Software Revision
Grafy I.