CODEBHAVYA โ€ข ADS LEVEL 18

#๏ธโƒฃ Hashing and Hash Tables

Convert keys into table locations and master collisions using separate chaining, linear probing, quadratic probing, double hashing, tombstones and dynamic rehashing.

LEARNING GOALS

๐ŸŽฏ Learning Objectives

  • Explain hashing, buckets, collisions, load factor and clustering.
  • Design division, multiplication, folding and string hash functions.
  • Insert, search and delete using separate chaining.
  • Trace linear probing, quadratic probing and double hashing.
  • Use tombstones correctly during open-address deletion.
  • Explain resizing and rehashing when the load factor grows.
  • Compare expected, worst-case and amortized costs.
  • Recognize universal, perfect, cuckoo and Robin Hood hashing.
DIRECT ACCESS THROUGH A FUNCTION

๐Ÿงญ 1. Hashing Fundamentals

A hash table stores a key in a bucket selected by a hash function. Instead of comparing against many sorted elements, it calculates where the key should be and examines only that location or a short collision path.

1

Read Key

Accept an integer, string or record key.

2

Compute Hash

Transform the key into an integer hash code.

3

Select Bucket

Compress the hash code into the table range.

4

Resolve Collision

Use a chain or a probe sequence when occupied.

Bucket

A table location that stores an entry or begins a chain.

Collision

Different keys map to the same initial bucket.

Load factor

ฮฑ = n/m, where n is keys and m is buckets.

Expected access

O(1) with good distribution and controlled load.

Worst case: Hash tables can degrade to O(n) when many keys collide. Constant-time performance is expected, not an unconditional guarantee.
DISTRIBUTE KEYS UNIFORMLY

๐Ÿงฎ 2. Hash Functions

Method Formula or idea Important note
Division h(k) = k mod m Choose m carefully, commonly a prime.
Multiplication โŒŠm(kA mod 1)โŒ‹ Less sensitive to the table size.
Mid-square Square the key and take middle digits Middle digits depend on several input digits.
Folding Split the key and add its parts Useful for long numeric identifiers.
Polynomial string h = (h ร— p + character) mod m Character order affects the result.
Universal Randomly choose from a hash family Limits adversarial collision patterns.

Good Hash Function

Fast, deterministic, uses the whole key and spreads expected inputs uniformly.

Poor Hash Function

Ignores important key variation or repeatedly maps common inputs into a few buckets.

Integer examples with m = 11: h(27) = 5, h(38) = 5 and h(49) = 5. These keys collide because each differs by 11.
COLLISIONS ARE NORMAL

๐Ÿ’ฅ 3. Collision Resolution

When the key universe is larger than the table, collisions are unavoidable. Correct tables preserve every colliding key and still follow a reproducible search path.

Separate Chaining

Every bucket owns a linked list or another secondary container. Colliding keys stay together.

Open Addressing

All keys stay inside the array. A probe formula generates alternative buckets.

Linear probing

(h(k) + i) mod m

Quadratic probing

(h(k) + cโ‚i + cโ‚‚iยฒ) mod m

Double hashing

(hโ‚(k) + i ร— hโ‚‚(k)) mod m

Probe requirement

Search repeats the exact insertion sequence.

Golden rule: Never stop an open-address search at a deleted bucket. Stop only at the key, a truly empty bucket, or after a full probe cycle.
ONE LIST PER BUCKET

๐Ÿ”— 4. Separate Chaining

Separate chaining stores each entry in the linked list selected by h(key). Its load factor may exceed 1 because the number of records is not limited by the bucket count.

Insert, Search and Delete

  1. Calculate index = h(key).
  2. Search the selected chain for the key.
  3. Insert a new node if the key is absent.
  4. Search compares nodes until the key or list end.
  5. Delete reconnects the predecessor to the removed nodeโ€™s successor.
Expected chain length: approximately ฮฑ under simple uniform hashing. Chaining remains practical near or slightly above ฮฑ = 1.
๐Ÿ’ป Complete C Program โ€” Separate Chaining View program 
#include <stdio.h>
#include <stdlib.h>

#define SIZE 11

typedef struct Node {
    int key;
    struct Node *next;
} Node;

Node *table[SIZE];

int hashKey(int key) {
    int value = key % SIZE; /* hash compute */
    return value < 0 ? value + SIZE : value;
}

void initialize(void) {
    for (int i = 0; i < SIZE; i++)
        table[i] = NULL; /* chain create table */
}

Node *searchKey(int key) {
    int index = hashKey(key); /* chain search hash */
    Node *current = table[index];

    while (current != NULL) { /* chain search loop */
        if (current->key == key)
            return current; /* chain search found */

        current = current->next;
    }

    return NULL; /* chain search miss */
}

int insertKey(int key) {
    int index = hashKey(key); /* chain insert hash */

    for (Node *current = table[index];
         current != NULL;
         current = current->next) {

        /* chain insert check */

        if (current->key == key)
            return 0;
    }

    Node *node = malloc(sizeof(Node));

    if (node == NULL)
        exit(EXIT_FAILURE);

    node->key = key;
    node->next = table[index];
    table[index] = node; /* chain insert link */

    return 1;
}

int deleteKey(int key) {
    int index = hashKey(key); /* chain delete hash */
    Node *current = table[index];
    Node *previous = NULL;

    while (current != NULL) { /* chain delete loop */
        if (current->key == key) {
            if (previous == NULL)
                table[index] = current->next;
            else
                previous->next = current->next;

            free(current); /* chain delete remove */
            return 1;
        }

        previous = current;
        current = current->next;
    }

    return 0; /* chain delete miss */
}

void display(void) {
    for (int i = 0; i < SIZE; i++) {
        printf("%2d:", i);

        for (Node *current = table[i];
             current != NULL;
             current = current->next) {

            printf(" -> %d", current->key);
        }

        printf("\n");
    }
}

void destroy(void) {
    for (int i = 0; i < SIZE; i++) {
        Node *current = table[i];

        while (current != NULL) {
            Node *next = current->next;
            free(current);
            current = next;
        }
    }
}

int main(void) {
    int values[] = {
        27, 18, 29, 28, 39, 13, 16
    };

    int count =
        sizeof(values) / sizeof(values[0]);

    initialize();

    for (int i = 0; i < count; i++)
        insertKey(values[i]); /* chain build */

    display();

    printf(
        "Search 39: %s\n",
        searchKey(39) ? "Found" : "Not Found"
    );

    printf(
        "Delete 28: %s\n",
        deleteKey(28) ? "Deleted" : "Not Found"
    );

    display();
    destroy();

    return 0;
}

Sample Input

27 18 29 28 39 13 16
Search: 39
Delete: 28

Key Result

Search 39: Found
Delete 28: Deleted
KEEP EVERY KEY IN THE ARRAY

๐Ÿ“ 5. Open Addressing

Open addressing generates a sequence of candidate buckets. It has good cache locality, but performance drops sharply as the table becomes crowded.

Method Probe Main strength Main issue
Linear h + i Simple and cache-friendly Primary clustering
Quadratic h + iยฒ Reduces primary clustering Secondary clustering; may not visit every bucket
Double hashing hโ‚ + iยทhโ‚‚ Best distribution of the three Needs a valid non-zero step relatively prime to m

Open-Address Search

  1. For i = 0 to m โˆ’ 1, compute the next probe index.
  2. If the slot contains the key, return found.
  3. If the slot was never used, return not found.
  4. If occupied by another key or marked deleted, continue probing.
  5. After m probes, report not found.
๐Ÿ’ป Complete C Program โ€” Linear, Quadratic and Double Hashing View program 
#include <stdio.h>

#define SIZE 11
#define EMPTY 0
#define OCCUPIED 1
#define DELETED 2

typedef enum {
    LINEAR,
    QUADRATIC,
    DOUBLE_HASHING
} Strategy;

typedef struct {
    int key;
    int state;
} Slot;

Slot table[SIZE];

int positiveMod(int value, int modulus) {
    int result = value % modulus;

    return result < 0
        ? result + modulus
        : result;
}

int hashOne(int key) {
    return positiveMod(
        key,
        SIZE
    ); /* hash compute */
}

int hashTwo(int key) {
    return 1 + positiveMod(
        key,
        SIZE - 1
    ); /* open second hash */
}

int probeIndex(
    int key,
    int attempt,
    Strategy strategy
) {
    int first = hashOne(key);

    if (strategy == LINEAR)
        return (
            first + attempt
        ) % SIZE; /* open linear probe */

    if (strategy == QUADRATIC)
        return (
            first + attempt * attempt
        ) % SIZE; /* open quadratic probe */

    return (
        first + attempt * hashTwo(key)
    ) % SIZE; /* open double probe */
}

void initialize(void) {
    for (int i = 0; i < SIZE; i++)
        table[i].state =
            EMPTY; /* open create table */
}

int searchKey(
    int key,
    Strategy strategy
) {
    for (
        int attempt = 0;
        attempt < SIZE;
        attempt++
    ) { /* open search loop */

        int index = probeIndex(
            key,
            attempt,
            strategy
        );

        if (table[index].state == EMPTY)
            return -1; /* open search empty */

        if (
            table[index].state == OCCUPIED &&
            table[index].key == key
        )
            return index; /* open search found */
    }

    return -1; /* open search miss */
}

int insertKey(
    int key,
    Strategy strategy
) {
    int firstDeleted = -1;

    for (
        int attempt = 0;
        attempt < SIZE;
        attempt++
    ) { /* open insert loop */

        int index = probeIndex(
            key,
            attempt,
            strategy
        );

        if (
            table[index].state == OCCUPIED &&
            table[index].key == key
        )
            return 0;

        if (
            table[index].state == DELETED &&
            firstDeleted == -1
        )
            firstDeleted =
                index; /* open remember tombstone */

        if (table[index].state == EMPTY) {
            if (firstDeleted != -1)
                index = firstDeleted;

            table[index].key = key;

            table[index].state =
                OCCUPIED; /* open insert store */

            return 1;
        }
    }

    if (firstDeleted != -1) {
        table[firstDeleted].key = key;

        table[firstDeleted].state =
            OCCUPIED; /* open insert tombstone */

        return 1;
    }

    return 0; /* open insert full */
}

int deleteKey(
    int key,
    Strategy strategy
) {
    int index =
        searchKey(
            key,
            strategy
        ); /* open delete search */

    if (index == -1)
        return 0;

    table[index].state =
        DELETED; /* open delete tombstone */

    return 1;
}

void display(void) {
    for (int i = 0; i < SIZE; i++) {
        printf("%2d: ", i);

        if (table[i].state == OCCUPIED)
            printf("%d", table[i].key);
        else if (table[i].state == DELETED)
            printf("DELETED");
        else
            printf("EMPTY");

        printf("\n");
    }
}

int main(void) {
    int values[] = {
        27, 18, 29, 28, 39, 13, 16
    };

    int count =
        sizeof(values) / sizeof(values[0]);

    Strategy strategy =
        DOUBLE_HASHING;

    initialize();

    for (int i = 0; i < count; i++)
        insertKey(
            values[i],
            strategy
        ); /* open build */

    display();

    printf(
        "Search 39: index %d\n",
        searchKey(39, strategy)
    );

    printf(
        "Delete 28: %s\n",
        deleteKey(28, strategy)
            ? "Deleted"
            : "Not Found"
    );

    display();

    return 0;
}

Sample Input

Table size: 11
Keys: 27 18 29 28 39 13 16
Strategy: Double Hashing

Key Result

Search 39: Found
Delete 28: Deleted
Deleted slot remains a tombstone.
CONTROL THE LOAD FACTOR

โ™ป๏ธ 6. Deletion, Tombstones and Rehashing

True empty slot

No key has ever occupied it; an unsuccessful search may stop.

Tombstone

A key was deleted; search must continue through it.

Insertion reuse

Remember the first tombstone, but first ensure the key is not later in the probe sequence.

Rehash

Create a larger table and insert every live key using the new modulus.

Dynamic Rehashing

  1. Monitor the load factor after insertion or deletion.
  2. When the threshold is crossed, choose a larger table sizeโ€”commonly the next prime above 2m.
  3. Create a completely empty new table.
  4. Reinsert each occupied entry; never copy old indices or tombstones directly.
  5. Replace the old table only after all live entries are stored.
Typical policy: Resize open-address tables near ฮฑ = 0.5 to 0.75. The precise threshold depends on the probe method and performance target.
MODERN HASHING IDEAS

๐Ÿš€ 7. Advanced Hashing Techniques

Cuckoo Hashing

Each key has two candidate positions. Insertion may evict and relocate existing keys; lookup checks only two places.

Robin Hood Hashing

During probing, keys with longer probe distances can take slots from keys with shorter distances.

Perfect Hashing

A static known key set is arranged to guarantee O(1) worst-case lookup without collisions.

Universal Hashing

A function is randomly chosen from a family to reduce the effect of hostile input patterns.

Consistent Hashing

Distributed keys move only a limited amount when servers join or leave.

Bloom Filter

A compact probabilistic structure can reject definite absences, but may report false positives.

CHOOSE THE RIGHT POLICY

โš–๏ธ 8. Comparison

Method Storage Deletion Cache locality Recommended load
Separate chaining Table plus nodes Direct unlink Lower May exceed 1
Linear probing Array only Tombstone/backshift Excellent Usually below 0.7
Quadratic probing Array only Tombstone Good Often below 0.5
Double hashing Array only Tombstone Good Usually below 0.7
Cuckoo hashing Two candidate tables/locations Simple lookup removal Good Resize on insertion cycle
INTERACTIVE ALGORITHM VISUALIZATION

๐ŸŽฌ 9. Premium Hash Table Visualizer

Choose a collision strategy and operation, then follow hash calculations, collisions, chain movement, probes, tombstones and rehashing step by step.

CodeBhavya Code Bhavya
Choose a method and operation, verify the input and click Load Visualizer.
SELECTABLE C PROGRAM TRACER

๐Ÿ” 10. Program Tracing โ€” Hashing

Select a strategy and operation. The matching complete C source appears with line numbers, live variables and the evolving hash table.

Select a program and operation, then click Load Program Tracer.
PERFORMANCE SUMMARY

โฑ๏ธ 11. Complexity Analysis

Operation Expected Worst case Reason
Search O(1) O(n) Short chain/probe versus all keys colliding
Insert O(1) O(n) Available location versus long collision path
Delete O(1) O(n) Locate then unlink or mark
Rehash O(n) O(nยฒ) with pathological insertion Every live key must be reinserted
Amortized resizing: If table capacity grows geometrically, occasional O(n) rehashes still give O(1) amortized insertion under standard assumptions.
WHERE HASHING IS USED

๐Ÿงฉ 12. Applications

Compiler Symbol Tables

Map identifiers to type, scope and memory information.

Database Hash Indexes

Accelerate equality queries and hash joins.

Caches and Dictionaries

Associate request keys or words with stored values.

Duplicate Detection

Track previously observed items in expected constant time.

Password Storage

Use dedicated slow salted cryptographic password hashesโ€”not ordinary table hashes.

Distributed Storage

Consistent hashing distributes keys across changing servers.

DEBUGGING CHECKLIST

โš ๏ธ 13. Common Mistakes

Using negative indices

Normalize a negative remainder into the range 0 to m โˆ’ 1.

Stopping at a tombstone

A deleted marker does not terminate an open-address search.

Copying positions during resize

Changing m changes every compressed hash; all entries must be reinserted.

Allowing excessive load

Long chains and probe clusters destroy expected constant time.

Invalid double-hash step

A zero or non-coprime step can prevent a probe sequence from reaching the table.

Confusing table and password hashes

Fast non-cryptographic hashes must not protect passwords.

CHECK YOUR UNDERSTANDING

โœ๏ธ 14. Practice Problems

Solve each problem first. Use Hint only when required, then open Show Answer to verify your reasoning.

1. What is a collision?

2. For m = 11, where does key 38 initially hash?

3. What does ฮฑ = n/m represent?

4. Can chaining have ฮฑ greater than 1?

5. Can open addressing have ฮฑ greater than 1?

6. What clustering occurs in linear probing?

7. Why must search use the same probe formula as insertion?

8. What is a tombstone?

9. Why cannot search stop at a tombstone?

10. What must happen when table size changes?

11. Which method usually has the strongest cache locality?

12. What problem does quadratic probing reduce?

13. What must be true about a double-hash step?

14. What is the expected search time of a controlled hash table?

15. What is the worst-case search time?

16. Which method checks two possible locations during lookup?

17. Which hashing technique supports changing server sets?

18. Can a Bloom filter produce false negatives?

19. Should a fast table hash store passwords?

20. When is perfect hashing most suitable?

QUICK RECALL

๐Ÿ“ 15. Quick Revision

  • A hash function maps a key to a bucket; collisions are unavoidable for large key universes.
  • Load factor ฮฑ = n/m strongly affects performance.
  • Separate chaining stores colliding keys outside the main array.
  • Open addressing keeps all keys in the array and follows a probe sequence.
  • Linear probing suffers primary clustering; quadratic probing reduces it.
  • Double hashing uses a key-dependent non-zero probe step.
  • Tombstones preserve search paths after deletion.
  • Resizing requires reinserting all live keys with the new modulus.
  • Expected operations are O(1); the worst case is O(n).
  • Cryptographic/password hashes and hash-table functions serve different purposes.