A hash table

A hash table turns a key into an index and stores the value there, so a lookup costs one hash and a short walk. Two keys may land in the same bucket, and the table must handle that collision. The linked list from lesson 51 is the chain that does it.

A hash function

The hash below is djb2: start at 5381 and multiply by 33 for every byte. It is fast and spreads short strings well enough for a demonstration. The byte is cast to unsigned char before it is added, and the accumulator is unsigned, so the value is never negative.

#include <stdio.h> static unsigned long hash(const char *text) { unsigned long value = 5381; while (*text != 0) { value = value * 33 + (unsigned char) *text; text++; } return value; } int main(void) { const char *words[3] = {"apple", "banana", "cherry"}; for (int i = 0; i < 3; i++) { printf("%-7s %lu mod 8 = %lu\n", words[i], hash(words[i]), hash(words[i]) % 8); } return 0; }

gcc -Wall -Wextra hash.c -o hash
./hash

apple 210706734647 mod 8 = 7
banana 6953343506470 mod 8 = 6
cherry 6953390638546 mod 8 = 2

The three words land in three different buckets of eight. The remainder is the bucket index; a good hash makes the remainders spread evenly, and the table size is usually a prime or a power of two depending on the mixing step.

Buckets and lookups

The table is an array of bucket heads, each a linked list of entries. Put allocates an entry, links it at the front of its bucket, and stores the key pointer. Get hashes the key, walks its bucket, and compares with strcmp until it finds a match or reaches the end.

#include <stdio.h> #include <stdlib.h> #include <string.h> #define BUCKETS 8 struct Entry { const char *key; int value; struct Entry *next; }; static struct Entry *table[BUCKETS]; static unsigned long hash(const char *text) { unsigned long value = 5381; while (*text != 0) { value = value * 33 + (unsigned char) *text; text++; } return value; } static int put(const char *key, int value) { unsigned long index = hash(key) % BUCKETS; struct Entry *entry = malloc(sizeof *entry); if (entry == NULL) { return 0; } entry->key = key; entry->value = value; entry->next = table[index]; table[index] = entry; return 1; } static int get(const char *key, int *out) { unsigned long index = hash(key) % BUCKETS; for (struct Entry *entry = table[index]; entry != NULL; entry = entry->next) { if (strcmp(entry->key, key) == 0) { *out = entry->value; return 1; } } return 0; } int main(void) { int value = 0; put("apple", 1); put("banana", 2); put("cherry", 3); if (get("banana", &value)) { printf("banana: %d\n", value); } if (!get("durian", &value)) { printf("durian: missing\n"); } for (int i = 0; i < BUCKETS; i++) { struct Entry *entry = table[i]; while (entry != NULL) { struct Entry *next = entry->next; free(entry); entry = next; } } return 0; }

gcc -Wall -Wextra table.c -o table
./table

banana: 2
durian: missing

The key pointer is stored, not a copy, so the caller must keep the string alive; a table that owns its keys would duplicate them with the arena or strdup. The lookup compares the string contents, never the pointers, because equal keys may be different buffers.

Collisions

Six words in eight buckets must collide somewhere, and the bucket lengths show where. The words were chosen to share prefixes, which djb2 spreads less evenly than unrelated text. A chain of two costs two string comparisons; a chain of ten would cost ten, which is why the load factor matters.

#include <stdio.h> #include <stdlib.h> #include <string.h> #define BUCKETS 8 struct Entry { const char *key; struct Entry *next; }; static struct Entry *table[BUCKETS]; static unsigned long hash(const char *text) { unsigned long value = 5381; while (*text != 0) { value = value * 33 + (unsigned char) *text; text++; } return value; } static void put(const char *key) { unsigned long index = hash(key) % BUCKETS; struct Entry *entry = malloc(sizeof *entry); if (entry == NULL) { return; } entry->key = key; entry->next = table[index]; table[index] = entry; } int main(void) { const char *words[6] = {"apple", "apricot", "avocado", "banana", "blueberry", "cherry"}; for (int i = 0; i < 6; i++) { put(words[i]); } for (int i = 0; i < BUCKETS; i++) { int count = 0; for (struct Entry *entry = table[i]; entry != NULL; entry = entry->next) { count++; } printf("bucket %d: %d\n", i, count); } for (int i = 0; i < BUCKETS; i++) { struct Entry *entry = table[i]; while (entry != NULL) { struct Entry *next = entry->next; free(entry); entry = next; } } return 0; }

gcc -Wall -Wextra chain.c -o chain
./chain

bucket 0: 0
bucket 1: 1
bucket 2: 2
bucket 3: 0
bucket 4: 0
bucket 5: 0
bucket 6: 1
bucket 7: 2

Five of the eight buckets are used and the longest chain has two entries, so the average lookup is one or two comparisons. A table that grows past its load factor resizes: allocate a larger bucket array, rehash every entry into it, and free the old array.

A negative bucket index

The hash in this lesson is unsigned for a reason. A signed accumulator built from plain char bytes turns negative as soon as a byte above 127 arrives, and the remainder inherits the sign. The table below indexes with -2:

#include <stdio.h> #include <stdlib.h> #define BUCKETS 8 static int hash(const char *text) { int value = 0; while (*text != 0) { value = value * 31 + *text; text++; } return value; } int main(void) { char word[3] = {(char) 0xC3, (char) 0xA9, 0}; int index = hash(word) % BUCKETS; int *buckets = calloc(BUCKETS, sizeof *buckets); if (buckets == NULL) { return 1; } printf("index: %d\n", index); buckets[index] = 1; printf("stored\n"); free(buckets); return 0; }

gcc -fsanitize=address -g -Wall -Wextra negative.c -o negative
./negative 2>&1 | head -n 6

index: -2
=================================================================
==903==ERROR: AddressSanitizer: heap-buffer-overflow on address 0x6e62a6620008 at pc 0x65432c5e64a1 bp 0x7ffefee74150 sp 0x7ffefee74140
WRITE of size 4 at 0x6e62a6620008 thread T0
#0 0x65432c5e64a0 in main /tmp/c5/L52/negative.c:27
#1 0x7232a7103153 in libc_start_main_stage2 src/env/__libc_start_main.c:95

The write landed eight bytes before the allocation, which the report names as "8 bytes before 32-byte region". The fix is in the hash: read the bytes as unsigned char and keep the accumulator unsigned long, as the first section does, so the remainder can only be a valid bucket index.

Exercises

  1. Add an erase function that removes a key from its chain and frees the entry.
  2. Store the value as a void * so the table can hold either an int or a string, and test both.
  3. Resize the table from eight to sixteen buckets when the entry count passes six, rehashing every chain.

Questions

A new set of questions in a new order every time. Choose one answer for each, then check.

  1. What does a hash table do when two keys reach the same bucket?

    Answer

    It keeps a chain of entries in that bucket

    Collisions are expected, and the table stores a linked list per bucket and compares the keys along the chain.

  2. Why does the hash accumulate in an unsigned value?

    Answer

    A signed remainder could become a negative index

    A negative accumulator gives a negative remainder, which is not a valid bucket index; the unsigned type keeps it non-negative.

  3. What does the table store for each key?

    Answer

    The pointer that the caller passed in

    This implementation stores the pointer, so the caller must keep the string alive; owning the keys would require a copy.

  4. What happens when the load factor grows too large?

    Answer

    The table resizes and rehashes every entry

    A larger bucket array and a rehash of every entry shorten the chains and keep lookups near constant time.

  5. What does this program print? #include <stdio.h> static unsigned long h(const char*t){unsigned long v=5381;while(*t){v=v*33+(unsigned char)*t;t++;}return v;} int main(void){const char*w[3]={"apple","banana","cherry"};for(int i=0;i<3;i++)printf("%lu ",h(w[i])%8);printf("\n");return 0;}

    Answer

    7 6 2

    The full hashes end in those remainders modulo eight, which is the bucket count.

  6. What does this program print? #include <stdio.h> #include <stdlib.h> #include <string.h> struct E{const char*k;int v;struct E*n;};static struct E*t[8]; static unsigned long h(const char*s){unsigned long v=5381;while(*s){v=v*33+(unsigned char)*s;s++;}return v;} static void put(const char*k,int v){unsigned long i=h(k)%8;struct E*x=malloc(sizeof*x);x->k=k;x->v=v;x->n=t[i];t[i]=x;} static int get(const char*k,int*o){for(struct E*e=t[h(k)%8];e;e=e->n)if(!strcmp(e->k,k)){*o=e->v;return 1;}return 0;} int main(void){int v=0;put("apple",1);put("banana",2);put("cherry",3);if(get("banana",&v))printf("banana: %d\n",v);if(!get("durian",&v))printf("durian: missing\n");return 0;}

    Answer

    banana: 2 / durian: missing

    Banana was stored with value 2, while durian has no entry and the lookup reports the miss.

  7. What bucket counts does this program print? #include <stdio.h> #include <stdlib.h> #include <string.h> struct E{const char*k;struct E*n;};static struct E*t[8]; static unsigned long h(const char*s){unsigned long v=5381;while(*s){v=v*33+(unsigned char)*s;s++;}return v;} int main(void){const char*w[6]={"apple","apricot","avocado","banana","blueberry","cherry"};for(int j=0;j<6;j++){unsigned long i=h(w[j])%8;struct E*e=malloc(sizeof*e);e->k=w[j];e->n=t[i];t[i]=e;}for(int i=0;i<8;i++){int c=0;for(struct E*e=t[i];e;e=e->n)c++;printf("%d ",c);}printf("\n");return 0;}

    Answer

    0 1 2 0 0 0 1 2

    The printed counts are 0, 1, 2, 0, 0, 0, 1 and 2, so five buckets are used.

  8. What index does this signed hash compute? #include <stdio.h> static int h(const char*t){int v=0;while(*t){v=v*31+*t;t++;}return v;} int main(void){char word[3]={(char)0xC3,(char)0xA9,0};printf("%d\n",h(word)%8);return 0;}

    Answer

    -2

    The negative accumulator produces -2 modulo eight, which is not a valid bucket index.

  9. What is the mistake in a hash that keeps a signed int accumulator?

    Answer

    A byte above 127 turns the remainder negative

    Plain char bytes can be negative on x86_64, and the signed remainder can point before the bucket array.

  10. Why does comparing key pointers instead of strings break a lookup?

    Answer

    Equal text may live in different buffers

    Two equal strings can have different addresses, so the lookup must compare the bytes with strcmp.

The code on this page was run with gcc (Alpine 15.2.0) 15.2.0 with the AddressSanitizer runtime on Alpine Linux 3.24.3 (x86_64) in a Docker container.

Article author: Arthur Isaev