Come scrivere una funzione di hash in C?

Question

Le tabelle hash sono il modo più veloce/migliore per archiviare/recuperare i dati.

mia comprensione di una tabella di hash, hash è la seguente (Si prega di correggermi se sbaglio o si prega di aggiungere Se c'è qualcosa di più):

• A Table Hash non è altro che una matrice (singolo o multidimensionale) per memorizzare i valori.
• hash è il processo per trovare l'indice/posizione nella matrice di inserire/recuperare i dati. Si prende un elemento dati e lo si passa come una (e) chiave (i) a una funzione hash e si otterrebbe l'indice/posizione in cui inserire/recuperare i dati.

Ho una domanda:

È la funzione di hash utilizzato per memorizzare/recuperare i dati diversi da una funzione di hash crittografico utilizzato in applicazioni di sicurezza per l'autenticazione come MD5, HMAC, SHA-1, ecc ..?

In che modo (s) sono diversi?

• come scrivere una funzione di hash in C?
• C'è qualche standard o linee guida?
• Come garantire che l'output di una funzione di hash i.e, l'indice non sia fuori intervallo?

Sarebbe bello se potessi citare alcuni buoni collegamenti per capirli meglio.

Answer 1

Bob Jenkins ha scritto una descrizione approfondita del suo bene, se un po 'datato, hash function. L'articolo ha collegamenti a funzioni di hash più recenti e migliori, ma l'articolo affronta le preoccupazioni di costruirne uno buono.

Inoltre, la maggior parte delle implementazioni di tabella hash in realtà utilizzano una serie di liste collegate per risolvere le collisioni. Se si desidera utilizzare solo un array, la funzione hash deve verificare la presenza di collisioni e creare un nuovo indice hash.

Le funzioni di hash crittografiche che si menzionano potrebbero essere utilizzate come funzioni hash per una tabella hash, ma sono molto più lente delle funzioni di hash progettate per una tabella hash. La velocità rende più facili gli attacchi di forza bruta.

Answer 2

un hash crittografico sottolinea che rende difficile per chiunque di creare intenzionalmente una collisione. Per una tabella hash, l'enfasi è normalmente sulla produzione di una ragionevole diffusione dei risultati rapidamente. Di conseguenza, i due sono in genere piuttosto diversi (in particolare, un hash crittografico normalmente è un lotto più lento).

Per una tipica funzione hash, il risultato è limitata solo dal tipo - esempio se restituisce un size_t, è perfettamente corretto restituire qualsiasi possibile size_t. Spetta a te ridurre l'intervallo di output in base alle dimensioni del tuo tavolo (ad esempio utilizzando il resto della divisione in base alla dimensione della tabella, che dovrebbe essere spesso un numero primo).

A titolo di esempio, un abbastanza tipico funzione hash normale potrebbe essere simile:

// warning: untested code. 
size_t hash(char const *input) { 

    const int ret_size = 32; 
    size_t ret = 0x555555; 
    const int per_char = 7; 

    while (*input) { 
     ret ^= *input++; 
     ret = ((ret << per_char) | (ret >> (ret_size - per_char)); 
    } 
    return ret; 
} 

L'idea di base è quella di avere ogni bit della stringa di input influire sul risultato, e (il più rapidamente possibile) hanno ogni bit del risultato influenzato da almeno una parte dell'input. Si noti che non lo raccomando particolarmente come una grande funzione di hash - solo cercando di illustrare alcune delle nozioni di base su ciò che si sta tentando di realizzare.

Answer 3

Gli obiettivi di progettazione sono diversi.

Con cryptographic hash functions si desidera, ad esempio, che l'hash e la funzione di hash non possano essere utilizzati per determinare i dati originali o altri dati che produrrebbero lo stesso hash.

Funzioni hash utilizzate con tabelle hash & altre strutture dati non necessitano di tali proprietà di sicurezza. Spesso è sufficiente se la funzione hash è veloce e distribuirà l'insieme di input in modo uniforme nell'insieme di possibili hash (per evitare inutili clustering/collisioni).