Хеширование значений указателя
Иногда необходимо взять хеш-функцию указателя; не объект указатель указывает на, но сам указатель. Много времени, люди просто плывут на плоскодонке и используют значение указателя в качестве целого числа, обрубают некоторые высокие биты, чтобы заставить его соответствовать, возможно, переключиться на верхний регистр известный - нулевые биты внизу. Вещь, значения указателя не обязательно хорошо распределяются в пространстве кода; на самом деле, если Ваше средство выделения делает свое задание, существует превосходный шанс, они все кластеризируются близко друг к другу.
Так, мой вопрос, кто-либо разработал хеш-функции, которые хороши для этого? Возьмите 32-или 64-разрядное значение, это, возможно, получило 12 битов энтропии в нем где-нибудь и распространило его равномерно через 32-разрядное пространство числа.
3 ответа
На этой странице перечислены несколько методов, которые могут быть полезны. Один из них, принадлежащий Кнуту, прост, как умножение (в 32 битах) на 2654435761, но "Плохие результаты хэширования получаются, если ключи отличаются в старших битах". В случае с указателями это достаточно редкая ситуация.
Вот еще несколько алгоритмов, включая тесты производительности.
Похоже, что магические слова - это "целочисленное хэширование".
Скорее всего, они будут демонстрировать локальность, да - но в младших битах, что означает, что объекты будут распределяться через хеш-таблицу. Вы увидите коллизии только в том случае, если адрес указателя кратен длине хеш-таблицы от другого указателя.
Почему бы просто не использовать существующую хэш-функцию?