October 17, 2026

Hashing in C — Complete Data Structures and Algorithms Tutorial with Examples

SEO Title: Hashing in C: Hash Functions, Hash Tables, Collision Handling, Linear Probing & Chaining

Meta Description: Learn hashing in C with practical examples, hash functions, hash tables, collision resolution, linear probing, chaining, C programs, outputs, complexity analysis, and real-world applications.

Suggested URL Slug: /hashing-in-c/

Introduction to Hashing

Hashing is an important technique in Data Structures and Algorithms (DSA) that helps us store and retrieve data efficiently.

Imagine you have 10,000 student records. If you store them in an ordinary array without any indexing strategy, finding a particular student may require checking many records one by one.

Hashing provides a way to calculate where a value should be stored using a hash function. Instead of searching through every element, we can often access the required location directly.

Hashing is commonly used in:

• Dictionaries and key-value storage

• Database indexing

• Caches and lookup tables

• Symbol tables in compilers

• Duplicate detection

• Fast data retrieval

1. Introduction to Hashing

Hashing is the process of converting a key into an index using a mathematical function called a hash function.

For example, suppose we have a hash table containing 10 buckets, indexed from 0 to 9.

We can use the following hash function:

index = key % 10;

Here, % is the modulo operator, which returns the remainder after division.

For key 23:

index = 23 % 10
index = 3

Therefore, key 23 can be stored at index 3.

For key 47:

index = 47 % 10
index = 7

The key 47 can be stored at index 7.

Hashing Example

Suppose we insert these keys:

23, 34, 45, 56, 67

Using key % 10, their locations are:

Each key maps to a location in the hash table.

Important: Different keys can produce the same index. This situation is called a collision, and we will learn how to handle it later.

2. Hash Functions

A hash function takes a key as input and produces a hash value, which is converted into a valid table index.

For a table of size TABLE_SIZE, a hash function should return an index from 0 to TABLE_SIZE - 1.

Properties of a Good Hash Function

A good hash function should:

1. Be fast to calculate.

2. Always produce a valid table index.

3. Distribute keys reasonably uniformly.

4. Reduce collisions for the expected input data.

5. Produce the same result for the same key when the function and table configuration remain unchanged.

A hash function cannot guarantee zero collisions for arbitrary keys when the number of possible keys exceeds the number of table slots.

Common Hashing Methods

1. Division Method

Uses the remainder after division.

index = key % TABLE_SIZE;

2. Multiplication Method

Multiplies the key by a chosen constant, then uses the fractional part to calculate an index. This method is useful in some hashing designs but requires more careful implementation.

3. Mid-Square Method

Squares the key and extracts selected middle digits to determine the hash value.

4. Folding Method

Splits a key into smaller sections, combines those sections, and converts the result into a table index.

For this tutorial, we will primarily use the division method because it is easy to understand and implement in C.

C Program: Implementing a Hash Function

#include 

#define TABLE_SIZE 10

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

int main(void) {
    int key = 23;
    int index = hashFunction(key);

    printf("Key: %d\n", key);
    printf("Hash index: %d\n", index);

    return 0;
}

Output:

Key: 23
Hash index: 3

How It Works

• TABLE_SIZE defines the number of buckets.

• hashFunction() calculates the remainder of the key divided by 10.

• The returned index identifies the bucket where the key can be stored.

This example assumes a non-negative key. For negative keys, C's remainder operator can return a negative result, so the index must be normalized before using it as an array index.

3. Hash Tables

A hash table is a data structure that stores keys, or key-value pairs, in buckets selected by a hash function.

In C, a simple hash table can be represented using an array.

For example:

#define TABLE_SIZE 10

int hashTable[TABLE_SIZE];

This creates an array with 10 integer elements.

However, an ordinary integer array needs a way to distinguish an unused bucket from a bucket containing a valid key. In the next example, we will use a separate occupied array.

C Program: Inserting and Searching in a Basic Hash Table

This program uses linear probing to resolve collisions. The same technique is explained in detail in Topic 5.

#include 

#define TABLE_SIZE 10

int hashTable[TABLE_SIZE];
int occupied[TABLE_SIZE] = {0};

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

int insert(int key) {
    int index = hashFunction(key);

    for (int i = 0; i < TABLE_SIZE; i++) {
        int pos = (index + i) % TABLE_SIZE;

        if (!occupied[pos]) {
            hashTable[pos] = key;
            occupied[pos] = 1;
            return pos;
        }

        if (hashTable[pos] == key) {
            return pos;
        }
    }

    return -1;
}

int search(int key) {
    int index = hashFunction(key);

    for (int i = 0; i < TABLE_SIZE; i++) {
        int pos = (index + i) % TABLE_SIZE;

        if (!occupied[pos]) {
            return -1;
        }

        if (hashTable[pos] == key) {
            return pos;
        }
    }

    return -1;
}

int main(void) {
    int keys[] = {23, 34, 45};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) {
        insert(keys[i]);
    }

    int key = 34;
    int index = search(key);

    if (index != -1) {
        printf("%d found at index %d\n", key, index);
    } else {
        printf("%d not found\n", key);
    }

    return 0;
}

Output:

34 found at index 4

Explanation

• The hash function calculates the initial bucket.

• insert() stores the key in an available bucket.

• If a bucket is occupied, linear probing checks subsequent buckets.

• search() follows the same probing sequence to find a key.

• The occupied array tracks which buckets contain keys, so a stored value of 0 is supported.

This simple implementation does not include deletion. Deleting elements from an open-addressed hash table requires special handling, usually with a deleted-marker state, so that searches do not stop prematurely.

4. Collision Handling

A collision occurs when two different keys map to the same hash-table index.

Consider this hash function:

index = key % 10;

Now insert the keys 23 and 33.

23 % 10 = 3
33 % 10 = 3

Both keys map to index 3. If the table uses only one slot per index, we need a collision-resolution technique.

Common Collision-Handling Techniques

1. Separate Chaining

Each bucket stores a collection of keys, commonly represented by a linked list.

2. Linear Probing

If the calculated slot is occupied, check the next slot until an available slot is found.

3. Quadratic Probing

Check positions using increasing quadratic offsets rather than checking only the next slot.

4. Double Hashing

Use a second hash function to calculate the step size for probing.

Example of a Collision

Suppose the table size is 10 and we insert 23, 33, and 43.

All three keys have the same initial hash index:

23 % 10 = 3
33 % 10 = 3
43 % 10 = 3

With linear probing, the placement can be:

Index 3: 23
Index 4: 33
Index 5: 43

With chaining, the bucket at index 3 can contain:

Index 3: 23 -> 33 -> 43 -> NULL

Both methods resolve the collision, but they organize data differently.

5. Linear Probing

Linear probing is an open-addressing collision-resolution technique. When a key's calculated bucket is already occupied, the algorithm checks the next bucket.

The probing formula is:

pos = (hashIndex + i) % TABLE_SIZE;

Here:

• hashIndex is the initial index.

• i is the probe number, starting at 0.

• TABLE_SIZE allows the search to wrap around to the beginning of the array.

Example

Insert 23, 33, and 43 into a table of size 10.

Key 23 -> Index 3
Key 33 -> Index 3 is occupied -> Index 4
Key 43 -> Index 3 is occupied -> Index 4 is occupied -> Index 5

The final table is:

Index 0: Empty
Index 1: Empty
Index 2: Empty
Index 3: 23
Index 4: 33
Index 5: 43
Index 6: Empty
Index 7: Empty
Index 8: Empty
Index 9: Empty

C Program: Linear Probing

#include 

#define TABLE_SIZE 10

int table[TABLE_SIZE];
int occupied[TABLE_SIZE] = {0};

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

int insert(int key) {
    int index = hashFunction(key);

    for (int i = 0; i < TABLE_SIZE; i++) {
        int pos = (index + i) % TABLE_SIZE;

        if (!occupied[pos]) {
            table[pos] = key;
            occupied[pos] = 1;
            return pos;
        }

        if (table[pos] == key) {
            return pos;
        }
    }

    return -1;
}

void display(void) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        if (occupied[i]) {
            printf("Index %d: %d\n", i, table[i]);
        } else {
            printf("Index %d: Empty\n", i);
        }
    }
}

int main(void) {
    int keys[] = {23, 33, 43};
    int n = sizeof(keys) / sizeof(keys[0]);

    for (int i = 0; i < n; i++) {
        insert(keys[i]);
    }

    display();

    return 0;
}

Output:

Index 0: Empty
Index 1: Empty
Index 2: Empty
Index 3: 23
Index 4: 33
Index 5: 43
Index 6: Empty
Index 7: Empty
Index 8: Empty
Index 9: Empty

Advantages of Linear Probing

• Simple to implement.

• Does not require linked-list nodes or dynamic allocation.

• Often has good cache performance because entries are stored in an array.

Disadvantages of Linear Probing

• Can suffer from primary clustering, where groups of occupied slots grow and attract more insertions.

• Performance degrades as the table becomes crowded.

• Deletion needs special handling so that searches can continue across previously occupied positions.

Time Complexity

Average-case performance assumes a suitable hash function and a reasonably low load factor. The worst case occurs when many probes are required.

6. Chaining

Separate chaining resolves collisions by storing multiple keys in the same bucket, usually using a linked list.

Each hash-table bucket points to the first node of its linked list.

For example, if 23, 33, and 43 all map to index 3, the bucket can store:

Bucket 3 -> 23 -> 33 -> 43 -> NULL

Unlike linear probing, chaining does not require every key to occupy a separate array slot.

C Program: Hash Table Using Chaining

#include 
#include 

#define TABLE_SIZE 10

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

struct Node *table[TABLE_SIZE] = {NULL};

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

void insert(int key) {
    int index = hashFunction(key);

    struct Node *current = table[index];

    while (current != NULL) {
        if (current->key == key) {
            return;  // Avoid duplicate keys
        }
        current = current->next;
    }

    struct Node *newNode = malloc(sizeof(struct Node));

    if (newNode == NULL) {
        printf("Memory allocation failed\n");
        return;
    }

    newNode->key = key;
    newNode->next = table[index];
    table[index] = newNode;
}

int search(int key) {
    int index = hashFunction(key);
    struct Node *current = table[index];

    while (current != NULL) {
        if (current->key == key) {
            return 1;
        }
        current = current->next;
    }

    return 0;
}

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

        struct Node *current = table[i];

        while (current != NULL) {
            printf("%d -> ", current->key);
            current = current->next;
        }

        printf("NULL\n");
    }
}

void freeTable(void) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        struct Node *current = table[i];

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

        table[i] = NULL;
    }
}

int main(void) {
    insert(23);
    insert(33);
    insert(43);
    insert(14);

    display();

    if (search(33)) {
        printf("33 found in hash table\n");
    } else {
        printf("33 not found\n");
    }

    freeTable();

    return 0;
}

Output:

Index 0: NULL
Index 1: NULL
Index 2: NULL
Index 3: 43 -> 33 -> 23 -> NULL
Index 4: 14 -> NULL
Index 5: NULL
Index 6: NULL
Index 7: NULL
Index 8: NULL
Index 9: NULL
33 found in hash table

Explanation

• Each bucket initially points to NULL.

• insert() calculates the index and creates a new linked-list node.

• The new node is added at the beginning of the bucket's linked list.

• search() traverses the list at the calculated index.

• freeTable() releases the dynamically allocated nodes before the program exits.

Advantages of Chaining

• Multiple keys can share the same bucket.

• The table does not need an empty array slot for every inserted key.

• Deletion can be implemented by removing the relevant linked-list node.

Disadvantages of Chaining

• Requires additional memory for pointers and linked-list nodes.

• Dynamic memory allocation adds overhead.

• A poor hash function can create long linked lists and slow down searches.

Linear Probing vs Chaining

7. Applications of Hashing

Hashing is widely used in software because it provides efficient lookup when keys are distributed well and the table is appropriately sized.

1. Dictionaries and Key-Value Storage

A program can map a username to a user record, or a product ID to product details.

2. Database Indexing

Hash-based indexes can support efficient equality lookups. They are not a replacement for ordered indexes when range queries or sorted traversal are required.

3. Caching

Applications use keys such as URLs, query parameters, or identifiers to locate cached data quickly.

4. Duplicate Detection

A program can use a hash table to track values already seen and detect duplicates without repeatedly scanning the entire collection.

5. Compiler Symbol Tables

Compilers can use hash tables to look up identifiers such as variable names and function names.

6. Frequency Counting

Hash tables can count how many times each word or number appears in a dataset.

C Program: Counting Frequencies with a Simple Hash Table

The following example counts occurrences of non-negative integers from 0 to 99 by using a direct-index array. This is a simple hashing-like technique for a small, bounded key range.

#include 

#define RANGE 100

int main(void) {
    int values[] = {10, 20, 10, 30, 20, 10};
    int n = sizeof(values) / sizeof(values[0]);
    int frequency[RANGE] = {0};

    for (int i = 0; i < n; i++) {
        if (values[i] >= 0 && values[i] < RANGE) {
            frequency[values[i]]++;
        }
    }

    printf("Frequency of 10: %d\n", frequency[10]);
    printf("Frequency of 20: %d\n", frequency[20]);
    printf("Frequency of 30: %d\n", frequency[30]);

    return 0;
}

Output:

Frequency of 10: 3
Frequency of 20: 2
Frequency of 30: 1

This direct-index approach is useful when keys come from a small, known range. For large or arbitrary keys, a general hash table is usually more practical.

Hashing Time Complexity

Let (n) be the number of stored keys and (m) be the number of buckets.

These are typical bounds for common hash-table implementations, not guarantees for every input. Worst-case behavior can occur when many keys collide or probing becomes extensive.

The load factor is:

[
\alpha = \frac{n}{m}
]

Here, (n) is the number of stored keys and (m) is the number of buckets.

For chaining, the load factor can exceed 1 because each bucket can hold multiple nodes. For open addressing, the load factor must remain below 1, and performance often deteriorates as the table fills.

Best Practices for Hashing in C

1. Choose a hash function suited to the key distribution.

2. Keep the load factor at a suitable level.

3. Handle collisions explicitly.

4. Check array indices before accessing the table.

5. Normalize negative keys if the application allows them.

6. Check the result of malloc() before using allocated memory.

7. Free dynamically allocated linked-list nodes when finished.

8. Handle duplicate keys according to the application's requirements.

9. Use a deletion strategy appropriate to the collision-resolution method.

10. Remember that hashing is optimized for lookup by key, not for keeping keys sorted.

Conclusion

Hashing is a fundamental DSA technique for efficient data storage and retrieval. In this module, we covered hash functions, hash tables, collision handling, linear probing, chaining, and real-world applications.

The two major collision-resolution techniques discussed here are:

• Linear probing: stores entries in the table array and searches for another available slot.

• Chaining: stores colliding keys in a collection, commonly a linked list, at the same bucket.

Understanding these approaches helps you choose the right data structure for lookup-heavy applications and prepares you for more advanced algorithms.