How to implement a hash table in Python?

Question

Jayant Kumar · Accepted Answer

Table of Contents
Introduction
A hash table is a data structure that provides efficient insertion, deletion, and lookup operations. It uses a hash function to map keys to indices in an underlying array. Understanding how to implement a hash table in Python can enhance your knowledge of data structures and improve the performance of various algorithms.
1. Key Concepts
Hash Table Basics

Hash Function: Converts a key into an index in the hash table. It should distribute keys uniformly to minimize collisions.
Collision Handling: Techniques like chaining (linked lists) or open addressing (probing) handle cases where multiple keys hash to the same index.
Load Factor: Ratio of the number of elements to the size of the hash table. It affects performance and determines when to resize the table.

Operations

Insertion: Add a key-value pair to the hash table.
Deletion: Remove a key-value pair from the hash table.
Lookup: Retrieve a value associated with a key.

2. Python Implementation
Hash Table Class
Here's a basic implementation of a hash table using chaining for collision handling:
class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]  # List of lists for chaining

def _hash(self, key):
        return hash(key) % self.size

def insert(self, key, value):
        index = self._hash(key)
        bucket = self.table[index]
        
        # Check if key already exists and update its value
        for i, kv in enumerate(bucket):
            if kv[0] == key:
                bucket[i] = (key, value)
                return
        
        # Key does not exist, insert new key-value pair
        bucket.append((key, value))

def get(self, key):
        index = self._hash(key)
        bucket = self.table[index]
        
        for kv in bucket:
            if kv[0] == key:
                return kv[1]
        
        raise KeyError(f"Key {key} not found")

def delete(self, key):
        index = self._hash(key)
        bucket = self.table[index]
        
        for i, kv in enumerate(bucket):
            if kv[0] == key:
                del bucket[i]
                return
        
        raise KeyError(f"Key {key} not found")

# Example Usage
ht = HashTable()
ht.insert("name", "Alice")
ht.insert("age", 30)
ht.insert("city", "New York")

print("Name:", ht.get("name"))  # Output: Name: Alice
print("Age:", ht.get("age"))    # Output: Age: 30

ht.delete("city")
try:
    print("City:", ht.get("city"))
except KeyError as e:
    print(e)  # Output: Key city not found

Explanation

Initialization: Creates a table with a specified size, where each slot is a list for chaining.
Hash Function: Uses Python's built-in hash() function and modulo operation to determine the index.
Insertion: Adds key-value pairs to the appropriate bucket or updates existing keys.
Lookup: Retrieves values based on keys by searching the corresponding bucket.
Deletion: Removes key-value pairs from the appropriate bucket.

3. Advanced Considerations

Resizing: To maintain efficiency, the hash table should be resized (doubled) when the load factor exceeds a certain threshold. This involves rehashing all existing keys.
Open Addressing: An alternative to chaining, where collisions are resolved by probing for the next available slot.

Conclusion
Implementing a hash table in Python involves creating a structure with efficient insertion, deletion, and lookup operations. By understanding and applying hash functions, collision handling, and resizing strategies, you can build a robust hash table suited to various applications. The provided code example demonstrates the fundamental concepts and can be extended or optimized based on specific requirements.

How to implement a hash table in Python?

Similar Questions