Funzione hash fascicolazione

Question

Nel oggetto locale v'è una sfaccettatura di fascicolazione.

L'aspetto di fascicolazione ha un metodo di hash che i rendimenti a lungo.
http://www.cplusplus.com/reference/std/locale/collate/ hash /

Due domande:

• Qualcuno sa quale metodo di hashing viene utilizzato.
• Ho bisogno di un valore a 32 bit.
  Se il mio tempo è più lungo di 32 bit, qualcuno sa sulle tecniche per piegare l'hash in una versione più breve. Posso vedere che, se fatto in modo errato che ripiegamento potrebbe generare un sacco di scontri (e se posso affrontare scontri come ho bisogno di tenerne conto in ogni caso, preferirei se fossero ridotti al minimo).

Nota: Non posso usare C ++ 0x caratteristiche
Boost può essere OK.

Answer 1

No, nessuno sa veramente - può variare da una realizzazione ad un altro. I requisiti principali sono (N3092, §20.8.15):

Per tutti i tipi di oggetti principali per i quali esiste un hash di specializzazione, l'hash di istanza dovrà:

1. soddisfare i requisiti di hash (20.2.4), con tonalità tipo argomento della funzione di chiamata, i requisiti DefaultConstructible (33), i requisiti CopyAssignable (37),
2. essere swappable (20.2.2) per lvalue,
3. fornire due tipi annidati result_type e argument_type che sarà sinonimi di size_t e Key, rispettivamente
4. soddisfa il requisito che se k1 == K2 è vero, h (k1) == h (k2) è anche vero, dove h è un oggetto di tipo hashish e K1 e K2 sono oggetti di tipo chiave.

e (N3092, §20.2.4):

Un tipo H soddisfa i requisiti Hash se:

1. è un tipo di funzione oggetto (20.8),
2. è satisifes i requisiti di CopyConstructible e distruttibile (20.2.1),
3. le espressioni indicate nella tabella seguente sono validi e hanno la semantica indicate, e
4. soddisfa tutti gli altri requisiti in questa sottoclausola.

§20.8.15 copre le esigenze sul risultato di hashing, §20.2.4 sul hash stesso. Come si può vedere, tuttavia, entrambi sono abbastanza generale. La tabella che viene menzionato copre sostanzialmente tre ulteriori requisiti:

1. Una funzione hash deve essere "pura" (vale a dire, il risultato dipende solo l'ingresso, non qualsiasi contesto, la storia, ecc.)
2. La funzione non deve modificare l'argomento che è passato ad esso, e
3. Non deve gettare eventuali eccezioni.

Algoritmi esatti sicuramente sono non specificato anche se - e nonostante la lunghezza, la maggior parte dei requisiti di cui sopra sono in realtà solo affermando requisiti che (almeno a me) sembrano abbastanza evidente. In breve, l'implementazione è libero di implementare l'hashing quasi ogni modo che vuole.

Answer 2

Se l'applicazione utilizza una funzione hash ragionevole, ci dovrebbe essere nessun bit del valore hash che ha una correlazione con l'ingresso speciale. Quindi, se la funzione di hash ti dà 64 bit "casuali", ma si vuole solo 32 di loro, si può semplicemente prendere la prima / ultima / ... 32 bit del valore come ti pare. Quali si prende non importa dal momento che ogni bit è casuale come quello successivo (che è ciò che rende una buona funzione di hash).

Quindi, il modo più semplice e ancora del tutto ragionevole per ottenere un valore hash a 32 bit potrebbe essere:

int32_t value = hash(...);

(Naturalmente questo crolla gruppi di 4 miliardi di valori verso il basso per uno, che assomiglia molto, ma che non può essere evitato se ci sono quattro miliardi di volte il numero di valori di origine come valori di riferimento.)