Что такое хеш-таблица?

Хеш-таблица (hash table) — это структура данных, реализующая интерфейс ассоциативного массива (словаря). Она обеспечивает в среднем O(1) время выполнения операций вставки, поиска и удаления пар «ключ-значение».

Принцип работы:

1. Хеш-функция преобразует ключ в целочисленный хеш-код.
2. Хеш-код отображается в индекс массива (бакета или корзины) с помощью операции (например, hash_code % array_size).
3. Если два разных ключа дают один индекс (коллизия), она разрешается одним из методов:
   • Метод цепочек: Каждый бакет содержит связный список (или дерево) пар ключ-значение.
   • Открытая адресация: Поиск следующего свободного бакета по определенному алгоритму (линейное/квадратичное пробирование).

Пример реализации на Python (упрощенная версия с цепочками):

class HashTable:
    def __init__(self, size=10):
        self.size = size
        self.table = [[] for _ in range(size)]  # Массив бакетов (списков)

    def _hash(self, key):
        return hash(key) % self.size  # Простая хеш-функция

    def put(self, key, value):
        bucket_index = self._hash(key)
        bucket = self.table[bucket_index]
        # Проверка на обновление существующего ключа
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)
                return
        bucket.append((key, value))

    def get(self, key):
        bucket_index = self._hash(key)
        bucket = self.table[bucket_index]
        for k, v in bucket:
            if k == key:
                return v
        raise KeyError(f"Key '{key}' not found")

# Использование
ht = HashTable()
ht.put("apple", 50)
ht.put("banana", 30)
print(ht.get("apple"))  # 50

В Python встроенный тип dict является высокооптимизированной хеш-таблицей.