Функция сортировки хэша

Question

В локальном объекте есть грань сопоставления.

У фасета сортировки есть хеш-метод, который возвращает long.
http://www.cplusplus.com/reference/std/locale/collate/hash/

Два вопроса:

• Кто-нибудь знает, какой метод хеширования используется?
• Мне нужно 32-битное значение.
  Если мой long длиннее 32 бит, кто-нибудь знает о методах свертывания хеша в более короткую версию? Я вижу, что если сделать неправильно, то сворачивание может привести к большому количеству столкновений (и хотя я могу справиться со столкновениями, поскольку мне все равно нужно это учитывать, я бы предпочел, чтобы они были минимизированы).

Примечание: Я не могу использовать функции C ++ 0x
Повышение может быть в порядке.

Answer 1

Нет, на самом деле никто не знает - это может варьироваться от одной реализации к другой. Основные требования (N3092, §20.8.15):

Для всех типов объектов Ключ, для которого существует хеш специализации, хеш экземпляра должен:

1. удовлетворяет требованиям Hash (20.2.4), с Key в качестве типа аргумента вызова функции, требований DefaultConstructible (33), требований CopyAssignable (37),
2. быть заменяемым (20.2.2) для lvalues,
3. предоставляет два вложенных типа result_type и arguments_type, которые должны быть синонимами для size_t и Key соответственно
4. удовлетворяет требованию, что если k1 == k2 истинно, h (k1) == h (k2) также истинно, где h - объект типа hash, а k1 и k2 - объекты типа Key.

и (N3092, §20.2.4):

Тип H соответствует требованиям Hash, если:

1. это тип объекта функции (20.8),
2. удовлетворяет требованиям CopyConstructible и Destructible (20.2.1),
3. выражения, показанные в следующей таблице, являются действительными и имеют указанную семантику, а
4. удовлетворяет всем остальным требованиям этого подпункта.

§20.8.15 охватывает требования к результату хеширования, §20.2.4 к самому хешу. Как вы можете видеть, однако, оба довольно общие. Упомянутая таблица в основном охватывает еще три требования:

1. Хеш-функция должна быть "чистой" (то есть результат зависит только от ввода, а не от контекста, истории и т. Д.)
2. Функция не должна изменять переданный ей аргумент, и
3. Не должно быть никаких исключений.

Точные алгоритмы определенно не определены , хотя - и, несмотря на длину, большинство требований, приведенных выше, на самом деле просто устанавливают требования, которые (по крайней мере для меня) кажутся довольно очевидными. Короче говоря, реализация может свободно реализовывать хеширование практически любым способом.

Answer 2

Если в реализации используется разумная хеш-функция, в хеш-значении не должно быть битов, которые имеют какую-либо особую корреляцию с входными данными.Поэтому, если хеш-функция дает вам 64 «случайных» бита, но вам нужно только 32 из них, вы можете просто взять первые / последние / ... 32 бита значения, как вам угодно.Какие из них вы берете, не имеет значения, поскольку каждый бит такой же случайный, как и следующий (именно это делает хорошую хеш-функцию).

Так что самый простой и все же вполне разумный способ получить 32-битное хеш-значениебыло бы:

int32_t value = hash(...);

(Конечно, это сводит группы из 4 миллиардов значений к одному, что выглядит много, но этого нельзя избежать, если исходных значений в четыре миллиарда раз больше, чемцелевые значения.)