Внедряем хэш-таблицы с нуля: от теории к работающему коду на Python

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

В основе хэш-таблицы лежат два компонента: функция хэширования и массив (список) «корзин» (buckets). Функция принимает ключ (например, строку или число) и возвращает целочисленный хэш-код. Идеальная функция равномерно распределяет ключи по корзинам. Затем этот хэш-код преобразуется в индекс массива (обычно через операцию взятия остатка от деления на размер массива). Если два разных ключа дают один и тот же индекс, возникает коллизия. Существует несколько методов их разрешения; мы реализуем метод цепочек, где каждая корзина содержит список (цепочку) пар ключ-значение.

Начнем с создания класса. Определим фиксированный начальный размер внутреннего массива, например, 8. Каждый элемент этого массива будет пустым списком.

class HashTable:
 def __init__(self, capacity=8):
 self.capacity = capacity
 self.buckets = [[] for _ in range(capacity)]  # Создаем список пустых списков
 self.size = 0  # Количество фактически хранимых элементов

Теперь нужна простая хэш-функция. В Python есть встроенная функция hash(), но для демонстрации и воспроизводимости создадим свою. Например, для строкового ключа просуммируем коды символов, умноженные на простое число.

 def _hash(self, key):
 if isinstance(key, str):
 hash_value = 0
 prime = 31
 for char in key:
 hash_value = (hash_value * prime + ord(char)) % self.capacity
 return hash_value
 else:
 # Для числовых ключей
 return hash(key) % self.capacity

Метод для вставки (put или __setitem__). Сначала вычисляем индекс корзины. Затем проходим по цепочке в этой корзине, проверяя, не существует ли уже такой ключ. Если ключ найден, обновляем его значение. Если не найден, добавляем новую пару в конец цепочки и увеличиваем счетчик size.

 def put(self, key, value):
 index = self._hash(key)
 bucket = self.buckets[index]
 for i, (k, v) in enumerate(bucket):
 if k == key:
 bucket[i] = (key, value)  # Обновление
 return
 bucket.append((key, value))
 self.size += 1

Метод для получения значения (get или __getitem__). Аналогично вычисляем индекс, ищем ключ в цепочке. Если нашли — возвращаем значение. Если нет — вызываем исключение KeyError.

 def get(self, key):
 index = self._hash(key)
 bucket = self.buckets[index]
 for k, v in bucket:
 if k == key:
 return v
 raise KeyError(f"Key '{key}' not found")

Метод удаления (delete или __delitem__). Находим ключ в цепочке и удаляем эту пару, уменьшая size.

 def delete(self, key):
 index = self._hash(key)
 bucket = self.buckets[index]
 for i, (k, v) in enumerate(bucket):
 if k == key:
 del bucket[i]
 self.size -= 1
 return
 raise KeyError(f"Key '{key}' not found")

Наша базовая реализация работает, но у нее есть серьезный недостаток: при большом количестве элементов производительность деградирует до O(n), если все ключи попадают в одну корзину. Необходима возможность увеличения размера внутреннего массива (rehashing) при достижении определенного коэффициента загрузки (load factor = size / capacity). Обычно порог выбирают 0.75.

Добавим приватный метод _resize, который будет создавать новый массив корзин в два раза больше, пересчитывать хэши для всех существующих пар и перемещать их в новые корзины. Вызов этого метода нужно добавить в конец метода put.

 def _resize(self):
 old_buckets = self.buckets
 self.capacity *= 2
 self.buckets = [[] for _ in range(self.capacity)]
 self.size = 0  # Сбросим, put его восстановит
 for bucket in old_buckets:
 for key, value in bucket:
 self.put(key, value)  # Перехэширование

 def put(self, key, value):
 # ... (старый код поиска и обновления/добавления)
 # После добавления нового элемента:
 if self.size / self.capacity > 0.75:  # Проверка коэффициента загрузки
 self._resize()

Теперь наша хэш-таблица стала динамической. Давайте протестируем ее работу:

ht = HashTable(4)
ht.put("apple", 10)
ht.put("banana", 20)
ht.put("orange", 30)
print(ht.get("banana"))  # 20
ht.put("banana", 25)  # Обновление
print(ht.get("banana"))  # 25
ht.delete("apple")
try:
 print(ht.get("apple"))
except KeyError as e:
 print(e)  # Key 'apple' not found
print(f"Size: {ht.size}, Capacity: {ht.capacity}")

В результате вы увидите, как таблица автоматически увеличивает capacity при добавлении элементов. Эта реализация, конечно, упрощена: она не учитывает многие оптимизации (например, использование кортежей вместо списков для пар), не реализует итераторы и другие специальные методы Python в полной мере. Однако она идеально раскрывает суть: хэш-функция, корзины, цепочки, разрешение коллизий и рехеширование. Создав такую структуру самостоятельно, вы глубже поймете, как работают встроенные ассоциативные массивы в любом языке программирования, и сможете лучше оценивать их производительность в ваших проектах.