Thread-Safe Hash Table Deletion

The Single-Threaded Delete Algorithm

Before we tackle the concurrency aspects, let's first solidify our understanding of the standard, single-threaded algorithm for deleting a node from a hash table's collision chain (a linked list).

The logic involves two main cases:

1. Deleting the head of the list: If the node to be deleted is the first one in the bucket, we must update the bucket's head pointer to point to the next node.
2. Deleting from the middle or end: If the node is elsewhere in the list, we need to "skip over" it by changing the next pointer of the previous node to point to the next pointer of the node we are deleting. This requires keeping track of the previous node as we traverse the list.

The following video provides an excellent walkthrough of this C implementation.

This single-threaded logic forms the heart of our operation. Now, let's make it thread-safe.

Implementing a Thread-Safe delete Operation

As with insert and lookup, we must protect the operation with the appropriate per-bucket lock. The entire process—from finding the node to unlinking it from the list—is a critical section. If we don't hold the lock for the entire duration, we risk severe bugs:

• Another thread could be looking up the node we are deleting, leading to a use-after-free error.
• Another thread could be inserting a new node at the head while we are modifying the same head pointer, leading to a lost update.
• Two threads could attempt to delete adjacent nodes simultaneously, leading to list corruption.

Therefore, the thread-safe algorithm is:

1. Calculate the bucket index for the given key.
2. Acquire the lock for that specific bucket.
3. Traverse the list using current and previous pointers to find the target node.
4. If the node is found, unlink it by updating either the bucket's head pointer or previous->next.
5. Release the lock.
6. Free the memory associated with the now-unlinked node.

The "Unlock-then-Free" Pattern

Pay close attention to steps 5 and 6. We release the lock before freeing the memory. This might seem counterintuitive, but it's a key optimization pattern in concurrent programming.

• Is it safe? Yes. The critical part is unlinking the node from the list. Once table->buckets[index] or previous->next is updated (inside the critical section), no other thread traversing the hash table can ever reach this node again. The only remaining pointer to the node is in our local current variable. It is now private to our thread, so we can safely free it without a lock.

• Why is it better? The free() function can sometimes be a blocking or time-consuming call, as it may need to interact with the memory manager's internal data structures. By moving free() outside the critical section, we minimize the amount of time the lock is held. This reduces lock contention and allows other threads waiting for that bucket's lock to proceed sooner, improving overall application throughput.

Let's integrate this pattern into a full implementation.

// A thread-safe HashTable_Delete implementation
// The function returns the value of the deleted item, or -1 if not found.
int HashTable_Delete(HashTable* table, const char* key) {
    unsigned int index = hash(key) % TABLE_SIZE;
    Node* prev = NULL;
    Node* current = NULL;
    int value = -1; // Value of the node to be deleted

    // 1. Acquire the lock
    pthread_mutex_lock(&table->locks[index]);

    // 2. Find the node to delete
    current = table->buckets[index];
    while (current != NULL) {
        if (strcmp(current->key, key) == 0) {
            break; // Found the node
        }
        prev = current;
        current = current->next;
    }

    // 3. If found, unlink it from the list
    if (current != NULL) {
        if (prev == NULL) {
            // It's the head of the list
            table->buckets[index] = current->next;
        } else {
            // It's in the middle or at the end
            prev->next = current->next;
        }
        // Save the data we need before freeing the node
        value = current->value;
    }

    // 4. Release the lock
    pthread_mutex_unlock(&table->locks[index]);

    // 5. Free the memory (if a node was unlinked)
    if (current != NULL) {
        free(current->key); // We must free the duplicated key
        free(current);      // And the node itself
    }

    return value;
}

This implementation correctly and efficiently removes an element from our concurrent hash table.

// Alternative implementation
// ... (lock and find the node as before) ...
if (current != NULL) {
    if (prev == NULL) {
        table->buckets[index] = current->next;
    } else {
        prev->next = current->next;
    }
    // Free memory BEFORE unlocking
    free(current->key);
    free(current);
}
pthread_mutex_unlock(&table->locks[index]);
// ...

Conclusion

Congratulations! You have now implemented all three fundamental operations—insert, lookup, and delete—for a thread-safe hash table using a fine-grained, per-bucket locking strategy.

Key Takeaways:

• Deleting from a shared linked list is a critical section that must be protected by a lock to prevent list corruption and use-after-free errors.
• The deletion logic must handle two cases: removing the head of the list and removing a node from the middle/end.
• The "unlock-then-free" pattern is a common and important optimization. It is safe because the node is completely unlinked from the shared data structure before the lock is released, making the subsequent free operation a local action. This pattern minimizes lock hold time and improves concurrency.

Preview of the Next Lesson:
Our current hash table works beautifully, but it has one major limitation: its size is fixed. What happens if we insert so many items that the collision chains become very long, degrading performance to that of a simple linked list? The answer is to resize the table. However, a resize operation potentially needs to move every single element to a new bucket. How can we do this safely when multiple threads are active? This will require us to analyze when a global lock might be necessary, which will be the focus of our next lesson.