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

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

Основные шаги:

1. Хеширование ключа: Ключ передается хеш-функции, которая возвращает числовое значение (хеш-значение).
2. Вычисление индекса бакета: Хеш-значение используется для вычисления индекса в массиве (обычно с помощью операции по модулю). index = хеш_значение % размер_массива.
3. Хранение/Поиск: Данные (пара ключ-значение) хранятся или извлекаются по вычисленному индексу.

Разрешение коллизий:

Коллизия возникает, когда два разных ключа имеют одинаковое хеш-значение и, следовательно, вычисляют один и тот же индекс бакета. Основные методы:

• Метод цепочек (Separate Chaining): Каждый бакет хранит связный список или другую структуру данных, содержащую все пары ключ-значение, которые хешируются в этот бакет.
• Метод открытой адресации (Open Addressing): Если бакет занят, ищется следующий свободный бакет по определенному правилу (например, линейное или квадратичное пробирование).

Пример (концептуальный):

# Простая хеш-функция (для иллюстрации)
def simple_hash(key, array_size):
    return sum(ord(c) for c in key) % array_size

# Реализация хеш-таблицы с методом цепочек
class SimpleHashTable:
    def __init__(self, size):
        self.size = size
        self.table = [[] for _ in range(size)] # Список списков для цепочек

    def insert(self, key, value):
        index = simple_hash(key, self.size)
        # Проверяем на наличие ключа для обновления значения
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                self.table[index][i] = (key, value)
                return
        self.table[index].append((key, value)) # Добавляем новую пару

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

    def delete(self, key):
        index = simple_hash(key, self.size)
        for i, (k, v) in enumerate(self.table[index]):
            if k == key:
                del self.table[index][i]
                return True # Удалено успешно
        return False # Ключ не найден

# Использование:
# ht = SimpleHashTable(10)
# ht.insert("apple", 5)
# print(ht.search("apple")) # Вывод: 5
# ht.insert("banana", 10)
# print(ht.search("banana")) # Вывод: 10
# ht.delete("apple")
# print(ht.search("apple")) # Вывод: None

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