Cos'è una buona funzione hash?

https://stackoverflow.com/questions/34595

09-06-2019
|

Domanda

Cos'è una buona funzione Hash?Ho visto molte funzioni di hash e applicazioni nei miei corsi sulle strutture dati al college, ma per lo più ho capito che è piuttosto difficile creare una buona funzione di hash.Come regola pratica per evitare collisioni il 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 come dimensione della tabella hash.Capisco che sia una funzione piuttosto buona per evitare collisioni e una collisione veloce, ma come posso crearne una migliore?Esistono funzioni hash migliori per i tasti stringa rispetto ai tasti numerici?

Soluzione

Per eseguire ricerche "normali" nelle tabelle hash praticamente su qualsiasi tipo di dati: questa di Paul Hsieh è la migliore che abbia mai usato.

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

Se ti interessa la sicurezza crittografica o qualsiasi altra cosa più avanzata, allora YMMV.Se vuoi solo una funzione hash generica per una ricerca nella tabella hash, allora questo è quello che stai cercando.

Altri suggerimenti

Non esiste una "buona funzione hash" per gli hash universali (ndr.sì, lo 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, cosa che probabilmente intendi.

Le tabelle hash hanno requisiti molto diversi.Tuttavia, trovare una buona funzione hash universale è difficile perché diversi tipi di dati espongono informazioni diverse che possono essere sottoposte ad hashing.Come regola generale è bene considerare Tutto informazioni che un tipo contiene allo stesso modo.Questo non è sempre facile e nemmeno possibile.Per ragioni statistiche (e quindi di collisione), è anche importante generare una buona distribuzione nello spazio del problema, ad es.tutti gli oggetti possibili.Ciò significa che quando si esegue l'hashing di numeri compresi tra 100 e 1050 non è opportuno lasciare che la cifra più significativa abbia un ruolo importante nell'hash perché per circa il 90% degli oggetti, questa cifra sarà 0.È molto più importante lasciare che siano le ultime tre cifre a determinare l'hash.

Allo stesso modo, quando si esegue l'hashing delle stringhe è importante considerare tutti i caratteri, tranne quando si sa in anticipo che i primi tre caratteri di tutte le stringhe saranno gli stessi;considerarli poi è uno spreco.

Questo è in realtà uno dei casi in cui consiglio di leggere ciò che Knuth ha da dire L'arte della programmazione informatica, vol.3.Un'altra buona lettura è quella di Julienne Walker L'arte dell'hashing.

Gli scopi principali delle funzioni di hashing sono due:

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

È impossibile consigliare un hash senza sapere per cosa lo stai utilizzando.

Se stai semplicemente creando una tabella hash in un programma, non devi preoccuparti di quanto sia reversibile o hackerabile l'algoritmo...SHA-1 o AES non sono completamente necessari per questo, faresti meglio a usare un file variazione del FNV.FNV ottiene una migliore dispersione (e quindi meno collisioni) rispetto a un semplice mod principale come quello che hai menzionato ed è più adattabile alle diverse dimensioni di input.

Se utilizzi gli hash per nascondere e autenticare informazioni pubbliche (come l'hashing di una password o di un documento), dovresti utilizzare uno dei principali algoritmi di hashing controllati dal pubblico. La Hash Function Lounge è un buon punto di partenza.

Questo è un buon esempio e anche un esempio del perché non vorresti mai scriverne uno.È un hash Fowler / Noll / Vo (FNV) che è in parti uguali genio informatico e puro 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;
}

Modificare:

Landon Curt Noll consiglia il suo sito l'algoritmo FVN-1A rispetto all'algoritmo FVN-1 originale:L'algoritmo migliorato disperde meglio l'ultimo byte nell'hash.Ho adattato l'algoritmo di conseguenza.

Direi che la regola pratica principale è non rotolare il proprio.Prova a utilizzare qualcosa che sia stato accuratamente testato, ad esempio SHA-1 o qualcosa del genere.

Una buona funzione hash ha le seguenti proprietà:

Dato l'hash di un messaggio, è computazionalmente impossibile per un utente malintenzionato trovare un altro messaggio in modo tale che i suoi hash siano identici.
Data una coppia di messaggi, m' e m, è computazionalmente impossibile trovarne due tali che h(m) = h(m')

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

Laddove le prestazioni non siano un grosso problema, dovresti sempre utilizzare una funzione hash sicura.Esistono 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 nei nuovi progetti.La maggior parte dei crittografi, me compreso, li considererebbe rotti.La principale fonte di debolezza in entrambi questi progetti è che la seconda proprietà, che ho sottolineato sopra, non vale per queste costruzioni.Se un utente malintenzionato può generare due messaggi, m e m', che hanno entrambi lo stesso valore, può utilizzare questi messaggi contro di te.Anche SHA-1 e MD5 subiscono attacchi con estensioni dei messaggi, che possono indebolire fatalmente la tua applicazione se non stai attento.

Un hashish 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 aiuti!

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

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

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow