Hashing

Simulation Speed:1x

Collision Handling

Collisions occur when two different keys hash to the same index. There are several strategies to handle collisions effectively.

Linear Probing

Search for the next empty slot sequentially until one is found.

// Linear Probing
int insert(HashTable* table, int key, int value) {
    int index = hash(key);
    while (table[index].occupied) {
        index = (index + 1) % table->size;
    }
    table[index].key = key;
    table[index].value = value;
    table[index].occupied = true;
    return index;
}

Pros: Simple, good cache performance
Cons: Clustering, secondary collisions

Quadratic Probing

Try slots at quadratic intervals using P(x) = (x² + x)/2 with a power-of-two table size.

// Quadratic Probing
int insert(HashTable* table, int key, int value) {
    int index = hash(key);
    int i = 0;
    while (table[index].occupied) {
        i++;
        int offset = (i * i + i) / 2;
        index = (hash(key) + offset) % table->size;
    }
    table[index].key = key;
    table[index].value = value;
    table[index].occupied = true;
    return index;
}

Pros: Complete coverage with power-of-two table size
Cons: Table size must be power of two

Double Hashing

Use a second hash function to determine the probe interval.

// Double Hashing
int insert(HashTable* table, int key, int value) {
    int index = hash1(key);
    int step = hash2(key);
    while (table[index].occupied) {
        index = (index + step) % table->size;
    }
    table[index].key = key;
    table[index].value = value;
    table[index].occupied = true;
    return index;
}

Pros: Better distribution
Cons: More computation needed

Chaining

Each slot contains a linked list of elements.

// Chaining
struct Node {
    int key;
    int value;
    struct Node* next;
};

void insert(HashTable* table, int key, int value) {
    int index = hash(key);
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = NULL;
    
    if (table[index] == NULL) {
        table[index] = newNode;
    } else {
        struct Node* current = table[index];
        while (current->next != NULL) {
            current = current->next;
        }
        current->next = newNode;
    }
}

Pros: Simple, works well with high load
Cons: Extra memory for links

Load Factor

The load factor (α) is the ratio of occupied slots to total slots. It affects collision probability and performance.

Load Factor (α) = n/m
where:
n = number of stored elements
m = table size

Typical resize threshold: α > 0.7