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

Question

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

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

Answer 1

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

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

Кажется, что магические слова - это "целочисленное хеширование».

Answer 2

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

Answer 3

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

Answer 4

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