30.6. Quick Hashing¶
30.6.1. A Quick Introduction to Hashing¶
30.6.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\).
30.6.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?"
30.6.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.
30.6.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.
30.6.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.
30.6.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; }
30.6.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 }
30.6.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.
30.6.1.9. Quadratic Probing¶
30.6.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.
