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