Overview

A hash table is a data structure that maps keys to values for efficient data retrieval. It uses a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.

Program Structure

The following Python program implements a simple hash table:

class HashTable:
    def __init__(self, size=10):
        """Initialize the hash table with a specified size."""
        self.size = size
        self.table = [[] for _ in range(size)]

    def _hash(self, key):
        """Compute the hash for a given key."""
        return hash(key) % self.size

    def insert(self, key, value):
        """Insert a key-value pair into the hash table."""
        index = self._hash(key)
        for kv in self.table[index]:
            if kv[0] == key:
                kv[1] = value  # Update existing value
                return
        self.table[index].append([key, value])  # Add new key-value pair

    def delete(self, key):
        """Delete a key-value pair from the hash table."""
        index = self._hash(key)
        for i, kv in enumerate(self.table[index]):
            if kv[0] == key:
                del self.table[index][i]
                return

    def retrieve(self, key):
        """Retrieve the value associated with a given key."""
        index = self._hash(key)
        for kv in self.table[index]:
            if kv[0] == key:
                return kv[1]  # Return the associated value
        return None  # Key not found

    def __str__(self):
        """String representation of the hash table for debugging."""
        return str(self.table)

Documentation

Class: HashTable

The HashTable class implements a basic hash table with the following methods:

Methods

• __init__(size=10): Initializes the hash table with a specified size. Defaults to 10.
• _hash(key): Computes the hash value for the given key.
• insert(key, value): Inserts a key-value pair into the hash table. If the key already exists, it updates the value.
• delete(key): Deletes the key-value pair associated with the specified key.
• retrieve(key): Retrieves the value associated with the specified key. Returns None if the key is not found.
• __str__(): Returns a string representation of the hash table for debugging purposes.

Usage Example

Below is an example of how to use the HashTable class:

# Create a hash table instance
ht = HashTable()

# Insert key-value pairs
ht.insert("name", "Alice")
ht.insert("age", 30)
ht.insert("city", "New York")

# Retrieve values
print(ht.retrieve("name"))  # Output: Alice
print(ht.retrieve("age"))   # Output: 30

# Delete a key-value pair
ht.delete("city")

# Print the hash table
print(ht)  # Output: Hash table structure

Explanation of the Program Structure:

1. Class Definition: The HashTable class encapsulates all the functionality related to the hash table.
2. Initialization (__init__): Initializes the hash table with a specified size and creates a list of empty lists (buckets).
3. Hash Function (_hash): Computes the hash index for a given key using Python’s built-in hash() function.
4. Insertion (insert): Inserts a new key-value pair or updates an existing one if the key already exists.
5. Deletion (delete): Removes a key-value pair from the table.
6. Retrieval (retrieve): Retrieves the value associated with a key.
7. String Representation (__str__): Provides a way to output the current state of the hash table, useful for debugging.

Usage:

The usage example demonstrates creating an instance of the hash table, inserting key-value pairs, retrieving values, and deleting a key. This highlights the core functionalities of the hash table.

Conclusion

This basic hash table implementation in Python demonstrates how to store and retrieve key-value pairs efficiently. It highlights fundamental concepts such as hashing and collision handling using separate chaining.