A hashtable, also known as a hash map, is a data structure used to store key-value pairs efficiently. It provides average constant time (O(1)) operations for insertion, retrieval, and deletion, making it a fundamental tool in computer science.
A hashtable works by applying a hash function to a key to generate an index where its corresponding value is stored in an internal array. The hash function should ideally distribute keys evenly to reduce collisions.
Collisions occur when multiple keys map to the same index. They are commonly resolved using:
- Chaining: Each array index holds a list of key-value pairs.
- Open Addressing: A new position is found within the array (e.g., linear probing).
Basic operations:
- Insert(key, value): Compute index and add or update the value.
- Get(key): Compute index and retrieve the value.
- Delete(key): Compute index and remove the key-value pair.
Python Example:
python
class HashTable:
def __init__(self, size):
self.size = size
self.table = [[] for _ in range(size)]
def _hash_function(self, key):
return hash(key) % self.size
def insert(self, key, value):
index = self._hash_function(key)
for pair in self.table[index]:
if pair[0] == key:
pair[1] = value
return
self.table[index].append([key, value])
def get(self, key):
index = self._hash_function(key)
for pair in self.table[index]:
if pair[0] == key:
return pair[1]
raise KeyError(f'Key {key} not found')
def delete(self, key):
index = self._hash_function(key)
for i, pair in enumerate(self.table[index]):
if pair[0] == key:
del self.table[index][i]
return
raise KeyError(f'Key {key} not found')
Usage Example:
python
hash_table = HashTable(10)
hash_table.insert('apple', 5)
hash_table.insert('banana', 10)
print(hash_table.get('apple')) # Output: 5
hash_table.insert('apple', 7)
print(hash_table.get('apple')) # Output: 7
hash_table.delete('apple')
# hash_table.get('apple') # Raises KeyError
Hashtables are used in many real-world scenarios such as caches, databases, indexing, and dictionaries. They are implemented as built-in types in many languages, like dict in Python, HashMap in Java, and Map in JavaScript.