При реализации пользовательской хеш-таблицы с открытой адресацией я обнаружил, что для моего приложения это помогает производительности, если я поменяю зондированный элемент в строке заполненных слотов с помощью той, которая находится в первом месте расположения зонда. (Чтобы оптимизировать таблицу для быстрого получения элементов с часто используемым доступом)Какое имя для этой оптимизации таблицы хэшей?
Есть ли название для этой оптимизации?
Ваша проблема очень похожа на list update problem от поля online-competitive algorithms.
Решение, которое вы использовали, называется MTF (move to front). Известно, что это решение является 2-конкурентным, а это означает, что он будет в два раза хуже, чем гипотетический противник, который заранее знает будущее.
Обратите внимание, что вы можете сделать немного лучше, чем с помощью bit algorithm, для чего требуется еще один бит + случайный вариант, но он является конкурентоспособным на 7-4.
Спасибо, ** проблема с обновлением списка ** действительно кажется уместным! Я искал ссылки на ссылку _hash table_, но должен был подумать, что запуск заполненных зондов может, конечно, рассматриваться как _list_ ... – onno
Добро пожаловать. FWIW, я думаю, это тоже увлекательная проблема. Обратите внимание: если бы вы использовали цепочку столкновений, это была бы именно эта проблема. Исследование немного отличается - стоимость перемещения последнего элемента на какую-то позицию, сдвигая все назад, не является постоянной, как в списке. Тем не менее, я думаю, что это самая близкая проблема для вас. –
Наиболее общим термином для такого рода оптимизации является, вероятно, self-organization.
Спасибо. Это действительно хороший термин. Я нашел старую бумагу, которая, по-видимому, описывает обмен: http://www.sciencedirect.com/science/article/pii/0020019085901036 Я еще не покупал бумагу, но показана первая страница, и моя оптимизация кажется так называемый метод H2. – onno
В целом этот подход называется кэшированием MRU. Однако это не относится к хэш-таблицам. – rustyx
Спасибо. Я googled «кеширование» и «переход к фронту», но только нашел статьи о хэш-таблицах, которые используются для реализации кэшей ... Мне интересно, есть ли еще варианты оптимизации чтения и доступа к ним (и это) в литературе , чтобы -если они доступны, попробуйте их в моем приложении. – onno