Словарь это массив, хеш-функция и план на случай, когда два ключа попали в одну ячейку — 5 сентября 2026 г. в 08:18:13.174
Словарь это массив, хеш-функция и план на случай, когда два ключа попали в одну ячейку Автор собирает хеш-таблицу на Rust с нуля, чтобы показать, почему словари и HashMap быстрые и где они ломаются. Первая версия проста: hash(key) % capacity даёт индекс в массиве. Она тут же ломается на коллизии: в таблице на 16 ячеек «Bananas» и «Eggs» попадают в один слот, и второе значение затирает первое. Классический ответ, список в каждой ячейке, работает, но разбрасывает узлы по памяти и промахивается мимо кеша процессора. Поэтому автор реализует линейное пробирование: если ячейка занята, идём в следующую по кругу. Дальше видно, почему таблицу приходится перестраивать, когда она заполняется, и почему вставка в словарь иногда внезапно дорогая. Код короткий, Rust знать не обязательно, идея переносится на dict в Python и Map в JavaScript. #основы