Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.140.255.150] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Есть строка, подчиняющаяся следующей маске: XXX-??, где Х - малая буква латинского алфавита, ? - любая арабская цифра, - это дефис - const. Примеры строк: azz-92, rat-11, hhh-00 Это строка является ключом для некоторого объекта (абсолютно не важна его природа). Объектов пусть будет 20 штук. Нужна хеш-функция, принимающая такой ключ и в качестве ответа возвращающая значение из отрезка от 0 до 19 (это индексы карманов в хеш-таблице, ведь всего 20 объектов нужно хранить). Очевидно, что желательно стремится к совершенной хеш-функции, чтобы не получались коллизии. Меня интересует в принципе, что нужно пробовать вычислять, чтобы построить адекватную хеш-функцию? Использовать ASCII-коды символов ключа или байты конкретные (сдвиги)? |
Сообщ.
#2
,
|
|
|
Если эти 20 объектов заранее известны, то нужно построить Perfect Hash - про
"совершенной хеш-функции" написано верно. Если неизвестны, то любая - хорошая или плохая - хэш функция даст коллизии для 1 757 600 вариантов на 20 мест. |
Сообщ.
#3
,
|
|
|
Цитата MBo @ Если неизвестны Эти строки-ключи вводятся с клавиатуры. Т е заранее точно неизвестно, хотя общее кол-во возможных ключей как бы известно (ты вроде бы и посчитал их по ф-лам комбинаторики 1 757 600 вариантов) Mbo, я правильно понимаю, что адекватную ХФ можно построить только тогда, когда количество карманов в хеш-таблице сопоставимо с количеством обрабатываемых объектов? |
Сообщ.
#4
,
|
|
|
Сравнивать качество хэш-функций применительно к описанной ситуации можно лишь в случае, когда набор значений заведомо НЕ случаен - т.е. когда при известном значении части элементов набора вероятность некоего значения очередного элемента зависит от этого значения. Иначе устроит любая хэш-функция, не имеющая статистической погрешности.
|
Сообщ.
#5
,
|
|
|
Когда ключи ввели - можно их использовать для построения совершенной функции, или уже поздно?
Что значит "адекватная ХФ"? Если хэш-функция не заведомая дрянь, то процент коллизий зависит только от уровня заполненности таблицы. |
Сообщ.
#6
,
|
|
|
Akina, спс за пояснение!
Сейчас введу максимум конкретики: 1) хеш-таблица имеет ровно 20 карманов. Кол-во карманов не меняется - static vector. 2) хеш-функция НЕ динамическая, т е она прописана один раз и обрабатывает любые поступающие ключи. 3) ключи у объектов не повторяются (уникальные ключи) Как я понял, всего возможно получить около 1.75 млн различных ключей. В моем понимании хеш-функция будет около совершенной, если для 1.75/20 = 87 500 ключей хеш-функция вернет в качестве ответа 0, для следующей группы 87 500 ключей вернет 1 и т.д. Т е эти 1.75 млн вариантов разбиваются на 20 групп по 87 500 наборов и для каждого набора хф выдает свой индекс. При вводе с клавиатуры 20 ключей, примерно каждый из ключей попадет в одну из групп (понятно, что с учетом теории вероятностей это маловероятно, но все же). Можно создать такую хеш-функцию? |
Сообщ.
#7
,
|
|
|
Цитата FasterHarder @ Можно создать такую хеш-функцию? Легко! Отбрасываем буквы и тире, и получаем остаток от деления числа на 20. Идеальная для описанной модели хэш-функция!!! |
Сообщ.
#8
,
|
|
|
Цитата Akina @ Отбрасываем буквы и тире, и получаем остаток от деления числа на 20 хм, ясно! Понятно, что две последних цифры нужно брать в качестве двузначного целого числа. и такая хф будет соответствовать этому: Цитата Akina @ Иначе устроит любая хэш-функция, не имеющая статистической погрешности. P.S. в целом ведь для более сложных ключей построение адекватной хф задача ведь абсолютно нетривиальная. Вроде на практике стараются использовать уже готовые хф, а не разрабатывать с нуля. Наверняка можно убить сотни часов, а так и не построить нормальной хф... |
Сообщ.
#9
,
|
|
|
Цитата Akina @ Легко! Отбрасываем буквы и тире, и получаем остаток от деления числа на 20. Идеальная для описанной модели хэш-функция!!! При вычислении целого буквенные разряды надо считать по соответствующему основанию (можно не сдвигать к нулю). Одна из самых плохих хэш-функций для данного случая. Если последние цифры кодов совпадают, то все коды сваливаются в два кармана. А при некоторых условиях все они оказываются даже не в двух, а в одном кармане. По мне, так куда лучше функция вида sum(s[i]*C[i]) mod 20, s[i] меняющиеся символы кода (их числовые значения, можно сразу взять остаток от деления на 20). С[i] заранее выбранные коэффициенты, взаимно-простые с длиной таблицы (любые нечётные, кроме 5 и 15) Ещё лучше вместо кодов символов использовать какие-нибудь их нелинейные комбинации (что-нибудь типа, например, a1 = s[1] ^ int(s[2]*3)) Это лучше разгоняет значения функции для кодов отличающихся, к примеру, одной единственной буквой. Добавлено Можно включить в сумму и не меняющиеся символы, просто поставив им в соответствие коэффициент, равный 0. Добавлено Цитата FasterHarder @ Это для криптографически стойких имеет смысл не изобретать велосипед. Для хэш-таблиц обычно важно время вычисления функции, а от коллизий избавиться всё равно не получается - слишком малы размеры таблиц. Существует несколько видов неплохих функций, к некоторым надо лишь подобрать подходящие константы. Вроде на практике стараются использовать уже готовые хф, а не разрабатывать с нуля. Добавлено Один из вариантов совсем простой хэш функции 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. |
Сообщ.
#10
,
|
|
|
amk, big спс тебе за столь развернутый ответ!
но, мне типа это, непонятно, как ты пришел к такой формуле, то бишь чем ты руководствовался: k = k*3 + ord© # k += (k << 1) + ord© т е ты придумал такую зависимость. Она типа какая-то стандартная и ты лишь немного подкрутил ее. |
Сообщ.
#11
,
|
|
|
Конкретно эту хэш-функцию я нашёл в исходниках компилятора Small-С v2.1 Джеймса Хендрикса (это где-то в районе 1980 г.) где она использовалась в функциях работы с таблицей глобальных символов (в версиях до 2.0 использовалась простая таблица с линейным поиском). Там правда была таблица с рехэшированием, и размер таблицы был другой. Для локальных символов как и ранее, использовалась простая таблица, с последовательным заполнение, позволяющая быструю очистку вышедших из зоны видимости символов, обычным сдвигом указателя начала таблицы на запомненную ранее позицию.
Метод с отдельными множителями для каждого символа сходен с методом вычисления контрольной цифры в наших ИНН. Может быть он где-то описан, но он достаточно прост, чтобы до него можно было дойти самому. Модификация с нелинейным смешиванием соседних символов сделана по аналогии с методом перемешивания разрядов в некоторых генераторах псевдо случайных чисел. Кстати, метод с отдельными множителями более общий, при выборе множителей 3, 1, 7, 9, 3, 1 и делителе 20 он даёт для строки длины 6 тот же результат, что и описанный итеративный метод. Кстати, этот ряд показывает, что конкретно эта функция для делителя 20 не очень хороша. Смена множителя ничего не меняет - другие множители дают картину не лучше, а большинство даже хуже. После # в Питоне идёт комментарий. Там описан альтернативный способ вычисления без умножения. |
Сообщ.
#12
,
|
|
|
FasterHarder
Вы уж простите за некоторую резкость, но в голове у Вас ну полный винегрет. Или Вам нужна хэш-функция, идеальная вообще, или идеальная для конкретного случая, для набора, имеющего некий набор особенностей и отвечающего некоему набору условий. А Вы, видимо, не определились, поскольку скачете зайцем от одного варианта к другому и обратно... |
Сообщ.
#13
,
|
|
|
Да, кстати, FasterHarder речь идёт о 20 ячейках, в которых можно хранить не больше 20 объектов, или всё же о карманах, каждый из которых может, вообще говоря, содержать любое количество объектов?
|
Сообщ.
#14
,
|
|
|
Цитата Akina @ Вы уж простите за некоторую резкость, но в голове у Вас ну полный винегрет. можно и на ты (как обычно) )) Akina, я прекрасно понял твой вариант хеш-функции и он меня вполне устраивает! я никуда не прыгаю, т к вообще изначально в 1-ом посте даже писал, что: Цитата FasterHarder @ Меня интересует в принципе, что нужно пробовать вычислять, чтобы построить адекватную хеш-функцию? т е меня интересовали общие принципы построения ХФ, поэтому и стал уточнять вариант amk. Цитата amk @ Да, кстати, FasterHarder речь идёт о 20 ячейках, в которых можно хранить не больше 20 объектов, или всё же о карманах, каждый из которых может, вообще говоря, содержать любое количество объектов? я так понимаю, что ты намекаешь на хеш-таблицу, базирующуюся на цепочках? Если, да, то нет, используется хеш-таблица с открытой адресацией. Т е 1 карман предназначен для 1 объекта! P.S. таки да, хеш-функции я знаю и понимаю не досконально, разумеется... |
Сообщ.
#15
,
|
|
|
Цитата FasterHarder @ меня интересовали общие принципы построения ХФ Принцип построения - гарантия равномерности. И перекосило меня вот от этой фразы: Цитата FasterHarder @ для более сложных ключей построение адекватной хф задача ведь абсолютно нетривиальная. Вроде на практике стараются использовать уже готовые хф, а не разрабатывать с нуля. Наверняка можно убить сотни часов, а так и не построить нормальной хф... Для любого детерминированного набора простейшей хэш-функцией всегда будет номер элемента набора (с учётом свёртки - как правило, ширина хэша меньше ширины набора,- последняя цифра номера по основанию ширины хэша). А особенности набора как правило позволяют построить достаточно простую функцию вычисления этого номера. Твоя же фраза относится к тем странным случаям, когда от хэша просят не только равномерности, но ещё и непредсказуемости (т.е. знание хэша элемента не позволяет предсказать хэш элемента, имеющего от этого определённое смещение). |
Сообщ.
#16
,
|
|
|
Цитата FasterHarder @ В таком случае делай размер таблицы хотя-бы на 25-30% больше числа записываемых в неё объектов. Или отказывайся от хэш-таблицы и пользуйся простым вектором. нет, используется хеш-таблица с открытой адресацией. Т е 1 карман предназначен для 1 объекта! |
Сообщ.
#17
,
|
|
|
FasterHarder
Ну и вот тебе ещё |
Сообщ.
#18
,
|
|||||||||||||||||||||
|
Подсчитал тут кое-что в обед
Размер - число ячеек (карманов) в таблице Заполнение - ожидаемое число коллизий при занесении таблицу 20 объектов Поиск - ожидаемое число проверок при поиске объекта, находящегося в таблице Поиск 2 - ожидаемое число проверок при поиске объекта, отсутствующего в таблице (до выяснения этого факта) |