Hash Tables & Graphs

Hash Tables

• Hash Function: Maps keys to array indices — hash(key) = key % TABLE_SIZE. Good hash functions distribute keys uniformly. Common: djb2, FNV-1a for string keys
• Chaining: Each array slot is a linked list — collisions add to the list. Simple to implement, handles high load factors well. Average O(1), worst O(n)
• Open Addressing: Collisions probe for next empty slot — Linear probing (i+1, i+2...), Quadratic probing (i+1², i+2²...), Double hashing (i + j*hash2(key))
• Load Factor: Number of elements / table size. When load factor > 0.75, resize (double table size, rehash all elements). Keeps operations close to O(1)
• Applications: Symbol tables (compilers), caches, database indexing, counting frequencies, implementing sets, detecting duplicates in O(n) time
• Implementation in C: struct HashNode { char* key; int value; struct HashNode* next; }; Array of HashNode pointers. malloc/free for dynamic chains

Try It Yourself: Linked List

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

// Node structure for linked list
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Create a new node
Node* createNode(int data) {
    Node* node = (Node*)malloc(sizeof(Node));
    node->data = data;
    node->next = NULL;
    return node;
}

// Insert at the beginning
Node* insertFront(Node* head, int data) {
    Node* node = createNode(data);
    node->next = head;
    return node;
}

// Print the linked list
void printList(Node* head) {
    Node* current = head;
    while (current != NULL) {
        printf("%d -> ", current->data);
        current = current->next;
    }
    printf("NULL
");
}

int main() {
    Node* head = NULL;

    // Build list: 30 -> 20 -> 10 -> NULL
    head = insertFront(head, 10);
    head = insertFront(head, 20);
    head = insertFront(head, 30);

    printf("Linked List: ");
    printList(head);
    printf("Try adding more nodes!
");
    return 0;
}

Quick Quiz — Data Structures