algorithm
Hash-funktioner

Introduktion till hashfunktioner

Hash-funktion h() är en godtycklig funktion som kartlade data x ∈ X av godtycklig storlek till värde y ∈ Y med fast storlek: y = h(x) . Bra hashfunktioner har följande begränsningar:

• hash funktioner fungerar som likformig distribution

• hashfunktioner är deterministiska. h(x) ska alltid returnera samma värde för ett givet x

• snabb beräkning (har körtid O (1))

I allmänhet är hashfunktionens storlek mindre än inmatningsdata: |y| < |x| . Hashfunktioner är inte vändbara eller med andra ord kan det vara kollision: ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2) . X kan vara begränsat eller oändligt och Y är ändligt.

Hash-funktioner används i många delar av datavetenskap, till exempel inom programvaruteknik, kryptografi, databaser, nätverk, maskininlärning och så vidare. Det finns många olika typer av hashfunktioner, med olika domänspecifika egenskaper.

Ofta är hash ett heltal. Det finns speciella metoder för att programmera språk för hashberäkning. Till exempel GetHashCode() metoden C# GetHashCode() för alla typer Int32 värde (32 bitars heltal). I Java tillhandahåller varje klass hashCode() -metod som returnerar int . Varje datatyp har egna eller användardefinierade implementationer.

Hash-metoder

Det finns flera metoder för att bestämma hash-funktionen. Utan förlust av allmänhet, låter x ∈ X = {z ∈ ℤ: z ≥ 0} positiva heltal. Ofta är m prime (inte för nära en exakt effekt på 2).

Hashbord

Hashfunktioner som används i hashtabeller för att beräkna index till en rad slots. Hashtabellen är datastruktur för att implementera ordböcker (nyckelvärdesstruktur). Bra implementerade hashtabeller har O (1) tid för nästa operationer: infoga, söka och radera data med nyckel. Mer än en tangent kan hash till samma kortplats. Det finns två sätt att lösa kollision:

1. Kedja: länkad lista används för att lagra element med samma hashvärde i spåret

2. Öppen adressering: noll eller ett element lagras i varje kortplats

De nästa metoderna används för att beräkna sondesekvenser som krävs för öppen adressering

Där i ∈ {0, 1, ..., m-1} , h'(x), h1(x), h2(x) är hjälp hashfunktioner, c1, c2 är positiva hjälpkonstanter.

exempel

Låter x ∈ U{1, 1000}, h = x mod m . Nästa tabell visar hashvärdena om inte prim och prim. Fet text anger samma hashvärden.

länkar

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduktion till algoritmer.

• Översikt över Hash-tabeller

• Wolfram MathWorld - Hash-funktion

Hashkoder för vanliga typer i C #

De hash-koder som produceras av GetHashCode() metod för inbyggda och gemensamma C # typer från den System visas nedan.

Boolean

1 om värdet är sant, 0 annars.

Byte , UInt16 , Int32 , UInt32 , Singel

Värde (om nödvändigt gjuten till Int32).

SByte

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

Röding

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

Int16

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

Int64 , dubbel

Xor mellan nedre och övre 32 bitar med 64 bitars antal

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

UInt64 , DateTime , TimeSpan

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

Decimal

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

Objekt

RuntimeHelpers.GetHashCode(this);

Standardimplementeringen används synkroniseringsblocksindex .

Sträng

Beräkningen av Hash-kod beror på plattformstypen (Win32 eller Win64), funktionen för att använda randomiserad sträng hashning, Debug / Release-läge. Vid Win64-plattform:

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);

Värde typ

Det första icke-statiska fältet är att leta efter och få sin hashcode. Om typen inte har några icke-statiska fält, returneras hashkoden för typen. Hashkoden för en statisk medlem kan inte tas eftersom om den medlemmen är av samma typ som den ursprungliga typen hamnar beräkningen i en oändlig slinga.

Null <T>

return hasValue ? value.GetHashCode() : 0;

Array

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

referenser

• GitHub. Net Core CLR