[20.11.2025] Zombie Hashing: Reanimating Tombstones in a Graveyard

[Ruslan Savchenko]

Сегодня в 16:30 состоится доклад Дмитрия Савичева по статье "Zombie Hashing: Reanimating Tombstones in a Graveyard".

Аннотация:

Хэш-таблицы с открытой адресацией широко распространены в индустрии благодаря своей эффективности, что делает задачу их оптимизации крайне важной. Однако, как показывает теория и практика, стандартные методы разрешения коллизий в таких хэш таблицах демонстрируют снижение производительности при высоком коэффициенте заполнения (load factor), во многом из-за накопления маркеров удаления (tombstones).

В рамках семинара будут рассмотрены перспективные алгоритмы, преодолевающие это ограничение: Graveyard Hashing (амортизированный алгоритм) и Zombie Hashing (неамортизированный алгоритм)

Мы проанализируем, каким образом эти подходы превращают «надгробные камни» из помехи в функциональный элемент, повышающий эффективность работы таблицы.