Как разреженная хеш-таблица Google обрабатывает столкновения?

Question

Как разреженная хеш-таблица Google обрабатывает столкновения? т.е. когда 2 элемента отображаются в одно и то же ведро, как он решает, куда поместить новый (сталкивающийся) элемент? Я читаю Какова основная идея реализации разреженной хэш-таблицы? но этот ответ не охватывает идею столкновения.

Answer 1

Ваш вопрос дан ответ в документации здесь, а именно:

2c) Если t.sparsetable[i % 32] назначен, но для значения, отличного от foo, посмотрите на t.sparsetable[(i+1) % 32], Если это также не помогает, попробуйте t.sparsetable[(i+3) % 32], затем t.sparsetable[(i+6) % 32], В общем, продолжайте пробовать следующий треугольный номер.

Вы можете прочитать о треугольных числах здесь.