What components does a hash table consist of?

A hash table consists of two main components:

1. Array (or list) of buckets: This is the primary storage structure. Each bucket can contain one or more data elements (key-value pairs).

2. Hash function: An algorithm that transforms an input key into a numerical index, which is used to determine the bucket where the corresponding data element should be stored or found.

Additionally, mechanisms such as:

• Chaining method: Each bucket stores a list (e.g., linked list) of elements that hash to that index.
• Open addressing method: In case of a collision, the algorithm searches for the next free bucket following a certain strategy (linear probing, quadratic probing, double hashing).

# Example of a simple hash function
def simple_hash(key, array_size):
    # Convert key to a number
    if isinstance(key, str):
        hash_value = sum(ord(char) for char in key)
    elif isinstance(key, int):
        hash_value = key
    else:
        raise TypeError("Unsupported key type")

    # Return index within array size
    return hash_value % array_size

# Example of a bucket array component for chaining method
class HashTable:
    def __init__(self, size):
        self.size = size
        self.array = [[] for _ in range(self.size)] # Array of lists (chains)

    def insert(self, key, value):
        index = simple_hash(key, self.size)
        self.array[index].append((key, value)) # Add key-value pair to list

    def search(self, key):
        index = simple_hash(key, self.size)
        for k, v in self.array[index]:
            if k == key:
                return v
        return None # Key not found