Hash index equality mock concept in Python
A simple hash index class in Python that stores key-value pairs in buckets and demonstrates basic equality-based lookup.
Python code
35 linesclass HashIndex:
def __init__(self):
self._buckets = {}
def insert(self, key, value):
"""Insert a key-value pair into the hash index."""
index = hash(key) % 10
if index not in self._buckets:
self._buckets[index] = []
self._buckets[index].append((key, value))
def lookup(self, key):
"""Retrieve the value associated with a key."""
index = hash(key) % 10
if index in self._buckets:
for stored_key, stored_value in self._buckets[index]:
if stored_key == key:
return stored_value
return None
def __repr__(self):
return f"HashIndex(buckets={self._buckets})"
if __name__ == "__main__":
index = HashIndex()
index.insert("apple", 5)
index.insert("banana", 8)
index.insert("orange", 3)
index.insert("apple", 12) # Duplicate key, stored as separate entry
print(index.lookup("apple"))
print(index.lookup("banana"))
print(index.lookup("missing"))
print(index)
Output
12
8
None
HashIndex(buckets={6: [('banana', 8)], 7: [('apple', 5), ('apple', 12), ('orange', 3)]})
How it works
The class uses Python's built-in hash() function to compute a bucket index by taking the modulo of the hash value with 10. Each bucket is a list of key-value tuples, and inserting appends to the bucket. Lookup scans the bucket and compares stored keys with the target key using ==, returning the first matching value. Note that duplicate keys are stored as separate entries, so the lookup returns the most recently inserted value that matches.
Common mistakes
- Assuming hash keys are unique; using modulo can cause collisions.
- Not handling duplicate keys; inserting the same key multiple times creates multiple entries.
- Using mutable keys that change hash value after insertion, breaking lookups.
Variations
- Use a dictionary of lists with chaining and store the latest value on duplicate insert.
- Implement open addressing instead of chaining to handle collisions.
Real-world use cases
- Simulating database index behavior for query planning and optimization testing.
- Teaching hash table fundamentals in a computer science course.
- Building a simple in-memory key-value store for prototyping or small-scale caching.
Sponsored
More from Database scaling & optimization
- Approximate Count with HyperLogLog in Python medium
- B-Tree Insert and In-Order Traversal in Python hard
- Broadcast a Small Reference Table in Python easy
- Build a Full Text Search Index in Python medium
- Build a Partial Index Mock in Python for Database Filtering easy
- Composite index leftmost prefix in Python medium
Keep learning
Related tutorials and quizzes for this topic.