Hash tables Flashcards
What is a hash table?
A data structure that stores records containing keyed data items and uses a hash function to compute an array index from the key.
Hash tables aim for near constant-time (O(1)) average complexity for insertion and searching operations.
How does a hash function for integer keys work?
h(k) = k mod N, where N is the size of the hash table array.
This ensures the hash value is within the valid range of array indices (0 to N-1).
What is the suggested hash function for float keys?
hfloat(k) = hint(round(k)), where the float is rounded to the nearest integer before hashing.
The effectiveness of hash functions depends on the distribution of keys.
How can string keys be hashed?
hstring(k) = (Σ k[i]) mod N, where Σ k[i] is the sum of ASCII values of each character in the string.
Folding is an improved method where groups of characters are treated as integers.
What is the basic algorithm for inserting an item into a hash table?
Algorithm hashTableInsert(i): index = h(item.key()), table[index] = i
This assumes a perfect hash function without collisions.
What is a collision in a hash table?
When two different keys hash to the same array index.
Collisions are inevitable due to practical limitations on hash table size.
What are the four main methods for resolving collisions?
- Open Addressing
- Linear Probing
- Quadratic Probing
- Double Hashing
- Separate Chaining
What is Open Addressing in collision resolution?
Probing the hash table for an alternative unused index when a collision occurs.
The sequence of alternative indices is determined by a probing function.
What is Linear Probing?
A collision resolution method where the next indices checked are (h(k) + j) mod N.
Linear probing can lead to clustering of occupied slots.
What is Quadratic Probing?
A probing method using a quadratic function for p(j), such as p(j) = (-1)^(j-1) * (ceil(j/2))^2.
This reduces clustering compared to linear probing.
What is Double Hashing?
A technique that uses a second hash function h2(k) to determine the probe increment.
The probing function is of the form p(j) = h2(k) * j.
What is Separate Chaining?
An approach where each index in the hash table points to a container ADT, typically a linked list, to hold items that hash to that index.
This method allows easy handling of collisions by adding new items to the linked list.
What is the load factor of a hash table?
LF = s/N, where s is the number of items stored and N is the size of the hash table array.
A high load factor increases the likelihood of collisions.
What happens when the load factor exceeds a certain threshold?
The hash table is resized, creating a larger array and rehashing all existing items.
This maintains overall efficiency despite being an expensive operation.
How is deletion handled in a hash table with open addressing?
Marking a slot as ‘available, but previously occupied’ to avoid breaking probe sequences.
This allows the search process to continue correctly.
What is the algorithm for searching an item in a hash table?
Algorithm hashTableSearch(k): index = h(k), check if item at index matches key, else continue probing.
If the index is empty, it indicates the item does not exist.
True or False: Hash tables are considered a type of keyed dictionary.
True.
They support operations like looking up, searching for, and deleting items by key.
What is the impact of a high load factor on performance?
Increases collision frequency, leading to longer search and insertion times, degrading performance towards O(n).
Keeping the load factor small is crucial for maintaining efficiency.
Fill in the blank: The basic concept of a hash table is to use a _______ to map keys to array indices.
[hash function]
Fill in the blank: The probing function in linear probing can be expressed as _______.
[p(j) = j]
What is a special marker used for in deletion from hash tables?
To indicate a slot that was previously occupied but is now available.
This prevents breaking the probe sequence for other items.
