Conflict Resolution in Hash Tables with Chaining

Hash tables are fundamental data structures designed to provide near-instantaneous, $O(1)$ average-time complexity for insertions, lookups, and deletions. However, their underlying mechanics rely on mapping a theoretically infinite or exceptionally large key space into a finite, bounded array.

Because of the Pigeonhole Principle, collisions are inevitable: two distinct keys passed through a hash function can produce the exact same array index. Without conflict resolution, incoming writes will overwrite existing values at that slot, resulting in a lossy, corrupt hash table.

Two classical techniques exist to handle collisions:

1. Open Addressing (e.g., Linear Probing, Quadratic Probing, Double Hashing)
2. Chaining (Separate Chaining)

This guide breaks down the mechanics, trade-offs, and implementation nuances of chaining—from standard singly linked lists to self-balancing binary search trees.

---

The Core Concept of Chaining

Instead of searching for an alternative empty slot within the primary array (as in open addressing), chaining delegates collision management to an auxiliary data structure located at each array bucket.

When multiple keys map to index i, they are placed together inside the auxiliary collection rooted at bucket i. The array effectively changes from an array of values into an array of collections.

Bucket Array
+-------+
|   0   | ---> [ K2 | V2 ] -> null
+-------+
|   1   | ---> null
+-------+
|   2   | ---> [ K1 | V1 ] -> [ K3 | V3 ] -> null
+-------+
|   3   | ---> null
+-------+

---

Chaining with Singly Linked Lists

The most widespread implementation of chaining uses a singly linked list. Doubly linked lists or circular linked lists introduce pointer overhead and operational complexity that rarely justify their minor benefits in a hash table context.

Data Layout

Each slot in the array stores a pointer to the head of a linked list (or NULL if empty). Each node in the list stores:

• The application Key (retained to disambiguate collisions during lookups and deletions)
• The associated Value
• A pointer to the Next node

typedef struct Node {
    void *key;
    void *value;
    struct Node *next;
} Node;

typedef struct Slot {
    Node *head;
} Slot;

typedef struct HashTable {
    Slot *buckets;
    size_t capacity;
} HashTable;

Why must the key be stored in the node?
Because multiple keys map to the same bucket (e.g., hash("apple") % N == hash("ant") % N), we cannot rely solely on the array index to locate a value. Storing the key allows node-by-node comparisons during lookup, update, and deletion.

---

Hash Table Operations Under Linked List Chaining

1. Insertion (Put)

To insert a key-value pair (k, v):

1. Pass k to the hash function to compute the target bucket index: i = hash(k) % capacity.
2. Access the linked list at buckets[i].
3. Decide on the node placement strategy.

Placement Strategies and Trade-offs

Strategy	Time Complexity	Pros	Cons
Insert at Head	$O(1)$	Fastest write path; immediate pointer reassignment.	Risk of duplicate keys if existence is not checked first.
Insert at Tail	$O(1)$ (with tail pointer) or $O(L)$	Preserves insertion order across collisions.	Requires maintaining a tail pointer per bucket or traversing the list.
Sorted / Ordered Insert	$O(L)$	Keeps nodes lexicographically sorted for ordered traversals.	Requires traversing on every insertion to locate the correct spot.

flowchart TD
    A[Incoming Key-Value Pair] --> B[Compute Bucket Index: hash mod N]
    B --> C{Key already exists in chain?}
    C -- Yes --> D[Update Value in Place]
    C -- No --> E{Insertion Strategy}
    E -- Head Insertion --> F[Point New Node to Head -> Update Bucket Head]
    E -- Tail Insertion --> G[Append to Tail Pointer]
    E -- Sorted Insertion --> H[Traverse and Insert in Correct Lexical Order]

Handling Duplicate Keys:
In production implementations, a put(k, v) operation typically searches the chain first. If key k is already present, it updates the existing node’s value in place. If k is absent, it inserts the new node (typically at the head).

2. Deletion (Remove)

Deleting a key k requires locating the node and rewiring the pointers around it:

1. Compute i = hash(k) % capacity in $O(1)$ time.
2. Traverse the linked list starting from buckets[i].head.
3. Maintain a reference to prev_node while traversing.
4. When current_node->key == k is found:
   • If current_node == head, update buckets[i].head = current_node->next.
   • Else, update prev_node->next = current_node->next.
5. Free the memory allocated for current_node.

bool delete_key(HashTable *table, void *key, int (*cmp)(void*, void*)) {
    size_t idx = hash(key) % table->capacity;
    Node *curr = table->buckets[idx].head;
    Node *prev = NULL;

    while (curr != NULL) {
        if (cmp(curr->key, key) == 0) {
            if (prev == NULL) {
                table->buckets[idx].head = curr->next;
            } else {
                prev->next = curr->next;
            }
            free(curr);
            return true;
        }
        prev = curr;
        curr = curr->next;
    }
    return false;
}

3. Lookup (Get)

Lookup mirrors the search phase of deletion:

1. Compute i = hash(k) % capacity ($O(1)$).
2. Sequentially scan the linked list at buckets[i] until a node matches key k.
3. Return the associated value, or NULL if the end of the list is reached.

---

Performance Degradation and Load Factors

If the hash function distributes keys uniformly across the array, the average chain length is defined by the load factor $\alpha$:

$\alpha = \frac{N}{M}$

Where:

• $N$ is the total number of elements in the hash table.
• $M$ is the capacity (number of buckets) of the array.

The $O(N)$ Pathological Case

When $\alpha$ remains small (e.g., $\le 0.75$), lookup and deletion operations take $O(1 + \alpha) \approx O(1)$ time. However, two scenarios can trigger catastrophic degradation to $O(N)$:

1. A Poor Hash Function: Keys clump into a single bucket, collapsing the hash table into a single linked list.
2. High Load Factor Without Resizing: Storing thousands of keys in a small, fixed-capacity array (e.g., 4,000 keys across 4 buckets yields an average chain length of 1,000 nodes per bucket).

To prevent this, dynamic hash tables trigger a rehash/resize operation when $\alpha$ crosses a predefined threshold, doubling the array capacity and redistributing the chains.

---

Chaining with Self-Balancing Binary Trees

In scenarios where the bucket array cannot be dynamically resized (e.g., memory-constrained embedded environments or strictly bounded capacity), or when an adversarial workload creates deliberate hash collisions, using linked lists creates severe lookup bottlenecks.

To solve this, buckets can use a self-balancing binary search tree (such as a Red-Black Tree or AVL Tree) instead of a singly linked list.

Bucket Array
+-------+
|   0   | --->      [ Node B ]
+-------+          /          \
|   1   |   [ Node A ]      [ Node C ]
+-------+
|   2   | ---> null
+-------+

Complexity Comparison

Operation	Singly Linked List (Average)	Singly Linked List (Worst Case)	Self-Balancing BST (Worst Case)
Search / Lookup	$O(1)$	$O(L)$	$O(\log L)$
Insertion	$O(1)$ (at head)	$O(L)$ (with deduplication)	$O(\log L)$
Deletion	$O(1)$	$O(L)$	$O(\log L)$

(Where $L$ is the number of colliding elements in that specific bucket.)

Trade-Offs of Tree-Based Chaining

1. Guaranteed Upper Bounds: Even if 1,000 elements collide in a single bucket, a balanced tree restricts lookup depth to approximately $\log_2(1000) \approx 10$ pointer traversals, compared to up to 1,000 sequential comparisons in a linked list.
2. Higher Insertion / Deletion Cost: Inserting into a balanced tree requires balancing rotations and color flips, making writes more computationally expensive than prepending to a linked list.
3. Memory Footprint: Tree nodes require extra metadata (left child pointer, right child pointer, parent pointer, and balance factor/color bit), which increases memory usage per key-value entry.
4. Cache Locality: Neither structure offers the cache locality of flat open-addressing arrays, but tree nodes with multiple child pointers increase cache misses during traversal.

Real-World Application:
This hybrid strategy is notably utilized in modern runtimes (such as Java’s HashMap). When a bucket’s chain length exceeds a specific threshold (e.g., 8 elements), the linked list converts into a Red-Black Tree. If removals drop the bucket size below a lower threshold (e.g., 6 elements), it converts back into a singly linked list to conserve memory.

---

Key Architectural Takeaways

• Collisions are structural: Hashing inherently compresses a large key domain into a smaller index range; collisions must be handled by design.
• Singly linked lists excel for low collision rates: Head insertion provides $O(1)$ write speeds with minimal structural overhead.
• Beware of unbounded chains: High collision rates degrade lookups to linear scans ($O(L)$), negating the primary benefit of using a hash table.
• Self-balancing trees offer bounded resilience: When array resizing is impossible or high collision rates are anticipated, self-balancing search trees bound worst-case search and deletion times to $O(\log L)$.