Collisions in Hash Tables

This lesson is about how collisions occur, and the common strategies like Linear Probing, Chaining, and Re-sizing array used in resolving them.

🔍 What is Collision?

As we know, Hash functions generate an index corresponding to every key, so it is accessed in O(1). There are times when the Hash function generates the same index of the array for two different keys; this causes the collision.

For Example:

Let’s say we are storing phone numbers as keys, but each number (e.g. 1-123-123) is too large itself to be stored as a key, or in another way, to be used in an array’s index. It is passed to the hash function, (which performs certain calculations) and the index is returned:

1+123+123=2471+123+123 = 247

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.