How to implement a hash table using the C language?

1 year ago
Benjamin Taylor
2 minutes

The basic steps to implementing a hash table are as follows:

  1. Definition of the data structure of a hash table including the size of the hash table, the number of buckets, and the structure of the buckets.
  2. Implement a hash function: mapping keys to bucket indices.
  3. Implementing functions for hash table operations, such as insertion, search, and deletion.
  4. Resolving conflicts: When multiple keys map to the same bucket, methods like using linked lists or open addressing are needed to handle conflicts.

Here is a simple example code in C language for implementing a hash table.

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

#define TABLE_SIZE 10

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

Node* table[TABLE_SIZE];

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

void insert(char* key, int value) {
    int index = hash_function(key);
    Node* new_node = (Node*)malloc(sizeof(Node));
    new_node->key = key;
    new_node->value = value;
    new_node->next = table[index];
    table[index] = new_node;
}

int search(char* key) {
    int index = hash_function(key);
    Node* current = table[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            return current->value;
        }
        current = current->next;
    }
    return -1; // key not found
}

void delete(char* key) {
    int index = hash_function(key);
    Node* current = table[index];
    Node* prev = NULL;
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            if (prev == NULL) {
                table[index] = current->next;
            } else {
                prev->next = current->next;
            }
            free(current);
            return;
        }
        prev = current;
        current = current->next;
    }
}

int main() {
    insert("apple", 5);
    insert("banana", 10);
    
    printf("Value of apple: %d\n", search("apple"));
    printf("Value of banana: %d\n", search("banana"));
    
    delete("apple");
    
    printf("Value of apple after deletion: %d\n", search("apple"));
    
    return 0;
}

The above code implements a simple hash table, including insert, search, and delete operations. In this example, the hash function calculates the hash value using the sum of the ASCII codes of the characters, and handles collisions using linked lists. You can modify and expand this example according to your own needs.

bannerAds