Hashtable

A Hashtable is my favourite data structure, as it allows efficient access to values based on unique keys. It usually offers constant time complexity for lookups.

Introduction:

A Hashtable is a data structure that implements an associative array abstract data type, a structure that can map keys to values. It uses a hash function to compute an index into an array of buckets or slots.

Properties:

• Keys in a Hashtable are unique.
• Each key is associated with a single value.
• Insertion, deletion and retrieval operations are generally of time complexity O(1).
• The collision is resolved by using various techniques such as chaining and open addressing.

Steps in the algorithm:

1. Check if the key is present.
2. If the key is not present, then insert the new key-value pair as a new entry.
3. If the key is present, update the corresponding value.
4. If a collision occurs (i.e., two different keys hash to the same index), use a collision resolution technique to resolve it.

Image:

Links

For more information? The link is here