Hash Tables Flashcards
A data structure where key is also the index.
Direct-Address-Table
Direct addressing works well if the universe U of keys is _________.
small
________ reduce the storage requirement to O |K| while maintaining O 1 average-case time.
Hash tables
We use a ___________ to compute the position from the key k.
hash function
An ideal theoretical abstraction that says each key is equally likely to hash to any
of the m positions, independently of
where any other keys have hashed to.
independent uniform hashing
independent uniform hash function aka _______________
a random oracle
A good hash function ___________________ an
independent uniform hash function.
approximates
Uses a single, fixed hash function for any data.
Static hashing
If the hash function is known, keys can be maliciously hashed to the same position.
The hash function is picked at random
from a family of hashing functions.
Random hashing
Collision Resolutions
Chaining (Open Hashing)
Probing (Closed Hashing)
Each nonempty hash-table slot T[j]
points to a linked list of all the keys whose hash value is j.
Chaining aka Open Hashing
When inserting a new element,
- if its “first-choice” location is free,
insert the element
- else if its “second-choice” location is
free, insert the element
- and so on, until a free spot is found
aka _________________
Probing, Open Addressing aka Closed Hashing
If the first choice position is occupied, probe the next position
Linear Probing
__________ prevents the formation of blocks in linear probing
quadratic probing
