Как проверить хэш-функцию?

Есть ли способ проверить качество хэш-функции? Я хочу иметь хороший спред при использовании в хеш-таблице, и было бы замечательно, если бы это было подтверждено в unit test.

EDIT. Для выяснения моей проблемы было то, что я использовал значения long в Java таким образом, что первый 32-разрядный код кодировал идентификатор, а второй 32-разрядный кодировал другой идентификатор. К сожалению, хэш Java длинных значений просто XOR - первые 32 бит со вторыми 32 битами, что в моем случае привело к очень низкой производительности при использовании в HashMap. Поэтому мне нужен другой хеш и хотелось бы иметь Unit Test, чтобы эта проблема больше не ползла.

Ответ 1

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

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

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

Для вашего конкретного приложения вместо простого сопоставления их вместе попробуйте комбинировать 32-битные значения способами, которые типичная хорошая хэш-функция объединила бы два indepenet ints. То есть умножить на простое число и добавить.

Ответ 2

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

Например, если вы являетесь хеширующими строками, которые представляют собой правильные полные (первые + последние) имена, вы, скорее всего, не будете заботиться о том, как вещи с числовыми символами символов ASCII.

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

Изменить: В вашем случае с 64-разрядной длиной, действительно ли есть причина использовать хэш-карту? Почему бы просто не использовать сбалансированное дерево напрямую и использовать длинный ключ напрямую, а не переигрывать его? Вы платите небольшой штраф за общий размер node (2x размер для значения ключа), но можете в конечном итоге сохранить его в производительности.

Ответ 3

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

Ответ 4

Основываясь на вашем пояснении:

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

Кажется, у вас есть некоторые неприятные "резонансы" между тем, как вы назначаете два значения ID и размеры ваших экземпляров HashMap.

Вы явно определяете свои карты или используете значения по умолчанию? Кажется, что проверка QAD указывает, что HashMap<Long,String> начинается с 16-ведровой структуры и удваивается при переполнении. Это означало бы, что только бит младшего разряда значений идентификатора фактически участвует в выборе хеш-ковша. Вы можете попробовать использовать один из конструкторов, который принимает параметр начального размера и создает карты с начальным размером.

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

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