Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 26
А чем плох вариант «Поксорить хэшкоды всех полей»? По-моему там будет достаточно равномерное распределение.
>odd prime
Какое-то лишнее упоминание про «нечетность».
Единственное четное простое число это 2…
Какое-то лишнее упоминание про «нечетность».
Единственное четное простое число это 2…
Интересный эксперимент. Но диапазон от 0 до 100 не очень валидная выбора — очевидно, что (37*x + y) mod 2^31 будет тем дальше разносить соседние значения, чем больше сами значения. Поэтому на малых x,y плотность коллизий большая, и поэтому на малых значениях лУчший результат показывает выбор бОльшего простого множителя, который разносит соседние значения дальше. Есть подозрение, что если проверить диапазон (100 000, 100 100) — результат может заметно измениться.
Но вообще — да, конечно, если нужно выжимать максимум, нужно внимательно смотреть на хэшфункции. Но тогда уж и на реализацию хэштаблицы нужно смотреть очень внимательно.
Но вообще — да, конечно, если нужно выжимать максимум, нужно внимательно смотреть на хэшфункции. Но тогда уж и на реализацию хэштаблицы нужно смотреть очень внимательно.
Руслан, я проверял этот диапазон. Результат тот же. Если в формуле (x1 — x2) / (y2-y1) = q умножить числитель и знаменатель на любое целое число, то коллизия останется, но ее можно будет сдвинуть по числовой оси.
Прошу прощения, промахнулся с ответом.
Прошу прощения, промахнулся с ответом.
Первый вопрос — а как вы думаете, почему в стандартной библиотеке используется chaining HashMap, когда open addressing, вообще говоря, в разы быстрее и в разы компактнее? Мое предположение — как раз потому, что chaining более толерантен к плохой хэш-функции. Тут уже правильно замечали — однократные коллизии мало что меняют, их практически нереально избежать для хэш-функции общего вида. Важно, чтобы не было явно выделенных точек, вокруг которых кучкуются значения хэша.
Т.е. вопрос состоит в выборе критерии качества хэша. Вы берете просто количество коллизий — это ок для прикидки, но не вполне понятно, как это скажется на реальной работе. По-хорошему качество хэша надо проверять так: брать хэш-таблицу (конкретную реализацию), генерировать набор ключей, вставлять, смотреть на гистограмму коллизий (гистограмма в осях кратность коллизии/количество). Брать другую хэш-функцию, делать то же самое. Я так (буквально недавно) выбирал хэш-функцию для справочников. Это тоже не однозначный вариант, то он хоть ближе к ответу на вопрос «какая хэш-функция лучше на практике». Еще ближе был бы эксперимент с последующим чтением некой подвыборки ключей, и подсчетом среднего количества проб — тут прямая (хоть и не обязательно точная) оценка именно производительности — того, что, в конечном счете, и нужно от хорошего хэша.
Т.е. вопрос состоит в выборе критерии качества хэша. Вы берете просто количество коллизий — это ок для прикидки, но не вполне понятно, как это скажется на реальной работе. По-хорошему качество хэша надо проверять так: брать хэш-таблицу (конкретную реализацию), генерировать набор ключей, вставлять, смотреть на гистограмму коллизий (гистограмма в осях кратность коллизии/количество). Брать другую хэш-функцию, делать то же самое. Я так (буквально недавно) выбирал хэш-функцию для справочников. Это тоже не однозначный вариант, то он хоть ближе к ответу на вопрос «какая хэш-функция лучше на практике». Еще ближе был бы эксперимент с последующим чтением некой подвыборки ключей, и подсчетом среднего количества проб — тут прямая (хоть и не обязательно точная) оценка именно производительности — того, что, в конечном счете, и нужно от хорошего хэша.
Еще я забыл написать в статье, что алгоритм от Блоха оставляет незадействованным промежуток от 0 до 17*372 (для двух переменных). Для 3-х переменных степень при 37 будет равна трем. А это 861101. Понятно, что после переполнения этот промежуток тоже будет использован, но как-то не очень красиво.
Собственно, подобную ошибку допустил и я в своем примере. Правильная hash функция будет иметь вид:
Собственно, подобную ошибку допустил и я в своем примере. Правильная hash функция будет иметь вид:
p*x1+q*y1-min(p,q)=h
Если не ошибаюсь, то про использование простого числа как основание хэша написал Дональд Кнут в третьем томе(про сортировку и поиск вроде как) и это не является какой-то магией.
Универсальная реализация, предложенная Блохом, на то и универсальная, чтобы не делать никаких предположений относительно значений ваших полей. В случае с int считается, что любое значение равновероятно. Было бы не очень красиво, если бы универсальная функция снижала число коллизий в диапазоне 0..100 или ещё каком-то. Может, у вас все числа в диапазоне от 2^30 до 2^30+100? Или идут с каким-нибудь хитрым шагом? Для любой хэш-функции можно подобрать неподходящие данные. И наоборот — если вы знаете о данных наперёд, ничто не мешает подобрать подходящую хэш-функцию. Например, в случае с тремя полями int, где каждое заведомо от 0 до 100, напишите (a*101+b)*101+c — у вас гарантированно не будет ни одной коллизии.
Универсальная реализация может быть хорошая, а может быть и не очень. Для примера из 3 short полей (как у Блоха) эта реализация не очень удачная. Если человеку нужно реализовать hashCode(), то он, обычно, или сгенерирует его с средствами IDE или обратиться к Блоху или Эккелю. И получит не очень хороший результат.
Меня смущает, что Блох не проводит оценки качества своего алгоритма. И не заостряет внимание на то, что этим нужно заняться, если у вас высоконагруженная система.
Кстати, для диапазона от 230 до 230+100 результат будет тот же.
Меня смущает, что Блох не проводит оценки качества своего алгоритма. И не заостряет внимание на то, что этим нужно заняться, если у вас высоконагруженная система.
Кстати, для диапазона от 230 до 230+100 результат будет тот же.
Коллизии — это, конечно, интересно. Но более интересно, все-таки, распределение. Если одинаковый хэш будет у 3х элементов — это не страшно. Даже не смотря на то что все элементы будут иметь «близнецов». А вот если у 100, то это гораздо хуже.
Дальше, Вы рассматриваете сплошной интервал, а это не отражает реальности. Если вам надо обращаться по значению в сплошном интервале или в почти заполненном, легче воспользоваться массивами или другими более продвинутыми структурами, которые дадут быстрый доступ к нужному элементу. В реальности интересен такой вопрос: какова будет вероятность получить L коллизий, если взять K случайных значений из N возможных?
Есть еще другой аспект — скорость вычисления хэш-функции. Найти элемент в списке из 3х может быть легче, чем вычислить сложную хэш-функцию, которая не будет давать коллизий.
Ну и, естественно, бросаться переписывать хэш-функции стоит только тогда когда вы точно знаете, что причина низкой производительности в них.
Дальше, Вы рассматриваете сплошной интервал, а это не отражает реальности. Если вам надо обращаться по значению в сплошном интервале или в почти заполненном, легче воспользоваться массивами или другими более продвинутыми структурами, которые дадут быстрый доступ к нужному элементу. В реальности интересен такой вопрос: какова будет вероятность получить L коллизий, если взять K случайных значений из N возможных?
Есть еще другой аспект — скорость вычисления хэш-функции. Найти элемент в списке из 3х может быть легче, чем вычислить сложную хэш-функцию, которая не будет давать коллизий.
Ну и, естественно, бросаться переписывать хэш-функции стоит только тогда когда вы точно знаете, что причина низкой производительности в них.
Множим первое значение на просто число. Множим второе значение на простое число. И так со всеми значениями. Результат ксорим. Даёт результат близкий к оптимальному.
Простые числа вбираются так, чтобы они были максимально равномерно распределены в диапазоне 0..2^32. Т.е. для двух чисел оптимальными будут простые числа P1~2^8 P2~2^24.
Быстро, хорошо, удобно, теоретически обосновано. Даёт отличное распределение.
Простые числа вбираются так, чтобы они были максимально равномерно распределены в диапазоне 0..2^32. Т.е. для двух чисел оптимальными будут простые числа P1~2^8 P2~2^24.
Быстро, хорошо, удобно, теоретически обосновано. Даёт отличное распределение.
И на всякий случай, вариант без умножения (таки довольно тяжёлая операция):
/* Количество элементов равно количеству чисел, участвующий в генерации хеш-функции.
Пространство хеш-функции делим пропорцинально кол-ву составляющий.
В нашему случае - 32 бита хеш-функция делится на два диапазона по 16 бит.
*/
const unsigned int P1= 70507 ;// Простое число для первого элемента.
unsigned int counter1=P1; // Счётчик для первого элемента.
unsigned int shift1=0; // Счётчик для сдвига второго числа.
const unsigned int P2= 69221;// Простое число для второго элемента.
unsigned int counter2=P2; // Счётчик для второго элемента.
unsigned int shift2=15; // Счётчик для сдвига второго элемента.
/* Возвращает хеш-функцию для любый двух чисел. */
unsigned int getHash(unsigned int n1, unsigned int n2) {
// Вычисляем первую составляющую (для первого числа).
// Циклический сдвиг суммы счётчика и значения на указанное число бит).
unsigned int v1=couter1+n1;
v1=(v1<<shift1)|(v1>>31-shift1);
counter1+=P1; // Увеличиваем счётчик для первого элемента.
shift1=(shift1+1)&31; // Увеличиваем значение сдвига первого элемента.
// Аналогично вычисляем второй элемент:
unsigned int v2=couter2+n2;
v2=(v2<<shift2)|(v2>>31-shift2);
counter2+=P2; // Увеличиваем счётчик для второго элемента.
shift2=(shift2+1)&31; // Увеличиваем значение сдвига второго элемента.
// Вычисляем и возвращаем хэш:
return v1 xor v2;
}
Да, кстати, каюсь и посыпаю голову пеплом — это не хэш-функция в чистом виде. Это скорее многопоточный генератор псведослучайных чисел. Подсмотрен, если не ошибаюсь, в каких-то исходниках Java, где использовался в качестве генератора хэш-значения по-умолчанию для объектов (чистую хэш функцию от адреса использовать нельзя, так как из-за работы сборщика мусора, выравнивания и сжатия указателей высока вероятность того, что объекты будут выделяться по одним и тем же адресам и вызывать коллизии). В результате там есть такой алгоритм. Один из параметров — threadID. Второй — адрес объекта. Позволяет генерировать псевдослучайный хэш независимо для каждого потока. В нынешней Java-машине есть ключ, который этот режим включает (по-идее, повышает производительность если создаётся много объектов).
Не разделяю я любовь отечественных программистов к функции XOR.
Берём P1=257, P2=16777259, рассматриваем две точки на плоскости.
В промежутке от 0 до 1500 — нет коллизий. В промежутке от 0 до 3000 получаем уже 3504 коллизии. Заменяем XOR на обычное сложение — коллизий не будет и в более широком промежутке.
Берём P1=257, P2=16777259, рассматриваем две точки на плоскости.
В промежутке от 0 до 1500 — нет коллизий. В промежутке от 0 до 3000 получаем уже 3504 коллизии. Заменяем XOR на обычное сложение — коллизий не будет и в более широком промежутке.
Есть мнение, что равномерность распределения тоже важна. Почему до 3000 рассматриваете? В общем случае, если у нас какие-то достаточно случайные значения на входе, то коллизий будет примерно одинаково, но xor даст более равномерное распределение хэшей. А если в дальнейшем хэш сужаеься до, например, восьми бит (и мало ли как это делается — например, xor'ом сех байт, как в некотопых библиотеках), то может иметь значение. Хотя, это все довольно спицифично для задачи.
А любовь растет, на сколько я понимаю, из мнения, что две различные операции уменьшают вероятность коллизий при дальнейшей обработке. Ведь мы не знаем, кто и как будет использовать результат — будет ли там сложение/вычитание или xor и с чем.
А любовь растет, на сколько я понимаю, из мнения, что две различные операции уменьшают вероятность коллизий при дальнейшей обработке. Ведь мы не знаем, кто и как будет использовать результат — будет ли там сложение/вычитание или xor и с чем.
Интервал до 3000 я взял просто для примера (чтобы не долго считалось). Если Ваш алгоритм вычисление хеша имеет коллизии на таком интервале, то он будет иметь их и на большем интервале. А для моего алгоритма есть теоретическое обоснование отсутствия коллизий на интервале от 0 до 216. Я не предлагаю сейчас начинать спор о допустимости использования функции XOR. Для двух переменных это не очень оправдано, а, возможно, для 10 — будет в самый раз.
Только вот для HaspMap не так уж требуются хэши в диапазоне 0...232, он всё равно их урежет до размера внутренней таблицы.
Одно дело иметь хорошую hash функцию и осознанно не использовать всех ее свойств, и совсем другое дело думать, что имеешь хорошую hash функцию, но ошибаться.
Для тех, кто все еще не верит, что hash функция от Блоха не очень хороша, проведем небольшой эксперимент.
Возьмем промежуток от 0 до 216, возьмем случайную точку на плоскости примерно из середины этого промежутка. Координаты точки: (32127, 32123). Переберем все точки на заданном промежутке и посчитаем коллизии.
У меня получилось 2114. Много это или мало — пусть каждый решает сам.
Возьмем промежуток от 0 до 216, возьмем случайную точку на плоскости примерно из середины этого промежутка. Координаты точки: (32127, 32123). Переберем все точки на заданном промежутке и посчитаем коллизии.
У меня получилось 2114. Много это или мало — пусть каждый решает сам.
bugs.sun.com/bugdatabase/view_bug.do?bug_id=4045622
…
Of the remaining four, I'd probably select P(31), as it's the cheapest to calculate on a
RISC machine (because 31 is the difference of two powers of two). P(33) is
similarly cheap to calculate, but it's performance is marginally worse, and
33 is composite, which makes me a bit nervous.
…
Of the remaining four, I'd probably select P(31), as it's the cheapest to calculate on a
RISC machine (because 31 is the difference of two powers of two). P(33) is
similarly cheap to calculate, but it's performance is marginally worse, and
33 is composite, which makes me a bit nervous.
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Заметки о реализации hashCode() в Java