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
In double hashing, what is done to resolve a collision?
A second hash function
What is the scheme of perfect hashing?
Each secondary table can be constructed several times until it is collision free
What problem does quadratic probing introduce?
Secondary clustering
What is a downside of double hashing?
Likely to be slower than quadratic probing
T/F The hashing function should be a simple algorithm that distributes the keys evenly among the cells
T
What are three common collision resolution strategies?
Linear probing Quadratic probing Double hashing
What is done if sliding in hopscotch hashing is unsuccessful?
Rehash
How does open addressing resolve collisions?
By storing a colliding element in an alternate cell
In universal hashing, what is the probability of a collision if a hash function is chosen at random?
1/M
T/F Each secondary table can be constructed several times until it is collision free
T
In linear probing, cells are tried ____ until an empty cell is found
Sequentially
With a lambda of 1.0, what should the average list be?
1 node
What does quadratic probing help prevent?
Primary clustering
In open addressing, how is the alternate cell chosen?
By another function called the collision resolution strategy
For ints, how does a hash function convert keys to indices?
key % tableSize
