Funzione di hash per quattro numeri interi senza segno (C ++)

Question

Sto scrivendo un programma in questo momento che produce quattro numeri interi a 32 bit senza segno come output da una determinata funzione. Voglio eseguire il hash di questi quattro numeri interi, in modo da poter confrontare l'output di questa funzione con output futuri.

Ho problemi a scrivere una funzione di hashing decente. Quando ho originariamente scritto questo codice, ho inserito una semplice aggiunta di ciascuno dei quattro numeri interi, che sapevo non sarebbe bastato. Ho provato diverse altre tecniche, come spostare e aggiungere, senza risultati. Ottengo un hash, ma è di scarsa qualità e la funzione genera un sacco di collisioni.

L'output hash può essere un numero intero a 32 o 64 bit. La funzione in questione genera molti miliardi di hash, quindi le collisioni sono un vero problema qui, e sono disposto a usare una variabile più grande per garantire che ci siano meno collisioni possibili.

Qualcuno può aiutarmi a capire come scrivere una funzione hash di qualità?

Answer 1

Perché non memorizzi i quattro numeri interi in una struttura dati adeguata e li confronti tutti? Il vantaggio di hashing in questo caso mi sembra dubbio, a meno che lo storage non sia un problema.

Se l'archiviazione è un problema, puoi utilizzare una delle funzioni hash analizzate qui .

Answer 2

Ecco una funzione hash abbastanza ragionevole da 4 numeri interi a 1 numero intero:

unsigned int hash = in[0];
hash *= 37;
hash += in[1];
hash *= 37;
hash += in[2];
hash *= 37;
hash += in[3];

Con input distribuiti uniformemente fornisce output distribuiti uniformemente. Tutti i bit dell'ingresso partecipano all'uscita e ogni valore di ingresso (sebbene non tutti i bit di ingresso) può influenzare ogni bit di uscita. È probabile che sia più veloce della funzione che produce l'output, nel qual caso nessuna prestazione riguarda.

Esistono altri hash con altre caratteristiche, ma accumulare con moltiplicazione per primo è un buon inizio fino a prova contraria. Puoi provare ad accumulare con xor invece di addizione, se lo desideri. In entrambi i casi, è facile generare collisioni (ad esempio {1, 0, a, b} si scontra con {0, 37, a, b} per tutte a, b), quindi potresti voler scegliere un numero primo che pensi abbia nulla a che fare con eventuali bug di implementazione plausibili nella tua funzione. Quindi, se la tua funzione ha un sacco di modulo-37 aritmetica, potresti usare invece 1000003.

Answer 3

Poiché l'hashing può generare collisioni, è necessario comunque conservare le chiavi in ??memoria per scoprire queste collisioni. Hashmap e altre strutture di dati standard fanno questo nella loro contabilità interna.

Dato che la chiave è così piccola, basta usare la chiave direttamente anziché l'hashing. Questo sarà più veloce e non garantirà collisioni.

Answer 4

Sono pienamente d'accordo con Vinko: basta confrontarli tutti. Se desideri comunque una buona funzione di hashing, devi analizzare la distribuzione dei tuoi 4 numeri interi non censurati. Quindi devi creare la tua funzione di hashing in un modo, in modo che il risultato sia persino distribuito su tutto l'intervallo del valore di hashing a 32 bit.

Un semplice esempio: supponiamo che la maggior parte delle volte, il risultato di ciascuna funzione sia compreso nell'intervallo da 0 a 255. Quindi potresti facilmente fondere gli 8 bit inferiori di ciascuna funzione nel tuo hash. La maggior parte delle volte, potresti trovare il risultato direttamente, solo a volte (quando una funzione restituisce un risultato più grande) potresti avere una collisione.

Per riassumere - senza informazioni su come sono distribuiti i risultati delle 4 funzioni, non possiamo aiutarti con una buona funzione di hashing.

Answer 5

Perché un hash? Sembra che un set std :: set o std :: multi sarebbe più adatto per memorizzare questo tipo di output. Tutto quello che dovresti fare è avvolgere i quattro numeri interi in una struttura e scrivere una semplice funzione di confronto.

Answer 6

Prova a utilizzare CRC o FNV . FNV è bello perché è veloce e ha un metodo definito per piegare i bit per ottenere "più piccolo" valori hash (ad es. 12 bit / 24 bit / ecc.)

Anche il vantaggio di generare un hash a 64 bit da un numero di 128 bit (4 X 32 bit) è un po 'discutibile perché, come altri hanno suggerito, potresti semplicemente usare il valore originale come chiave in un set . Vuoi davvero che il numero di bit nell'hash rappresenti il ??numero di valori che hai originariamente. Ad esempio, se il set di dati ha 100.000 valori 4X32-bit, probabilmente si desidera un valore di hash a 17 o 18 bit, non un hash a 64 bit.

Answer 7

Potrebbe essere un po 'eccessivo, ma considera Boost.Hash . Genera codice molto semplice e buoni valori.