Как называется эта оптимизация хеш-таблицы?
Реализуя пользовательскую хеш-таблицу с открытой адресацией, я обнаружил, что для моего приложения это повышает производительность, если я заменяю проверенный элемент в ряду заполненных слотов на тот, который находится в первом расположении зонда. (Чтобы оптимизировать таблицу, чтобы быстрее получать часто используемые элементы)
Есть ли название для этой оптимизации?
2 ответа
Ваша проблема очень похожа на проблемуобновления списка из области онлайн-конкурентных алгоритмов.
Решение, которое вы использовали, известно как MTF (двигаться вперед). Известно, что это решение является 2-конкурентным, что означает, что оно будет в два раза хуже, чем гипотетический противник, заранее знающий будущее.
Обратите внимание, что вы можете сделать это немного лучше, чем с битовым алгоритмом, который требует еще один бит + случайная операция, но имеет 7-4 конкурентоспособности.
Наиболее общий термин для такого рода оптимизации, вероятно, самоорганизация.