На главную Наши проекты:
Журнал   ·   Discuz!ML   ·   Wiki   ·   DRKB   ·   Помощь проекту
ПРАВИЛА FAQ Помощь Участники Календарь Избранное RSS
msm.ru
! правила раздела Алгоритмы
1. Помните, что название темы должно хоть как-то отражать ее содержимое (не создавайте темы с заголовком ПОМОГИТЕ, HELP и т.д.). Злоупотребление заглавными буквами в заголовках тем ЗАПРЕЩЕНО.
2. При создании темы постарайтесь, как можно более точно описать проблему, а не ограничиваться общими понятиями и определениями.
3. Приводимые фрагменты исходного кода старайтесь выделять тегами code.../code
4. Помните, чем подробнее Вы опишете свою проблему, тем быстрее получите вразумительный совет
5. Запрещено поднимать неактуальные темы (ПРИМЕР: запрещено отвечать на вопрос из серии "срочно надо", заданный в 2003 году)
6. И не забывайте о кнопочках TRANSLIT и РУССКАЯ КЛАВИАТУРА, если не можете писать в русской раскладке :)
Модераторы: Akina, shadeofgray
Страницы: (2) [1] 2  все  ( Перейти к последнему сообщению )  
> Создание хорошей хеш-функции
    Всем хай! Сходу к делу!

    Есть строка, подчиняющаяся следующей маске: XXX-??, где Х - малая буква латинского алфавита, ? - любая арабская цифра, - это дефис - const.
    Примеры строк: azz-92, rat-11, hhh-00

    Это строка является ключом для некоторого объекта (абсолютно не важна его природа). Объектов пусть будет 20 штук.
    Нужна хеш-функция, принимающая такой ключ и в качестве ответа возвращающая значение из отрезка от 0 до 19 (это индексы карманов в хеш-таблице, ведь всего 20 объектов нужно хранить). Очевидно, что желательно стремится к совершенной хеш-функции, чтобы не получались коллизии.

    Меня интересует в принципе, что нужно пробовать вычислять, чтобы построить адекватную хеш-функцию? Использовать ASCII-коды символов ключа или байты конкретные (сдвиги)?
      Если эти 20 объектов заранее известны, то нужно построить Perfect Hash - про
      "совершенной хеш-функции" написано верно.

      Если неизвестны, то любая - хорошая или плохая - хэш функция даст коллизии для 1 757 600 вариантов на 20 мест.
        Цитата MBo @
        Если неизвестны

        Эти строки-ключи вводятся с клавиатуры. Т е заранее точно неизвестно, хотя общее кол-во возможных ключей как бы известно (ты вроде бы и посчитал их по ф-лам комбинаторики 1 757 600 вариантов)

        Mbo, я правильно понимаю, что адекватную ХФ можно построить только тогда, когда количество карманов в хеш-таблице сопоставимо с количеством обрабатываемых объектов?
          Сравнивать качество хэш-функций применительно к описанной ситуации можно лишь в случае, когда набор значений заведомо НЕ случаен - т.е. когда при известном значении части элементов набора вероятность некоего значения очередного элемента зависит от этого значения. Иначе устроит любая хэш-функция, не имеющая статистической погрешности.
            Когда ключи ввели - можно их использовать для построения совершенной функции, или уже поздно?

            Что значит "адекватная ХФ"?
            Если хэш-функция не заведомая дрянь, то процент коллизий зависит только от уровня заполненности таблицы.
              Akina, спс за пояснение!

              Сейчас введу максимум конкретики:
              1) хеш-таблица имеет ровно 20 карманов. Кол-во карманов не меняется - static vector.
              2) хеш-функция НЕ динамическая, т е она прописана один раз и обрабатывает любые поступающие ключи.
              3) ключи у объектов не повторяются (уникальные ключи)

              Как я понял, всего возможно получить около 1.75 млн различных ключей.
              В моем понимании хеш-функция будет около совершенной, если для 1.75/20 = 87 500 ключей хеш-функция вернет в качестве ответа 0, для следующей группы 87 500 ключей вернет 1 и т.д. Т е эти 1.75 млн вариантов разбиваются на 20 групп по 87 500 наборов и для каждого набора хф выдает свой индекс.

              При вводе с клавиатуры 20 ключей, примерно каждый из ключей попадет в одну из групп (понятно, что с учетом теории вероятностей это маловероятно, но все же).

              Можно создать такую хеш-функцию?
                Цитата FasterHarder @
                Можно создать такую хеш-функцию?

                Легко!
                Отбрасываем буквы и тире, и получаем остаток от деления числа на 20. Идеальная для описанной модели хэш-функция!!!
                  Цитата Akina @
                  Отбрасываем буквы и тире, и получаем остаток от деления числа на 20

                  хм, ясно! Понятно, что две последних цифры нужно брать в качестве двузначного целого числа.
                  и такая хф будет соответствовать этому:
                  Цитата Akina @
                  Иначе устроит любая хэш-функция, не имеющая статистической погрешности.



                  P.S. в целом ведь для более сложных ключей построение адекватной хф задача ведь абсолютно нетривиальная. Вроде на практике стараются использовать уже готовые хф, а не разрабатывать с нуля. Наверняка можно убить сотни часов, а так и не построить нормальной хф...
                    Цитата Akina @
                    Легко!
                    Отбрасываем буквы и тире, и получаем остаток от деления числа на 20. Идеальная для описанной модели хэш-функция!!!

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

                    По мне, так куда лучше функция вида sum(s[i]*C[i]) mod 20,
                    s[i] меняющиеся символы кода (их числовые значения, можно сразу взять остаток от деления на 20).
                    С[i] заранее выбранные коэффициенты, взаимно-простые с длиной таблицы (любые нечётные, кроме 5 и 15)

                    Ещё лучше вместо кодов символов использовать какие-нибудь их нелинейные комбинации (что-нибудь типа, например, a1 = s[1] ^ int(s[2]*3)) Это лучше разгоняет значения функции для кодов отличающихся, к примеру, одной единственной буквой.

                    Добавлено
                    Можно включить в сумму и не меняющиеся символы, просто поставив им в соответствие коэффициент, равный 0.

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

                    Добавлено
                    Один из вариантов совсем простой хэш функции
                    ExpandedWrap disabled
                      def h(s):
                          k = 0
                          for c in s:
                              k = k*3 + ord(c) # k += (k << 1) + ord(c)
                          return k%20

                    короткая, неплохо разгоняет коды, можно обойтись без умножения, считается быстро, даже на каком нибудь древнем i8080, m6800 или немного более молодом PIC16.
                    Сообщение отредактировано: amk -
                      amk, big спс тебе за столь развернутый ответ!
                      но, мне типа это, непонятно, как ты пришел к такой формуле, то бишь чем ты руководствовался:
                      k = k*3 + ord© # k += (k << 1) + ord©

                      т е ты придумал такую зависимость. Она типа какая-то стандартная и ты лишь немного подкрутил ее.
                      Сообщение отредактировано: FasterHarder -
                        Конкретно эту хэш-функцию я нашёл в исходниках компилятора Small-С v2.1 Джеймса Хендрикса (это где-то в районе 1980 г.) где она использовалась в функциях работы с таблицей глобальных символов (в версиях до 2.0 использовалась простая таблица с линейным поиском). Там правда была таблица с рехэшированием, и размер таблицы был другой. Для локальных символов как и ранее, использовалась простая таблица, с последовательным заполнение, позволяющая быструю очистку вышедших из зоны видимости символов, обычным сдвигом указателя начала таблицы на запомненную ранее позицию.
                        Метод с отдельными множителями для каждого символа сходен с методом вычисления контрольной цифры в наших ИНН. Может быть он где-то описан, но он достаточно прост, чтобы до него можно было дойти самому.
                        Модификация с нелинейным смешиванием соседних символов сделана по аналогии с методом перемешивания разрядов в некоторых генераторах псевдо случайных чисел.

                        Кстати, метод с отдельными множителями более общий, при выборе множителей 3, 1, 7, 9, 3, 1 и делителе 20 он даёт для строки длины 6 тот же результат, что и описанный итеративный метод. Кстати, этот ряд показывает, что конкретно эта функция для делителя 20 не очень хороша. Смена множителя ничего не меняет - другие множители дают картину не лучше, а большинство даже хуже.

                        После # в Питоне идёт комментарий. Там описан альтернативный способ вычисления без умножения.
                          FasterHarder
                          Вы уж простите за некоторую резкость, но в голове у Вас ну полный винегрет.
                          Или Вам нужна хэш-функция, идеальная вообще, или идеальная для конкретного случая, для набора, имеющего некий набор особенностей и отвечающего некоему набору условий. А Вы, видимо, не определились, поскольку скачете зайцем от одного варианта к другому и обратно...
                            Да, кстати, FasterHarder речь идёт о 20 ячейках, в которых можно хранить не больше 20 объектов, или всё же о карманах, каждый из которых может, вообще говоря, содержать любое количество объектов?
                              Цитата Akina @
                              Вы уж простите за некоторую резкость, но в голове у Вас ну полный винегрет.

                              можно и на ты (как обычно) ))
                              Akina, я прекрасно понял твой вариант хеш-функции и он меня вполне устраивает!
                              я никуда не прыгаю, т к вообще изначально в 1-ом посте даже писал, что:
                              Цитата FasterHarder @
                              Меня интересует в принципе, что нужно пробовать вычислять, чтобы построить адекватную хеш-функцию?

                              т е меня интересовали общие принципы построения ХФ, поэтому и стал уточнять вариант amk.

                              Цитата amk @
                              Да, кстати, FasterHarder речь идёт о 20 ячейках, в которых можно хранить не больше 20 объектов, или всё же о карманах, каждый из которых может, вообще говоря, содержать любое количество объектов?

                              я так понимаю, что ты намекаешь на хеш-таблицу, базирующуюся на цепочках? Если, да, то нет, используется хеш-таблица с открытой адресацией. Т е 1 карман предназначен для 1 объекта!

                              P.S. таки да, хеш-функции я знаю и понимаю не досконально, разумеется...
                                Цитата FasterHarder @
                                меня интересовали общие принципы построения ХФ

                                Принцип построения - гарантия равномерности. И перекосило меня вот от этой фразы:
                                Цитата FasterHarder @
                                для более сложных ключей построение адекватной хф задача ведь абсолютно нетривиальная. Вроде на практике стараются использовать уже готовые хф, а не разрабатывать с нуля. Наверняка можно убить сотни часов, а так и не построить нормальной хф...

                                Для любого детерминированного набора простейшей хэш-функцией всегда будет номер элемента набора (с учётом свёртки - как правило, ширина хэша меньше ширины набора,- последняя цифра номера по основанию ширины хэша). А особенности набора как правило позволяют построить достаточно простую функцию вычисления этого номера.
                                Твоя же фраза относится к тем странным случаям, когда от хэша просят не только равномерности, но ещё и непредсказуемости (т.е. знание хэша элемента не позволяет предсказать хэш элемента, имеющего от этого определённое смещение).
                                0 пользователей читают эту тему (0 гостей и 0 скрытых пользователей)
                                0 пользователей:


                                Рейтинг@Mail.ru
                                [ Script execution time: 0,0501 ]   [ 16 queries used ]   [ Generated: 28.03.24, 20:16 GMT ]