Processing math: 100%

OpenDSA Modules Collection with Slides

Chapter 30 Slides

Show Source | | About « 30.5. Hashing :: Contents :: 30.7. Algorithm Analysis »

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; // probe
Each 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¶

1 / 3 Settings
<<<>>>

Under quadratic probing, two keys with different home positions will have diverging probe sequences. Consider a value that hashes to slot 5. Its probe sequence is 5, then 5 + 1 = 6, then 5 + 4 = 9, then (5 + 9) % 10 = 4, and so on.

0
1
2
3
4
5
6
7
8
9

Saving...
Server Error
Resubmit

1 / 3 Settings
<<<>>>

Unfortunately, quadratic probing has the disadvantage that typically not all hash table slots will be on the probe sequence.

0
1
2
3
4
5
6
7
8
9

Saving...
Server Error
Resubmit

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.

30.6.1.11. Tombstones¶

1 / 16 Settings
<<<>>>

Let's see an example of the deletion process in action. As usual, our example will use a hash table of size 10, the simple mod hash function, and collision resolution using simple linear probing.

0
1
2
3
4
5
6
7
8
9

Saving...
Server Error
Resubmit

Contact Us || Privacy | | License « 30.5. Hashing :: Contents :: 30.7. Algorithm Analysis »