Course contentsShow
← Computer Science
Lesson 419 of 2,87210. Hash TablesFree lesson

Separate Chaining: Concept

Introduction to separate chaining where each bucket stores a linked list of colliding elements.

Separate Chaining: Concept

What you'll learn: How separate chaining resolves hash collisions by letting each bucket hold multiple elements in a linked list.

The Problem: Multiple Keys, Same Bucket

You already know that collisions happen when two different keys hash to the same index. Now we need a strategy to handle them. Separate chaining is one of the most straightforward solutions.

How Separate Chaining Works

Instead of storing just one element per bucket in your hash table, each bucket holds a linked list. When a collision occurs, you simply add the new element to that bucket's list.

Think of it like a filing cabinet with drawers (buckets). Normally you'd put one folder per drawer. But if two folders belong in the same drawer based on your filing system (hash function), you just stack them inside that drawer rather than forcing one into a different drawer.

The Structure

  • The hash table is an array of pointers
  • Each array element points to the head of a linked list (or is nullptr if empty)
  • When inserting: hash the key, go to that bucket, insert into its linked list
  • When searching: hash the key, go to that bucket, traverse its linked list to find the element
  • When deleting: hash the key, go to that bucket, delete from its linked list

Why It Works

Separate chaining completely eliminates the "what do I do when the spot is taken?" problem. There's always room—you just grow the list. If your hash function distributes keys well, most lists stay short (ideally just 1 element), keeping operations fast.

Key Takeaway: Separate chaining resolves collisions by storing a linked list at each hash table bucket, allowing multiple elements to coexist at the same index without conflict.