C Programming Data Structures Hash Table Hash Map And Hash Set Complete Guide

Hash Tables, Hash Maps, and Hash Sets in C Programming

1. Introduction to Hashing and Data Structures

Hashing is a technique used to implement data structures such as hash tables, hash maps, and hash sets, which provide efficient data retrieval and management. These structures are crucial in handling large datasets due to their average-case constant time complexity for insertion, deletion, and lookup operations.

2. Hash Table

A hash table is a data structure that implements an associative array, a structure that can map keys to values. It uses a hash function to compute an index into an array in which an element will be inserted or searched.

Structure:

• Array: Stores the elements.
• Hash Function: Maps keys to indices.

Basic Operations:

• Insertion: Use the hash function to find the index and insert the element.
• Search/Retrieve: Hash the key to find the index and check if the element is present.
• Deletion: Locate the element via hashing and remove it.

Handling Collisions:

• Chaining: Each array index points to a linked list (or another data structure) that stores all elements whose keys hash to that index.
• Open Addressing: All elements are stored in the array itself. Techniques include:
  • Linear Probing: If a hash collision occurs, check the next available slot.
  • Quadratic Probing: Use a quadratic function to find the next slot.
  • Double Hashing: Use a second hash function to determine the steps to take.

Example Use Case:

• Efficiently manage user data where each user has a unique identifier (key) and profile information (value).

C Implementation Example:

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

#define TABLE_SIZE 10

typedef struct Entry {
    char key[50];
    int value;
    struct Entry* next;
} Entry;

Entry* table[TABLE_SIZE];

unsigned int hash(const char* key) {
    unsigned int hash = 0;
    for (int i = 0; key[i]; i++) {
        hash = (hash + key[i]) % TABLE_SIZE;
    }
    return hash;
}

void insert(char* key, int value) {
    unsigned int index = hash(key);
    Entry* entry = (Entry*)malloc(sizeof(Entry));
    strcpy(entry->key, key);
    entry->value = value;
    entry->next = table[index];
    table[index] = entry;
}

int search(char* key) {
    unsigned int index = hash(key);
    Entry* entry = table[index];
    while (entry) {
        if (strcmp(entry->key, key) == 0)
            return entry->value;
        entry = entry->next;
    }
    return -1; // Not found
}

void delete(char* key) {
    unsigned int index = hash(key);
    Entry* entry = table[index];
    Entry* prev = NULL;
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            if (prev) {
                prev->next = entry->next;
            } else {
                table[index] = entry->next;
            }
            free(entry);
            return;
        }
        prev = entry;
        entry = entry->next;
    }
}

int main() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        table[i] = NULL;
    }

    insert("Alice", 23);
    insert("Bob", 25);

    printf("Alice's age: %d\n", search("Alice")); // Output: Alice's age: 23
    delete("Alice");
    printf("Alice's age: %d\n", search("Alice")); // Output: Alice's age: -1

    return 0;
}

3. Hash Map

A hash map (also known as a dictionary or associative array) is a data structure that stores key-value pairs and allows for fast retrieval based on keys. In C, a hash map can be implemented using hash tables, as shown above.

Key Characteristics:

• Key-Value Pairs: Each key is associated with a value.
• Dynamic Resizing: Hash maps often handle resizing automatically to maintain performance as more elements are added.
• Non-Contiguous Storage: Unlike arrays, hash maps do not store elements in contiguous memory.

Example Use Case:

• Implementing a symbol table in a compiler that associates variable names (keys) with their values or types (values).

C Implementation Note: Standard C does not provide built-in hash maps, so developers often use third-party libraries like GLib or implement custom solutions.

4. Hash Set

A hash set is a data structure that stores unique elements and provides efficient methods for adding, removing, and testing for the presence of elements. It is similar to a hash table but with keys only (no associated values).

Structure:

• Array: Stores the elements.
• Hash Function: Maps elements to indices.

Basic Operations:

• Insertion: Hash the element and insert it.
• Search: Hash the element and check if it exists.
• Deletion: Hash the element and remove it.

Handling Collisions:

• Chaining: Like hash tables.
• Open Addressing: Like hash tables.

Example Use Case:

• Implementing a set of visited URLs in a web crawler to avoid revisiting the same pages.

C Implementation Example:

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

#define TABLE_SIZE 10

typedef struct Entry {
    char key[50];
    struct Entry* next;
} Entry;

Entry* table[TABLE_SIZE];

unsigned int hash(const char* key) {
    unsigned int hash = 0;
    for (int i = 0; key[i]; i++) {
        hash = (hash + key[i]) % TABLE_SIZE;
    }
    return hash;
}

void insert(char* key) {
    unsigned int index = hash(key);
    Entry* entry = (Entry*)malloc(sizeof(Entry));
    strcpy(entry->key, key);
    entry->next = table[index];
    table[index] = entry;
}

int search(char* key) {
    unsigned int index = hash(key);
    Entry* entry = table[index];
    while (entry) {
        if (strcmp(entry->key, key) == 0)
            return 1; // Found
        entry = entry->next;
    }
    return 0; // Not found
}

void delete(char* key) {
    unsigned int index = hash(key);
    Entry* entry = table[index];
    Entry* prev = NULL;
    while (entry) {
        if (strcmp(entry->key, key) == 0) {
            if (prev) {
                prev->next = entry->next;
            } else {
                table[index] = entry->next;
            }
            free(entry);
            return;
        }
        prev = entry;
        entry = entry->next;
    }
}

int main() {
    for (int i = 0; i < TABLE_SIZE; i++) {
        table[i] = NULL;
    }

    insert("Alice");
    printf("Is Alice in the set? %s\n", search("Alice") ? "Yes" : "No"); // Output: Yes
    delete("Alice");
    printf("Is Alice in the set? %s\n", search("Alice") ? "Yes" : "No"); // Output: No

    return 0;
}

5. Importance and Applications

• Efficiency: Hash tables, hash maps, and hash sets offer fast average-case performance for common operations.
• Flexibility: These structures are versatile and can be customized to handle different types of data and requirements.
• Memory Utilization: Efficient use of memory compared to other data structures like balanced trees.
• Real-world Applications: Widely used in databases, caches, symbol tables, URL management, etc.

Summary: Hash tables, hash maps, and hash sets are essential data structures in C programming that provide efficient ways to manage key-value pairs and unique elements. They are characterized by their ability to perform operations in constant time on average, making them ideal for applications that require fast data retrieval and modification. Implementing these structures requires careful consideration of collision resolution strategies and hash function design to ensure optimal performance.