OberonCore
https://forum.oberoncore.ru/

Хэш 63% - что это за закон природы такой?
https://forum.oberoncore.ru/viewtopic.php?f=27&t=3554
Страница 1 из 6

Автор:  Сергей Губанов [ Четверг, 25 Август, 2011 13:51 ]
Заголовок сообщения:  Хэш 63% - что это за закон природы такой?

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

Если значение хэшкода h ограничено диапазоном (0 <= h) & (h < N), то при хэшировании N случайных объектов различных хэшкодов получается примерно 0.63 * N или меньше если хэшфункция совсем плохая.

Придумать хэшфункцию ограниченную числом N, которая при хэшировании N случайных объектов выдавала бы больше чем 63 процента с копейками различных хэшкодов не удаётся, почему-то.

Наиболее простая "63%" хэшфункция:
Код:
      private static unsafe uint Hash (char* a, int n)
      {
         uint h = 0;
         int i = 0;
         while (i < n)
         {
            h = h * 2 + a[i++];
         }
         return h % N;
      }

Перепробовал кучу других вариантов какие-только в голову пришли, но лучше чем 63 с копейками процентов не получается :roll: :roll: :roll:

Что это за закон природы такой?

Автор:  Ярослав Романченко [ Четверг, 25 Август, 2011 14:16 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

http://en.wikipedia.org/wiki/Hash_table#Load_factor
Цитата:
With a good hash function, the average lookup cost is nearly constant as the load factor increases from 0 up to 0.7(about 2/3 full) or so.[citation needed] Beyond that point, the probability of collisions and the cost of handling them increases.

Автор:  albobin [ Четверг, 25 Август, 2011 15:21 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N.
0.63

Автор:  Сергей Губанов [ Четверг, 25 Август, 2011 15:26 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Ярослав Романченко писал(а):
http://en.wikipedia.org/wiki/Hash_table#Load_factor
Цитата:
With a good hash function, the average lookup cost is nearly constant as the load factor increases from 0 up to 0.7(about 2/3 full) or so.[citation needed] Beyond that point, the probability of collisions and the cost of handling them increases.
Они говорят, что скорость поиска перестаёт быть постоянной и начинает увеличиваться если хэштаблица заполнена более чем на 2/3.
albobin писал(а):
Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N.
0.63
Вот только почему? Где-то тут, видимо, запрятана центральная предельная теорема...

Автор:  albobin [ Четверг, 25 Август, 2011 15:40 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Сергей Губанов писал(а):
Ярослав Романченко писал(а):
http://en.wikipedia.org/wiki/Hash_table#Load_factor
Цитата:
With a good hash function, the average lookup cost is nearly constant as the load factor increases from 0 up to 0.7(about 2/3 full) or so.[citation needed] Beyond that point, the probability of collisions and the cost of handling them increases.
Они говорят, что скорость поиска перестаёт быть постоянной и начинает увеличиваться если хэштаблица заполнена более чем на 2/3.
albobin писал(а):
Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N.
0.63
Вот только почему? Где-то тут, видимо, запрятана центральная предельная теорема...

Почему что?
1. Почему 0.63 в "Сгенерите N раз случайное целое число из диапазона 1..N ..." ?
или
2. Почему в исходной проблеме те же 0.63?

IMHO это по сути одно и то же.

Автор:  Сергей Губанов [ Четверг, 25 Август, 2011 15:44 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Придумал формулу:

0.63212.... = 1 - 1/e = 1 - Limit[(1 - 1/n)^n, n->Infinity]

Автор:  Сергей Губанов [ Четверг, 25 Август, 2011 15:54 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Вероятность того что два числа совпадут равна 1/N, а не совпадут равна 1 - 1/N. Вероятность того что все числа будут разными равна (1 - 1/N)^N-1, то есть примерно 1/e = 0.367879. А вероятность совпадений 1 - 1/e = 0.632121

Автор:  Владислав Жаринов [ Четверг, 25 Август, 2011 16:00 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Сергей Губанов писал(а):
Вероятность того что два числа совпадут равна 1/N, а не совпадут равна 1 - 1/N. Вероятность того что все числа будут разными равна (1 - 1/N)^N-1, то есть примерно 1/e = 0.367879. А вероятность совпадений 1 - 1/e = 0.632121
Сергей Губанов писал(а):
...
Перепробовал кучу других вариантов какие-только в голову пришли, но лучше чем 63 с копейками процентов не получается :roll: :roll: :roll:
Что это за закон природы такой?
Так получается, что все сгенерированные числа могут быть разными? Или только в бесконечности? :)

Автор:  Сергей Губанов [ Четверг, 25 Август, 2011 16:12 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Да, точно. Это я не правильно сказал. Надо ещё раз подумать.

Автор:  Владислав Жаринов [ Четверг, 25 Август, 2011 16:17 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Я не к тому, что формула неправильная... просто м.б. смысл у неё другой... допустим, не вероятностный?..
Интуитивно кажется - это как бы "предел возможности имитировать алгоритмически" разнообразие действительности...

Автор:  albobin [ Четверг, 25 Август, 2011 16:27 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

0.63 естественно при N не равном 2 :)

Автор:  Александр Ильин [ Четверг, 25 Август, 2011 16:28 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Сергей Губанов писал(а):
Вероятность того что два числа совпадут равна 1/N, а не совпадут равна 1 - 1/N. Вероятность того что все числа будут разными равна (1 - 1/N)^N-1, то есть примерно 1/e = 0.367879. А вероятность совпадений 1 - 1/e = 0.632121

Всё правильно, при N стремящемся к бесконечности такой предел и будет:
N = 1 => 1
N = 2 => 0.5
N = 3 => 4/9 = 0,44[4]
N = 4 => 27/64 = 0,390625
...
Естественно, при равной вероятности выпадения всех чисел.

Доп: Исправил одну цифру.

Автор:  Владислав Жаринов [ Четверг, 25 Август, 2011 16:34 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Александр Ильин писал(а):
...
Естественно, при равной вероятности выпадения всех чисел.
Как я понимаю, у Сергея "образовался закон", о котором говорил allbobin - что всегда в выборке из N чисел, "случайно" составленной по любому алгоритму, будет не более, чем ок.63% разных числовых объектов. Т.е. ок. 37% членов выборки будут совпадать с уже имеющимися.

Автор:  Сергей Губанов [ Четверг, 25 Август, 2011 17:11 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Драконограф писал(а):
Я не к тому, что формула неправильная... просто м.б. смысл у неё другой...
Да формула просто угадана. Смысл пока не понят.

Видимо рассуждать следует так. Есть таблица на N значений. Начинаем её заполнять. На каком-то шаге в ней X ячеек пусты и N-X ячеек заполнены быть может с повторениями (начальное значение X=N). Добавляем ещё одно случайное число. Оно может попасть в незаполненную ячейку с вероятностью X/N или в уже заполненную с вероятностью (N-X)/N. Попав в свободную ячейку оно уменьшит количество свободных ячеек на единицу. А попав в заполненную ячейку оно не изменяет состояние Ф[X] системы. Рисуем граф переходов:

На каждом шаге
Ф[X] переходит в Ф[X-1] с вероятностью X/N
или
Ф[X] остаётся самой собой с вероятностью (N-X)/N

Надо видимо отыскать наиболее вероятный путь в этом графе переходов.

Кстати, вероятность того что все числа будут разными равна (N/N)*((N-1)/N)*((N-2)/N)*((N-3)/N)*...*(3/N)*(2/N)*(1/N). Для N=10 это 0.00036288, для N=20 это 2.3202*10^{-8}. Вобщем, все числа разными при больших N не будут практически никогда.

Автор:  albobin [ Четверг, 25 Август, 2011 17:30 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

IMHO формула должна быть ((N-1)/N)^N
трактовка такова: это вероятность непопадания в конкретную ячейку, а это и есть доля "дыр" во всём диапазоне
остаётся только вычесть из единицы и получить "заполненность" диапазона

Автор:  Сергей Губанов [ Четверг, 25 Август, 2011 17:35 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Сергей Губанов писал(а):
На каждом шаге
Ф[X] переходит в Ф[X-1] с вероятностью X/N
или
Ф[X] остаётся самой собой с вероятностью (N-X)/N
Нарисовал начало этого процесса для N=10:
Вложение:
graph.png
graph.png [ 11.19 КБ | Просмотров: 7249 ]

Автор:  Сергей Губанов [ Четверг, 25 Август, 2011 18:59 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Полный граф для N=5 (красная линия - наиболее вероятный путь)
Вложение:
graph5.png
graph5.png [ 10.72 КБ | Просмотров: 7233 ]

Автор:  Александр Ильин [ Четверг, 25 Август, 2011 19:54 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

albobin писал(а):
IMHO формула должна быть ((N-1)/N)^N
Неа, у Сергея Губанова правильная формула. У вас показатель степени не тот, должен быть N-1. А возводимая в степень часть (N-1)/N = N/N - 1/N = 1 - 1/N, т.е. как у Сергея.

Смотрите, для N = 3:
1) первое число уникально с вероятностью = 1;
2) второе число либо уникально с вероятностью = (N-1)/N, т.е. 2/3, либо совпадает с первым числом с вероятностью = 1/3 = 1-(N-1)/N;
3) третье число:
- если первые два числа равны, то третье уникально с вероятностью = 2/3; сам этот вариант имеет вероятность = 1/3 (см. пункт 2), т.е. общая вероятность = 1/3*2/3;
- если первые два числа не равны (уникальны), то третье уникально с вероятностью = 1/3; сам этот вариант имеет вероятность = 2/3 (см. пункт 2), т.е. общая вероятность = 1/3*2/3;

Итого: третье число уникально с вероятностью = 1/3*2/3+1/3*2/3 = 2/9+2/9 = 4/9 = (1-1/N)^(N-1) = (1-1/3)^2 = (2/3)^2 = 4/9.

Для N = 4:
1) аналогично;
2) аналогично, только N = 4, т.е. второе число либо равно первому с вероятностью 1/4, либо уникально с вероятностью 3/4;
3)
- если первые два равны, то общая вероятность уникальности третьего = 1/4*3/4;
- если первые два уникальны, то общая вероятность уникальности третьего = 3/4*2/4;
4) здесь у нас уже 4 варианта в соответствии с таблицей истинности:
Код:
2 число уникально?    3 число уникально?   вероятность уникальности 4 числа:
      да                    да                   3/4*2/4*1/4 = 6/64
      да                    нет                  3/4*2/4*2/4 = 12/64
      нет                   да                   1/4*3/4*2/4 = 6/64
      нет                   нет                  1/4*1/4*3/4 = 3/64
Легко показать, что сумма строк правого столбца - это расписанный куб разности (1-1/4)^3 = (1-1/N)^(N-1) = 27/64 = (3/4)^3.

Для N = 5 таблица истинности опять увеличится вдвое, и т.д.

Автор:  Владислав Жаринов [ Четверг, 25 Август, 2011 20:08 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Вот что вызывает вопрос:
albobin в viewtopic.php?p=64996#p64996 писал(а):
Сгенерите N раз случайное целое число из диапазона 1..N и посчитайте отношение "к-во различных чисел"/N.
0.63
Если понимать это как экспериментальный факт (как и результаты Сергея), то надо принять, что 0,63 - это верхняя граница доли уникальных чисел в псевдослучайной последовательности при сколь угодно большой её длине N. И выходит, что вероятность события "все числа в последовательности разные" равна нулю... как и более широкого события "доля разных чисел в последовательности превышает 0,63". Т.е. такое приложение вероятности, получается, здесь не проходит... или это не надо понимать как верхнюю границу?..

Автор:  albobin [ Четверг, 25 Август, 2011 20:12 ]
Заголовок сообщения:  Re: Хэш 63% - что это за закон природы такой?

Александр Ильин писал(а):
albobin писал(а):
IMHO формула должна быть ((N-1)/N)^N
Неа, у Сергея Губанова правильная формула. У вас показатель степени не тот, должен быть N-1. А возводимая в степень часть (N-1)/N = N/N - 1/N = 1 - 1/N, т.е. как у Сергея.

Вероятность непопадания в конкретную ячейку за один "выстрел" равно (N-1)/N, ( N-1 для наглядности)
Вер.-ть. N непопаданий в конкретную ячейку соответственно степень N, X=((N-1)/N)^N
Вер-ть того что было хотя бы одно попадание в конкретную ячейку равно 1-X
Остаётся лишь только интерпретировать нужным образом, как "заполненность" ячейки и / или всего диапазона.

Страница 1 из 6 Часовой пояс: UTC + 3 часа
Powered by phpBB® Forum Software © phpBB Group
https://www.phpbb.com/