Из каких компонентов состоит хеш-таблица?

Хеш-таблица состоит из двух основных компонентов:

1. Массив (или список) ячеек (buckets): Это основная структура хранения. Каждая ячейка может содержать один или несколько элементов данных (пар ключ-значение).

2. Хеш-функция: Алгоритм, который преобразует входной ключ в числовой индекс, который используется для определения ячейки, где должен быть сохранен или найден соответствующий элемент данных.

Кроме того, для разрешения коллизий (ситуаций, когда разные ключи хешируются в один и тот же индекс) используются механизмы, такие как:

• Метод цепочек (chaining): В каждой ячейке хранится список (например, связный список) элементов, которые хешировались в этот индекс.
• Метод открытой адресации (open addressing): При коллизии алгоритм ищет следующую свободную ячейку, следуя определенной стратегии (линейное пробирование, квадратичное пробирование, двойное хеширование).

# Пример простой хеш-функции
def simple_hash(key, array_size):
    # Преобразование ключа в число
    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 hash_value % array_size

# Пример компонента массива ячеек для метода цепочек
class HashTable:
    def __init__(self, size):
        self.size = size
        self.array = [[] for _ in range(self.size)] # Массив списков (цепочки)

    def insert(self, key, value):
        index = simple_hash(key, self.size)
        self.array[index].append((key, value)) # Добавление пары ключ-значение в список

    def search(self, key):
        index = simple_hash(key, self.size)
        for k, v in self.array[index]:
            if k == key:
                return v
        return None # Ключ не найден