Collisions: Chaining

Intermediate Algorithms and Data Structures English

Also available: Deutsch

Created by Best · 16.08.2026 at 09:13 UTC

Chaining stores colliding entries in a list (or a tree) per bucket. Insertion depends on the structure of the bucket.

Advantage: simple deletion logic. Disadvantage: additional pointers and poor cache locality with long chains.

Strategy	Where the entry sits	Deletion
Chaining	inside the bucket structure	local in the chain
Open addressing	later slot in the table	needs a tombstone
## Where used

Classic HashMap buckets (historically lists, today often trees beyond a threshold). Understanding chaining explains worst-case behavior and attacks with colliding keys.

Depth

In chaining, each table slot points to a collection of all entries that land there. Searching, inserting, and deleting first handle the index and only then work on this local collection. Lists are simple, but for long chains, other structures can also be sensible.

If the distribution is adequate, the average chain length is controlled by the load factor. In the worst case, however, many keys accumulate at one location, and the search approaches a linear examination. Chaining tolerates an occupancy above the table length because buckets can hold multiple entries.

Difficulty levels

Handle a collision by inserting into a bucket list.
Relate expected chain length to the load factor.
Analyze the degenerate case of a poor hash function.

Pitfalls

When updating, an already equal key must not be blindly appended as a second entry. Another mistake is to only check the hash value and not the key equality.

University approvals: 0

Tasks

Question 1

Where are colliding keys located in Chaining?

In different tables

In the same bucket structure

Only on the stack

Only in TreeMap

Question 2

What happens with chaining when a hash function assigns almost all keys to the same index?

The local search can approach a linear search.

Collisions disappear after the first insertion.

Each access remains constant regardless of the chain length.

The table automatically sorts all keys globally.

Question 3

Implement a bucket with chaining. insert adds values, contains searches linearly in the list.

Hint

List<Integer> provides add(value) and contains(value). Autoboxing converts int to Integer.

import java.util.ArrayList;
import java.util.List;

class ChainBucket {
  private final List<Integer> values = new ArrayList<>();

  void insert(int value) {
    // TODO
  }

  boolean contains(int value) {
    // TODO
    return false;
  }
}

Starter code is prefilled; replace TODO blocks with your solution.

Runtime output (stdout/stderr)

1 test case will be used for grading

Run checks runtime behavior only. Final correctness is evaluated when you submit.

Card Info

Topic: Algorithms and Data Structures
Difficulty: Intermediate
Completed: 0 users

Creator

Best

BestBuddy