Hash tables

Introduction

A hash table finds a value by its key, such as a student's mark by name, in O(1) on average. A hash function turns the key into a number, and that number modulo the table size picks a bucket. Python's dictionaries and most databases' indexes work this way.

Two keys can land in the same bucket: a collision. A hash table is mostly about handling collisions well.

Searching by name through a million records one at a time is hopeless, and even a tree takes around twenty comparisons. A hash table goes almost straight there, by turning the key itself into the position where its value is kept.

How it works

Open addressing: linear probing

#include <stdio.h>
#define SIZE 7
#define EMPTY -1

int table[SIZE];

void insert(int key) {
    int i = key % SIZE;
    while (table[i] != EMPTY) i = (i + 1) % SIZE;   // taken: try the next slot
    table[i] = key;
}

int find(int key, int *probes) {
    int i = key % SIZE;
    *probes = 1;
    while (table[i] != EMPTY) {
        if (table[i] == key) return i;
        i = (i + 1) % SIZE;
        (*probes)++;
    }
    return -1;
}

int main(void) {
    for (int i = 0; i < SIZE; i++) table[i] = EMPTY;
    insert(10);
    insert(17);
    insert(24);
    insert(5);
    int probes;
    int at = find(24, &probes);
    printf("24 is in slot %d after %d probes\n", at, probes);
    return 0;
}

Without lists, each key goes straight into the array. If its slot is taken, try the next one, wrapping round at the end: this is linear probing. Here 10, 17 and 24 all hash to 3, so they take slots 3, 4 and 5, and 5 (which hashes to 5) is pushed on to 6. Finding 24 then takes 3 probes.

Keep it from getting full

The load factor is items ÷ buckets. As it grows, chains get longer and probes run further, and O(1) slowly becomes O(n). Real tables resize (often doubling) when the load factor passes about 0.7, moving every entry to its new bucket.

A hash table keeps no order: to list keys sorted, you need a BST or a sort.

Syntax

unsigned h = 0;
for (int i = 0; key[i] != '\0'; i++) h = h * 31 + key[i];
unsigned bucket = h % BUCKETS;

Example

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUCKETS 5

typedef struct entry {
    char key[12];
    int value;
    struct entry *next;
} Entry;

Entry *table[BUCKETS];   // globals start as NULL: every bucket is empty

unsigned hash(const char *key) {
    unsigned h = 0;
    for (int i = 0; key[i] != '\0'; i++) h = h * 31 + key[i];
    return h % BUCKETS;
}

void put(const char *key, int value) {
    unsigned b = hash(key);
    for (Entry *e = table[b]; e != NULL; e = e->next) {
        if (strcmp(e->key, key) == 0) {
            e->value = value;   // already there: update it
            return;
        }
    }
    Entry *e = malloc(sizeof(Entry));
    strcpy(e->key, key);
    e->value = value;
    e->next = table[b];
    table[b] = e;
}

int get(const char *key, int *value) {
    for (Entry *e = table[hash(key)]; e != NULL; e = e->next) {
        if (strcmp(e->key, key) == 0) {
            *value = e->value;
            return 1;
        }
    }
    return 0;
}

int main(void) {
    put("rahim", 81);
    put("karim", 67);
    put("nadia", 92);
    put("rahim", 85);
    int v;
    if (get("rahim", &v)) printf("rahim: %d\n", v);
    if (!get("sumi", &v)) printf("sumi: not found\n");
    return 0;
}

Each bucket holds a linked list of the entries that hash to it. Here "rahim" and "nadia" both land in bucket 4, so bucket 4's list has two nodes. Watch the heap blocks and the arrows from table.

• put: walk the bucket's list; if the key is there, change its value; otherwise add a new entry at the front.
• get: walk the bucket's list and compare keys with strcmp.

The hash function h = h * 31 + c mixes every character, so similar keys spread out. It uses unsigned, because unsigned arithmetic wraps round safely when the number gets too big.

Line by line

1. Entry holds a key, a value and a pointer to the next entry in the same bucket.
2. table is an array of BUCKETS list heads, and global variables start as NULL.
3. hash mixes each character into h, and returns it modulo the table size.
4. put walks the key's bucket. If the key is already there, it updates the value and returns.
5. Otherwise put creates an entry and adds it at the front of the bucket's list.
6. get walks the bucket and compares with strcmp, reporting success through its return value.
7. main stores three names, updates rahim, and finds that sumi is not there.

Expected result

rahim: 85
sumi: not found

In the real world

Python's dictionaries and JavaScript's objects and Map are hash tables, and so are many database indexes. Compilers use one to remember every variable name in a program.

Common mistakes

• Comparing string keys with ==, which compares addresses, not text. Use strcmp.
• A hash function that ignores most of the key (just the first letter, say): many collisions.
• With linear probing, forgetting to wrap round with % SIZE, or looping forever in a full table.

Best practices

• Compare the full key after hashing, because different keys can share a bucket.
• Grow the table before the load factor gets high.
• Use a hash function that depends on every character of the key.

Summary

A hash table turns a key into a bucket number, so a lookup usually touches only a few items. Collisions are handled with chains or probing, and a low load factor is what keeps the average at O(1).

Mark lesson complete