How to Implement Hash Table in Python: Simple Guide

In Python, you can implement a hash table using a dictionary which stores key-value pairs with fast lookup. To build one from scratch, create a class that uses a list of buckets and a hash function to store and retrieve values efficiently.

Syntax

A basic hash table implementation involves these parts:

• Class definition: To create a hash table object.
• Hash function: Converts keys to an index.
• Buckets: A list to hold key-value pairs.
• Insert method: Adds key-value pairs.
• Get method: Retrieves values by key.

python

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

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

    def insert(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

Example

This example shows how to create a hash table, add key-value pairs, and retrieve values by keys.

python

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

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

    def insert(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

# Create hash table
ht = HashTable()

# Insert key-value pairs
ht.insert('apple', 5)
ht.insert('banana', 3)
ht.insert('orange', 10)

# Retrieve values
print(ht.get('apple'))   # Output: 5
print(ht.get('banana'))  # Output: 3
print(ht.get('grape'))   # Output: None

Output

5
3
None

Common Pitfalls

Common mistakes when implementing hash tables include:

• Not handling collisions properly, which can cause lost data.
• Using a poor hash function that causes many keys to map to the same bucket.
• Not updating existing keys when inserting duplicates.
• Returning incorrect values or errors when keys are missing.

Always check for existing keys in the bucket before adding new pairs and handle missing keys gracefully.

python

class HashTableWrong:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]

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

    def insert(self, key, value):
        index = self._hash(key)
        # Wrong: just appending without checking duplicates
        self.buckets[index].append((key, value))

    def get(self, key):
        index = self._hash(key)
        bucket = self.buckets[index]
        for k, v in bucket:
            if k == key:
                return v
        return None

# Correct way checks for duplicates before inserting

class HashTableRight:
    def __init__(self, size=10):
        self.size = size
        self.buckets = [[] for _ in range(size)]

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

    def insert(self, key, value):
        index = self._hash(key)
        bucket = self.buckets[index]
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

Quick Reference

Hash Table Implementation Tips:

• Use a good hash function (Python's built-in hash() is fine for most cases).
• Handle collisions by storing multiple items in buckets (lists).
• Check for existing keys before inserting to update values.
• Return None or raise an error if key not found.
• Choose bucket size based on expected data volume for efficiency.

Key Takeaways

Use a list of buckets and a hash function to implement a hash table in Python.

Always handle collisions by storing multiple key-value pairs in the same bucket.

Check for existing keys before inserting to update values correctly.

Return None or handle missing keys gracefully when retrieving values.

Python's built-in hash() function is suitable for hashing keys in most cases.