Collate Hash-Funktion

Question

Im lokalen Objekt gibt es eine collate Facette.

Die collate Facette hat ein Hash-Verfahren, dass die Renditen lang.
http://www.cplusplus.com/reference/std/locale/collate/ hash /

Zwei Fragen:

• Weiß jemand, welches Hashing-Verfahren verwendet wird.
• Ich brauche einen 32-Bit-Wert.
  Wenn meine lange dauert länger als 32 Bits, weiß jemand über Techniken zum Falten des Hash in eine kürzere Version. Ich kann sehen, dass, wenn sie falsch gemacht, dass Falten viele Auseinandersetzungen erzeugen könnten (und obwohl ich mit Auseinandersetzungen bewältigen kann, wie ich nehmen muß, dass ohnehin in Betracht, ich würde es vorziehen, wenn sie minimiert wurden).

Hinweis: Ich kann nicht mit C ++ 0x kennzeichnet
Boost kann in Ordnung sein.

Answer 1

Nein, niemand wirklich weiß - es kann von einer Implementierung zur anderen variieren. Die primären Anforderungen sind (N3092, §20.8.15):

Für alle Objekttypen Key für die es eine Spezialisierung Hash existiert, die Instanziierung Hash hat folgende Aufgaben:

1. erfüllt die Hash-Anforderungen (20.2.4) mit Key als Funktionsaufruf Argumenttyp, die DefaultConstructible Anforderungen (33), die CopyAssignable Anforderungen (37)
2. sein swappable (20.2.2) für lvalues,
3. bieten zwei verschachtelte Typen result_type und argument_type die Synonyme für size_t und Key sein soll bzw.
4. erfüllt die Anforderung, dass, wenn k1 == k2 wahr ist, h (k1) == h (k2) ist auch wahr, wobei h ein Objekt vom Typ Hash und k1 und k2 sind Objekte vom Typ Key.

und (N3092, §20.2.4):

Ein Typ H erfüllt die Hash Anforderungen, wenn:

1. es ist eine Funktion Objekttyp (20,8),
2. es satisifes die Anforderungen der CopyConstructible und zerstörbare (20.2.1)
3. die Ausdrücke in der folgenden Tabelle dargestellt ist gültig und hat die angegebene Semantik und
4. es erfüllt alle anderen Anforderungen in diesem Unterabschnitt.

§20.8.15 deckt die Anforderungen an das Ergebnis der Hashing §20.2.4 auf dem Hash selbst. Wie Sie sehen können, jedoch sind beide ziemlich allgemein. Die Tabelle, die im Grunde deckt drei weitere Anforderungen erwähnt wird:

1. Eine Hash-Funktion muss „reine“ sein (das heißt, hängt das Ergebnis nur auf der Eingabe kein Kontext, Geschichte, etc.)
2. Die Funktion muss das Argument nicht ändern, die ihm übergeben wird, und
3. Es darf keine Ausnahmen auslösen.

Exakte Algorithmen sind auf jeden Fall nicht angegeben, obwohl - und trotz der Länge, die meisten der oben genannten Anforderungen sind wirklich nur unter Angabe Anforderungen, dass (zumindest für mich) scheinen ziemlich offensichtlich. Kurz gesagt, ist die Umsetzung fast jede mögliche Weise zu implementieren frei Hashing es will.

Answer 2

Wenn die Implementierung eine angemessene Hash-Funktion verwendet, sollte es keine Bits in dem Hash-Wert sein, der eine besondere Beziehung hat mit dem Eingang. Also, wenn die Hash-Funktion, die Sie 64 „random“ Bits gibt, aber Sie wollen nur 32 von ihnen, können Sie nehmen nur die erste / letzte / ... 32 Bits des Werts als Sie bitte. Welche Sie nehmen spielt keine Rolle, da in jeder Hinsicht genauso zufällig wie die nächste (das ist, was eine gute Hash-Funktion macht).

So ist die einfachste und doch ganz sinnvoll über einen 32-Bit-Hash-Wert zu erhalten wäre:

int32_t value = hash(...);

(Natürlich ist diese kollabiert Gruppen von 4 Milliarden Werte bis auf eine, die aussieht wie eine Menge, aber das nicht vermieden werden kann, wenn es vier Milliarden Mal so viele Quellwerte als Zielwerte.)