search

How to implement a hash table in Python?

To implement a hash table in Python, you can create a class that defines the data structure and provides methods for key-value manipulation. Here's an example implementation of a hash table in Python:

class HashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)]

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

    def insert(self, key, value):
        index = self._hash(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(key)
        for pair in self.table[index]:
            if pair[0] == key:
                return pair[1]
        raise KeyError(f"Key '{key}' not found in the hash table.")

    def remove(self, key):
        index = self._hash(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 in the hash table.")

In this implementation, the HashTable class represents a hash table. It initializes an empty table, which is implemented as a list of lists. Each sublist represents a bucket and can hold multiple key-value pairs that have the same hash value.

The _hash method is used to compute the hash code for a given key. It applies the built-in hash function to the key and performs modulo division to ensure the hash code falls within the range of the table size.

The insert method inserts a key-value pair into the hash table. It computes the hash code of the key, checks if the key already exists in the bucket, and updates the value if so. Otherwise, it appends a new pair to the bucket.

The get method retrieves the value associated with a given key from the hash table. It computes the hash code, searches for the key in the corresponding bucket, and returns the value if found. If the key is not found, a KeyError is raised.

The remove method removes a key-value pair from the hash table based on the given key. It computes the hash code, searches for the key in the bucket, and deletes the pair if found. If the key is not found, a KeyError is raised.

Here's an example of using the hash table implementation:

hash_table = HashTable(10)
hash_table.insert("apple", 5)
hash_table.insert("banana", 10)
hash_table.insert("cherry", 15)

print(hash_table.get("banana"))  # Output: 10

hash_table.remove("apple")
print(hash_table.get("apple"))  # Raises KeyError: Key 'apple' not found in the hash table.

This example demonstrates how to create a hash table, insert key-value pairs, retrieve values based on keys, and remove pairs from the hash table.

Related Questions You Might Be Interested