Hashing fundamentals #1: Chaining and its implementation with Linked List

Photo by Maria Lysenko on Unsplash

Table of contents:
· What is chaining?
· Chaining performance
· Chaining implementation
· Simple chaining implementation with Linked List in Java

What is chaining?

If you have heard of hashing before, chances are that you know collision is a common challenge in hashing. A collision occurs when different keys are mapped to the same location in a hash table. For example:

Hash table with Linked List chaining illustration

In the example above, the hash function maps different keys to the same slot, for example, key 5 and 10 are mapped to slot 0; key 47, 12 and 22 are mapped to slot 2, resulting in collisions. By chaining the values in the same slot, we can solve the collision problem. It’s important to note that the collision problem can also be handled using another technique — Open Addressing, which I will discuss in another post.

Chaining performance

Assuming that all keys are uniformly distributed in the hash table, the performance of chaining for a random set of keys is as…