Separate Chaining

This method, which is also known as open hashing, implements a linked list to store colliding elements.

Open Addressing

Instead of using a separate data structure like a linked list to store colliding elements, open addressing (or closed hashing) stores all elements in the hash table array. To store, retrieve, and remove colliding elements, this method employs different probing techniques.

Linear Probing

Hash table is probed sequentially till a free slot is found: [hash(input) + c] mod table_size. The simplest form of linear probing is where c = 1. This method suffers from primary clustering - colliding elements occupy the next available slot and cluster in specific regions.

Quadratic Probing

Increments for the probing sequence are computed by taking the square of the occupied index position until a free slot is found in the hash table: [hash(input) + occupied_index + occupied_index^2] mod table_size. This method suffers from secondary clustering - different colliding elements follow the same probing sequence and lead to repeated collision patterns.

Double Hashing

Increments for the probing sequence are computed using a different hash function for optimal cluster reduction: [hash(input) + [occupied_index * hash_2(input)]] mod table_size

Coalesced Hashing

This is a hybrid approach that leverages separate chaining to link colliding elements but stores the linked elements within the hash table array like open addressing.

Rehashing

Resize the hash table (usually by doubling) and recompute element positions to reduce collisions.

Perfect Hashing

For a set of static keys (no insertions, deletions) that are already known, a random hash function can be found, based on the keys, to ensure that no collisions will occur. This helps achieve constant worst-case access time.

A Brief on Collision Resolution

Table of contents