#algorithm #hash #hashmap
#алгоритм #хэш #hashmap
Вопрос:
В принципе, мне интересно, что происходит или может произойти под капотом, когда я запускаю что-то вроде этого:
for key in some_hash_map.keys():
print(key)
Речь идет только об использовании обратной хеш-функции?
Комментарии:
1. хэш (набор или карта) представляет собой набор сегментов (занятых или незанятых). прохождение по ключам подразумевает прохождение по занятым сегментам
Ответ №1:
Типичная хеш-таблица может быть реализована в виде массива сегментов, каждый из которых имеет связанный список записей.
Поиск по хэшу выполняется путем запуска хэш-функции для поиска нужного сегмента, а затем поиска в сегменте.
Итерация по ключам реализуется путем итерации по сегментам, выполняя поиск по каждому списку по очереди.
Если сегментов слишком много, вы тратите впустую память, и итерация выполняется медленно. Слишком мало, и связанные списки становятся медленными. Но мы можем динамически изменять размер количества сегментов для фиксированных накладных расходов на ключ.
Если хэш-функция не работает должным образом, то хэш будет работать ужасно.
Комментарии:
1. Спасибо! Итак, я полагаю, пары ключ-значение хранятся в 2-х кортежах внутри этих связанных списков.
2. @m_ocean Это один из способов его реализации. Пара ключ / указатель на значение также распространена.