🧠 Building a Simple Hash Table in C (with Linear Probing)

Hash tables are among the most efficient data structures when it comes to fast lookup, insert, and delete. In this article, we’ll implement a simple hash table in C — from scratch — using open addressing with linear probing.

We’ll cover:

Creating key-value pairs using a struct
A simple string hash function
Collision resolution with linear probing
Insert, search, and delete operations
A full working demo with explanation

🧱 Data Structure Design

We define a structure HashItem to store each key-value pair in the table.

#define TABLE_SIZE 100

typedef struct {
    char* key;
    int value;
    int isOccupied; // 0 = empty, 1 = occupied, -1 = deleted

} HashItem;

HashItem table[TABLE_SIZE]; // global hash table

Here:

key is a string (char pointer)
value is an integer
isOccupied tracks the slot status:
- 0: empty
- 1: occupied
- -1: deleted (tombstone marker)

🔑 Hash Function

A basic string hash function that spreads keys reasonably well.

unsigned int hash(const char* key) {
    unsigned int hash = 0;
    while (*key)

    hash = (hash * 31) + *key++;  // simple hash logic

    return hash % TABLE_SIZE;

}

This gives us an index between 0 and TABLE_SIZE - 1.

🔧 Insertion Logic

Handles collisions using linear probing.

void insert(const char* key, int value) {
    int index = hash(key);
    int originalIndex = index;

    while (table[index].isOccupied == 1 && strcmp(table[index].key, key) != 0) {

    index = (index + 1) % TABLE_SIZE;

        if (index == originalIndex) {

        printf("Hash table full!\n");

            return;

}
}

    if (table[index].isOccupied != 1) {

    table[index].key = strdup(key);  // copy key to heap
    table[index].value = value;
    table[index].isOccupied = 1;
} else {
    table[index].value = value; // update if key exists
}

}

⚠️ Notes:

strdup() allocates memory for the key.
If the key already exists, it updates the value.

🔍 Search Function

int get(const char* key) {
    int index = hash(key);
    int originalIndex = index;

    while (table[index].isOccupied != 0) {
        if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0)
            return table[index].value;

    index = (index + 1) % TABLE_SIZE;

        if (index == originalIndex)
            break;

    return -1; // not found

}

This returns the value if found, or -1 if not present.

🗑️ Deletion

void delete(const char* key) {
    int index = hash(key);
    int originalIndex = index;

    while (table[index].isOccupied != 0) {
        if (table[index].isOccupied == 1 && strcmp(table[index].key, key) == 0) {
            free(table[index].key);  // deallocate memory

        table[index].key = NULL;
        table[index].isOccupied = -1;
        printf("Deleted '%s'\n", key);

            return;

    }

    index = (index + 1) % TABLE_SIZE;

        if (index == originalIndex) 
            break;

}

printf("Key '%s' not found.\n", key);

}

We use -1 as a deleted marker so we can continue probing during future searches.

🧪 Demo

int main() {

insert("apple", 10);
insert("banana", 20);
insert("orange", 30);
insert("grape", 40);

printf("apple: %d\n", get("apple"));
printf("banana: %d\n", get("banana"));

delete("banana");

printf("banana after delete: %d\n", get("banana"));

insert("banana", 50); // reinserting
printf("banana new: %d\n", get("banana"));

    return 0;

}

📤 Output

apple: 10
banana: 20
Deleted 'banana'
banana after delete: -1
banana new: 50

✅ Summary

We implemented a simple fixed-size hash table in C using:

A basic hash function for strings
Linear probing for collision resolution
Markers for deleted slots
Manual memory management (malloc, strdup, free)

This is perfect for learning how hash maps work under the hood.

🚀 Bonus Ideas

Implement dynamic resizing (rehashing)
Use double hashing or quadratic probing
Store generic values using void*
Add load factor thresholds

Swagata Mandal @hacknova

🧠 Building a Simple Hash Table in C (with Linear Probing)

Comments 0 total