Hash Table Implementation in Python

This article deals with implementing Hash Table using Python programming language. Hash Table is a data structure where data are stored in an associative manner (in key, value format). The key/index is unique. This kind of storage makes it easier to find the data later on.

Hash Table stores data into an array format. It uses a hashing function that generates a slot or an index to store/insert any element or value.

We will be creating our own hashing function and hash table. Perfect hashing or perfect hash function is the one which assigns a unique slot for every key value. Sometimes, there can be cases where the hash function generates the same index for multiple key values. The size of the hash table can be increased to improve the perfection of the hash function.

Implementation of code in python is here 

Collision

A collision occurs when two items/values get the same slot/index, i.e. the hashing function generates same slot number for multiple items. If proper collision resolution steps are not taken then the previous item in the slot will be replaced by the new item whenever the collision occurs.

Collision Resolution

There are generally two ways to resolve a collision:

1. Linear Probing
2. Chaining

1. Linear Probing

One way to resolve collision is to find another open slot whenever there is a collision and store the item in that open slot. The search for open slot starts from the slot where the collision happened. It moves sequentially through the slots until an empty slot is encountered. The movement is in a circular fashion. It can move to the first slot while searching for an empty slot. Hence, covering the entire hash table. This kind of sequential search is called Linear Probing.

2. Chaining

The other way to resolve collision is Chaining. This allows multiple items exist in the same slot/index. This can create a chain/collection of items in a single slot. When the collision happens, the item is stored in the same slot using chaining mechanism.
While implementing Chaining in Python, we first create the hash table as a nested list (lists inside a list).