Как я могу проверить, что моя хеш-функция хороша с точки зрения максимальной нагрузки?

Question

Я прочитал различные статьи по проблеме «Шарики и бункеры», и кажется, что если хеш-функция работает правильно (т. Е. Фактически это случайное распределение), то следующее должно быть / должно быть верно, если я хеширую n значений в хеш-таблицу с n слотами (или ячейками):

1. Вероятность того, что ячейка пуста, для больших n равна 1/e.
2. Ожидаетсяколичество пустых корзин равно n/e.
3. Вероятность того, что в корзине имеется k шаров, равна <= 1/ek! (исправлено).
4. Вероятность того, что в корзине не менее k столкновений, составляет <= ((e/k)**k)/e (исправлено).

Их легко проверить.Но тест max-load (максимальное количество коллизий с высокой вероятностью) обычно указывается расплывчато.

В большинстве текстов утверждается, что максимальное количество коллизий в любом бине равно O( ln(n) / ln(ln(n)) ).Некоторые говорят, что это 3*ln(n) / ln(ln(n)).Другие документы смешивают ln и log - обычно не определяя их, или утверждают, что log - это база журнала e, а затем используют ln в другом месте.

Is ln - журнал для базы e или 2 и является ли эта формула max-load правильной и насколько большой должна быть n для запуска теста?

Эта лекция, кажется, лучше всего ее освещает, но я не математик.

http://pages.cs.wisc.edu/~shuchi/courses/787-F07/scribe-notes/lecture07.pdf

Кстати, with high probability, кажется, означает 1 - 1/n.

Answer 1

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

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

Существует точное ожидаемое значение для каждой двери для определенного количества людей. Например, при 5 человек и 5 дверях ожидаемая максимальная дверь точно на 1,2864 {(1429-625) / 625} выше среднего значения (p / d), а минимальная дверь точно -0,9616 {(24-625) / 625 } ниже среднего. Абсолютное значение расстояния самой высокой двери от среднего значения немного больше, чем у самой маленькой двери, потому что все люди могут пройти через одну дверь, но не менее нуля может пройти через одну из дверей. При большом количестве людей (p / d> 3000) разница между абсолютной величиной расстояния от самой высокой двери до средней и самой низкой двери становится незначительной.

Для нечетного числа дверей центральная дверь по существу равна нулю и не масштабируется, но все остальные двери масштабируются из определенных значений, представляющих p = d. Эти округленные значения для d = 5:

-1,163 -0,495 0 * 0,495 1,163 * медленно приближается к нулю от -0.12

Из этих значений вы можете вычислить ожидаемое количество людей для любого количества людей, проходящих через каждую из 5 дверей, включая максимальную дверь. За исключением средней упорядоченной двери, разница со средним масштабируется на sqrt (p / d).

Итак, для p = 50000 и d = 5:
Ожидаемое количество людей, проходящих через максимальную дверь, которая может быть любой из 5 дверей, = 1.163 * sqrt (p / d) + p / d. = 1,163 * кв.м. (10000) + 10000 = 10 116,3 Для p / d <3000 результат из этого уравнения должен быть немного увеличен. </p>

С увеличением числа людей средняя дверь медленно становится все ближе и ближе к нулю с -0.11968 при p = 100 и d = 5. Его всегда можно округлить до нуля, и, как и у других 4-х дверей, разница довольно велика.

Значения для 6 дверей: -1,272 -0,643 -0,202 0,20,6 0,643 1,272

Для 1000 дверей приблизительные значения: -3,25, -2,95, -2,79… 2,79, 2,95, 3,25

Для любых d и p существует точное ожидаемое значение для каждой из заказанных дверей. Надеемся, что существует хорошее приближение (с относительной погрешностью <1%). Какой-то профессор или математик где-то должен знать. </p>

Для тестирования равномерного распределения вам потребуется несколько усредненных упорядоченных сеансов (хорошо работает 750-1000), а не большее количество людей. Независимо от того, что различия между действительными сессиями велики. Это природа случайности. Столкновения неизбежны. *

Ожидаемые значения для 5 и 6 дверей были получены путем вычисления полной грубой силы с использованием 640-битных целых чисел и усреднения сходимости абсолютных значений соответствующих противоположных дверей. Для d = 5 и p = 170: -6.63901 -2.95905 -0.119342 2.81054 6.90686 (27.36099 31.04095 33.880658 36.81054 40.90686) Для d = 6 и p = 108: -5,19024 -2,7711 -0,973979 0,734434 2,66716 5,53372 (12.80976 15,2289 17,026021 18,734434 20,66716 23,53372)

Я надеюсь, что вы можете равномерно распределить ваши данные.

• Почти гарантировано, что все сыновья Джорджа Формана или другие подобные ситуации будут бороться с вашей хэш-функцией. А правильное непредвиденное планирование - работа всех хороших программистов.

Answer 2

Это увлекательная статья / лекция - мне жаль, что я не взял несколько формальных классов алгоритмов.

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

Во-первых, база журналов. Эти числа даны в виде обозначения big-O, а не в виде абсолютных формул. Это означает, что вы ищете что-то «порядка ln (n) / ln (ln (n))», не с ожиданием абсолютного ответа, а с тем, чтобы при увеличении n отношение n к максимальное количество столкновений должно следовать этой формуле. Детали фактической кривой, которую вы можете отобразить, будут варьироваться в зависимости от реализации (и я не знаю достаточно о практических реализациях, чтобы сказать вам, что такое «хорошая» кривая, за исключением того, что она должна следовать этим отношениям big-O). Эти две формулы, которые вы разместили, на самом деле эквивалентны в нотации big-O. Число 3 во второй формуле является просто константой и связано с конкретной реализацией. Менее эффективная реализация будет иметь большую константу.

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

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

Затем увеличьте N, скажем, 1000, 10000 и т. Д. Увеличьте его логарифмически, потому что ваша формула логарифмическая. По мере увеличения вашего N ваша максимальная нагрузка должна увеличиваться на порядок ln (n) / ln (ln (n)). Если оно увеличивается со скоростью 3 * ln (n) / ln (ln (n)), это означает, что вы следуете теории, изложенной в этой лекции.

Этот вид эмпирического теста также покажет вам, где нарушается ваш подход. Может случиться так, что ваш алгоритм хорошо работает для N <10 миллионов (или некоторого другого числа), но выше этого он начинает разрушаться. Почему это может быть? Возможно, у вас есть ограничение на 32 бита в вашем коде, не осознавая этого (т. Е. Используя «float» вместо «double»), или некоторые другие детали реализации. Такие подробности позволяют узнать, где ваш код будет хорошо работать на практике, а затем, когда ваши практические потребности изменятся, вы сможете изменить свой алгоритм. Возможно, заставить алгоритм работать для очень больших наборов данных делает его очень неэффективным для очень маленьких наборов данных, или наоборот, поэтому точное определение этого компромисса поможет вам дополнительно охарактеризовать, как вы могли бы адаптировать свой алгоритм для конкретных ситуаций. Всегда полезно иметь полезный навык. </p>

РЕДАКТИРОВАТЬ: доказательство того, почему основание функции журнала не имеет значения с записью big-O:

log N = log_10 (N) = log_b (N)/log_b (10)= (1/log_b(10)) * log_b(N)

1 / log_b (10) является константой, и в нотации big-O константы игнорируются. Базовые изменения бесплатны, поэтому вы сталкиваетесь с такими изменениями в газетах.

Answer 3

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

1. Для начала, ln и log кажутсяобратиться к журналу Base-E, если вы посмотрите на математику за теорию.Но, как указал mmr, для оценок O (...) это не имеет значения.

2. max-load можно определить для любой вероятности, которая вам нравится.Типичная используемая формула:

   1-1 / n ** c

В большинстве работ по теме используется

1-1/n

Примером может бытьпроще всего.

Скажем, у вас есть хеш-таблица из 1000 слотов, и вы хотите хешировать 1000 вещей.Скажем, вы также хотите узнать max-load с вероятностью 1-1/1000 или 0.999.

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

Использование формулы для вероятности получения точно k идентичных значений хеш-функции

Pr[ exactly k ] = ((e/k)**k)/e

, а затем путем накопления вероятности точно 0..k элементы до тех пор, пока общее количество не станет равным или не превысит 0.999, это говорит о том, что k является max-load.

например.

Pr[0] = 0.37
Pr[1] = 0.37
Pr[2] = 0.18
Pr[3] = 0.061
Pr[4] = 0.015
Pr[5] = 0.003     // here, the cumulative total is 0.999
Pr[6] = 0.0005
Pr[7] = 0.00007

Итак, в этом случае max-loadравно 5.

Так что, если моя хеш-функция хорошо работает на моем наборе данных, то я должен ожидать, что максимальное количество идентичных хеш-значений (или коллизий) будет 5.

Если это не так, это может быть связано со следующими причинами:

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

2. Ваша хеш-функция не работает с вашими данными - попробуйте ее с произвольными данными.

3. Ваша хеш-функция не работает.

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

Кстати, моя хеш-функция работала хорошо - кроме коротких (1..4 символа) strings.

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

Надеюсь, это поможет.