Data Structures 18 - Hash Table

A hash table is a highly efficient data structure primarily used for fast lookup, insertion, and deletion operations. It maps keys to specific positions in the table via a hash function, thereby accelerating data access. Below is a detailed and systematic guide to hash table implementation, covering basic concepts, hash functions, collision resolution methods, and concrete implementation in C.

1. Basic Concepts

• Hash Function: A function that maps an input (key) to an index position in the hash table.
• Hash Table: An array used to store key-value pairs.
• Collision: When different keys are mapped to the same index position by the hash function.
• Load Factor: The ratio of the number of elements in the hash table to the size of the hash table, used to measure how full the hash table is.

2. Hash Functions

The choice of hash function has a significant impact on the performance of a hash table. A good hash function should distribute keys uniformly and minimize collisions. Common hash functions include:

unsigned int hash_function(const char *key) {
    unsigned int hash = 0;
    while (*key) {
        hash = (hash << 5) + *key++;
    }
    return hash;
}

3. Collision Resolution Methods

There are two common collision resolution methods:

• Chaining: Each index position in the hash table stores a linked list. When a collision occurs, the new element is added to the linked list.
• Open Addressing: When a collision occurs, the next available position is sought to store the element.

4. Concrete Implementation in C

4.1 Defining the Structure

First, define the hash table structure, including the linked list node and the hash table itself.

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

#define TABLE_SIZE 100

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

typedef struct HashTable {
    HashNode **table;
} HashTable;

4.2 Initializing the Hash Table

HashTable* create_table() {
    HashTable *hashTable = (HashTable*) malloc(sizeof(HashTable));
    hashTable->table = (HashNode**) malloc(TABLE_SIZE * sizeof(HashNode*));
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable->table[i] = NULL;
    }
    return hashTable;
}

4.3 Inserting Elements

void insert(HashTable *hashTable, const char *key, int value) {
    unsigned int index = hash_function(key) % TABLE_SIZE;
    HashNode *newNode = (HashNode*) malloc(sizeof(HashNode));
    newNode->key = strdup(key);
    newNode->value = value;
    newNode->next = hashTable->table[index];
    hashTable->table[index] = newNode;
}

4.4 Searching for Elements

int search(HashTable *hashTable, const char *key) {
    unsigned int index = hash_function(key) % TABLE_SIZE;
    HashNode *node = hashTable->table[index];
    while (node != NULL) {
        if (strcmp(node->key, key) == 0) {
            return node->value;
        }
        node = node->next;
    }
    return -1; // Not found
}

4.5 Deleting Elements

void delete(HashTable *hashTable, const char *key) {
    unsigned int index = hash_function(key) % TABLE_SIZE;
    HashNode *node = hashTable->table[index];
    HashNode *prev = NULL;
    while (node != NULL && strcmp(node->key, key) != 0) {
        prev = node;
        node = node->next;
    }
    if (node == NULL) {
        return; // Key not found
    }
    if (prev == NULL) {
        hashTable->table[index] = node->next;
    } else {
        prev->next = node->next;
    }
    free(node->key);
    free(node);
}

4.6 Freeing the Hash Table

void free_table(HashTable *hashTable) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        HashNode *node = hashTable->table[i];
        while (node != NULL) {
            HashNode *temp = node;
            node = node->next;
            free(temp->key);
            free(temp);
        }
    }
    free(hashTable->table);
    free(hashTable);
}

5. Example Code

int main() {
    HashTable *hashTable = create_table();

    insert(hashTable, "key1", 1);
    insert(hashTable, "key2", 2);
    insert(hashTable, "key3", 3);

    printf("Value for 'key1': %d\n", search(hashTable, "key1"));
    printf("Value for 'key2': %d\n", search(hashTable, "key2"));
    printf("Value for 'key3': %d\n", search(hashTable, "key3"));

    delete(hashTable, "key2");
    printf("Value for 'key2' after deletion: %d\n", search(hashTable, "key2"));

    free_table(hashTable);

    return 0;
}

Written by Professor Min Fan

Code

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
#define TABLE_SIZE 100 // Size of the hash table
#define KEY_SIZE 50  // Maximum length of a key
#define VALUE_SIZE 100 // Maximum length of a value
 
typedef struct KeyValuePair {
    char key[KEY_SIZE];
    char value[VALUE_SIZE];
    struct KeyValuePair *next; // Pointer to the next node, handles collisions
} KeyValuePair;
 
typedef struct {
    KeyValuePair *table[TABLE_SIZE]; // Hash table array
} HashTable;
 
// Initialize the hash table
void initHashTable(HashTable *hashTable) {
    for (int i = 0; i < TABLE_SIZE; i++) {
        hashTable->table[i] = NULL;
    }
}

Output

Collision, move forward for key 57.
Collision, move forward for key 95.
Collision, move forward for key 95.
Search result of 95 is: r
Search result of 38 is: l
Search result of 57 is: w
Search result of 4 is: x
Press any key to continue