Che cos'è una buona funzione hash?

Question

Che cos'è una buona funzione hash? Ho visto molte funzioni di hash e applicazioni nei miei corsi di strutture dati al college, ma per lo più ho capito che è piuttosto difficile fare una buona funzione di hash. Come regola generale per evitare collisioni mio professore ha detto che:

function Hash(key) 
    return key mod PrimeNumber 
end 

(mod è l'operatore% in C e linguaggi simili)

con il numero primo ad essere la dimensione della tabella hash. Ho capito che è una funzione piuttosto buona per evitare collisioni e una veloce, ma come posso farne una migliore? Esistono migliori funzioni di hash per le chiavi stringa rispetto ai tasti numerici?

Answer 1

Per fare "normali" ricerche di hash su praticamente qualsiasi tipo di dati - questo di Paul Hsieh è il migliore che abbia mai usato.

http://www.azillionmonkeys.com/qed/hash.html

Se avete a cuore crittograficamente sicuro o qualsiasi altra cosa più avanzata, quindi YMMV. Se si desidera semplicemente una funzione di hash di tipo kick kick ass per una ricerca hash table, allora questo è quello che stai cercando.

Answer 2

Direi che la regola principale non è quella di eseguire il rollover. Prova a utilizzare qualcosa che è stato accuratamente testato, ad es. SHA-1 o qualcosa del genere.

Answer 3

Non esiste una "buona funzione di hash" per gli hash universali (si, so che esiste una cosa come "hashing universale" ma non è quello che intendevo). A seconda del contesto, diversi criteri determinano la qualità di un hash. Due persone hanno già menzionato SHA. Questo è un hash crittografico e non è affatto buono per le tabelle hash che probabilmente intendi.

Le tabelle hash hanno requisiti molto diversi. Tuttavia, trovare universalmente una buona funzione di hash è difficile perché diversi tipi di dati espongono informazioni diverse che possono essere sottoposte a hash. Come regola generale è bene considerare tutte le informazioni di cui un tipo vale ugualmente. Questo non è sempre facile o addirittura possibile. Per ragioni di statistica (e quindi di collisione), è anche importante generare una buona diffusione nello spazio del problema, cioè tutti gli oggetti possibili. Ciò significa che quando numeri di hashing tra 100 e 1050 non è opportuno lasciare che le cifre più significative giochino un ruolo importante nell'hash perché per ~ 90% degli oggetti, questa cifra sarà 0. È molto più importante lasciare le ultime tre le cifre determinano l'hash.

Analogamente, quando si eseguono stringhe di hashing è importante considerare tutti i caratteri, tranne quando è noto in anticipo che i primi tre caratteri di tutte le stringhe saranno uguali; Considerare questi poi è uno spreco.

Questo è in realtà uno dei casi in cui consiglio di leggere ciò che Knuth ha da dire in The Art of Computer Programming, vol. 3. Un'altra buona lettura è di Julienne Walker The Art of Hashing.

Answer 4

Una funzione di hash buona ha le seguenti proprietà:

1. dato un hash di un messaggio è computazionalmente impossibile per un utente malintenzionato di trovare un altro messaggio in modo tale che i loro hash sono identici.

2. Dato un paio di messaggio, m 'e m, è computazionalmente impossibile trovare due in modo tale che che H (m) = h (m')

I due casi sono non lo stesso. Nel primo caso, esiste un hash pre-esistente per il quale stai cercando di trovare una collisione. Nel secondo caso, stai cercando di trovare qualsiasi due messaggi che si scontrano. Il secondo compito è notevolmente più semplice a causa del "paradosso" del compleanno.

Dove le prestazioni non sono un gran problema, è necessario utilizzare sempre una funzione di hash sicura.Ci sono attacchi molto intelligenti che possono essere eseguiti forzando le collisioni in un hash. Se usi qualcosa di forte fin dall'inizio, ti proteggerai da questi.

Non utilizzare MD5 o SHA-1 in nuovi progetti. La maggior parte dei crittografi, me incluso, li considererebbe rotto. La principale fonte di debolezza in entrambi questi progetti è che la seconda proprietà, che ho delineato sopra, non regge per queste costruzioni. Se un utente malintenzionato può generare due messaggi, me m ', che entrambi hanno lo stesso valore, possono usare questi messaggi contro di te. Anche SHA-1 e MD5 soffrono di attacchi di estensione dei messaggi, che possono indebolire fatalmente la tua applicazione se non stai attento.

Un hash più moderno come Whirpool è una scelta migliore. Non soffre di questi attacchi di estensione dei messaggi e utilizza la stessa matematica utilizzata da AES per dimostrare la sicurezza contro una varietà di attacchi.

Spero che questo aiuti!

Answer 5

Ci sono due scopi principali di funzioni hash:

• per disperdere uniformemente punti di dati in n bit.
• per identificare in modo sicuro i dati di input.

È impossibile raccomandare un hash senza sapere a cosa si sta utilizzando.

Se stai solo creando un hash table in un programma, non devi preoccuparti di come sia reversibile o hackerabile l'algoritmo ... SHA-1 o AES non è assolutamente necessario per questo, dovresti stare meglio usando un variation of FNV. FNV ottiene una migliore dispersione (e quindi meno collisioni) rispetto a una semplice mod primaria come hai detto tu, ed è più adattabile alle diverse dimensioni di input.

Se si utilizzano gli hash per nascondere e autenticare le informazioni pubbliche (come l'hashing di una password o un documento), è necessario utilizzare uno dei principali algoritmi di hashing esaminati da un controllo pubblico. The Hash Function Lounge è un buon punto di partenza.

Answer 6

Questo è un esempio di buono e anche un esempio del perché non si vorrebbe mai scriverne uno. Si tratta di una Fowler/Noll/Vo (FNV) Hash, che è in parti uguali informatica genio e pura voodoo:

unsigned fnv_hash_1a_32 (void *key, int len) { 
    unsigned char *p = key; 
    unsigned h = 0x811c9dc5; 
    int i; 

    for (i = 0; i < len; i++) 
     h = (h^p[i]) * 0x01000193; 

    return h; 
} 

unsigned long long fnv_hash_1a_64 (void *key, int len) { 
    unsigned char *p = key; 
    unsigned long long h = 0xcbf29ce484222325ULL; 
    int i; 

    for (i = 0; i < len; i++) 
     h = (h^p[i]) * 0x100000001b3ULL; 

    return h; 
} 

Edit:

• Landon Curt Noll Raccomandazione his site the-1A FVN algoritmo tramite l'algoritmo FVN-1 originale: l'algoritmo migliorato disperdere meglio l'ultimo byte dell'hash. Ho regolato l'algoritmo di conseguenza.

Answer 7

Quello che stai dicendo qui è che vuoi averne uno che usi abbia resistenza alle collisioni. Prova a usare SHA-2.Oppure prova a usare un (buon) codice di blocco in una funzione di compressione unidirezionale (mai provato prima), come AES in modalità Miyaguchi-Preenel. Il problema è che è necessario:

1) avere un IV. Prova a utilizzare i primi 256 bit delle parti frazionarie della costante di Khinchin o qualcosa del genere. 2) hanno uno schema di riempimento. Facile. Spostalo da un hash come MD5 o SHA-3 (Keccak [pronunciato 'ket-chak']). Se non ti interessa la sicurezza (alcuni altri hanno detto questo), guarda FNV o lookup2 di Bob Jenkins (in realtà sono il primo a raccomandare lookup2) Prova anche MurmurHash, è veloce (controlla questo: .16 CPB).