Implementing a HashMap in C Language

In the world of data structures, a HashMap is an efficient tool for storing and retrieving data. It stores data in the form of key-value pairs, allowing for insertions, deletions, and lookups to be performed in average constant time complexity. Today, we will implement a simple HashMap using the C programming language.

1. Introduction to HashMap Principles

A HashMap is implemented based on a hash table. A hash table is a data structure that allows direct access based on keys. It uses a hash function to map keys to specific locations, known as hash buckets. Ideally, different keys should yield different hash values calculated by the hash function, enabling quick access to the corresponding values. However, due to the limitations of hash functions, hash collisions—where different keys yield the same hash value—are unavoidable. There are various methods to resolve hash collisions, with the most common being separate chaining and open addressing. In this implementation, we will use separate chaining.

2. C Language Implementation of HashMap

1. Defining Structures

First, we need to define some structures to represent the HashMap and its related elements.

// Define the hash table node structure
typedef struct HashNode {
    int key;
    int value;
    struct HashNode* next;
} HashNode;

// Define the hash table structure
typedef struct HashMap {
    HashNode** table;
    int size;
} HashMap;

In the code above, the HashNode structure represents a node in the hash table, containing a key (key), a value (value), and a pointer to the next node (next). The HashMap structure represents the entire hash table, containing a pointer to an array of pointers to HashNode and the size of the hash table (size).

2. Initializing HashMap

// Initialize the hash table
HashMap* createHashMap(int capacity) {
    HashMap* map = (HashMap*)malloc(sizeof(HashMap));
    map->size = capacity;
    map->table = (HashNode**)malloc(capacity * sizeof(HashNode*));
    for (int i = 0; i < capacity; i++) {
        map->table[i] = NULL;
    }
    return map;
}

This function creates a new HashMap. It first allocates memory for the HashMap structure, then sets the size of the hash table and allocates memory for the array of pointers to HashNode, initializing each element of the array to NULL.

3. Hash Function

// Simple hash function
int hashFunction(int key, int size) {
    return key % size;
}

Here, we use a simple modulo hash function that calculates the hash value by taking the key modulo the size of the hash table. In practical applications, the design of the hash function is more complex to reduce hash collisions.

4. Insertion Operation

// Insert key-value pair
void put(HashMap* map, int key, int value) {
    int index = hashFunction(key, map->size);
    HashNode* node = map->table[index];
    while (node!= NULL) {
        if (node->key == key) {
            node->value = value;
            return;
        }
        node = node->next;
    }
    HashNode* newNode = (HashNode*)malloc(sizeof(HashNode));
    newNode->key = key;
    newNode->value = value;
    newNode->next = map->table[index];
    map->table[index] = newNode;
}

The insertion operation first calculates the hash bucket index corresponding to the key using the hash function. If there are nodes in that bucket, it traverses the linked list to check for the same key. If found, it updates the value; if not, it creates a new node and inserts it at the head of the list.

5. Lookup Operation

// Lookup value
int get(HashMap* map, int key) {
    int index = hashFunction(key, map->size);
    HashNode* node = map->table[index];
    while (node!= NULL) {
        if (node->key == key) {
            return node->value;
        }
        node = node->next;
    }
    return -1; // Return -1 if not found
}

The lookup operation also calculates the index using the hash function, then searches the corresponding linked list for the key. If found, it returns the corresponding value; otherwise, it returns -1 to indicate not found.

3. Conclusion

Through the above steps, we have implemented a simple HashMap in C. Although this implementation is quite basic, it covers the core principles and operations of a HashMap. In practical applications, further optimizations can be made to the hash function and memory management. Mastering the implementation of HashMap is greatly beneficial for understanding data structures and algorithms and improving programming skills. I hope this article provides you with a deeper understanding of implementing a HashMap in C.