Как сделать хэш-таблицу?

Как сделать хэш-таблицу

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

Встроенные хэш-таблицы в Python

# dict — это хэш-таблица
my_dict = {'John': 30, 'Jane': 25}
my_dict['Alice'] = 28
print(my_dict['John'])  # O(1) доступ

# set — тоже хэш-таблица (без значений)
my_set = {1, 2, 3}
1 in my_set  # O(1) поиск

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

Шаг 1: Хэшируем ключ

# Python вычисляет хэш ключа
key = "John"
hash_value = hash(key)  # Returns integer
print(hash_value)  # Example: 8918402244155651631

# hash для int
print(hash(123))  # 123

# hash для tuple
print(hash((1, 2)))  # Вычисляет хэш

# Важно: hash для mutable типов не работает
# hash([1, 2])  # TypeError: unhashable type
# hash({})      # TypeError: unhashable type

Шаг 2: Находим индекс в массиве

# Хэш-таблица использует внутренний массив размера N
array_size = 16
index = hash_value % array_size  # Берём остаток
print(index)  # 0-15

Шаг 3: Сохраняем или ищем

# Массив хранит пары (ключ, значение)
# array[index] = [(key1, value1), (key2, value2), ...]

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

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 set(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
        
        raise KeyError(f"Key {key} not found")
    
    def __contains__(self, key):
        """Проверяет наличие ключа"""
        try:
            self.get(key)
            return True
        except KeyError:
            return False

# Использование
ht = HashTable()
ht.set('name', 'John')
ht.set('age', 30)

print(ht.get('name'))  # John
print('age' in ht)     # True
print(ht.get('job'))   # KeyError

Коллизии (collisions)

Когда разные ключи получают одинаковый хэш:

# Пример коллизии
key1 = "John"
key2 = "Jane"

hash1 = hash(key1) % 16  # Индекс 5
hash2 = hash(key2) % 16  # Индекс 5 (коллизия!)

# Решение: chaining (используем список в каждой ячейке)
array[5] = [(key1, value1), (key2, value2)]

Производительность

# Средний случай:
# set: O(1)
# get: O(1)
# delete: O(1)

# Худший случай (много коллизий):
# O(n) если все ключи попадают в один bucket

# Python dict использует optimized версию
# и автоматически увеличивает размер при необходимости

Правильная реализация с resizing

class ImprovedHashTable:
    def __init__(self, size=16):
        self.size = size
        self.count = 0
        self.table = [[] for _ in range(size)]
    
    def _resize(self):
        """Увеличивает размер при необходимости"""
        if self.count > self.size * 0.75:  # Load factor 0.75
            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.set(key, value)
    
    def _hash(self, key):
        return hash(key) % self.size
    
    def set(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))
        self.count += 1
        self._resize()
    
    def get(self, key):
        index = self._hash(key)
        for k, v in self.table[index]:
            if k == key:
                return v
        raise KeyError(key)

Python dict детально

# Python dict использует очень оптимизированную реализацию
d = {}
d['a'] = 1
d['b'] = 2

# Внутренне это компактная хэш-таблица
# с специальной оптимизацией для string ключей

# Можно посмотреть внутреннее состояние
print(d.__sizeof__())  # Размер в памяти

# В Python 3.6+ dict сохраняет порядок вставки
# (до этого порядок был не гарантирован)
for key in d:
    print(key)  # 'a', затем 'b'

Хэш-функция

# Хорошая хэш-функция должна:
# 1. Быстро вычисляться
# 2. Равномерно распределяться
# 3. Быть детерминированной (один вход = один выход)

# Примеры хэш-функций
def simple_hash(s):
    """Плохая хэш-функция"""
    return len(s)  # Много коллизий

def djb2_hash(s):
    """Лучше, но всё равно слабая"""
    hash_value = 5381
    for char in s:
        hash_value = ((hash_value << 5) + hash_value) + ord(char)
    return hash_value & 0x7FFFFFFF  # Положительное число

# Python использует собственную оптимизированную функцию
print(hash("hello"))  # Встроенная оптимизированная

Вывод

Хэш-таблица реализуется:

1. Массив — основное хранилище
2. Хэш-функция — преобразует ключ в индекс
3. Collision handling — обычно chaining (список в каждой ячейке)
4. Resizing — увеличение размера при росте

В Python используй встроенный dict — он уже оптимизирован. Саму реализацию нужно знать для собеседований и понимания производительности.