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