Идеальное хэширование

    Какова сложность поиска элемента по ключу?

    Это зависит от того, какую структуру данных использовать.

    В односвязном списке - линейная сложность.

    В отсортированном массиве или в двоичном дереве поиска - логарифмическая сложность.

    В хэш-таблице - сложность константная. Но это в лучшем случае. А в худшем … стремится к линейной…

    А можно ли создать идеальную хэш-таблицу, чтобы сложность поиска элемента даже в худшем случае оставалась константной?

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

    Идеально! Поговорим о том, как это сделать.
    Кстати, на курсе «Алгоритмы и структуры данных» на платформе OTUS у нас есть отдельный модуль, посвящённый вопросам создания хэш-таблиц.


    Представьте англо-русский словарь. Английские слова являются ключами, а перевод - значениями. Время поиска любого слова в таком словаре может происходить за константное время, как если бы мы обращались к элементу массива по индексу!

    Взял, такой, хэш-код слова “dog”, вычислил хэш-функцию, поколдовал ещё немножко, и, вуаля, в руках уже «собака» на поводке указателе!

    Как такое возможно?

    Предположим, в словаре 10.000 слов-ключей. Для их хранения мы открываем хэш-таблицу на 10.000 элементов. Возможно ли создать «волшебную» хэш-функцию-биекцию, которая каждый ключ отображала бы на индекс массива, где он должен лежать? Наверное, это возможно, если создать «небольшую» нейронную сеть и обучить её. 

    Если же ограничиваться простейшей хэш-функцией вида «(A * k + B) % P % N», с возможностью подбора лишь двух коэффициентов A и В, то создать “волшебную” биекцию вряд ли удастся - коллизий не избежать. В этой формуле:
    k - хэшкод уникального ключа,
    P - заранее заданное простое число, большее любого возможного ключа k,
    N - размер хеш-таблицы, то есть количество всех ключей.

    Идея идеального хэширования заключается в двухэтапном хэшировании.

    На первом этапе находим «квартиру», а  на втором этапе - «комнату», где располагается искомое значение.

    Это напоминает метод разрешения коллизий методом цепочек. Но если в методе цепочек в каждой “квартире” расположен односвязный список «комнат», то в идеальном хэшировании мы в каждой квартире создадим отдельную хэш-таблицу с матрицей «комнат». Это будут «квадрокомнатные квартиры», но обо всём по порядку.

    Первый этап

    Минимизация количества «комнат» в «квартирах».

    Поскольку список всех ключей известен заранее, то можно подобрать такие коэффициенты, чтобы максимальное количество «комнат» (коллизий) в одной «квартире» было минимальным. Достаточно несколько десятков попыток, чтобы минимизировать максимальное количество коллизий. 

    Например, за 100 итераций подбора коэффициентов для словаря из 10.000 ключей максимальное количество коллизий для одного элемента не превышает 10.

    Итак, на первом этапе мы подбираем глобальные коэффициенты А и В для хэш-функции вида «(A * k + B) % P % N». Эта функция вычисляет номер «квартиры», в которой находится значение для заданного ключа. При этом минимизируется максимальное количество «комнат» (коллизий) в каждой «квартире».

    Второй этап

    Для размещения K элементов в одной «квартире» мы резервируем «комнат». Такая «квадрокомнатная квартира» позволит без особого труда подобрать коэффициенты A и B для размещения K элементов без единой коллизии, потому что значения всех ключей известно заранее (напомним, что хэш-коды всех ключей различны). Коэффициенты подбираются для каждой «квартиры» отдельно и хранятся в каждом элементе первой хэш-таблицы, вместе с количеством «комнат».

    Вот и всё!

    Для поиска любого элемента в идеальной хэш-таблице необходимо выполнить следующие действия:

    1. Найти номер «квартиры» i по хэш-коду ключа k: «(A * k + B) % P % N».

    2. Взять коэффициенты для вычисления номера комнаты: Ai, Bi, .

    3. Найти номер «комнаты» по формуле: «(Ai * k + Bi) % P % K²»

    4. Вернуть значение из найденной «комнаты».

    В любом случае (как в лучшем, так и худшем) на поиск элемента потребуется константное количество действий, которое не зависит от общего количества элементов.

    Расход памяти

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

    Возьмём, для примера, хэш-таблицу из N = 10 элементов. В каждом элементе может быть от 0 до 10 коллизий. Вычислим вероятность коллизий, умножим на затраты по памяти и найдём математическое ожидание объёма памяти для размещения одного элемента.

    Итого: для хранения “квартир” нужно N ячеек памяти, для хранения “комнат” - примерно 1.9 * N. Суммарный расход памяти: 2.9 * N = О(N) - линейный.

    Заключение

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


    А теперь небольшой бонус. 15 января я проведу Demo Day курса "Алгоритмы и структуры данных" на платформе OTUS, приглашаю всех желающих узнать подробно о курсе и задать вопросы лично.

    Также хочу посоветовать еще несколько статей из своего блога, которые уже успели получить хороший отклик у читателей:

    OTUS
    Цифровые навыки от ведущих экспертов

    Комментарии 9

      0

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

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

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

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

              Зато они будут работать нормально. Тривиальным функциям в статье можно скормить кучу чисел, делящихся на N^2 и убить всю таблицу гарантированно.

            0

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

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

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


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

                  0
                  Если выбрать несколько чисел кратных k^2, то здесь поможет подбор большого значения A, которое может быть от 1 до P-1, в результате чего после умножения x*a и нахождения остатка %P могут получиться числа не кратные k^2. Они ещё должны сначала пройти первое сито и создать ровно k коллизий после первого этапа хеширования.
                  К тому же, ещё раз обращу внимание на изначальное условие — список всех ключей известен заранее, до начала выбора коэффициентов хэш-таблиц.
                  В любом случае, спасибо за ваши ценные комментарии.

            Только полноправные пользователи могут оставлять комментарии. Войдите, пожалуйста.

            Самое читаемое