Python: Hash Table Implementation

1. Introduction

A hash table is a data structure that stores key-value pairs. It uses a hash function to compute an index into an array in which an element will be inserted or searched. By using hash tables, we can achieve constant-time average complexity for search operations.

2. Program Overview

In this program, we will:

1. Implement a basic hash table from scratch.

2. Use a simple hash function.

3. Handle collisions using chaining (linked list).

3. Code Program

class HashTable:
    def __init__(self, capacity=50):
        # Initialize the hash table with given capacity
        self.capacity = capacity
        self.size = 0
        self.slots = [None] * self.capacity

    def _hash(self, key):
        # Compute the hash value of a given key
        return hash(key) % self.capacity

    def insert(self, key, value):
        # Insert a key-value pair into the hash table
        key_hash = self._hash(key)
        key_value = [key, value]

        if self.slots[key_hash] is None:
            self.slots[key_hash] = list([key_value])
            self.size += 1
            return True
        else:
            for pair in self.slots[key_hash]:
                if pair[0] == key:
                    pair[1] = value
                    return True
            self.slots[key_hash].append(key_value)
            return True

    def search(self, key):
        # Search for a key in the hash table and return its value
        key_hash = self._hash(key)
        if self.slots[key_hash] is not None:
            for pair in self.slots[key_hash]:
                if pair[0] == key:
                    return pair[1]
        return None

    def delete(self, key):
        # Delete a key-value pair from the hash table
        key_hash = self._hash(key)

        if self.slots[key_hash] is None:
            return False

        for i in range(0, len(self.slots[key_hash])):
            if self.slots[key_hash][i][0] == key:
                self.slots[key_hash].pop(i)
                return True
        return False

# Test the HashTable class
ht = HashTable()
ht.insert("apple", 1)
ht.insert("banana", 2)
ht.insert("orange", 3)

print("Value of apple:", ht.search("apple"))
print("Value of banana:", ht.search("banana"))
print("Value of orange:", ht.search("orange"))

ht.delete("apple")
print("Value of apple after deletion:", ht.search("apple"))

Output:

Value of apple: 1
Value of banana: 2
Value of orange: 3
Value of apple after deletion: None

4. Step By Step Explanation

1. The HashTable class initializes an empty hash table with a specified capacity (default is 50).

2. The _hash method computes the hash of the key, which is used to find an index for storing key-value pairs.

3. The insert method adds key-value pairs to the table. If there's a collision (same index for different keys), the value is added to a list at that slot (chaining).

4. The search method looks for a key and returns its corresponding value.

5. The delete method removes a key-value pair from the table.

In the example, we've added three fruit names as keys with numbers as values. After searching for the values, we then delete the key "apple" and check its value, which returns None as expected.