Hashing and Hash Tables

What makes a good hash function?

A good hash function has four properties:

1. Same key, same slot, every time. Otherwise a stored key could never be found again.
2. Quick to compute. The whole point is speed.
3. Spreads the keys evenly over all the slots, so few keys collide.
4. Uses the whole key, not just a part of it.

Property 4 is where the table size matters. A sari-sari store keeps its prices in a hash table with m = 10. Prices are often round numbers: ₱10, ₱20, ₱30, ₱40, ₱50. But k mod 10 is just the last digit, and every one of these ends in 0:

With m = 10, all five prices pile into slot 0, and finding one is as slow as searching a list. With a prime table size such as 7, 11, or 101, the remainder depends on the whole number, so keys that share a pattern still spread out. That is why books (and exams) like prime table sizes.

Separate chaining in Java

The table is an array of chain heads: Node[] table = new Node[m];. Each Node holds a key and next, like the nodes in the Linked lists lesson. Every bucket starts as null (no chain yet). Step through insert(92) when bucket 1 already holds 50 and 85:

 1void insert(int key) { 2  int i = key % m;               // which bucket? 3  Node newNode = new Node(key); 4  if (table[i] == null) {        // empty bucket 5    table[i] = newNode; 6    return; 7  } 8  Node current = table[i]; 9  while (current.next != null) { // walk to the last node10    current = current.next;11  }12  current.next = newNode;        // add at the end of the chain13}

Here is how to read the key lines aloud:

Clusters

Look at the final table: slots 0 to 4 are one solid block. Any new key whose home slot is anywhere in that block has to walk to the end of it, and then it makes the block longer. Try 69: 69 mod 7 = 6, and slot 6 is taken, so it wraps around to 0, 1, 2, 3, 4 (all taken) and lands in slot 5 after 7 tries.

These blocks are called clusters (books say primary clustering). They are linear probing's big weakness, and the reason for the methods in Part 6.

Searching: follow the same path

A search must take the same tries the insert took. It stops in one of two ways: it finds the key, or it reaches an empty slot. An empty slot means the key was never inserted: if it had been, it would have stopped there at the latest.

In Java, the table is an int[]. Since keys are 0 or more, the value -1 can stand for "empty" (named EMPTY). Step through find(92), then find(15):

 1int find(int key) { 2  int home = key % m; 3  for (int i = 0; i < m; i++) { 4    int slot = (home + i) % m;          // linear probing 5    if (table[slot] == EMPTY) { 6      return -1;                        // a never-used slot: stop 7    } 8    if (table[slot] == key) { 9      return slot;                      // found it10    }11  }12  return -1;                            // tried every slot13}

Here is how to read the key lines aloud:

Deleting: leave a mark

Deleting from a chain is easy: unlink the node. In open addressing, it is tricky, because other keys may have probed past the slot you want to empty. Step through deleting 85:

Both tables in one program

Here is the chaining table and the linear-probing table in one runnable file, with insert, search, remove, and print. Run it and match the output to the pictures above:

 1class Node {
 2  int key;
 3  Node next;
 4
 5  Node(int key) {
 6    this.key = key;
 7  }
 8}
 9
10class ChainTable {
11  Node[] table;
12  int m;
13
14  ChainTable(int m) {
15    this.m = m;
16    table = new Node[m];           // every bucket starts as null
17  }
18
19  void insert(int key) {
20    int i = key % m;               // which bucket?
21    Node newNode = new Node(key);
22    if (table[i] == null) {        // empty bucket
23      table[i] = newNode;
24      return;
25    }
26    Node current = table[i];
27    while (current.next != null) { // walk to the last node
28      current = current.next;
29    }
30    current.next = newNode;        // add at the end of the chain
31  }
32
33  boolean contains(int key) {
34    Node current = table[key % m]; // only this bucket's chain
35    while (current != null) {
36      if (current.key == key) {
37        return true;
38      }
39      current = current.next;
40    }
41    return false;
42  }
43
44  void print() {
45    for (int i = 0; i < m; i++) {
46      System.out.print(i + ":");
47      Node current = table[i];
48      while (current != null) {
49        System.out.print(" " + current.key);
50        current = current.next;
51      }
52      System.out.println();
53    }
54  }
55}
56
57class ProbeTable {
58  static final int EMPTY = -1;     // never used
59  static final int DELETED = -2;   // a key was removed here
60  int[] table;
61  int m;
62
63  ProbeTable(int m) {
64    this.m = m;
65    table = new int[m];
66    for (int i = 0; i < m; i++) {
67      table[i] = EMPTY;
68    }
69  }
70
71  boolean insert(int key) {
72    int home = key % m;
73    for (int i = 0; i < m; i++) {
74      int slot = (home + i) % m;   // linear probing
75      if (table[slot] == EMPTY || table[slot] == DELETED) {
76        table[slot] = key;
77        return true;
78      }
79    }
80    return false;                  // no free slot
81  }
82
83  int find(int key) {
84    int home = key % m;
85    for (int i = 0; i < m; i++) {
86      int slot = (home + i) % m;          // linear probing
87      if (table[slot] == EMPTY) {
88        return -1;                        // a never-used slot: stop
89      }
90      if (table[slot] == key) {
91        return slot;                      // found it
92      }
93    }
94    return -1;                            // tried every slot
95  }
96
97  void remove(int key) {
98    int slot = find(key);
99    if (slot != -1) {
100      table[slot] = DELETED;       // a mark, not EMPTY
101    }
102  }
103
104  void print() {
105    for (int i = 0; i < m; i++) {
106      if (table[i] == EMPTY) {
107        System.out.println(i + ": -");
108      } else if (table[i] == DELETED) {
109        System.out.println(i + ": deleted");
110      } else {
111        System.out.println(i + ": " + table[i]);
112      }
113    }
114  }
115}
116
117public class Main {
118  public static void main(String[] args) {
119    int[] keys = {50, 700, 76, 85, 92, 73};
120
121    ChainTable chain = new ChainTable(7);
122    for (int i = 0; i < keys.length; i++) {
123      chain.insert(keys[i]);
124    }
125    chain.print();
126    System.out.println(chain.contains(92));   // true
127    System.out.println(chain.contains(15));   // false
128
129    ProbeTable probe = new ProbeTable(7);
130    for (int i = 0; i < keys.length; i++) {
131      probe.insert(keys[i]);
132    }
133    probe.print();
134    System.out.println(probe.find(92));       // 3
135    probe.remove(85);
136    System.out.println(probe.find(92));       // still 3
137    System.out.println(probe.find(85));       // -1
138  }
139}

▶ This program runs as is. Try it in the Programiz online compiler: tap Copy, paste it there, and press Run.

Output:

0: 700
1: 50 85 92
2:
3: 73
4:
5:
6: 76
true
false
0: 700
1: 50
2: 85
3: 92
4: 73
5: -
6: 76
3
3
-1

Two new lines to read aloud:

Good to know: these tables assume every key is different, like student IDs. A real table would first search for the key and skip it if it is already there. Negative keys need Math.floorMod(key, m), because Java's % gives a negative remainder for a negative number.

Quadratic probing

Same keys, same table:

See 92: its third try jumped from slot 1 straight to slot 5 (1 + 2² = 5), out of the crowd.

Double hashing

With m = 7, R = 5. Same keys again:

The three results side by side

In this tiny example, double hashing needed the most tries. With only 7 slots and 6 keys, every method runs into full slots. The payoff of quadratic probing and double hashing shows in big tables, where linear probing's clusters keep growing and the other two scatter the keys.

Here is a summary of the four methods: