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

Question

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

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

Answer 1

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

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

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

Answer 2

Почему бы просто не использовать существующий hash function?

Answer 3

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

Answer 4

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