C DSA Hash Tables

What is a Hash Table?

Think of a wall of lockers. If you had to open every locker to find your bag, it would take a long time. Instead, a simple rule tells you which locker is yours, so you can go straight to it.

A hash table works the same way.

A hash table stores values in an array. Each place in the array is called a bucket. A hash function uses the value itself (like a name) to calculate which bucket it goes in.

To find the value later, you use the hash function again, and go straight to the right bucket. You do not have to check every item, like in a linear search.

Hash tables are often used when you need to find something fast. For example:

• Your phone finds a contact by name.
• A website checks if a username is already taken.
• A dictionary app finds the meaning of a word.

The Hash Function

A hash function turns a value into a bucket number. Here is a simple hash function for names, for a hash table with 10 buckets:

1. Add together the numbers of all the letters in the name. In C, every character is stored as a number, its ASCII value (see Characters).
2. Use the modulo operator (%) to get the remainder when you divide by 10. The result is always a number from 0 to 9.

For example, for "Liam":

'L' + 'i' + 'a' + 'm' = 76 + 105 + 97 + 109 = 387
387 % 10 = 7

So "Liam" goes in bucket 7. Here is the same hash function in C:

#include <stdio.h>
#define SIZE 10

int hash(char name[]) {
  int sum = 0;
  for (int i = 0; name[i] != '\0'; i++) {
    sum += name[i];
  }
  return sum % SIZE;
}

int main() {
  printf("Liam: %d\n", hash("Liam"));
  printf("Anja: %d\n", hash("Anja"));
  printf("Jenny: %d\n", hash("Jenny"));
  return 0;
}

Liam: 7
Anja: 8
Jenny: 6

The hash function always gives the same bucket for the same name. That is how you find the name again later.

Note: This hash function is easy to understand, but it is not a very good one. Names with the same letters, like "Amy" and "May", always get the same bucket. Real hash tables use hash functions that spread the values out better.

Collisions

Sometimes two different names get the same bucket. For example, "Anja" and "Ali" both get bucket 8. This is called a collision.

A simple way to solve it: if the bucket is already taken, use the next free bucket. After the last bucket, start again at bucket 0. This is called linear probing.

Another common way is to let each bucket hold a linked list of all the names that get that bucket. In this chapter, we use linear probing, because it only needs an array.

Try it! Add names to a hash table with 10 buckets, and see where each name goes:

The yellow bucket is the name you just added. A red bucket was already taken, so the name had to move on.

Create a Hash Table

In C, you can build a hash table for names with an array of strings. An empty string means that the bucket is empty.

The insert() function puts a name in its bucket. The find() function returns the bucket a name is in, or -1 if the name is not in the table:

#include <stdio.h>
#include <string.h>
#define SIZE 10

char table[SIZE][20]; // 10 buckets, each with room for a name

int hash(char name[]) {
  int sum = 0;
  for (int i = 0; name[i] != '\0'; i++) {
    sum += name[i];
  }
  return sum % SIZE;
}

void insert(char name[]) {
  int index = hash(name);
  // If the bucket is taken, try the next one
  while (table[index][0] != '\0') {
    index = (index + 1) % SIZE;
  }
  strcpy(table[index], name);
}

int find(char name[]) {
  int index = hash(name);
  while (table[index][0] != '\0') {
    if (strcmp(table[index], name) == 0) {
      return index;
    }
    index = (index + 1) % SIZE;
  }
  return -1; // An empty bucket: the name is not in the table
}

int main() {
  insert("Liam");
  insert("Anja");
  insert("Jenny");
  insert("Ali");

  printf("Ali is in bucket %d\n", find("Ali"));

  if (find("Tom") == -1) {
    printf("Tom is not in the table\n");
  }

  return 0;
}

Ali is in bucket 9
Tom is not in the table

Run the simulation below to see how the code above works, one step at a time. The yellow bucket is where the code is looking. A red bucket holds another name, so the code moves on:

Example Explained

• table is created outside main(), so it starts filled with zeros. That means every bucket starts as an empty string.
• insert() starts at the bucket from hash(). While the bucket is taken, it moves to the next one. (index + 1) % SIZE goes back to 0 after the last bucket.
• find() starts at the same bucket, and moves on until it finds the name. If it reaches an empty bucket, the name is not in the table.
• "Ali" collides with "Anja" in bucket 8, so it is stored in bucket 9. That is why the program prints Ali is in bucket 9.

Note: This simple hash table must never be completely full. Then there would be no empty bucket, so insert() and find() could keep looking forever. Real hash tables get bigger when they start to get full.

Why Are Hash Tables Fast?

Imagine that you have 1,000 names, and you want to find one of them:

• Linear search may have to check all 1,000 names.
• A binary search tree needs about 10 steps.
• A hash table usually needs just 1 step: calculate the bucket, and look there.

Collisions make it a little slower, because find() must check more than one bucket. To keep collisions rare, a hash table should have many more buckets than names, and the hash function should spread the names out over all the buckets.

Real-Life Example: Phone Contacts

In real programs, a hash table usually stores a key and a value. The key decides the bucket, and the value is stored in the same bucket. Here, the key is a name, and the value is a phone number.

We use an array of structs, so each bucket holds both a name and a phone number:

#include <stdio.h>
#include <string.h>
#define SIZE 10

struct Contact {
  char name[20];
  char phone[20];
};

struct Contact book[SIZE];

int hash(char name[]) {
  int sum = 0;
  for (int i = 0; name[i] != '\0'; i++) {
    sum += name[i];
  }
  return sum % SIZE;
}

void add(char name[], char phone[]) {
  int index = hash(name);
  while (book[index].name[0] != '\0') {
    index = (index + 1) % SIZE;
  }
  strcpy(book[index].name, name);
  strcpy(book[index].phone, phone);
}

int find(char name[]) {
  int index = hash(name);
  while (book[index].name[0] != '\0') {
    if (strcmp(book[index].name, name) == 0) {
      return index;
    }
    index = (index + 1) % SIZE;
  }
  return -1;
}

int main() {
  add("Liam", "98765432");
  add("Anja", "91234567");
  add("Ali", "99887766");

  int index = find("Ali");
  if (index != -1) {
    printf("Ali's phone number is %s\n", book[index].phone);
  }

  return 0;
}

Ali's phone number is 99887766

Here are the buckets after the three add() calls. The other buckets (0 to 6) are empty:

To find Ali's number, find() starts at bucket 8, because hash("Ali") is 8. Bucket 8 holds Anja, so it moves on to bucket 9, where it finds Ali and the phone number. It does not have to look at every contact.

Summary

• A hash table stores values in an array of buckets.
• A hash function turns a key, like a name, into a bucket number.
• When two keys get the same bucket, it is called a collision. A simple solution is to use the next free bucket (linear probing).
• Finding a value usually takes just one step, no matter how much data you have.

Hash tables, binary search trees and binary search are all much faster than checking every item. But how do programmers measure "fast"? Find out in the next chapter!