0% completed
A Hashtable is a data structure that stores key-value pairs and allows fast lookups, insertions, and deletions. It is an essential tool in programming for efficiently managing and retrieving data.
Imagine a locker system where:
- Your name is the key.
- Your belongings are the values.
- A locker number (computed from your name) determines where you store/retrieve items.
Instead of searching through an entire list, a Hashtable calculates an index using a hash function, allowing quick access to values.
Key Characteristics of Hashtables
✅ Fast Lookups (O(1) Time Complexity): Unlike arrays or lists, where searching takes O(n) time, Hashtables can retrieve values in O(1) time on average.
✅ Efficient Insertions & Deletions: Since elements are stored by computed indices, adding and removing elements is quick and efficient.
✅ Unique Keys: Each key is unique, meaning duplicate keys overwrite previous values.
✅ No Guaranteed Order: Unlike arrays or linked lists, Hashtables do not preserve order.
Operations on Hashtable
A Hashtable works by mapping keys to specific indices using a hash function.
This function determines where in an array a particular key-value pair should be stored.
- Key Insertion – The key is passed through a hash function, which generates an index. The value is then stored at that index.
Note: In the next lesson, we will learn more about hash functions.
- Lookup – When searching for a key, the Hashtable computes the index and retrieves the value directly.
- Deletion – The key-value pair is removed by computing the index and clearing that entry.
When to Use a Hashtable?
- Quick lookups (e.g., finding user data from an ID).
- Removing duplicates (e.g., tracking unique users).
- Storing and retrieving configuration settings.
- Fast caching systems (e.g., database indexing).
Table of Contents
Key Characteristics of Hashtables
Operations on Hashtable
When to Use a Hashtable?