Оптимизация хеш-таблиц

В нескольких реализациях хеш-таблиц я видел использование эвристик, таких как «транспонирование» или «перемещение на передний план» для элементов в ведре.

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

Оптимизация хэш-функций в сторону, пожалуйста.


hash compiler-construction hashtable compiler-theory
person Flavius    schedule 02.12.2009    source источник

Ответы (1)


arrow_upward
4
arrow_downward

Если происходят коллизии и, следовательно, в корзинах есть несколько элементов, которые необходимо проверить, было бы удобно, если бы часто используемые элементы находились в начале списка.

Эти эвристики имеют смысл, если есть основания предполагать, что к элементу, к которому недавно обращались, вероятно, скоро будет обращен доступ снова. Когда кто-то рассматривает что-то вроде новостей, вполне вероятно, что последние новости будут часто доступны.

person djna    schedule 02.12.2009
comment
Это также известно как самооптимизирующийся список, в котором наиболее часто используемые элементы всплывают в начале списка. - person David R Tribble; 03.12.2009
comment
Что сказал Loadmaster... Плюс: Взгляните на splay-tree (wiki!), чтобы понять, почему перемещение элементов на передний план в целом является хорошей идеей. - person Nils Pipenbrinck; 03.12.2009