Hash Collison

Palistha
1 min readMay 4, 2022

--

Technically, the data we put in the hash table is optimized to be evenly distributed in our memory(until available). However, sometimes, there may be a situation where two or more keys generate the same hash value.

Generating Hash value form Hash function

It means two or more data will be stored in the same memory location. This is known as a collision. Here, USA and Canada has same hash value.

Collison

The collision occurs when different keys point to one memory location. We cannot avoid a collision.

Hash Collision

As you can see keys USA and Canada are stored in the same memory location 98216.

How does collision affect time complexity?

In the case of a collision, we cannot directly access the data in the hash table. So the time complexity of the hashtable to access the data will not be O(1) anymore. The time complexity to access the data in the hash table becomes O(n).

In case you don’t know about time complexities: Big O in Simple Words.

--

--

Palistha
Palistha

Written by Palistha

Learning and Sharing Everyday

No responses yet