C Programming: Linear Probing

Welcome to our comprehensive guide on C Programming's Linear Probing! This tutorial is designed to help you understand and master this essential concept, whether you're a beginner or an intermediate learner. Let's dive in!

What is Linear Probing?

Linear Probing is a collision resolution method used in Hash Tables to handle situations where two keys collide (have the same hash value). When a collision occurs, we perform a linear search (hence the name) starting from the next available slot to find an empty location for the colliding keys. 💡 Linear Probing makes hash tables more efficient by reducing the number of collisions.

Understanding Hash Tables

Before we delve into Linear Probing, let's quickly review Hash Tables. A Hash Table is a data structure used to store data using keys. The keys are used to access the data, and the data itself is stored as values in the Hash Table.

Creating a Simple Hash Table

Here's a simple example of a Hash Table implementation in C:

#include <stdio.h>
#include <stdlib.h>

#define SIZE 10

typedef struct {
    int key;
    int value;
    int is_occupied;
} HashTableEntry;

HashTableEntry* create_hash_table() {
    HashTableEntry* table = (HashTableEntry*)malloc(SIZE * sizeof(HashTableEntry));

    for (int i = 0; i < SIZE; i++) {
        table[i].key = -1;
        table[i].value = -1;
        table[i].is_occupied = 0;
    }

    return table;
}

int hash_function(int key, int table_size) {
    return key % table_size;
}

void insert(HashTableEntry* table, int key, int value) {
    int index = hash_function(key, SIZE);

    while (table[index].is_occupied) {
        index = (index + 1) % SIZE;
    }

    table[index].key = key;
    table[index].value = value;
    table[index].is_occupied = 1;
}

int main() {
    HashTableEntry* table = create_hash_table();

    insert(table, 1, 10);
    insert(table, 2, 20);
    insert(table, 3, 30);
    // More insertions...

    // ... and then you can access the values using the keys:
    printf("Value for key 1: %d\n", table[hash_function(1, SIZE)].value);

    return 0;
}

📝 Note: This simple implementation doesn't handle collisions yet. We'll modify it to use Linear Probing shortly.

Implementing Linear Probing

Now, let's enhance our Hash Table implementation to handle collisions using Linear Probing:

// Add this function to handle collisions using Linear Probing:
int linear_probing(int index, int table_size) {
    return (index + 1) % table_size;
}

void insert(HashTableEntry* table, int key, int value) {
    int index = hash_function(key, SIZE);

    while (table[index].is_occupied) {
        index = linear_probing(index, SIZE);

        if (table[index].key == key) {
            // Key already exists, update the value:
            table[index].value = value;
            return;
        }
    }

    table[index].key = key;
    table[index].value = value;
    table[index].is_occupied = 1;
}

Now, our Hash Table can handle collisions by performing Linear Probing when needed!

Quiz Time!

Keep exploring, and happy coding! 🚀