A hash table with chaining in C

A bucket array of linked nodes: hash to a bucket, then walk the short chain.

#include <stdlib.h>
#include <string.h>

#define BUCKETS 16

typedef struct Entry {
    char *key;
    int value;
    struct Entry *next;
} Entry;

static size_t hash(const char *key) {
    size_t h = 5381;
    for (const char *p = key; *p; p++) {
        h = h * 33u + (unsigned char) *p;
    }
    return h % BUCKETS;
}

static char *copy_key(const char *key) {
    size_t n = strlen(key) + 1;
    char *copy = malloc(n);
    if (copy != NULL) {
        memcpy(copy, key, n);
    }
    return copy;
}

int table_put(Entry **buckets, const char *key, int value) {
    size_t slot = hash(key);
    for (Entry *e = buckets[slot]; e != NULL; e = e->next) {
        if (strcmp(e->key, key) == 0) {
            e->value = value;
            return 1;
        }
    }
    Entry *entry = malloc(sizeof *entry);
    if (entry == NULL) {
        return 0;
    }
    entry->key = copy_key(key);
    if (entry->key == NULL) {
        free(entry);
        return 0;
    }
    entry->value = value;
    entry->next = buckets[slot];
    buckets[slot] = entry;
    return 1;
}

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

How it works

1. The hash is reduced modulo the bucket count.
2. Collisions live together in one chain.
3. strdup is POSIX, so ISO C copies the key by hand.

Keywords and builtins used here

• Entry
• NULL
• char
• const
• copy_key
• for
• hash
• if
• int
• return
• size_t
• sizeof
• static
• struct
• table_get
• table_put
• typedef
• unsigned

The run, in numbers

Lines

60

Characters to type

1080

Tokens

367

Three-star pace

105 tpm

At the three-star pace of 105 tokens a minute, this run takes about 210 seconds.

Type this snippet

Step 3 of 4 in Trees, tables & heaps, step 13 of 20 in Data structures & algorithms.

← Previous Next →