Hashing Flashcards
What are the desired properties of a hash function
- Fast and easy to compute
- Even spread of keys
- Table size should not be ‘much larger’ than the number of entries.
What is one of the main problems with universal hashing
for any function there exists a set of entries that all hash to the same location
what are two commonly used strategies to reduce collisions
Seperate chaining: a hash tab;e of lists
open addressing: find a new position in the hash table
What are dynamic arrays?
Arrays where we start with a reasonable capacity, then when that capacity is reached double it.
What is the amortised analysis of dynamic arrays?
Copying the old array takes time Omega n
So in worst case adding a new element may require Omega n
However, the new array allows adding n more elements before the size is increased again
What is the consequence of the amortised analysis of dynamic arrays?
Many simple add operations for each expensive one mean it averages out to be efficient in terms of runtime
What is the total runtime of n add operations in dynamic arrays?
Theta n
What is the amortised runtime of each add operation?
theta 1 (const)
What is the worst case runtime of each add operation?
Theta n
