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

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

Основные компоненты и принцип работы:

1. Массив (Buckets): Основное хранилище данных, представляющее собой массив определенного размера. Каждый элемент этого массива называется "ведром" (bucket) или "слотом".

2. Хеш-функция: Преобразует ключ в числовое значение (хеш-код). Хорошая хеш-функция распределяет ключи равномерно по хеш-кодам.

3. Индексирование: Хеш-код, полученный от хеш-функции, используется для определения индекса в массиве, где будет храниться или извлекаться значение, соответствующее данному ключу. Часто используется операция по модулю (хеш_код % размер_массива) для получения индекса в диапазоне от 0 до размер_массива - 1.

4. Разрешение коллизий: Поскольку разные ключи могут иметь одинаковый хеш-код (хеш-коллизия), хеш-таблица должна иметь механизм их разрешения. Два основных подхода:

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

Процесс вставки (put):

1. Вычисляется хеш-код ключа.
2. Вычисляется индекс ведра на основе хеш-кода.
3. Пара ключ-значение помещается в соответствующее ведро. При использовании метода цепочек добавляется в список ведра. При открытой адресации ищется свободное место.

Процесс извлечения (get):

1. Вычисляется хеш-код и индекс ведра для данного ключа.
2. Переход к соответствующему ведру.
3. Если используется метод цепочек, поиск пары ключ-значение в списке ведра. Если используется открытая адресация, поиск пары в массиве, начиная с вычисленного индекса, используя ту же стратегию пробирования, что и при вставке.
4. Сравнение ключей (так как разные ключи могут иметь одинаковый хеш-код) для нахождения нужной пары.

Процесс удаления (delete):

1. Похож на извлечение: вычисляется хеш-код и индекс.
2. Находится пара ключ-значение.
3. Пара удаляется. Для открытой адресации обычно используется "ленивое удаление" (пометка слота как удаленного), чтобы не нарушить последовательности поиска при извлечении.

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

Предположим, у нас есть небольшой массив из 5 ведер, и мы используем метод цепочек.

Ключ	Хеш-функция	Индекс (хеш % 5)	Ведро
"apple"	$\approx 110$	$110 % 5 = 0$	Ведро 0: [("apple", "red")]
"banana"	$\approx 221$	$221 % 5 = 1$	Ведро 1: [("banana", "yellow")]
"cherry"	$\approx 332$	$332 % 5 = 2$	Ведро 2: [("cherry", "red")]
"date"	$\approx 115$	$115 % 5 = 0$	Ведро 0: [("apple", "red"), ("date", "brown")]

При поиске "date", хеш-функция дает хеш-код $\approx 115$, индекс 0. Переходим к Ведру 0 и просматриваем список, пока не найдем ключ "date".

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

В Python хеш-таблица реализована в типе данных dict.

# Создание словаря
my_dict = {"apple": "red", "banana": "yellow"}

# Вставка
my_dict["cherry"] = "red"

# Извлечение
color_of_banana = my_dict["banana"]

# Удаление
del my_dict["apple"]

# Проверка существования ключа
if "date" in my_dict:
    print("date is in the dictionary")
else:
    print("date is not in the dictionary")

# Принцип работы хеширования ключей (Python использует свою внутреннюю реализацию)
# hash("apple") # Вернет целочисленный хеш-код для строки "apple"
# hash(100)     # Вернет целочисленный хеш-код для целого числа 100
# Неизменяемые объекты (строки, числа, кортежи) являются хешируемыми и могут использоваться как ключи словарей.
# Изменяемые объекты (списки, словари, множества) не являются хешируемыми по умолчанию.