In hashing, hash key is calculated in O(1) time complexity and the required location in hash table is accessed in O(1).

Insertion: In average case, while insertion, hash code of key is generated in O(1). The last node of list is also reached in constant time. Hence, creation of new node and insertion in required location is done in constant time.

Deletion: In average case, node to be deleted can be reached in constant time. Hence deletion takes place in O(1) complexity.

Searching: Calculation of hash code and finding the location in hash table takes constant time. Even if hash tables employs chaining to resolve collision, let total number of elements be n and size of hash map be m, then size of each chain will be n/m. As n/m is a fixed value, in average case, searching in hashing takes O(1) complexity.

Hence, all basic operations in average case take O(1) time in hashing.

Hashing Techniques

Static Hashing: Static hashing is a technique that involves dividing the hash table into a fixed number of slots or buckets during initialization. Each slot can store one or more key-value pairs. The hash function maps the keys to specific slots in the hash table.

In the above diagram, the hash table is divided into three slots: Slot 0, Slot 1, and Slot 2. Each slot can store key-value pairs. The hash function determines the slot for a given key. For example, if the hash function maps Key A to Slot 0, then the corresponding key-value pair will be stored in Slot 0.

Dynamic Hashing: Dynamic hashing is a technique that allows the hash table to resize and reorganize itself dynamically based on the number of keys being stored. It helps to minimize collisions and improves the overall efficiency of the hash table.

In the above diagram, the hash table initially has two buckets: Bucket 0 and Bucket 1. As more key-value pairs are added, and if a certain threshold is reached (e.g., the number of keys per bucket exceeds a predefined limit), the hash table dynamically resizes itself. In this case, it splits the overloaded bucket into two new buckets: Bucket 2 and Bucket 3.

The hash function determines which bucket a key-value pair belongs to. When the hash table is resized, the hash function is updated accordingly to distribute the keys evenly across the new buckets.

Dynamic hashing allows for more flexibility as the hash table adapts to accommodate a varying number of keys efficiently.