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

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

Определение и назначение

Хэш-таблица (hash table) — это структура данных, которая реализует ассоциативный массив, то есть структуру, которая сопоставляет ключи значениям. В Python словарь (dict) и множество (set) — это реализации хэш-таблиц. Хэш-таблица позволяет выполнять операции поиска, вставки и удаления за среднее время O(1) (константное время).

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

Хэш-таблица работает в три этапа:

1. Хеширование ключа

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

key = "name"
hash_value = hash(key)
print(hash_value)  # Пример: 8730966881815815643

2. Поиск индекса

Хэш-код приводится к индексу массива (бакета) с помощью операции модуля:

table_size = 16
index = hash_value % table_size
print(index)  # Пример: 11

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

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

• Метод цепочек (chaining): в каждом бакете хранится список пар ключ-значение
• Открытая адресация: ищется следующее свободное место в таблице

Python использует открытую адресацию с зондированием (probing).

Практический пример

# Python словарь — это хэш-таблица
person = {
    "name": "Alice",
    "age": 30,
    "city": "Moscow"
}

# O(1) поиск
name = person["name"]  # Очень быстро

# O(1) вставка
person["email"] = "alice@example.com"

# O(1) удаление
del person["city"]

Простая реализация хэш-таблицы

class HashTable:
    def __init__(self, size=16):
        self.size = size
        self.table = [[] for _ in range(size)]  # Метод цепочек
    
    def _hash(self, key):
        """Вычисляет индекс для ключа"""
        return hash(key) % self.size
    
    def insert(self, key, value):
        """Вставляет пару ключ-значение"""
        index = self._hash(key)
        bucket = self.table[index]
        
        # Проверяем, есть ли уже такой ключ
        for i, (k, v) in enumerate(bucket):
            if k == key:
                bucket[i] = (key, value)  # Обновляем
                return
        
        bucket.append((key, value))  # Добавляем новую пару
    
    def get(self, key):
        """Получает значение по ключу"""
        index = self._hash(key)
        bucket = self.table[index]
        
        for k, v in bucket:
            if k == key:
                return v
        
        return None
    
    def delete(self, key):
        """Удаляет пару по ключу"""
        index = self._hash(key)
        bucket = self.table[index]
        
        for i, (k, v) in enumerate(bucket):
            if k == key:
                del bucket[i]
                return True
        
        return False

# Использование
ht = HashTable()
ht.insert("name", "Alice")
ht.insert("age", 30)
print(ht.get("name"))  # Alice
ht.delete("age")

Сложность операций

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

Коллизии и их разрешение

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

# Пример коллизии
key1 = "ab"
key2 = "ba"

if hash(key1) % 16 == hash(key2) % 16:
    print("Коллизия!")

Методы разрешения:

1. Метод цепочек — в каждой ячейке хранится список

table[index] = [(key1, value1), (key2, value2)]

1. Открытая адресация — ищется следующая пустая ячейка

def probe(index):
    return (index + 1) % size  # Линейное зондирование

Динамическое расширение (Rehashing)

Когда хэш-таблица переполняется (коэффициент заполнения > 0.75), она расширяется:

class DynamicHashTable:
    def __init__(self):
        self.size = 16
        self.table = [[] for _ in range(self.size)]
        self.count = 0  # Количество элементов
    
    def insert(self, key, value):
        # Проверяем, нужно ли расширение
        if self.count / self.size > 0.75:
            self._rehash()
        
        index = hash(key) % self.size
        self.table[index].append((key, value))
        self.count += 1
    
    def _rehash(self):
        """Создаёт новую таблицу большего размера"""
        old_table = self.table
        self.size *= 2
        self.table = [[] for _ in range(self.size)]
        self.count = 0
        
        # Перехэшируем все элементы
        for bucket in old_table:
            for key, value in bucket:
                self.insert(key, value)

Требования к хэш-функции

Хорошая хэш-функция должна:

1. Быстро вычисляться — O(1)
2. Равномерно распределять ключи по индексам
3. Быть детерминированной — один ключ всегда даёт один хэш-код
4. Минимизировать коллизии — разные ключи должны давать разные коды

Применение хэш-таблиц

Словари и множества — основное применение в Python:

students = {"Alice": 90, "Bob": 85}  # dict
unique_ids = {1, 2, 3, 3}  # set

Кэширование — быстрый поиск закэшированных значений:

cache = {}  # O(1) доступ
if key in cache:
    return cache[key]

Подсчёт частоты — подсчёт вхождений элементов:

from collections import Counter
freq = Counter([1, 2, 2, 3, 3, 3])  # {3: 3, 2: 2, 1: 1}

Заключение

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