19th November 2022, 2 min read

Introduction to Hashing

Original post is here eklausmeier.goip.de/blog/2022/11-19-introduction-to-hashing.

In continuation of Simple Exercises for a C Programming Language Course here is a short introduction to hashing ("Streuspeicher"). Original task at hand is: Count how many times a number occurs in a list of numbers? The numbers itself can can vary wildly, while the number of numbers is not usually quite small, say 30,000. That way we cannot just use a simple array and put the numbers as index into the array, as the number values can vastly exceed 30,000. One solution is to use a hash table. This hash table contains the number as key, and the value (of the hash) is the number of occurences. Below simple C program does not actually solve the task at hand, but shows the building block to do that.

Chosing a proper hash function can be a topic of its own. See, for example Hash functions: An empirical comparison -- article by Peter Kankowski. Here we just use the modulus of the number w.r.t. to the maximum size of the hash table. For simplicity, let's take seven slots for our hash table.

Hash lookup is "usually" quite fast, see Hashing Just Random Numbers, i.e., it is O(1). But this can change, if the hash table gets full. The number of occupied slots to free slots in a hash table is called load-factor. If this load-factor approaches one, performance gets worse and worse.

Clearing the hash table is just setting every value to zero.

#define MAXHASH	7

// Hash table for (key,value). key must be nonzero, otherwise thought to be unused.
struct { int key, value; } H[MAXHASH];

void hash_init() {
    int i;
    for (i=0; i<MAXHASH; ++i) { H[i].key = 0; H[i].value = 0; }
}

Inserting and lookup using so called "open-addressing". This means, when a slot in the hash table is occupied, we just look at its neighbor. If the neighbor is occupied as well, then look at the neighbor of the neighbor, and so on.

int hash_insert(int key, int value) {
    int i = key % MAXHASH;
    int k = MAXHASH;

    while (H[i].key != 0) {
        i = (i + 1) % MAXHASH;
        if (--k <= 0) {
            printf("Hash table is full.\n");
            return (-1);
        }
    }
    H[i].key = key;
    H[i].value = value;
    return i;
}


int hash_lookup(int key, int *value) {
    int i = key % MAXHASH;
    int k = MAXHASH;

    while (H[i].key != key) {
        i = (i + 1) % MAXHASH;
        if (--k <= 0) return (-1);
    }
    *value = H[i].value;
    return i;
}

The main program, using above functions, is now:

#include <stdio.h>
#include <string.h>

int main(int argc, char *argv[]) {
    char inp[200], cmd;
    int i, key, value, ret;

    for (;;) {
        fgets(inp,200,stdin);
        if (strstr(inp,"stop") != NULL) break;
        key = 0, value = 0;
        sscanf(inp,"%c %d %d",&cmd,&key,&value);
        if (cmd == 'i')	// insert into hash
            printf("ret=%d\n",hash_insert(key,value));
        else if (cmd == 's') {	// search in hash
            ret = hash_lookup(key,&value);
            printf("ret=%d, value=%d\n",ret,value);
        } else if (cmd == 'p') {	// print entire hash
            for (i=0; i<MAXHASH; ++i)
                printf("\t%d\t%d\t%d\n",i,H[i].key,H[i].value);
        }
    }

    return 0;
}

Running the program:

i 14 14
ret=0
i 15 15
ret=1
i 16 16
ret=2
s 15
ret=1, value=15
p
        0       14      14
        1       15      15
        2       16      16
        3       0       0
        4       0       0
        5       0       0
        6       0       0
s 21
ret=-1, value=0
stop