Hash Collision

Hash collision is when the hash function generates the same index for multiple keys.

There are 2 possible ways to cope with the collision:

• Open Addressing;
• Collision resolution by chaining.

Open Addressing

In this type of problem-solving, each free slot of the hash table will be filled with elements that create a collision.

In this case, the hash table won’t be so helpful as if we place our collision element as the last element of the hash table, the time needed to find the element will be O(n).

We were trying to cope with that problem but received the same time complexity.

Don’t worry! We have one more solver!

Collision resolution by chaining

The hash table is transformed into the linked list array in this case.

The time needed to cope with this task O(n/k) (k - the number of ‘rows' in the hash table).

As the k is constant due to the rules, the time complexity is written O(n).

You probably don’t understand why did I say that hash tables are better than a linked list?

But in this case, the time spent to check the file with O(n/k) time complexity will be a better option than the O(n). It sounds OK, but we are still not sure if we need to perform so many actions to receive almost the same we received with the simple linked list.

But in a linked list, the time complexity is O(n) on average, but in the hash table, O(n) is the worst case, so the hash table is sometimes better than a linked list.

Nice hash function:

• Makes use of all info provided by key;
• Uniformly distributes output across the table;
• Maps similar keys to very different hash values;
• Uses only fast operations.

If we follow these rules, we will receive a fast-working hash table and save our hash function from the worst O(n) case and receive O(1) as the best option!