Какой самый быстрый и переносимый способ хеширования, который мы знаем, это выравнивание указателя по фиксированному размеру int?

Question

Если у нас есть набор указателей, которые, как мы знаем, выровнены по sizeof(void *) Какой самый быстрый способ их хешировать?

Примечания:

• Примером использования в качестве примера является взятие элементов массива указателей или выделение памяти и сохранение в хэш-карте. Отмечая это, потому что этот вопрос не о криптографическом хешировании, необходимом для паролей, безопасности и т. Д.

• Под фиксированным размером int я имею в виду, что мы знаем точный размер int, и он не изменится (возможно, это важно, поскольку некоторые библиотеки хеширования используют intptr_t или size_t для своих значений, возвращаемых хэшированием который может дать другой ответ на этот вопрос).

• Для портативного устройства это должно работать для 32, 64 бит, big & little endian.

• (uint32_t)(((intptr_t)p) >> 2) дает хорошие результаты для 32-битной системы с прямым порядком байтов, однако я предполагаю, что она теряет значимые биты для 64-битных систем, и я не уверен, дает ли это полезное распределение для младшей последовательности.

Answer 1

Если вы в порядке создания ограничения на 64-битный вход -> 64-битный выход, функция финализатора хэша mumur3 имеет очень хорошие свойства.

Вот 64 бит (из обсуждения здесь: http://zimbry.blogspot.com/2011/09/better-bit-mixing-improving-on.html)

UInt64 MurmurHash3Mixer( UInt64 key )
{
  key ^= (key >> 33);
  key *= 0xff51afd7ed558ccd;
  key ^= (key >> 33);
  key *= 0xc4ceb9fe1a85ec53;
  key ^= (key >> 33);
  return key;
}

Некоторое дополнительное обсуждение открытия таких функций, включая 32-битные -> 32-битные варианты. https://nullprogram.com/blog/2018/07/31/

Погугливая с такими терминами, как "полная лавина" или "смешивание mumur3 против ...", вы получите, казалось бы, бесконечное количество вещей для чтения.

еще одна ссылка: Как создать собственный миксер Murmur Avalanche?

Answer 2

Когда мод математика быстра, быстрый хеш мод должен быть равен prime <= TARGET_TYPE_MAX. Мод будет использовать все биты p для формирования хеша.

При использовании наибольшего простого числа теряются только несколько ведер, но цель - скорость.

Пример, если целевой tpye равен uint32_t, используйте 4294967291u.

Для целочисленных типов с изменяющимся размером, таких как int, используйте макросы для выбора предварительно вычисленного простого числа. Простое число чуть меньше, чем степень двух .

#define LARGEST_PRIME8 251u
#define LARGEST_PRIME15 32749u
#define LARGEST_PRIME16 65521u
#define LARGEST_PRIME31 2147483647u
#define LARGEST_PRIME32 4294967291u
#define LARGEST_PRIME63 9223372036854775783u
#define LARGEST_PRIME64 18446744073709551557u

uint32_t hash = (uint32_t) ((uintptr_t)(void *)p) % LARGEST_PRIME32);