При повторном поиске одного и того же строкового ключа в словаре почему хеш обычно не вычисляется заново?
В CPython вычисленный хеш объекта строки кэшируется внутри самого Unicode-объекта. Поэтому при последующих обращениях к словарю с тем же объектом строки используется сохранённое значение, что уменьшает стоимость поиска.
Это не означает, что поиск становится бесплатным: словарь всё равно выполняет вычисление позиции, проверку занятой ячейки и при коллизиях — сравнение ключей.
Словари реализованы как хеш-таблицы. Для поиска ключа сначала нужен его хеш, а затем выполняется обращение к предполагаемой позиции в таблице.
Строки часто используются как ключи конфигураций, атрибутов, маршрутов и сообщений протокола. Повторное вычисление хеша для длинной строки создавало бы лишние затраты, поэтому CPython хранит уже вычисленный результат в объекте строки.
В горячем цикле приложение может многократно искать значения по строковым ключам. Если ключи длинные или хеширование выполняется для большого числа различных строк, стоимость вычисления хешей становится частью времени работы.
Важно не делать ошибочный вывод, что любой повторный поиск одинакового текста использует один общий кэш. Кэш принадлежит конкретному объекту строки, а не значению во всём процессе.
При первом вызове хеширования строки CPython вычисляет хеш и сохраняет его в структуре объекта. При следующем хешировании того же строкового объекта сохранённое значение возвращается без повторного прохода по символам.
Словарь также хранит хеш ключа, находящегося в таблице. Однако для проверяемого ключа поиска хеш обычно всё равно нужно получить, чтобы выбрать позицию для поиска. Кэш строки устраняет именно повторное вычисление этого хеша.
Если существуют два разных объекта строки с одинаковым содержимым, каждый объект может иметь собственный кэш. Поэтому одинаковый текст не гарантирует единого вычисления хеша. Интернирование может заставить одинаковые строки использовать один объект, но применять его только ради ускорения поиска следует после измерений: интернирование увеличивает время жизни строк и может увеличить потребление памяти.
Механизм относится прежде всего к реализации строк в CPython, а не к универсальному обещанию языка Python для всех хешируемых объектов. У пользовательского объекта метод __hash__ может вызываться при каждом поиске, если сам объект не реализует собственное кэширование.
Хеш должен оставаться неизменным, пока объект используется как ключ. Для строк это обеспечивается их неизменяемостью. Если нарушить это правило у изменяемого хешируемого объекта, словарь может перестать находить ранее добавленный ключ.
В обработчике событий профилирование показало много обращений к словарю по длинным именам полей. Рассматривались три варианта: вручную сохранять хеши, интернировать все входные строки или заменить внешние имена на целочисленные идентификаторы.
Ручное кэширование хешей оказалось лишним: для обычных строк CPython уже делает это, а дополнительная структура усложнила код. Массовое интернирование отклонили из-за риска удерживать большое количество уникальных входных строк.
Для ограниченного набора известных полей выбрали преобразование имён в заранее зарегистрированные целочисленные идентификаторы. Это уменьшило размер ключей и стоимость работы в горячем пути, но потребовало таблицы соответствий и отдельной обработки неизвестных имён. Если бы профилирование не показало заметную стоимость строковых операций, оставили бы исходный вариант ради простоты.
Нет. Кэш хранится в конкретном объекте строки. Два разных объекта с одинаковым содержимым могут вычислить один и тот же хеш независимо. Интернирование иногда объединяет такие объекты, но это отдельный механизм с собственной стоимостью и влиянием на время жизни объектов.
Нет. После получения хеша словарь вычисляет позицию, исследует таблицу, обрабатывает коллизии и при необходимости сравнивает ключи на равенство. Кэш особенно полезен для длинных строк и повторного использования тех же объектов, но не превращает поиск в простое обращение по адресу.
Кэширование хеша строки — деталь реализации строк в CPython. Пользовательский класс может выполнять __hash__ заново при каждом обращении, а его вычисление может зависеть от состояния объекта. Поэтому оптимизацию нужно проверять отдельно для конкретного типа и версии реализации Python, а не предполагать наличие общего кэша для всех ключей.