Идеальное хеширование без чтения из памяти параметров h2(k)?

Question

[floppa322]

Узкое горлышко для хеш таблиц с идеальным хешиваронием (2-х уровневым) - количество чтений из памяти: contains(k): вычисление h1(k), чтение из памяти параметров для h2(k), вычисление h2(k), чтение из памяти k. Итого 2 обращение к памяти (если реализация со статически заданным размером бакета).
Есть ли подходы, как можно сократить количество чтений из памяти до 1-го ? Например, вычислив h1(k) = x, как-то по x вычислить (восстановить) (а не прочитать из памяти) параметры для h2 ?

P.S.: Вот примерный алгоритм построения моей реализации 2-х уровневой хэш таблицы с идеальным хешированием (если потребуется):
1. Зафиксируем размер бакета = (m/n)^2 * k, где k некоторый коэффициент
2. Используя хеш функцию для внешней таблицы h1, заполнить все бакеты, если какой-то бакет переполнился, повторить шаг 2 с другой h1
3. Для каждого бакета заполнять бакет, пока есть коллизии, меняя h2

P.S.: Вариант с хеш таблицей размером m = n^2 (где в среднем за 2 раза произойдёт её построение без коллизий) тоже не годится из-за больших затрат памяти

Comments

[mayton2019]

Пишу как-бы мозговой штурм по теме.

Хеш таблицы (ХТ) бывают двух видов. В основном. Это метод списков и открытая адресация.
В промышленности и в бизнесе (насколько я видел) в основном используется первый тип ХТ. У них
нет проблемы которую ты нарисовал. Никакие двухуровневые таблицы им не нужны. И этот тип реализован в С++/Java/C# e.t.c. библиотеках поддержки коллекций. В некоторых современных вариантах списки могут
превращаться в красно-черные деревья. Поэтому может быть гибрид хеш+R&B.

Второй тип подходит для редких кейсов типа хранения примитивов достаточно компактно. Но надо тонко
подбирать грань keys/capacity чтоб не попасть в ситуацию 3 и 4 и 5 обращения к памяти. Там будет резкий
рост времени отклика.

Твое идеальное хеширование в принципе сводится ко 2 типу. Надо только подбирать keys/capacity до тех пор пока нет коллизий и нет повторных чтений. Учитывая что у тебя идеальное хеширование (ключи не меняются) то можно майнить такие
конфигурации. Тоесть подбирать их длительное время для достижения почти идеального результата.

Эффективность твоего метода также зависит от выбора менеджмента памяти. Допустим для Java там возможностей не очень много а для С++/C можно играть union поинтеров и самих данных и достигать каких-то более лучших
результатов. Например делая вспомогательные структуры более компактными.

[floppa322]

mayton2019, забыл упомянуть в самом вопросе, что вариант с размером хеш таблицы m = n^2, где в среднем за 2 раза удастся построить таблицу (только с одной внейшней h1, без h2i) не подходит из-за больших затрат по памяти.

Ну и что касается, "заранее предпосчитать" это тоже не подходит, если, например, требуется относительно быстрое построение хеш таблицы, где она является частью (шагом) какого-то другого алгоритма. Ну и даже если речь идёт о том, что сбилдить таблицу на старте сервера, то вариант с предподсчётом тоже может не подойти, если не хочется, чтобы сервер стартовал пол часа

[mayton2019]

floppa322, вот вики пишет

Данная технология применяется в различных словарях и базах данных, в алгоритмах со статической (известной заранее) информацией.

я вот как себе это понимаю. Есть справочники которые редко меняются. Страны. Валюты. Языки. Всякие там биржевые тикеры. У тебя всегда есть достаточно времени чтобы расчитать эту таблицу почти идеально.

Вариант с 2 таблицами я-бы сразу выкинул. Неэффективное использование памяти. И выигрыш - ничтожный.

[floppa322]

mayton2019, так вариант с двумя как раз и противопоставляют варианту с одной, там как раз смысл в том, что квадрат растёт нелинейно и ((m/n)^2)*n (где (m/n)^2 размер бакета) много лучше n^2 (там примерно ((m/n)^2)*n ~ 4n получается при допустимом по времени построения размеру бакета)

[mayton2019]

floppa322, дружище если ты оптимизируешь время загрузки данных в таблицу - то ты сразу проиграл. Бери метод списков и все будет работать чудесно.

Хочешь открытая адресация с майнингом - попробуй не удваивать а умножать на 10% размер массива. Там именно массив а не бакеты. Я думаю что через 2-3 итерации все сойдется.

By the way. Я понимаю что ты - теоретик. Но мне всегда интересна практическая сторона вопроса. Какие ключи
ты хочешь хранить? Строки? Числа? Сколько из будет? Какой лимит времени ты хотел-бы потратить на
инициализацию системы? Вот меня как дата-инженера это в первую очередь беспокоит. А вовсе не нелинейность.

[floppa322]

mayton2019, ну и необязательно справочники, которые содержат данные вроде стран.
Такая хеш таблица может быть вспомогательной структорой данных в каком-то другом алгоритме, тогда время её1 построения критично.
Или, например, список каких-то (их не так много, что можно хранить в оперативке, а не на диске) user'ов в оперативной памяти сервера, на старте сервера можно сбилдить таблицу, и запомнить max id (key) user'a, и при запросе contains, если id <= max id, то идти в эту статическую хеш таблицу, иначе в динамическую

[floppa322]

mayton2019, да нет, если какой-то код, в данном случае contains(k), читал дважды из памяти (при этом времени на вычисления тратил совсем немного), то уменьшение количества обращений к памяти в 2 раза увеличит скорость работы этого кода тоже почти вдвое. А contains(k) у PerfectHashTable фактически единственный метод

[mayton2019]

floppa322, я все таки хочу понять мотивацию. Тебе нужна вспомогательная стуктура для алгоритма. Если ты уже дошел до такой ситуации что тебе нужна мемоизация расчетов (max(id)) то будь добр - потрать время на подготовку.
Основной алгоритм отработает быстро. Если хочешь идеальное хешировние - то по ссылке которую ты приводишь все равно нет гарантий что идеальная генерация закончится в 1 итерацию. Тоесть полюбому построение таблицы у тебя - слабое место. Ищи компромиссы.

[mayton2019]

floppa322,

А contains(k) у PerfectHashTable фактически единственный метод

если тебе нужен только contains - то посмотри в сторону Фильтра Блума. Это - probabalistic проверка но она
надежно работает для закрытие большего числа запросов.

Вобщем я выдохся. Я думаю что твой тюнинг он - очень специфичен. И его нельзя решать только теоретически.
У тебя должно быть как минмум 3 макета софта. Под open-adressing и под separate-chaining и под твой идеальный квадрат. Я напомню что самые лучшие реализации алгоритмов - обладают сильной когерентностью по памяти.
Это связано с кешами в железе. Поэтому твои теоретические обоснования могут сильно ошибаться в практике.
Вот. И результатом этих трех макетов должны быть 3 бенчмарка где ты показываешь практически
время инициализации структуры и среднее время доступа.

Вобшем все. Коллеги. Прошу отписать ваше мнение.

[floppa322]

mayton2019, ну у фильтра блума вообще будет K кэш миссов в среднем )
Тут-то я вообще с 2-х до 1-го хочу улучшить