Внутреннее устройство хеш-функций и обработка коллизий
Поймите, как Python хеширует объекты, как открытая адресация и метод цепочек разрешают коллизии и почему средняя сложность O(1) может ухудшиться до O(n)
«Внутреннее устройство хеш-функций и обработка коллизий» — бесплатный урок DSA Interview Prep на CoddyKit. Это урок 1 из 4. Ты можешь прочитать весь урок бесплатно ниже — а потом практиковать его прямо в браузере с встроенным редактором кода и ИИ-репетитором 24/7. Это часть пути обучения DSA Interview Prep, и твой прогресс синхронизируется между веб-версией и приложением CoddyKit. Курс DSA Interview Prep содержит 4 уроков всего.
Что такое хеш-таблица
Хеш-таблица (словарь в Python) сопоставляет ключи со значениями с помощью хеш-функции, которая преобразует любой ключ в целочисленный индекс внутреннего массива. Идеальная хеш-функция равномерно распределяет ключи по массиву, обеспечивая в среднем поиск, вставку и удаление за O(1). Внутренний массив называется таблицей хеширования или массивом корзин.
В Python dict — это высокооптимизированная хеш-таблица. Понимание её внутреннего устройства помогает рассуждать о поведении в худшем случае и выбирать подходящие ключи.
# Python dict is a hash map
hm = {}
hm['alice'] = 95
hm['bob'] = 87
hm['carol'] = 91
print(hm['alice']) # O(1) lookup: 95
print('bob' in hm) # O(1) membership: True
del hm['bob'] # O(1) deletion
print(hm) # {'alice': 95, 'carol': 91}Хеш-функции и метод __hash__
Python вызывает __hash__(key), чтобы вычислить целое число по ключу, а затем берёт остаток от деления этого числа на размер таблицы, чтобы найти индекс корзины. Встроенные типы, такие как int, str и tuple, имеют быстрые встроенные реализации хеширования. list и dict не поддерживают хеширование: они изменяемы, и их изменение сделало бы сохранённый хеш недействительным.
Хорошая хеш-функция равномерно распределяет ключи, детерминирована и быстро вычисляется. Хеш строк в Python рандомизируется при каждом запуске (это функция безопасности); используйте PYTHONHASHSEED=0, чтобы отключить рандомизацию для воспроизводимости при тестировании.
# Built-in hash in Python
print(hash(42)) # integer hashes to itself (CPython)
print(hash('hello')) # string hash (randomised per run)
print(hash((1, 2, 3))) # tuple hash: depends on contents
# Unhashable types
try:
hash([1, 2, 3]) # lists are mutable -> not hashable
except TypeError as e:
print('Error:', e)
# Custom class: define __hash__ and __eq__
class Point:
def __init__(self, x, y): self.x = x; self.y = y
def __hash__(self): return hash((self.x, self.y))
def __eq__(self, other): return self.x == other.x and self.y == other.y
points = {Point(1, 2): 'A', Point(3, 4): 'B'}
print(points[Point(1, 2)]) # 'A'Коллизии: когда два ключа хешируются в одну корзину
Коллизия возникает, когда два различных ключа дают один и тот же индекс корзины. Коллизии неизбежны (принцип Дирихле: ключей бесконечно много, а корзин — конечное количество). Две стандартные стратегии разрешения коллизий — метод цепочек и открытая адресация. Python использует вариант открытой адресации с псевдослучайным пробированием.
При методе цепочек в каждой корзине хранится связный список (или динамический массив); все ключи, попавшие в эту корзину из-за коллизии, образуют цепочку. При открытой адресации следующая пустая корзина ищется согласно последовательности пробирования.
# Simplified chaining hash map
class ChainingHashMap:
def __init__(self, capacity=8):
self.capacity = capacity
self.buckets = [[] for _ in range(capacity)]
def _idx(self, key):
return hash(key) % self.capacity
def put(self, key, val):
bucket = self.buckets[self._idx(key)]
for i, (k, v) in enumerate(bucket):
if k == key:
bucket[i] = (key, val)
return
bucket.append((key, val))
def get(self, key):
for k, v in self.buckets[self._idx(key)]:
if k == key:
return v
return None
hm = ChainingHashMap()
hm.put('a', 1); hm.put('b', 2)
print(hm.get('a')) # 1
print(hm.get('c')) # NoneОткрытая адресация: линейное пробирование
При линейном пробировании, если в индексе i возникает коллизия, таблица проверяет i+1, i+2, ... (переходя в начало после конца), пока не найдёт пустую ячейку. При поиске нужно проверять ту же последовательность, чтобы найти ключ. Для удаления требуется специальный маркер удаления вместо очистки ячейки, чтобы не нарушить цепочку пробирования.
Главный недостаток — кластеризация: когда образуется кластер заполненных ячеек, последующие вставки в эту область увеличивают его, и производительность приближается к O(n).
class LinearProbingHashMap:
DELETED = object() # tombstone sentinel
def __init__(self, capacity=8):
self.capacity = capacity
self.keys = [None] * capacity
self.vals = [None] * capacity
self.size = 0
def _probe(self, key):
idx = hash(key) % self.capacity
while self.keys[idx] is not None and self.keys[idx] != key:
idx = (idx + 1) % self.capacity
return idx
def put(self, key, val):
idx = self._probe(key)
if self.keys[idx] is None:
self.size += 1
self.keys[idx] = key
self.vals[idx] = val
def get(self, key):
idx = self._probe(key)
if self.keys[idx] == key:
return self.vals[idx]
return None
hm = LinearProbingHashMap()
hm.put('x', 10); hm.put('y', 20)
print(hm.get('x')) # 10Коэффициент заполнения и изменение размера
Коэффициент заполнения — это отношение количества сохранённых элементов к общей вместимости: α = n/m. По мере роста α вероятность коллизий увеличивается, а производительность снижается. Словарь Python увеличивает размер (удваивает вместимость), когда коэффициент заполнения превышает примерно 2/3. При изменении размера все существующие элементы хешируются заново и помещаются в новую, более крупную таблицу — это операция O(n), которая выполняется нечасто, поэтому амортизированная стоимость вставки остаётся равной O(1).
import sys
d = {}
prev_size = sys.getsizeof(d)
for i in range(30):
d[i] = i
new_size = sys.getsizeof(d)
if new_size != prev_size:
print(f'Resized at n={i+1}: {prev_size} -> {new_size} bytes')
prev_size = new_sizeСреднее O(1) и худшее O(n)
При хорошей хеш-функции коллизии редки, а ожидаемая длина цепочки постоянна независимо от n. Поэтому поиск, вставка и удаление в среднем выполняются за O(1). Однако в худшем случае, например при намеренно подобранных входных данных, отображающих все ключи в одну корзину, стоимость всех операций возрастает до O(n). Рандомизация начального значения хеша в Python снижает эффективность такой атаки, но теоретически не устраняет худший случай.
При анализе на собеседовании скажите: «В среднем O(1), в худшем случае O(n) из-за коллизий».
# Python randomised hash seed prevents worst-case hash-flooding
import os
print('PYTHONHASHSEED:', os.environ.get('PYTHONHASHSEED', 'random'))
# By default Python randomises the hash of strings each run
# This prevents an attacker from crafting keys that all collide
# To reproduce results in testing: PYTHONHASHSEED=0 python script.pyСловарь Python, словарь со значением по умолчанию и счётчик
В Python есть три заслуживающих внимания варианта хеш-таблиц. dict — это универсальная хеш-таблица; обращение к отсутствующему ключу вызывает KeyError. defaultdict(factory) возвращает значение по умолчанию при обращении к отсутствующему ключу (это полезно для сбора списков или подсчёта). Counter — специализированный подкласс для подсчёта хешируемых объектов; он также поддерживает арифметические операции между счётчиками.
from collections import defaultdict, Counter
# defaultdict for grouping
groups = defaultdict(list)
for word in ['apple', 'ant', 'banana', 'bee', 'avocado']:
groups[word[0]].append(word)
print(dict(groups))
# {'a': ['apple','ant','avocado'], 'b': ['banana','bee']}
# Counter for frequency
c = Counter('abracadabra')
print(c.most_common(3)) # [('a',5),('b',2),('r',2)]
print(c['a'] - Counter('aa')['a']) # counter subtractionХеш-таблица и хеш-множество
Хеш-множество хранит только ключи (без связанных значений), поддерживая проверку принадлежности, вставку и удаление за O(1). В Python хеш-множеством является set. Используйте множество, когда нужно только ответить на вопрос «существует ли этот элемент?», не сохраняя связанные данные. Используйте словарь, когда нужно сопоставить ключам значения (счётчики, результаты и т. д.).
# set for membership testing
visited = set()
for node in [1, 3, 5, 3, 7, 1]:
if node not in visited:
print('New node:', node)
visited.add(node)
# Set operations: union, intersection, difference
A = {1, 2, 3, 4}
B = {3, 4, 5, 6}
print('Union:', A | B) # {1,2,3,4,5,6}
print('Intersection:', A & B) # {3,4}
print('Difference:', A - B) # {1,2}Реализация хеш-таблицы с нуля (версия для собеседования)
Иногда на собеседовании Вас просят реализовать базовую хеш-таблицу. Основные компоненты: массив корзин фиксированного размера (используйте 16 или 1024), список пар (ключ, значение) в каждой корзине для метода цепочек, хеш-функция (используйте встроенную хеш-функцию Python и деление по модулю вместимости) и изменение размера при превышении коэффициентом заполнения значения 0,7. Если Вы заранее упомянете изменение размера и коэффициент заполнения, это продемонстрирует глубокое понимание темы.
class HashMap:
def __init__(self, capacity=16):
self.capacity = capacity
self.size = 0
self.buckets = [[] for _ in range(capacity)]
def _hash(self, key):
return hash(key) % self.capacity
def put(self, key, val):
b = self.buckets[self._hash(key)]
for i, (k, v) in enumerate(b):
if k == key:
b[i] = (key, val)
return
b.append((key, val))
self.size += 1
if self.size / self.capacity > 0.7:
self._resize()
def get(self, key, default=None):
for k, v in self.buckets[self._hash(key)]:
if k == key:
return v
return default
def _resize(self):
old = self.buckets
self.capacity *= 2
self.buckets = [[] for _ in range(self.capacity)]
self.size = 0
for bucket in old:
for k, v in bucket:
self.put(k, v)
hm = HashMap()
for i in range(20):
hm.put(i, i * 2)
print(hm.get(10)) # 20
print(hm.capacity) # should have resizedКогда хеш-таблицы дают сбой: нехешируемые ключи
Ключами словаря могут быть только хешируемые объекты. В Python объект является хешируемым, если у него есть метод __hash__ и метод __eq__, а его хеш-значение не изменяется в течение времени существования объекта. Списки, множества и словари изменяемы и поэтому не поддерживают хеширование. Кортежи и неизменяемые множества — хешируемая альтернатива спискам и множествам при использовании в качестве ключей.
Распространённая ловушка на собеседовании: для группировки анаграмм в качестве ключа словаря нужно использовать отсортированный кортеж, а не отсортированный список.
from collections import defaultdict
def groupAnagrams(strs):
groups = defaultdict(list)
for s in strs:
key = tuple(sorted(s)) # tuple is hashable; list is not
groups[key].append(s)
return list(groups.values())
print(groupAnagrams(['eat','tea','tan','ate','nat','bat']))
# [['eat','tea','ate'], ['tan','nat'], ['bat']]Итоги: сложность хеш-таблиц
Хеш-таблицы обеспечивают среднее время O(1) для вставки, удаления и поиска — это основа многих оптимальных решений задач на собеседованиях. Ключевые предположения таковы: хорошая хеш-функция равномерно распределяет ключи, коэффициент заполнения остаётся ограниченным (изменение размера поддерживает это условие), а объекты-ключи неизменяемы и хешируемы. При выполнении этих условий хеш-таблицы превращают линейные проходы за O(n) в поиск за O(1), позволяя решать задачу о двух слагаемых за O(n), а не за O(n²).
Быстрая проверка
Проверьте, насколько Вы поняли концепции курса «Структуры данных и алгоритмы — подготовка к собеседованию по программированию» из этого урока.
Итоги урока
В этом уроке Вы узнали: хеш-таблица сопоставляет ключи с индексами корзин с помощью хеш-функции и обеспечивает операции со средней сложностью O(1), коллизии разрешаются методом цепочек (связный список для каждой корзины) или открытой адресацией (поиск следующей пустой ячейки), и ключами словаря могут быть только неизменяемые хешируемые объекты — если нужен ключ-последовательность, используйте кортеж вместо списка. Далее мы решим задачу о двух слагаемых и рассмотрим её многочисленные варианты на собеседованиях.
Часто задаваемые вопросы
Урок «Внутреннее устройство хеш-функций и обработка коллизий» бесплатный?
Да — полный текст урока «Внутреннее устройство хеш-функций и обработка коллизий» бесплатно доступен здесь в веб-версии. Чтобы практиковать его интерактивно (встроенный редактор кода и ИИ-репетитор 24/7) и разблокировать остальной курс DSA Interview Prep, подпишись на CoddyKit PRO. Курс DSA Interview Prep содержит 4 уроков всего.
Чему я научусь в уроке «Внутреннее устройство хеш-функций и обработка коллизий»?
Поймите, как Python хеширует объекты, как открытая адресация и метод цепочек разрешают коллизии и почему средняя сложность O(1) может ухудшиться до O(n) Ты практикуешь DSA Interview Prep с помощью реального кода, который запускаешь прямо в браузере, и ИИ-репетитор 24/7 отвечает на твои вопросы во время урока.
Нужен ли мне опыт, чтобы начать DSA Interview Prep?
Предыдущий опыт не требуется. DSA Interview Prep на CoddyKit структурирован для всех уровней — от новичков до продвинутых, поэтому ты можешь начать отсюда или с самого начала и учиться в своем темпе. Это урок 1 из 4.
Сколько времени занимает урок «Внутреннее устройство хеш-функций и обработка коллизий»?
Большинство уроков CoddyKit занимают около 5–10 минут. Каждый из них компактный и интерактивный, поэтому ты постоянно делаешь прогресс и продолжаешь с того же места в веб-версии и приложении.
Можно ли писать и запускать код в этом уроке DSA Interview Prep?
Да. Каждый урок DSA Interview Prep включает встроенный редактор кода, поэтому ты пишешь и запускаешь реальный код прямо в браузере и получаешь моментальную обратную связь от AI — локальная установка не требуется.
Все уроки этого курса
- Внутреннее устройство хеш-функций и обработка коллизий
- Два слагаемых и множество вариантов
- Подсчёт частот и группировка
- Самая длинная последовательность и кэш LRU