Хэш-таблицы
Хэш-таблицы: быстрый поиск
- Хэш-таблица хранит элементы так, чтобы находить их очень быстро — обычно за один шаг.
- Это список ячеек. Хэш-функция преобразует ключ в номер ячейки.
- Вместо поиска каждого элемента вы сразу переходите к ячейке, где должен находиться ключ.
Хэш-функция
- Хэш-функция принимает ключ и возвращает индекс ячейки от
0доsize - 1. - Один и тот же ключ всегда дает ту же ячейку, поэтому вы можете найти его снова позже.
- Простая функция: сложите коды символов, затем примените
% size, чтобы оставаться в диапазоне.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch) # ord("A") is 65, ord("B") is 66, ...
return total % size
print(hash_key("cat", 10)) # a slot from 0 to 9
print(hash_key("cat", 10)) # same key -> same slot
print(hash_key("dog", 10))
Коллизии
- Два разных ключа могут хэшироваться в одну и ту же ячейку. Это коллизия.
- В таблице ограниченное количество ячеек, поэтому коллизии неизбежны при заполнении.
- Нам нужно правило того, что делать, если нужная ячейка уже занята.
Линейный пробинг
- Линейный пробинг: если ячейка занята, попробуйте следующую ячейку, затем следующую, с возвратом в начало.
- Продолжайте двигаться
(slot + 1) % size, пока не найдете свободную ячейку. - Ниже,
AиFоба хотят ячейку 0, поэтомуFпереносится в ячейку 1.
def hash_key(key, size):
total = 0
for ch in key:
total += ord(ch)
return total % size
def insert(table, key):
slot = hash_key(key, len(table))
while table[slot] is not None: # slot taken -> try the next one
slot = (slot + 1) % len(table)
table[slot] = key
return slot
table = [None] * 5
print(insert(table, "A")) # 0
print(insert(table, "F")) # 1 (A and F both hash to slot 0)
print(table) # ['A', 'F', None, None, None]
Поиск ключа
- Чтобы найти ключ: хэшируйте его, затем выполняйте линейный пробинг вперед, сравнивая каждую ячейку с ключом.
- Остановитесь и верните индекс, когда найдете его.
- Если вы достигли пустой ячейки (или проверили все ячейки), ключа нет — верните
-1.
Почему хэш-таблицы быстрые
- При малом количестве коллизий вставка и поиск занимают около одного шага — мы называем это
O(1). - По мере заполнения таблицы пробинг становится длиннее, поэтому разумно оставлять некоторые ячейки пустыми.
- В худшем случае (все ключи collidят) скорость падает до линейного сканирования,
O(n).
Распространенные ошибки
- Хэш-функция отображает ключ на индекс в таблице.
- Два ключа могут попасть в один индекс (коллизия). Решайте проблему так же, как в этом уроке — методом линейного зондирования; другим распространённым методом является цепочка (chaining).
Теперь попробуйте сами
- Постройте три части: хэш-функцию, вставку с пробингом и поиск.
- Каждая задача проверяет вашу функцию на случаях коллизий и возврата в начало (wrap-around).
- Нажмите Проверить ответ, чтобы протестировать её.
Хэширование в ячейку (корзину)
Функция хэширования отправляет каждый ключ в ячейку; коллизии образуют цепочку.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Напишите hash_key(key, size). Сложите коды символов строки key (используя ord(ch)) и верните итоговую сумму % size, чтобы результат был индексом от 0 до size - 1. Пример: строка hash_key("AB", 10) дает (65 + 66) % 10 = 1. Пустая строка возвращает 0.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
hash_key уже предоставлен. Напишите insert(table, key), используя линейную пробацию: перейдите в хеш-ячейку ключа; пока эта ячейка занята (не None), переходите к (slot + 1) % len(table); поместите ключ в первую свободную ячейку и верните его индекс.
Нажмите Запустить, чтобы увидеть результат здесь.
Сложность 4/5 · 280 монет + небольшой бонус за первое завершение сегодня
Функция hash_key предоставлена. Напишите find(table, key), которая возвращает индекс элемента key или -1, если он отсутствует. Начните с ячейки хэша и зондируйте вперед, сравнивая каждую ячейку. Остановитесь при пустой ячейке (ключа там нет). Убедитесь, что функция завершается даже при полной таблице — никогда не зацикливайтесь бесконечно.
Нажмите Запустить, чтобы увидеть результат здесь.