Open Addressing in Hashing in C: Explanation and Example

Open addressing in hashing in C is a technique to handle collisions by finding another empty slot within the hash table itself. Instead of using linked lists, it searches for the next available position using a probing sequence like linear probing, storing all elements directly in the array.

How It Works

Imagine you have a row of mailboxes (a hash table) and you want to put letters (data) into them based on their address (hash value). Sometimes, two letters want the same mailbox, causing a collision. Open addressing solves this by checking the next mailbox in line until it finds an empty one.

This process is called probing. The simplest way is linear probing, where you move one step at a time to the next slot. If the first slot is full, check the second, then the third, and so on, wrapping around if needed. This way, all data stays inside the original array without extra linked lists.

Example

This C program shows open addressing with linear probing to insert and search integers in a hash table.

c

#include <stdio.h>
#define TABLE_SIZE 7

int hash(int key) {
    return key % TABLE_SIZE;
}

void insert(int table[], int key) {
    int index = hash(key);
    int start_index = index;
    while (table[index] != -1) {
        index = (index + 1) % TABLE_SIZE;
        if (index == start_index) {
            printf("Hash table is full!\n");
            return;
        }
    }
    table[index] = key;
}

int search(int table[], int key) {
    int index = hash(key);
    int start_index = index;
    while (table[index] != -1) {
        if (table[index] == key) {
            return index;
        }
        index = (index + 1) % TABLE_SIZE;
        if (index == start_index) {
            break;
        }
    }
    return -1;
}

int main() {
    int hash_table[TABLE_SIZE];
    for (int i = 0; i < TABLE_SIZE; i++) {
        hash_table[i] = -1; // -1 means empty slot
    }

    insert(hash_table, 10);
    insert(hash_table, 20);
    insert(hash_table, 15);
    insert(hash_table, 7);

    int key = 15;
    int pos = search(hash_table, key);
    if (pos != -1) {
        printf("Key %d found at index %d\n", key, pos);
    } else {
        printf("Key %d not found\n", key);
    }

    return 0;
}

Output

Key 15 found at index 1

When to Use

Open addressing is useful when you want a simple hash table without extra memory for linked lists. It works well when the table is not too full, usually less than 70% full, to keep searching fast.

Use it in systems with limited memory or when you want fast lookups and insertions with predictable memory use. Examples include caching, symbol tables in compilers, and simple databases.

Key Points

• Open addressing stores all data inside the hash table array.
• Collisions are resolved by probing for the next free slot.
• Linear probing is the simplest probing method.
• Performance drops if the table gets too full.
• Good for memory-limited environments and fast access.

Key Takeaways

Open addressing handles collisions by searching for empty slots within the hash table array.

Linear probing checks the next slot one by one until it finds a free space.

It avoids extra memory use by not using linked lists for collisions.

Best used when the hash table load is low to maintain fast operations.

Common in caching, symbol tables, and simple in-memory databases.