17.20. Quick Hashing¶
17.20.1. A Quick Introduction to Hashing¶
17.20.1.1. Hashing (1)¶
Hashing: The process of mapping a key value to a position in a table.
A hash function maps key values to positions. It is denoted by \(h\).
A hash table is an array that holds the records. It is denoted by HT.
HT has \(M\) slots, indexed form 0 to \(M-1\).
17.20.1.2. Hashing (2)¶
For any value \(K\) in the key range and some hash function \(h\), \(h(K) = i\), \(0 <= i < M\), such that key(HT[i]) \(= K\).
Hashing is appropriate only for sets (no duplicates).
Good for both in-memory and disk-based applications.
Answers the question “What record, if any, has key value K?”
17.20.1.3. Collisions¶
Given: hash function h with keys \(k_1\) and \(k_2\). \(\beta\) is a slot in the hash table.
If \(\mathbf{h}(k_1) = \beta = \mathbf{h}(k_2)\), then \(k_1\) and \(k_2\) have a collision at \(\beta\) under h.
- Search for the record with key \(K\):
Compute the table location \(\mathbf{h}(K)\).
Starting with slot \(\mathbf{h}(K)\), locate the record containing key \(K\) using (if necessary) a collision resolution policy.
17.20.1.4. Closed Hashing¶
Closed hashing stores all records directly in the hash table.
Each record \(i\) has a home position \(\mathbf{h}(k_i)\).
If another record occupies the home position for \(i\), then another slot must be found to store \(i\).
The new slot is found by a collision resolution policy.
Search must follow the same policy to find records not in their home slots.
17.20.1.5. Collision Resolution¶
During insertion, the goal of collision resolution is to find a free slot in the table.
Probe sequence: The series of slots visited during insert/search by following a collision resolution policy.
Let \(\beta_0 = \mathbf{h}(K)\). Let \((\beta_0, \beta_1, ...)\) be the series of slots making up the probe sequence.
17.20.1.6. Insertion¶
// Insert e into hash table HT void hashInsert(const Key& k, const Elem& e) { int home; // Home position for e int pos = home = h(k); // Init probe sequence for (int i=1; EMPTYKEY != (HT[pos]).key(); i++) { pos = (home + p(k, i)) % M; // probe if (k == HT[pos].key()) { println("Duplicates not allowed"); return; } } HT[pos] = e; }
17.20.1.7. Search¶
// Search for the record with Key K bool hashSearch(const Key& K, Elem& e) const { int home; // Home position for K int pos = home = h(K); // Initial position is the home slot for (int i = 1; (K != (HT[pos]).key()) && (EMPTYKEY != (HT[pos]).key()); i++) pos = (home + p(K, i)) % M; // Next on probe sequence if (K == (HT[pos]).key()) { // Found it e = HT[pos]; return true; } else return false; // K not in hash table }
17.20.1.8. Probe Function¶
Look carefully at the probe function p():
pos = (home + p(k, i)) % M; // probeEach time p() is called, it generates a value to be added to the home position to generate the new slot to be examined.
\(p()\) is a function both of the element’s key value, and of the number of steps taken along the probe sequence. Not all probe functions use both parameters.
17.20.1.9. Quadratic Probing¶
17.20.1.10. Deletion¶
Deleting a record must not hinder later searches.
We do not want to make positions in the hash table unusable because of deletion.
Both of these problems can be resolved by placing a special mark in place of the deleted record, called a tombstone.
A tombstone will not stop a search, but that slot can be used for future insertions.
