Hashing in C

Introduction

Hello there, fellow coder! Ever wondered how databases retrieve data so quickly or how your password gets verified almost instantly? The secret sauce is a technique called “hashing”. Today, we’re going to dive into the world of hashing in C. Buckle up, it’s going to be a fun ride!

Understanding Hashing

Hashing, in the simplest terms, is a process that maps keys to values. Think of it like a super-efficient librarian who knows exactly where to find the book you’re looking for. In C, we use hashing to speed up data retrieval, making our programs faster and more efficient.

Let’s say we have a list of students and their grades, and we want to quickly look up a grade given a student’s name. We could use a hash function to convert the student’s name into an index in an array, and store the grade at that index. Here’s a simple example:

#include <stdio.h>

#define SIZE 20

int grades[SIZE] = {0};

unsigned int hash(char* name) {
    unsigned int index = 0;
    for (int i = 0; name[i] != '\0'; i++) {
        index += name[i];
    }
    return index % SIZE;
}

void storeGrade(char* name, int grade) {
    grades[hash(name)] = grade;
}

int main() {
    storeGrade("Alice", 85);
    storeGrade("Bob", 90);
    printf("Alice's grade: %d\n", grades[hash("Alice")]);
    printf("Bob's grade: %d\n", grades[hash("Bob")]);
    return 0;
}

In this code, we define a hash function that takes a string (the student’s name) and returns an index in the array. The storeGrade function stores a grade at the computed index. When we run this program, it will print “Alice’s grade: 85” and “Bob’s grade: 90”.

Hashing Techniques in C

There are several ways to implement hashing in C, but we’ll focus on two main techniques: open addressing and chaining.

Open Addressing

In open addressing, if a collision occurs (two keys map to the same index), we find another spot in the array for the second key. It’s like finding another parking spot if your usual one is taken. Here’s a simple example of open addressing using linear probing:

#include <stdio.h>

#define SIZE 20

int grades[SIZE] = {0};

unsigned int hash(char* name) {
    unsigned int index = 0;
    for (int i = 0; name[i] != '\0'; i++) {
        index += name[i];
    }
    return index % SIZE;
}

void storeGrade(char* name, int grade) {
    unsigned int index = hash(name);
    while (grades[index]) {
        index = (index + 1) % SIZE;
    }
    grades[index] = grade;
}

int main() {
    storeGrade("Alice", 85);
    storeGrade("Bob", 90);
    printf("Alice's grade: %d\n", grades[hash("Alice")]);
    printf("Bob's grade: %d\n", grades[hash("Bob")]);
    return 0;
}

In this code, the storeGrade function checks if the computed index is already occupied. If it is, it increments the index until it finds an open spot. This is known as linear probing.

Chaining

In chaining, each array index points to a linked list of keys that map to that index. It’s like hanging multiple keys on a single hook. Here’s a simple example of chaining:

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

#define SIZE 20

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

Node* createNode(int grade) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->grade = grade;
    newNode->next = NULL;
    return newNode;
}

unsigned int hash(char* name) {
    unsigned int index = 0;
    for (int i = 0; name[i] != '\0'; i++) {
        index += name[i];
    }
    return index % SIZE;
}

void storeGrade(Node* hashTable[], char* name, int grade) {
    unsigned int index = hash(name);
    Node* newNode = createNode(grade);
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

int main() {
    Node* hashTable[SIZE] = {NULL};
    storeGrade(hashTable, "Alice", 85);
    storeGrade(hashTable, "Bob", 90);
    printf("Alice's grade: %d\n", hashTable[hash("Alice")]->grade);
    printf("Bob's grade: %d\n", hashTable[hash("Bob")]->grade);
    return 0;
}

In this code, we first define a Node structure for our linked list. The createNode function creates a new node with the given grade. The hash function is the same as before. The storeGrade function inserts a new node at the correct index in the hash table. If there’s already a node at that index (a collision), the new node is added to the front of the list. When we run this program, it will print “Alice’s grade: 85” and “Bob’s grade: 90”.

Code Examples

Now, let’s roll up our sleeves and dive into some code!

Hashing Implementation in C

Let’s start with a simple hash function that uses the modulus operator. This function will take a key and return an index in the array where the value will be stored.

#include <stdio.h>

#define SIZE 20

unsigned int hash(int key) {
    return key % SIZE;
}

int main() {
    int key = 15;
    printf("The index for key %d is %u\n", key, hash(key));
    return 0;
}

In this code, we define a hash function that takes an integer key and returns the modulus of the key divided by the size of the hash table. This ensures that the index always falls within the range of the hash table size. When we run this program with a key of 15, it will print “The index for key 15 is 15”, because 15 modulus 20 is 15.

Hashing with Chaining in C

Now, let’s see how we can implement chaining in our hash table. In this example, we’ll use a linked list at each index of the array to handle collisions.

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

#define SIZE 20

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

Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory error\n");
        return NULL;
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

unsigned int hash(int key) {
    return key % SIZE;
}

void insert(Node* hashTable[], int key, int value) {
    unsigned int index = hash(key);
    Node* newNode = createNode(value);
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

int main() {
    Node* hashTable[SIZE] = {NULL};
    insert(hashTable, 15, 100);
    insert(hashTable, 25, 200);
    printf("Value at index %u: %d\n", hash(15), hashTable[hash(15)]->data);
    printf("Value at index %u: %d\n", hash(25), hashTable[hash(25)]->data);
    return 0;
}

In this code, we first define a Node structure for our linked list. The createNode function creates a new node with the given data. The hash function is the same as before. The insert function inserts a new node at the correct index in the hash table. If there’s already a node at that index (a collision), the new node is added to the front of the list. When we run this program, it will print “Value at index 15: 100” and “Value at index 5: 200”, because 15 and 25 modulus 20 are 15 and 5, respectively.

Hashing with Open Addressing in C

Finally, let’s implement open addressing in our hash table. In this example, we’ll use linear probing, which means if a collision occurs, we’ll check the next index until we find an open spot.

#include <stdio.h>

#define SIZE 20

int hashTable[SIZE] = {0};

unsigned int hash(int key) {
    return key % SIZE;
}

void insert(int key, int value) {
    unsigned int index = hash(key);
    while (hashTable[index]) {
        index = (index + 1) % SIZE;
    }
    hashTable[index]I apologize for the abrupt cut-off. Here's the complete code:

```c
#include <stdio.h>

#define SIZE 20

int hashTable[SIZE] = {0};

unsigned int hash(int key) {
    return key % SIZE;
}

void insert(int key, int value) {
    unsigned int index = hash(key);
    while (hashTable[index]) {
        index = (index + 1) % SIZE;
    }
    hashTable[index] = value;
}

int main() {
    insert(15, 100);
    insert(25, 200);
    printf("Value at index %u: %d\n", hash(15), hashTable[hash(15)]);
    printf("Value at index %u: %d\n", hash(25), hashTable[hash(25)]);
    return 0;
}


In this code, we first define a hash table as an array of integers. The hash function is the same as before. The insert function inserts a value at the correct index in the hash table. If there’s already a value at that index (a collision), it increments the index until it finds an open spot. This is known as linear probing. When we run this program, it will print “Value at index 15: 100” and “Value at index 5: 200”, because 15 and 25 modulus 20 are 15 and 5, respectively. However, since the index 15 is already occupied, the value 200 is stored at the next available index, which is 16.

Hash Table in C

A hash table is like a super-powered array. It uses a hash function to compute an index for a key, and stores the value at that computed index. This makes data retrieval extremely fast.

In other word, a hash table, also known as a hash map, is a powerful data structure that allows you to store and retrieve values quickly and efficiently. It’s like a super-powered array that uses a hash function to compute an index for a key, and stores the corresponding value at that computed index. This makes data retrieval extremely fast, as you can directly access the value by its key.

In C, a hash table can be implemented using an array of structures. Each structure, or ‘bucket’, holds a key-value pair. The key is passed through a hash function to generate an index, which determines where in the array the corresponding value will be stored. If two keys produce the same index (a situation known as a ‘collision’), the hash table must have a strategy to handle it. The two most common strategies are ‘chaining’, where each bucket holds a linked list of all key-value pairs with the same hash, and ‘open addressing’, where a collision triggers a search for the next available bucket.

Here’s a simple example of a hash table in C:

#include <stdio.h>

#define SIZE 20

typedef struct {
    int key;
    int value;
} HashTable;

HashTable hashTable[SIZE];

unsigned int hash(int key) {
    return key % SIZE;
}

void insert(int key, int value) {
    hashTable[hash(key)].key = key;
    hashTable[hash(key)].value = value;
}

int main() {
    insert(15, 100);
    insert(25, 200);
    printf("Value for key %d: %d\n", 15, hashTable[hash(15)].value);
    printf("Value for key %d: %d\n", 25, hashTable[hash(25)].value);
    return 0;
}

In this code, we first define a HashTable structure that holds a key-value pair. We then create an array of these structures. The hash function takes a key and returns an index in the array. The insert function stores a key-value pair at the computed index. When we run this program, it will print “Value for key 15: 100” and “Value for key 25: 200”, because 15 and 25 modulus 20 are 15 and 5, respectively.

Hash tables are a fundamental part of data structures and algorithms, and understanding them is crucial for any programmer. They offer a combination of efficiency and simplicity that is hard to beat!

Hashing Functions in C

A hash function is the magic that makes hashing possible. It takes a key and returns an index where the corresponding value can be found. There are many types of hash functions, but a good hash function produces a uniform distribution of values.

It’s a special kind of function that takes a key as input and returns an index where the corresponding value can be found. The goal of a hash function is to distribute the keys evenly across the array or hash table. A good hash function produces a uniform distribution of values, which minimizes the likelihood of collisions (when two keys produce the same index).

In C, a hash function can be as simple as taking the modulus of the key with the size of the hash table. This ensures that the index always falls within the range of the hash table size. Here’s an example of a simple hash function:

unsigned int hash(int key) {
    return key % SIZE;
}

In this code, SIZE is the size of the hash table. The hash function takes an integer key and returns the modulus of the key divided by SIZE. This ensures that the index always falls within the range of the hash table size.

However, this simple hash function may not distribute keys evenly, especially if the keys have a pattern or are not random. In such cases, more complex hash functions may be used. These can involve various operations such as multiplication, division, and bitwise operations to ensure a more uniform distribution of keys.

It’s important to note that while a good hash function minimizes collisions, it cannot eliminate them entirely. Therefore, a good hashing implementation also needs a strategy to handle collisions when they occur.

Understanding hash functions is crucial to mastering hashing in C. They are the engine that drives the efficiency of hash tables, making them a vital tool in a programmer’s toolkit.

Collision Resolution in Hashing

Collisions are inevitable in hashing. But fear not, there are several ways to resolve collisions, including open addressing and chaining, which we’ve already discussed.

Wrapping Up

And that’s a wrap! We’ve covered a lot of ground today, from understanding hashing to implementing it in C. Remember, practice makes perfect. So, keep coding and keep learning!

Frequently Asked Questions (FAQ)

Related Tutorials

If you enjoyed this tutorial, you might also like these:

• Command Line Arguments in C
• Function Pointers in C
• Efficient Memory Management in C
• Multithreading in C
• Network Programming in C
• Building a Web Server in C
• Introduction to Algorithms in C
• Advanced Algorithms in C
• Building a Chat Application in C
• Searching Algorithms in C
• Sorting Algorithms in C

Happy coding!