Pull to refresh

Comments 9

Очень интересно, но ничего не понял. Интуитивно понятно, что суммарный расход памяти будет линейный от размера адресной книги: в другом примере — улица-дом-квартира.
Как это можно пересчитать для более запутанных историй? Где структуры порядков различные?
Перечитаю ещё раз...

Криптографические хеш функции с достаточной вероятностью гарантируют отсутсвие коллизий.

Память у вас n^2. Всегда берется худший случай. А то прод взорвется в самый неподходящий момент.
У криптографических хеш-функций сложность вычисления же будет зашкаливать, относительно обычных?

Тяжеловато будет для реалтайм-обработки
Конечно. Но формально O(1). Как учебный пример гораздо лучше того что в статье.

Зато они будут работать нормально. Тривиальным функциям в статье можно скормить кучу чисел, делящихся на 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, но я все-равно смогу подобрать такой набор ключей, что у вас все взорвется. Со сложными хэшами вы ничего не сможете сказать о гарантии остутствия коллизий на втором этапе.

Спасибо за дельные замечания. Подправил формулы, добавил недостающее большое простое число P. Теперь оба коэффициента А и В имеют значение.

(Ax+B) % P % N слабо решает проблему. Во-первых, при изменении B, в большинстве значений x будет все тот же сдвиг элементов на 1.


А главное, это не решает основной проблемы — я элементарно могу подобрать тест, что все элементы попадут в одну комнату или всего несколько комнат. И при этом элементы попадут в одну и ту же ячейку в комнате. %P делает это немного сложнее, но не исключает этого. Достаточно взять 2 числа делящихся на k^2 * P. Если же P настолько большое, что такие числа не выбрать, то можно взять 2 маленьких числа делящихся на k^2.

Если выбрать несколько чисел кратных k^2, то здесь поможет подбор большого значения A, которое может быть от 1 до P-1, в результате чего после умножения x*a и нахождения остатка %P могут получиться числа не кратные k^2. Они ещё должны сначала пройти первое сито и создать ровно k коллизий после первого этапа хеширования.
К тому же, ещё раз обращу внимание на изначальное условие — список всех ключей известен заранее, до начала выбора коэффициентов хэш-таблиц.
В любом случае, спасибо за ваши ценные комментарии.
Only those users with full accounts are able to leave comments. Log in, please.