Collationner Fonction Hash

Question

Dans l'objet local il y a une facette d'assemblage.

La facette d'assemblage a une méthode de hachage qui retourne une longue.
http://www.cplusplus.com/reference/std/locale/collate/ hachage /

Deux questions:

• Quelqu'un sait quelle méthode est utilisée hash.
• J'ai besoin d'une valeur de 32 bits.
  Si ma longue est plus long que 32 bits, quelqu'un sait sur les techniques de pliage du hachage dans une version plus courte. Je peux voir que si mal fait que le pliage pourrait générer beaucoup d'affrontements (et si je peux faire face à des affrontements que je dois tenir compte de toute façon, je préférerais si elles ont été réduites au minimum).

Note: Je ne peux pas utiliser C ++ 0x caractéristiques
Boost peut être OK.

Answer 1

Non, personne ne sait vraiment - il peut varier d'une mise en œuvre à l'autre. Les exigences principales sont (N3092, §20.8.15):

Pour tous les types d'objets clés pour lesquels il existe un hachage de spécialisation, le hachage instanciation doit:

1. satisfaire aux exigences de hachage (20.2.4), avec clé comme le type d'argument d'appel de fonction, les exigences DefaultConstructible (33), les exigences CopyAssignable (37),
2. être swappable (20.2.2) pour lvalues,
3. fournir deux types imbriqués result_type et argument_type qui sont synonymes de size_t et Key, respectivement,
4. satisfaire à l'exigence que si k1 == est vrai k2, h (k1) == h (K2) est également vrai, où h est un objet de hachage de type et k1 et sont des objets de k2 de type clé.

et (N3092, §20.2.4):

Un type H est conforme aux exigences de hachage si:

1. est un type d'objet de fonction (20,8),
2. satisifes les exigences de CopyConstructible et destructible (20.2.1),
3. les expressions indiquées dans le tableau ci-dessous sont valables et ont la sémantique indiquée et
4. il satisfait à toutes les autres exigences de ce paragraphe.

§20.8.15 couvre les exigences sur le résultat de hachage, §20.2.4 sur le hachage lui-même. Comme vous pouvez le voir, cependant, les deux sont assez général. Le tableau qui est mentionné couvre essentiellement trois autres exigences:

1. Une fonction de hachage doit être « pure » (à savoir, le résultat ne dépend que de l'entrée, pas de contexte, histoire, etc.)
2. La fonction ne doit pas modifier l'argument qui est passé à, et
3. Il ne doit pas jeter des exceptions.

algorithmes exacts sont certainement pas spécifié si - et en dépit de la longueur, la plupart des exigences ci-dessus sont vraiment juste indiquant les exigences que (au moins pour moi) semble assez évident. En bref, la mise en œuvre est libre de mettre en œuvre hachant presque toute façon qu'il veut.

Answer 2

Si la mise en œuvre utilise une fonction de hachage raisonnable, il devrait y avoir aucun bit de la valeur de hachage qui ont une corrélation spéciale avec l'entrée. Donc, si la fonction de hachage vous donne 64 bits « au hasard », mais vous voulez seulement 32 d'entre eux, vous pouvez simplement prendre le premier / dernier / ... 32 bits de la valeur que vous s'il vous plaît. Quels sont ceux que vous prenez n'a pas d'importance puisque chaque bit est aussi aléatoire que la suivante (qui est ce qui fait une bonne fonction de hachage).

Ainsi, la façon la plus simple et pourtant tout à fait raisonnable d'obtenir une valeur de hachage 32 bits serait:

int32_t value = hash(...);

(Bien sûr, ce effondrements groupes de 4 milliards de valeurs à un seul, qui ressemble beaucoup, mais qui ne peuvent être évités s'il y a quatre milliards de fois plus de valeurs de source en tant que valeurs cibles.)