Hash Table with Chaining


What is Hashing?

Hashing is a technique to convert data (like a string, number, etc.) into a small fixed-size value called a hash code using a mathematical function called a hash function.

✅ Purpose:

  • Fast access

  • Fast insertion, deletion, and search

What is a Hash Table?

A Hash Table is a data structure that stores data in an array-like format using the hash code as an index.

  • Key → Hash Function → Index → Store value at that index

  • If two keys generate the same index, we resolve it using methods like chaining (linked list at that index) or open addressing (find next empty spot).

 How to Implement a Simple Hash Table?

Steps:

  1. Choose a hash function (e.g., key % size).

  2. Create an array of fixed size.

  3. Insert, search, and delete elements based on the hash value.


Key Points:

  • Hash Function: Should distribute keys evenly.

  • Collisions: Resolved by chaining (linked list) or open addressing (probing).

  • Time Complexity:

    • Best case: O(1) for insert/search/delete

    • Worst case (many collisions): O(n)


Algorithms for Hash Table

1. Hash Table with Chaining (using Linked List)

Idea:
Each index of the table stores a linked list to handle collisions (multiple keys at same index).

🔹 Insertion Algorithm (Chaining)

1. Compute index = hash(key)
2. Create a new node with (key, value)
3. Insert the new node at the beginning of the linked list at hashTable[index]

🔹 Search Algorithm (Chaining)


1. Compute index = hash(key)
2. Traverse the linked list at hashTable[index]
3. If node.key == key, return node.value
4. If end of list is reached, return NOT FOUND

🔹 Deletion Algorithm (Chaining)


1. Compute index = hash(key)
2. Traverse the linked list at hashTable[index]
3. If node.key == key:
     a. Adjust previous node's next pointer
     b. Free the current node
4. If end of list is reached without finding, print "Key not found"

C Program Hash Table with Chaining

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

#define SIZE 11

// Node for chaining
struct Node {
    int key;
    int value;
    struct Node* next;
};

struct Node* hashTable[SIZE];

// Hash function
int hashFunction(int key) {
    return key % SIZE;
}

// Insert key-value pair
void insert(int key, int value) {
    int index = hashFunction(key);
    
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->key = key;
    newNode->value = value;
    newNode->next = hashTable[index];
    hashTable[index] = newNode;
}

// Search for a value by key
int search(int key) {
    int index = hashFunction(key);
    struct Node* temp = hashTable[index];
    
    while (temp != NULL) {
        if (temp->key == key)
            return temp->value;
        temp = temp->next;
    }
    return -1; // not found
}

// Delete a key-value pair
void delete(int key) {
    int index = hashFunction(key);
    struct Node* temp = hashTable[index];
    struct Node* prev = NULL;
    
    while (temp != NULL) {
        if (temp->key == key) {
            if (prev == NULL)
                hashTable[index] = temp->next;
            else
                prev->next = temp->next;
            
            free(temp);
            printf("Deleted key %d\n", key);
            return;
        }
        prev = temp;
        temp = temp->next;
    }
    printf("Key %d not found!\n", key);
}

// Display hash table
void display() {
    for (int i = 0; i < SIZE; i++) {
        printf("[%d]: ", i);
        struct Node* temp = hashTable[i];
        while (temp != NULL) {
            printf("(%d,%d) -> ", temp->key, temp->value);
            temp = temp->next;
        }
        printf("NULL\n");
    }
}

int main() {
    int choice, key, value;
    
    while (1) {
        printf("\n1. Insert\n2. Search\n3. Delete\n4. Display\n5. Exit\nEnter your choice: ");
        scanf("%d", &choice);
        
        switch (choice) {
            case 1:
                printf("Enter key and value: ");
                scanf("%d%d", &key, &value);
                insert(key, value);
                break;
            case 2:
                printf("Enter key to search: ");
                scanf("%d", &key);
                value = search(key);
                if (value != -1)
                    printf("Found: Value = %d\n", value);
                else
                    printf("Key not found!\n");
                break;
            case 3:
                printf("Enter key to delete: ");
                scanf("%d", &key);
                delete(key);
                break;
            case 4:
                display();
                break;
            case 5:
                exit(0);
            default:
                printf("Invalid choice!\n");
        }
    }
    
    return 0;
}

Comments

Post a Comment

Popular posts from this blog

Data Structures Lab PCCSL307 KTU 2024 Scheme - Dr Binu V P

About Me    Learn the theory Data Structures and Algorithms PCCST303 Scheme and Assessments Experiment List and References Lab Assignments Format of the Lab Record Lab Cycle ( Mandatory Programs) 1.Polynomial Addition Using Arrays 2.Sparse Matrix- Transpose and Addition 3.Stack    Implement  stack using array    Infix to Postfix Conversion and Evaluation 4.Queue    Queue using array     Circular Queue using array     Double ended Queue using array 5.Singly Linked List      Singly  Linked list and operations     Stack using linked list     Queue using linked list    Polynomial addition using linked list    Polynomial multiplication using linked list     Priority Queue-Post office customers simulation     Circular Queue using Linked List 6. Doubly Linked List      Doubly Linked List- Operations     Double Ended Queue ...
Read more

Sparse Matrix - Transpose and Addition

Image
  A sparse matrix is a special type of matrix in which most of the elements are zero or have some default value. In contrast, a dense matrix is one in which most of the elements are non-zero. Sparse matrices are used in various fields, including computer science, numerical analysis, and scientific computing, when dealing with large datasets or systems where efficiency and memory usage are crucial.   As a rule of thumb, if 2/3 of the total elements in a matrix are zeros, it can be called a sparse matrix . Using a sparse matrix representation — where only the non-zero values are stored — the space used for representing data and the time for scanning the matrix are reduced significantly. In many real-world problems — like graphs, networks, or scientific simulations — the majority of elements in the matrix are zero . Such a matrix is called a Sparse Matrix . Formally: A matrix in which the number of zero elements is significantly greater than the number of non-zero elements. ...
Read more

Polynomial Addition using Arrays

Polynomial  Addition We can represent a polynomial as a collection of terms and every term is having a coefficient and exponent. So, we can represent this as a list of terms having coefficients and exponents.  Each term of a polynomial (like 3 x 2 3x^2 , 5 x 1 5x^1 , − 7 x 0 -7x^0 ) can be stored in a structure having two parts: coefficient (like 3, 5, -7) exponent (like 2, 1, 0) An array of such structures represents the whole polynomial. Structure Definition (Example in C) struct Term { int coeff; // Coefficient of the term int expo; // Exponent of the term }; And then you can declare: struct Term poly1 [10], poly2 [10], polyResult [20]; to represent polynomials. Algorithm to Add Two Polynomials Assumption : Both polynomials are sorted in decreasing order of exponents . Steps : Initialize three pointers (indexes): i = 0 for first polynomial (poly1), j = 0 for second polynomial (poly2), k = 0 for result polynomial (polyR...
Read more