# 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.

HThas \(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

hwith 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.