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

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

2 голосов
/ 03 декабря 2009

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

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

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

1 Ответ

4 голосов
/ 03 декабря 2009

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

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

...