Skip to main content
Back to path

Welcome to a Grasp lesson

Create a free account to keep studying and create your own study path.

Lesson 34

Non-Thread-Safe Hash Table Operations

Recommended resources

Hello! Welcome back.

In our previous lesson, we designed the complete architecture for a generic, non-thread-safe hash table using separate chaining. We defined the C structs (ch_node, ch_hash), established the pattern of using function pointers (key_ops, val_ops) for generic data handling, and discussed the importance of a good hash function.

Today, we will bring that blueprint to life. This lesson is entirely focused on implementing the core operations for our hash table: insert, lookup, and delete. By building a correct, functional, but non-thread-safe version first, we establish a solid baseline that we can then make concurrent in the upcoming lessons.

The Core Logic of a Chained Hash Table

As a quick refresher, our hash table structure consists of an array of "buckets," where each bucket is a pointer to the head of a linked list. All operations begin by finding the correct bucket for a given key.

Hash Table Implementation with Separate Chaining
A visual representation of our goal: an array where each index points to a linked list of nodes. Operations will involve finding the right bucket and then traversing its associated list.

The logic for insert, lookup, and delete all share a common first step: hashing the key to find a bucket, and then traversing the linked list at that bucket.

For a practical demonstration of how these operations work on a hash table with separate chaining, let's turn to a video walkthrough.

Understanding and implementing a Hash Table (in C)

This segment from Jacob Sorber's video on hash tables demonstrates how to adapt the insert, lookup, and delete logic to handle collisions using separate chaining (linked lists).

Please watch from 20:25 to 24:18. Focus on how each of the three main functions (insert, lookup, delete) is modified to traverse the linked list at the target bucket. This provides an excellent dynamic view of the algorithms we're about to implement.

Now, let's translate this into a robust C implementation based on the generic design from our last lesson. We'll examine the logic for each operation one by one.

A Complete Implementation

The following article provides a clean, well-explained implementation of a hash table that closely matches our design goals. It handles key/value updates, memory management, and all the edge cases of linked list manipulation.

a simple hash table in C - Leo Robinovitch @ The Leo Zone

This article, 'a simple hash table in C' by Leo Robinovitch, provides a concise and complete implementation of the functions we need to build. We will be studying its approach to insert, lookup, and delete.

Please read the sections titled 'Associating a key and value' (for the HashTable_set function), 'Looking up values by key' (for HashTable_get), and 'Deleting entries' (for HashTable_delete). As you read, compare the code to the algorithms described below.

Let's dissect the logic for each of these functions.

1. Lookup (HashTable_get)

Looking up a key is the most straightforward operation.

Algorithm:

  1. Calculate the key's hash and use the modulo operator to find the bucket index.
  2. Get the pointer to the head of the linked list at buckets[index].
  3. If the pointer is NULL, the key doesn't exist. Return NULL.
  4. If the list is not empty, traverse it node by node.
  5. In each node, use your key comparison function (e.g., strcmp for strings, or key_ops.eq in our generic design) to check if the node's key matches the search key.
  6. If a match is found, return the pointer to the value stored in that node (v->val).
  7. If you reach the end of the list without finding a match, the key is not in the table. Return NULL.

The HashTable_get function in the recommended reading implements this logic perfectly.

2. Insertion (HashTable_set)

Insertion must handle two scenarios: the key already exists (an update), or the key is new (an insert).

Algorithm:

  1. Calculate the bucket index for the key.
  2. Traverse the linked list at that index to see if the key already exists.
  3. If a match is found: This is an update.
    • You can simply overwrite the val pointer in the existing node (v->val = new_val).
    • In a more robust system, you would first free the old value (val_ops.free(v->val)) before assigning the new one.
  4. If no match is found: This is an insert.
    • Allocate memory for a new Entry (or ch_node).
    • Create a persistent copy of the key and value on the heap (using strdup or our key_ops.cp and val_ops.cp functions).
    • Set the next pointer of the new node to point to the current head of the list (h->buckets[bucket]).
    • Update the bucket to point to the new node, making it the new head of the list (h->buckets[bucket] = new_node). This is called "prepending."
    • Increment the hash table's size counter.

This process of inserting new elements is visualized below.

Hash Table Insertion with Separate Chaining
This diagram shows keys being inserted. When a key hashes to an index that is already occupied (e.g., inserting 85 after 50, both at index 1), the new element is added to the linked list at that index.

The HashTable_set function from the article implements this combined insert/update logic.

3. Deletion (HashTable_delete)

Deletion is the most complex operation because it requires careful manipulation of the linked list pointers to remove a node without breaking the chain.

Algorithm:

  1. Calculate the bucket index for the key.
  2. Traverse the linked list, but this time you must keep track of both the current node and the previous node.
  3. When you find the node to delete:
    • Case 1: The node is the head of the list (previous == NULL).
      • Update the bucket pointer to point to the next node in the list: h->buckets[bucket] = current->next;.
    • Case 2: The node is in the middle or at the end of the list.
      • Update the next pointer of the previous node to skip over the current node: previous->next = current->next;.
  4. After unlinking the node, you must free all memory associated with it:
    • Free the memory for the key (e.g., free(current->key) or key_ops.free(current->key)).
    • Free the memory for the value if your design requires it (val_ops.free(current->val)).
    • Free the memory for the node struct itself (free(current)).
  5. Decrement the hash table's size counter.

The HashTable_delete function in the article correctly handles these cases.

Test your understanding!

Imagine you have a hash table with TABLE_SIZE = 5. You are using a simple string hash function: hash(key) = strlen(key). Your operations are:

  1. insert("cat", "meow")
  2. insert("bee", "buzz")
  3. insert("wolf", "howl")
  4. insert("cat", "purr")
  5. delete("bee")

Describe the final state of bucket 3 and bucket 4. strlen("cat") is 3, strlen("bee") is 3, and strlen("wolf") is 4.

Show answer
  1. insert("cat", "meow"): strlen("cat") is 3. hash % 5 is 3 % 5 = 3. Bucket 3 now points to a node ("cat", "meow").
  2. insert("bee", "buzz"): strlen("bee") is 3. hash % 5 is 3. A collision occurs. The new node ("bee", "buzz") is prepended to the list. Bucket 3 now points to ("bee", "buzz"), which points to ("cat", "meow").
    • State of Bucket 3: ("bee", "buzz") -> ("cat", "meow") -> NULL
  3. insert("wolf", "howl"): strlen("wolf") is 4. hash % 5 is 4. Bucket 4 now points to a node ("wolf", "howl").
  4. insert("cat", "purr"): strlen("cat") is 3. The set function finds the existing "cat" node and updates its value. The list structure doesn't change.
    • State of Bucket 3: ("bee", "buzz") -> ("cat", "purr") -> NULL
  5. delete("bee"): The delete function finds the "bee" node. Since it's the head of the list in bucket 3, it updates the bucket pointer to point to the next element ("cat").

Final State:

  • Bucket 3: Points to the node ("cat", "purr"), which then points to NULL.
  • Bucket 4: Points to the node ("wolf", "howl"), which then points to NULL.

Conclusion

In this lesson, you have learned how to implement the three fundamental operations for a non-thread-safe hash table using separate chaining.

Key Takeaways:

  • Lookup (get) involves hashing to find the right bucket and then traversing a linked list to find the key.
  • Insertion (set) is a two-part process: first search for the key to see if it's an update, and if not, create a new node and prepend it to the linked list.
  • Deletion (delete) requires careful pointer manipulation to unlink a node from its list, with special handling for deleting the head node.
  • Proper memory management is crucial: mallocing nodes and copying data on insert, and freeing them on delete.

Preview of the Next Lesson:
We now have a complete, working hash table. However, if multiple threads try to insert or delete at the same time, we will encounter race conditions and corrupt our data structure. In the next lesson, we will finally introduce threading by designing a fine-grained locking strategy for the hash table using one mutex per bucket, making our data structure thread-safe.