Comments 9
Очень интересно, но ничего не понял. Интуитивно понятно, что суммарный расход памяти будет линейный от размера адресной книги: в другом примере — улица-дом-квартира.
Как это можно пересчитать для более запутанных историй? Где структуры порядков различные?
Перечитаю ещё раз...
Память у вас n^2. Всегда берется худший случай. А то прод взорвется в самый неподходящий момент.
Во-первых, вам нигде не нужно 2 коэффициента A и B. Можно положить B=0 — это просто сдвинет значения хешей для всех элементов. Для каждой вашей таблицы это просто циклический сдвиг ячеек.
Во-вторых, есть вариант, когда ваш подход не сработает вообще.
Самое тривиальное, когда хотя бы 2 числа в одной квадратной комнате делятся на k^2 — они в одну и ту же квадратную ячейку попадут (c номером Bi). Не гарантируется, что можно подобрать A так, что такого никогда не произойдет. Думаю, достаточно много чисел, делящихся на 1*4*9*16 все сломают. Надо чтобы каждая квадратная ячейка содержала или 0 или >=5 элементов.
В-третьих, если все ключи делятся на их общее количество, то у вас всегда на первом этапе все элементы попадут в одну квадратную комнату, и она съест N^2 памяти. А если хотя бы 2 ключа еще и на N^2 делятся, то у вас эти 2 ключа в одном и том же месте хранятся для любых коэффициентов.
И в конце, оценка потребления памяти у вас в среднем, а не максимальное. Так-то, почти любая хэш таблица в среднем не имеет коллизий, потребляет линейное количество памяти и работает за констату. Ваша "идеальная" ничем не лучше. Более того, она в плохих случаях вообще ломается.
Вы можете попробовать брать по другим модулям, а не N, k^2, но я все-равно смогу подобрать такой набор ключей, что у вас все взорвется. Со сложными хэшами вы ничего не сможете сказать о гарантии остутствия коллизий на втором этапе.
(Ax+B) % P % N слабо решает проблему. Во-первых, при изменении B, в большинстве значений x будет все тот же сдвиг элементов на 1.
А главное, это не решает основной проблемы — я элементарно могу подобрать тест, что все элементы попадут в одну комнату или всего несколько комнат. И при этом элементы попадут в одну и ту же ячейку в комнате. %P делает это немного сложнее, но не исключает этого. Достаточно взять 2 числа делящихся на k^2 * P. Если же P настолько большое, что такие числа не выбрать, то можно взять 2 маленьких числа делящихся на k^2.
К тому же, ещё раз обращу внимание на изначальное условие — список всех ключей известен заранее, до начала выбора коэффициентов хэш-таблиц.
В любом случае, спасибо за ваши ценные комментарии.
Идеальное хэширование