Growing a hash table

A chained table of eight buckets fills up. Watch what happens to every key when it doubles to sixteen.

⋯29static bool grow(struct table *t)30{31    size_t new_m = 2 * t->m;32    struct item **nb = malloc(new_m * sizeof *nb);33    if (nb == NULL)34        return false;35    for (size_t b = 0; b < new_m; b++)36        nb[b] = NULL;37    for (size_t b = 0; b < t->m; b++) {38        struct item *it = t->bucket[b];39        while (it != NULL) {40            struct item *next = it->next;41            size_t nbk = (size_t)it->key & (new_m - 1);42            it->next = nb[nbk];43            nb[nbk] = it;44            moved++;45            it = next;46        }47    }48    free(t->bucket);49    t->bucket = nb;50    t->m = new_m;51    return true;52}53 54bool put(struct table *t, int key)55{56    struct item *it = malloc(sizeof *it);57    if (it == NULL)58        return false;59    size_t b = (size_t)key & (t->m - 1);60    it->key = key;61    it->next = t->bucket[b];62    t->bucket[b] = it;63    t->n++;64    if (4 * t->n > 3 * t->m)65        return grow(t);66    return true;67}68 69void print(const struct table *t)70{71    for (size_t b = 0; b < t->m; b++) {72        if (t->bucket[b] == NULL)73            continue;74        printf("%zu:", b);75        for (const struct item *it = t->bucket[b]; it != NULL; it = it->next)76            printf(" %d", it->key);77        printf("\n");78    }79}80 81int main(void)82{83    struct table t;84    if (!init(&t, 8))85        return 1;86    const int keys[7] = { 3, 11, 19, 27, 6, 14, 30 };87    for (int i = 0; i < 6; i++)88        put(&t, keys[i]);89    print(&t);90    put(&t, keys[6]);91    printf("grown to %zu buckets, %d keys moved\n", t.m, moved);92    print(&t);93    for (size_t b = 0; b < t.m; b++) {94        struct item *it = t.bucket[b];95        while (it != NULL) {96            struct item *next = it->next;97            free(it);98            it = next;99        }100    }101    free(t.bucket);102    return 0;103}

Why every key moves

A key’s bucket is its hash mod m, so when m changes, the bucket changes. Growing a table cannot copy the buckets as they are: it allocates a larger array and places every key again. This is rehashing.

The table grows when the load factor α = n/m passes a limit, here 0.75. Doubling m brings α back to about half the limit, and the chains back to their short average length.

The code and its cost

static bool grow(struct table *t)
{
    size_t new_m = 2 * t->m;
    struct item **nb = malloc(new_m * sizeof *nb);
    if (nb == NULL)
        return false;
    for (size_t b = 0; b < new_m; b++)
        nb[b] = NULL;
    for (size_t b = 0; b < t->m; b++) {
        struct item *it = t->bucket[b];
        while (it != NULL) {
            struct item *next = it->next;
            size_t nbk = (size_t)it->key & (new_m - 1);
            it->next = nb[nbk];
            nb[nbk] = it;
            moved++;
            it = next;
        }
    }
    free(t->bucket);
    t->bucket = nb;
    t->m = new_m;
    return true;
}

bool put(struct table *t, int key)
{
    struct item *it = malloc(sizeof *it);
    if (it == NULL)
        return false;
    size_t b = (size_t)key & (t->m - 1);
    it->key = key;
    it->next = t->bucket[b];
    t->bucket[b] = it;
    t->n++;
    if (4 * t->n > 3 * t->m)
        return grow(t);
    return true;
}

The table’s size is a power of two, and the keys are not negative, so key & (m - 1), which keeps the key’s low bits, is key % m. put grows the table when 4n > 3m, that is α > 0.75, using whole numbers. grow does not copy any item: it re-links each one at the front of its new bucket’s chain, so each chain’s order is reversed.

main puts six keys, prints the table, puts the seventh, and prints again:

3: 27 19 11 3
6: 14 6
grown to 16 buckets, 7 keys moved
3: 3 19
6: 6
11: 11 27
14: 14 30

With a doubled power-of-two size, & (new_m - 1) uses one more bit of the key. A key whose next bit is 0 stays in bucket b; a key whose next bit is 1 moves to b + 8. The program places all 7 keys again, which is the 7 keys moved it prints, but only four change bucket: 3, 19 and 6 land in the bucket they had, and 11, 27, 14 and 30 go to b + 8.

The average cost

A growth moves all n keys, which is expensive, but it is rare: each doubling comes after the table has gained about as many keys again as it had at the last one. As with Dynamic arrays, the moves over n insertions add up to about 2n at most, and always to fewer than 3n, so an insertion costs O(1) on average, even counting the growths.

Growing by one bucket at a time would move every key at every insertion: O(n²) in all.

Power-of-two sizes and prime sizes

A power-of-two size lets the bucket be computed with a mask, key & (m - 1), which is fast, and makes doubling simple. But the mask uses only the key’s low bits, so the hash must mix its low bits well. A prime size uses a remainder, key % m, which is slower but forgives a weaker hash, as the Hash functions lesson showed for keys that are all multiples of 4.

Worked example

A thousand keys. Starting from 8 buckets and doubling when α > 0.75, the table grows at the 7th, 13th, 25th, 49th, 97th, 193rd, 385th and 769th key, just past 0.75 × 8, 16, 32, …, 1,024. It moves 7 + 13 + 25 + 49 + 97 + 193 + 385 + 769 = 1,538 keys in all, under 2 × 1,000: 1.54 moves per key, and ends with 2,048 buckets.

Keys that agree in their low bits. With m = 8 and keys that all leave remainder 3 when divided by 8, every key lands in bucket 3. Each doubling uses one more bit of the key, and splits the bucket in two.

Two checks. Which bucket holds 30 when there are 32 buckets? (30 & 31 = 30.) Why not grow by one bucket at a time? (Every key would move at every growth: O(n²) in all.)

Where it’s used

Every growable hash table in language libraries.

Databases’ hash indexes, some of which grow one bucket at a time, splitting it, instead of all at once.

Reference card

Platform: C11, gcc on x86-64 Linux: int 4 bytes, size_t and pointers 8, struct item 16, struct table 24, little-endian. Addresses in the pictures are short stand-ins, by one rule for the whole course; sizes are the real ones.