Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags

hash table
data structure
hashing
double hashing

What is double hashing?

Educative Answers Team

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

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.

RELATED TAGS

hash table
data structure
hashing
double hashing
Copyright ©2022 Educative, Inc. All rights reserved

Grokking Modern System Design Interview for Engineers & Managers

Ace your System Design Interview and take your career to the next level. Learn to handle the design of applications like Netflix, Quora, Facebook, Uber, and many more in a 45-min interview. Learn the RESHADED framework for architecting web-scale applications by determining requirements, constraints, and assumptions before diving into a step-by-step design process.

Keep Exploring