Хеширование значений указателя

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

Итак, мой вопрос: кто-нибудь разработал хеш-функции, которые хороши для этого? Возьмите 32- или 64-битное значение, которое может получить в нем 12 бит энтропии и равномерно распределить его по 32-разрядному номеру.

Ответ 1

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

Вот еще несколько алгоритмов, включая тесты производительности.

Кажется, что волшебные слова являются "целым хэшированием".

Ответ 2

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

Ответ 3

Если вы знаете наименьший возможный адрес указателя (что часто бывает, если вы работаете в большом буфере), просто преобразуйте указатель в целое число, вычитая наименьшее возможное значение указателя; например. это может быть адрес базы буфера. -Remember: указатель, вычитаемый из указателя, равен смещению (целое число). Итак: не "отбивайте" биты; его гораздо лучше конвертировать в смещение. Это приведет к тому, что значение смещения намного меньше значения указателя. Это может помочь в дальнейшем сдвинуть значение указателя вправо (например, разделить на 4) в некоторых случаях, прежде чем хэшировать его. Проблема с указателями часто заключается в том, что небольшие блоки памяти могут быть распределены по одному и тому же адресу (например, блок освобождается, а другой блок занимает освобожденное место блока).

Ответ 4

Почему бы просто не использовать существующую хеш-функцию ?