# Hash Tables

## 1. Hashing

• Save items in a key-indexed table (index is a function of the key).
• Hash function. Method for computing array index from key.
• Issues.

• Computing the hash function.
• Equality test: Method for checking whether two keys are equal.
• Collision resolution: Algorithm and data structure to handle two keys that hash to the same array index.
• Implementing hash code: strings

  public final class String {
private int hash = 0;
private final char[] s;
...
public int hashCode() {
int h = hash;
if(h != 0) return h;
int hash = 0;
for (int i = 0; i < length(); i++)
hash = s[i] + (31 * hash);
hash = h;
return h;
}
}

• Modular hashing

• An int between -2^31 and 2^31 - 1.
• Hash function. An int between 0 and M - 1 (for use as array index).

  private int hash(Key key) { return (key.hashCode() & 0x7fffffff) % M;}


### 1.1. Collisions

• Two distinct keys hashing to same index.
• Solutions: separate chaining and linear probing.

#### Collision resolution: Separate chaining symbol table

• Use an array of M < N linked lists.
• Hash: map key to integer i between 0 and M - 1.
• Insert: put at front of i^th chain (if not already there).
• Search: need to search only i^th chain.
• Typical choice: M ~ N / 5 ⇒ constant-time ops.

#### Collision resolution: Open addressing

• When a new key collides, find next empty slot, and put it there.
• Hash. Map key to integer i between 0 and M-1.
• Insert. Put at table index i if free; if not try i+1, i+2, etc.
• Search. Search table index i; if occupied but no match, try i+1, i+2, etc.
• Note. Array size M must be greater than number of key-value pairs N.
• Typical choice: α = N / M ~ ½.