C in 100 Seconds: Hash Table Concept

Hash Table — Concept

A hash table maps keys to array indices using a hash function. Instead of searching through every element, you compute an index directly from the key — constant time lookup.

The Hash Function

int hash(char *key) {
  int sum = 0;
  while (*key) {
    sum += *key;
    key++;
  }
  return sum % SIZE;
}

Add up the ASCII values of each character, then take modulo SIZE to get an index between 0 and 9. Simple but effective for demonstration.

Buckets

char *table[SIZE] = {NULL};

The table is just an array. Each position is a "bucket" — either empty (NULL) or holding a key. The hash function decides which bucket a key goes into.

Collisions

When two keys hash to the same index, that is a collision. In this simple version, the new value overwrites the old one — Alice at index 8 gets replaced by Eve. The next episode solves this with chaining.

Lookup

char *lookup(char *key) {
  int idx = hash(key);
  return table[idx];
}

Hash the key, return whatever is at that index. No loop, no search — constant time.

Student Code

Try it yourself: episode48/hashtable.c