Что такое хеш-таблица и почему это важно?

Хеш-таблица — это структура данных, которая хранит пары «ключ-значение» и обеспечивает доступ к элементам в среднем за O(1). В Python она реализована в виде словаря (dict) — одного из самых мощных инструментов языка. Если вы решаете задачи на LeetCode или пишете реальные проекты, без словарей не обойтись. В этой статье разберём, как работает хеш-таблица, какие операции с ней выполнять и как применять её в алгоритмах.

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

Основная идея — использовать хеш-функцию для преобразования ключа в индекс массива (бакета). Например, при выполнении mp["apple"] = 50 происходит следующее:

Ключ "apple" передаётся в хеш-функцию.
Хеш-функция возвращает большое число (хеш-код).
Сжатие: хеш-код делится по модулю на размер массива бакетов.
Полученный индекс определяет, где хранится пара.

В Python словарь автоматически управляет хешированием и коллизиями, поэтому вам не нужно реализовывать это вручную.

Создание словаря в Python

Словарь создаётся фигурными скобками или через функцию dict():

# Пустой словарь
mp = {}

# Словарь с начальными значениями
marks = {"Иван": 90, "Мария": 85, "Пётр": 75}

# Альтернативный способ
marks2 = dict(Иван=90, Мария=85, Пётр=75)

Основные операции со словарём

Вставка и обновление

Присваивание по ключу добавляет новую пару или обновляет существующую:

mp = {}
mp["apple"] = 10   # добавление
mp["apple"] = 20   # обновление
print(mp)  # {'apple': 20}

Доступ к значениям

Используйте квадратные скобки или метод get():

print(mp["apple"])  # 20
# Безопасный доступ: если ключа нет, вернёт None или значение по умолчанию
print(mp.get("banana"))        # None
print(mp.get("banana", 0))     # 0

Важно: если использовать mp["banana"], а ключа нет, возникнет ошибка KeyError.

Проверка наличия ключа

Оператор in — самый простой способ:

if "apple" in mp:
    print("Ключ есть")
else:
    print("Ключа нет")

Удаление элементов

Метод del или pop():

del mp["apple"]  # удалить ключ
value = mp.pop("banana", None)  # удалить и вернуть значение (если нет, None)

Размер и проверка на пустоту

print(len(mp))       # количество пар
print(bool(mp))      # False, если словарь пуст

Итерация по словарю

Перебирайте ключи, значения или пары:

for key in mp:
    print(key, mp[key])

for key, value in mp.items():
    print(key, value)

for value in mp.values():
    print(value)

Внутреннее устройство: хеш-функция и коллизии

Хеш-функция преобразует ключ в целое число. В Python для строк и чисел хеш вычисляется встроенной функцией hash().

print(hash("apple"))   # 123456789 (пример)
print(hash(42))        # 42

Коллизия — когда два разных ключа получают одинаковый хеш. Python использует метод открытой адресации: при коллизии ищет следующий свободный слот. Это обеспечивает среднюю сложность O(1).

Сравнение с другими структурами

В отличие от списка, где поиск занимает O(n), словарь даёт мгновенный доступ. Но словарь потребляет больше памяти и не гарантирует порядок (до Python 3.7). С версии 3.7 порядок вставки сохраняется.

Типичные задачи на собеседованиях

Подсчёт частоты символов

s = "banana"
freq = {}
for ch in s:
    freq[ch] = freq.get(ch, 0) + 1
print(freq)  # {'b': 1, 'a': 3, 'n': 2}

Поиск дубликатов

def has_duplicates(arr):
    seen = set()
    for x in arr:
        if x in seen:
            return True
        seen.add(x)
    return False

Два числа с суммой (Two Sum)

def two_sum(nums, target):
    seen = {}
    for i, num in enumerate(nums):
        complement = target - num
        if complement in seen:
            return [seen[complement], i]
        seen[num] = i
    return []

Первый неповторяющийся символ

def first_unique(s):
    freq = {}
    for ch in s:
        freq[ch] = freq.get(ch, 0) + 1
    for ch in s:
        if freq[ch] == 1:
            return ch
    return None

Практические советы

Используйте get() для безопасного доступа.
Для подсчёта частот удобен collections.Counter.
Для группировки данных — defaultdict из модуля collections.

from collections import Counter, defaultdict

freq = Counter("banana")
print(freq)  # Counter({'a': 3, 'b': 1, 'n': 2})

groups = defaultdict(list)
groups["a"].append(1)
groups["a"].append(2)
print(groups)  # {'a': [1, 2]}

Заключение

Хеш-таблица — фундаментальная структура, которую нужно знать каждому разработчику. В Python словарь — это мощный и гибкий инструмент, который ускорит ваши алгоритмы и упростит код. Практикуйтесь на задачах с LeetCode, и вы быстро освоите все приёмы.

Что делать прямо сейчас: возьмите любую задачу на подсчёт частот или поиск дубликатов и решите её с помощью словаря. Затем попробуйте реализовать собственную хеш-таблицу на Python для закрепления понимания.

Хеш-таблица в Python: полное руководство