What is double hashing?

Double hashing is a technique used for avoiding collisions in hash tables.

A collision occurs when two keys are hashed to the same index in a hash table. Collisions are a problem because every slot in a hash table is supposed to store a single element.

The hashing technique

A normal hashing process consists of a hash function taking a key and producing the hash table index for that key.

In double hashing, there are two hash functions. The second hash function is used to provide an offset value in case the first function causes a collision.

The following function is an example of double hashing:

(firstHash(key) + i * secondHash(key)) % tableSize 

In the computation above, the value of i will keep incrementing (the offset will keep increasing) until an empty slot is found.

1 of 10

Why use double hashing?

  • Double hashing is useful if an application requires a smaller hash table since it effectively finds a free slot.

  • Although the computational cost may be high, double hashing can find the next free slot faster than the linear probing approach.

Copyright ©2024 Educative, Inc. All rights reserved