Chapter 5 (Hashing) Flashcards
Table size should be a ____ ____
Prime number
In perfect hashing, what is the worst case access time?
O(1)
What is a drawback of the chaining method?
Allocating new nodes
What is the formula for the expected number of probes in a linear probing strategy?
1/(1-lambda)
What is the worst case running time for a find in hopscotch hashing?
O(1)
T/F Java hash tables require the “equals” and “hashCode” methods to be defined on the hashed objects
T
How many hash tables does cuckoo hashing use?
2
How does separate chaining handle collisions?
Each index contains a list. Each item that collides is contained in this list
What is primary clustering?
A large list of values clustered around the same cell
What is the primary drawback of linear probing?
Primary clustering
What is it called when two keys map to the same location?
Collision
What is lambda?
The ratio of the number of elements to the table size
What is the job of the hash function?
Mapping
What is the average running time for inserts, deletes, and finds for hashing?
O(1)
T/F Hashing supports operations like findMin and findMax
F
What is the worst case access time in cuckoo hashing?
O(1)
What is rehashing?
When a table is 50% full, create a new table twice the size of the old one and rehash everything to the new table
How can duplicates be handled with separate chaining?
Having a counter on each element
What does Horner’s rule give us?
A simple way to compute a polynomial using multiplication and addition
In perfect hashing, what is the space required?
O(n)
What is the strategy of quadratic probing?
First look 1 away, then 4, 9, 16, 25, etc.
If we want to hash 100 elements into a table size of 100, what would lambda be?
1.0
T/F Open addressing requires a large table
T
How can you keep the likelihood of a cycle in cuckoo hashing very small?
Keep the load < 0.5
