Hash Table Implementation in C

Overview

This is a lightweight and efficient Hash Table implementation written in C. It uses separate chaining (linked lists) to handle hash collisions.

Features

• Custom Hashing Algorithm: Implements a character-based polynomial rolling hash logic.
• Collision Handling: Uses linked lists to manage multiple keys mapping to the same index.
• Memory Management: Dynamically allocates memory for entries and duplicates strings for persistence.
• Standard Operations: Supports insertion, deletion, and lookup.

Data Structures

The implementation depends on the following definitions (assumed in library.h):

typedef struct entry {
    char *first;       // Key
    int second;        // Value
    struct entry *next; // Pointer for separate chaining
} entry;

typedef entry** HASH_TABLE;
#define TABLE_SIZE 1000 // Example size

Core API Reference

hash

Computes a hash value for a given string key.

int hash(char *s);

create_hash_table

Allocates and initializes a new hash table.

HASH_TABLE create_hash_table();

add_item

Inserts a key-value pair. Handles collisions by appending to the end of the chain.

int add_item(char key[], int val, HASH_TABLE *ptr);

lookup

Searches for a key and returns the associated value. Returns -1 if not found.

int lookup(char key[], HASH_TABLE *ptr);

delete_item

Removes an entry from the table and frees associated memory.

int delete_item(char key[], HASH_TABLE *ptr);

Implementation Details

Hashing Logic

The hash function uses a polynomial rolling approach where the hash value is updated for each character in the string:

hash_value = (hash_value * character) % TABLE_SIZE

Memory Safety

• Uses strdup() for key storage to avoid dangling pointers.
• delete_item explicitly calls free() on the duplicated key and the entry struct.

Usage Example

#include "library.h"
#include <stdio.h>

int main() {
    HASH_TABLE myTable = create_hash_table();

    // Insertion
    add_item("Apple", 100, &myTable);
    add_item("Banana", 200, &myTable);

    // Lookup
    int price = lookup("Apple", &myTable);
    printf("Price of Apple: %d\n", price);

    // Deletion
    delete_item("Apple", &myTable);

    return 0;
}