Hash Table Search

Idea

Hash Table Search maps a key via hash function to a slot—trading space for time, achieving near $O(1)$ lookups.

When to use

• Large data, very frequent lookups
• High-performance equality queries

Algorithm

1. Design a hash function $H(x)$ mapping key $x$ to a slot.
2. If empty, not found.
3. If occupied, compare key.
4. On collision, resolve (open addressing, chaining, etc.).

Pseudo-code:

pos = H(x)
if table[pos] == null:
    return -1
elif table[pos].key == x:
    return pos
else:
    // collision handling (e.g., linear probing or chaining)
    ...

Constructing a Hash Function

• Division method (modulo): $H(key) = key \bmod p$, where $p$ is the largest prime not greater than the table length $m$. It spreads the keys most evenly and is the most common choice.
• Direct addressing: $H(key) = a \times key + b$, suitable when the keys are distributed continuously.
• Digit analysis: take the few digits of the key that are distributed most evenly.
• Mid-square method: take the middle digits of the square of the key.
• Folding method: split the key into several parts and add them up.

Collision Handling

Open Addressing

On a collision, look for the next free slot inside the hash table.

• Linear probing: $H_i = (H(key) + i) \bmod m$, which easily produces clustering.
• Quadratic probing: $H_i = (H(key) + i^2) \bmod m$, which avoids clustering.

Chaining

All elements that hash to the same position are hung on one linked list. A search first locates the list, then scans it sequentially.

#include <stdlib.h>

#define M 13  // table length (a prime number)

typedef struct Node {
    int key;
    struct Node *next;
} Node;

// Hash function: division method
int H(int key) {
    return key % M;
}

// Search with chaining
Node *HashSearch(Node *hashtable[], int key) {
    int pos = H(key);
    Node *p = hashtable[pos];
    while (p != NULL && p->key != key)
        p = p->next;          // sequential search along the list
    return p;                 // the node that was found, or NULL
}

// Insert with chaining
void HashInsert(Node *hashtable[], int key) {
    int pos = H(key);
    Node *s = (Node *)malloc(sizeof(Node));
    s->key = key;
    s->next = hashtable[pos];  // insert at the head of the list
    hashtable[pos] = s;
}

Load Factor and Performance

The load factor $\alpha = \frac{\text{number of elements}}{\text{table length}}$ directly affects the search performance.

• The larger $\alpha$ is, the more collisions there are, and the lower the search efficiency.
• Average search length for chaining: $ASL_{\text{success}} \approx 1 + \frac{\alpha}{2}$
• Average search length for linear probing: $ASL_{\text{success}} \approx \frac{1}{2}\left(1 + \frac{1}{1-\alpha}\right)$
• In engineering practice $\alpha$ is usually kept in the 0.7 to 0.8 range.

Complexity

• Ideal: $O(1)$
• Worst (heavy collisions): $O(n)$
• In practice, near $O(1)$ with good hash & load factor

Exercises

Exercise 1

Hash-table search idea and common collision strategies?

Exercise 2

Average complexity? When does it degrade to $O(n)$?

Past exam

2020·408

What are the two steps of the hash search process? Which collision-handling methods exist?