algorithm
Funzioni hash

Introduzione alle funzioni di hash

La funzione hash h() è una funzione arbitraria che ha mappato i dati x ∈ X di dimensione arbitraria al valore y ∈ Y di dimensione fissa: y = h(x) . Le buone funzioni hash seguono le seguenti restrizioni:

• le funzioni di hash si comportano come una distribuzione uniforme

• le funzioni di hash sono deterministiche. h(x) dovrebbe sempre restituire lo stesso valore per una data x

• calcolo veloce (ha runtime O (1))

In generale, la dimensione della funzione hash è inferiore alla dimensione dei dati di input: |y| < |x| . Le funzioni di hash non sono reversibili o in altre parole possono essere collisioni: ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2) . X può essere finito o infinito e Y è finito.

Le funzioni di hash vengono utilizzate in molte parti dell'informatica, ad esempio in ingegneria del software, crittografia, database, reti, apprendimento automatico e così via. Esistono molti tipi diversi di funzioni hash, con proprietà differenti specifiche del dominio.

Spesso l'hash è un valore intero. Esistono metodi speciali nelle lingue di programmazione per il calcolo dell'hash. Ad esempio, nel metodo C# GetHashCode() per tutti i tipi restituisce il valore Int32 (numero intero a 32 bit). In Java ogni classe fornisce il metodo hashCode() che restituisce int . Ogni tipo di dati ha implementazioni proprie o definite dall'utente.

Metodi hash

Esistono diversi approcci per la funzione di determinazione dell'hash. Senza perdita di generalità, x ∈ X = {z ∈ ℤ: z ≥ 0} sono numeri interi positivi. Spesso m è primo (non troppo vicino a una potenza esatta di 2).

Tavolo hash

Funzioni hash utilizzate nelle tabelle hash per calcolare l'indice in una matrice di slot. La tabella hash è la struttura dati per l'implementazione dei dizionari (struttura chiave-valore). Le buone tabelle di hash implementate hanno il tempo O (1) per le operazioni successive: inserire, cercare ed eliminare i dati per chiave. Più di una chiave può avere hash nello stesso slot. Esistono due modi per risolvere la collisione:

1. Concatenamento: l'elenco collegato viene utilizzato per memorizzare elementi con lo stesso valore di hash nello slot

2. Indirizzamento aperto: zero o un elemento è memorizzato in ogni slot

I metodi successivi vengono utilizzati per calcolare le sequenze di probe richieste per l'indirizzamento aperto

Dove i ∈ {0, 1, ..., m-1} , h'(x), h1(x), h2(x) sono funzioni di hash ausiliari, c1, c2 sono costanti ausiliari positive.

Esempi

Consente x ∈ U{1, 1000}, h = x mod m . La prossima tabella mostra i valori hash in caso di non prime e prime. Il testo in grassetto indica gli stessi valori di hash.

link

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduzione agli algoritmi.

• Panoramica delle tabelle hash

• Wolfram MathWorld - Funzione hash

Codici hash per tipi comuni in C #

Di seguito sono riportati i codici hash prodotti dal metodo GetHashCode() per i tipi C # incorporati e comuni dello spazio System nomi System .

booleano

1 se valore è vero, 0 altrimenti.

Byte , UInt16 , Int32 , UInt32 , Single

Valore (se necessario, castato in Int32).

SByte

((int)m_value ^ (int)m_value << 8);

carbonizzare

(int)m_value ^ ((int)m_value << 16);

Int16

((int)((ushort)m_value) ^ (((int)m_value) << 16));

Int64 , doppio

Xo tra i 32 bit inferiori e superiori del numero a 64 bit

(unchecked((int)((long)m_value)) ^ (int)(m_value >> 32));

UInt64 , DateTime , TimeSpan

((int)m_value) ^ (int)(m_value >> 32);

Decimale

((((int *)&dbl)[0]) & 0xFFFFFFF0) ^ ((int *)&dbl)[1];

Oggetto

RuntimeHelpers.GetHashCode(this);

L'implementazione predefinita viene utilizzata indice del blocco di sincronizzazione .

Stringa

Il calcolo del codice hash dipende dal tipo di piattaforma (Win32 o Win64), caratteristica dell'utilizzo dell'hash stringa casuale, modalità Debug / Release. In caso di piattaforma Win64:

int hash1 = 5381;
int hash2 = hash1;
int c;
char *s = src;
while ((c = s[0]) != 0) {
    hash1 = ((hash1 << 5) + hash1) ^ c;
    c = s[1];
    if (c == 0)
        break;
    hash2 = ((hash2 << 5) + hash2) ^ c;
    s += 2;
}
return hash1 + (hash2 * 1566083941);

ValueType

Il primo campo non statico è cercare e ottenere hashcode. Se il tipo non ha campi non statici, viene restituito l'hashcode del tipo. Il codice hash di un membro statico non può essere preso perché se quel membro è dello stesso tipo del tipo originale, il calcolo finisce in un ciclo infinito.

Nullable <T>

return hasValue ? value.GetHashCode() : 0;

schieramento

int ret = 0;
for (int i = (Length >= 8 ? Length - 8 : 0); i < Length; i++) 
{
    ret = ((ret << 5) + ret) ^ comparer.GetHashCode(GetValue(i));
}

Riferimenti

• GitHub .Net Core CLR