Соберите хеш -функцию

Question

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

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

Два вопроса:

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

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

Answer 1

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

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

1. удовлетворить требования хеша (20.2.4), с ключом в качестве типа аргумента вызова функции, требования по умолчанию (33), требования копирования (37),
2. быть заменен (20.2.2) для lvalues,
3. Предоставьте два вложенных типа Result_type и Argent_type, которые должны быть синонимами для size_t и key, соответственно,
4. Удовлетворяйте требование, что если k1 == k2 верно, h (k1) == h (k2) также является истинной, где h является объектом хэша и K1 и K2 и K2 объектами типа ключа.

и (N3092, §20.2.4):

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

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