Как проверить, хорошо ли мое хеширование в hash_map?

Question

Я написал собственное хеширование для своего пользовательского ключа в stdext :: hash_map и хотел бы проверить, хорош ли хешер. Я использую STL, поставляемый с VS 2008. Как я знаю, типичная проверка - это проверка равномерности распределения по сегментам.

Как правильно организовать такую ​​проверку? Решение, которое мне приходит в голову, состоит в том, чтобы изменить исходные коды STL, добавив в hash_map метод, который проходит через сегменты и выполняет тему. Есть ли лучшие способы?

Может быть, наследовать от hash_map и создать там такой метод?

Answer 1

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

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

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

Answer 2

Я бы запустил один (большой) набор данных через stl :: hash_map. После этого я соберу результаты для всех групп, используя следующий метод

С hash_map:

size_type elems_in_bucket (size_type __n) const;

Наконец, я бы вычислил стандартное отклонение (SD) из распределения элемент-в-ведро .

Я бы сделал выше для разных хеш-функций. Какая бы хеш-функция ни привела к минимуму SD, она становится победителем (для этого набора данных).