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

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

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

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

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

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

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

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

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

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

На основании вашего пояснения:

I have used long values in Java in such a way that the first 32 bit encoded an ID and the second 32 bit encoded another ID. Unfortunately Java's hash of long values just XORs the first 32 bit with the second 32 bits, which in my case led to very poor performance when used in a HashMap.

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

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

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

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