Функция хеширования слияния

Question

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

Фрагмент сортировки имеет хэш-метод, который возвращает длинный.
http://www.cplusplus.com/reference/std/locale/collate/hash/

Два вопроса:

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

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

Answer 1

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

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

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

и (N3092, §20.2.4):

типа Н удовлетворяет требования Хеша, если:

1. это тип объекта функции (20.8),
2. его satisifes требования CopyConstructible and 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 млрд значений до одного, который выглядит, как много, но этого нельзя избежать, если количество исходных значений в четыре миллиарда раз больше, чем целевые значения.)