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

Question

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

РЕДАКТИРОВАТЬ : Для пояснения моя проблема заключалась в том, что я использовал значения long в Java таким образом, что первый 32-битный кодировал идентификатор, а второй 32-битный кодировал другой идентификатор. К сожалению, хэш длинных значений в Java просто XOR - первый 32-битный со вторым 32-битным, что в моем случае привело к очень низкой производительности при использовании в HashMap. Поэтому мне нужен другой хеш, и я хотел бы провести модульное тестирование, чтобы эта проблема больше не могла закрасться.

Answer 1

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

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

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

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

Answer 2

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

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

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

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

Answer 3

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

Answer 4

На основании ваших разъяснений:

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

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

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

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

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