algorithm
Hash-Funktionen

Einführung in Hashfunktionen

Die Hash-Funktion h() ist eine willkürliche Funktion, die Daten x ∈ X beliebiger Größe auf den Wert y ∈ Y fester Größe y ∈ Y : y = h(x) . Für gute Hash-Funktionen gelten folgende Einschränkungen:

• Hash-Funktionen verhalten sich wie eine gleichmäßige Verteilung

• Hash-Funktionen sind deterministisch. h(x) sollte immer den gleichen Wert für ein gegebenes x

• schnelle Berechnung (hat Laufzeit O (1))

Im Allgemeinen ist die Hash-Funktion kleiner als die Eingangsdatengröße: |y| < |x| . Hash-Funktionen sind nicht umkehrbar oder mit anderen Worten, es kann eine Kollision sein: ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2) . X kann eine endliche oder eine unendliche Menge sein und Y ist eine endliche Menge.

Hash-Funktionen werden in vielen Bereichen der Informatik verwendet, beispielsweise in der Softwaretechnik, Kryptographie, Datenbanken, Netzwerken, maschinellem Lernen usw. Es gibt viele verschiedene Arten von Hash-Funktionen mit unterschiedlichen domänenspezifischen Eigenschaften.

Hash ist oft ein ganzzahliger Wert. In den Programmiersprachen gibt es spezielle Methoden zur Hashberechnung. In C# GetHashCode() Methode für alle Typen beispielsweise den Int32 Wert (32-Bit-Ganzzahl) zurück. In Java jede Klasse die Methode hashCode() bereit, die int . Jeder Datentyp hat eigene oder benutzerdefinierte Implementierungen.

Hash-Methoden

Es gibt verschiedene Ansätze zur Bestimmung der Hash-Funktion. Ohne Verlust der Allgemeinheit sei x ∈ X = {z ∈ ℤ: z ≥ 0} positive ganze Zahlen. Oft ist m prim (nicht zu nahe an einer exakten Potenz von 2).

Hash-tabelle

Hash-Funktionen, die in Hash-Tabellen zum Berechnen des Index in ein Array von Slots verwendet werden. Hash-Tabelle ist eine Datenstruktur zum Implementieren von Wörterbüchern (Schlüsselwertstruktur). Gute implementierte Hashtabellen haben O (1) Zeit für die nächsten Operationen: Einfügen, Suchen und Löschen von Daten nach Schlüssel. Es können mehrere Tasten auf denselben Steckplatz zugreifen. Es gibt zwei Möglichkeiten, die Kollision aufzulösen:

1. Verkettung: Die verkettete Liste wird zum Speichern von Elementen mit demselben Hashwert in Slot verwendet

2. Offene Adressierung: In jedem Steckplatz ist null oder ein Element gespeichert

Die nächsten Methoden werden verwendet, um die für die offene Adressierung erforderlichen Sondensequenzen zu berechnen

Dabei sind i ∈ {0, 1, ..., m-1} , h'(x), h1(x), h2(x) Hashfunktionen, c1, c2 sind positive Hilfskonstanten.

Beispiele

Es sei x ∈ U{1, 1000}, h = x mod m . Die nächste Tabelle zeigt die Hash-Werte für den Fall, dass kein Prim und kein Prim steht. Fettgedruckter Text kennzeichnet dieselben Hashwerte.

Links

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest und Clifford Stein. Einführung in Algorithmen.

• Übersicht über Hash-Tabellen

• Wolfram MathWorld - Hash-Funktion

Hashcodes für häufig verwendete Typen in C #

Die Hash-Codes, die von der GetHashCode() -Methode für integrierte und allgemeine C # -Typen aus dem System Namespace erstellt werden, sind unten aufgeführt.

Boolean

1 wenn Wert wahr ist, sonst 0.

Byte , UInt16 , Int32 , UInt32 , Single

Wert (ggf. in Int32 umgewandelt).

SByte

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

Verkohlen

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

Int16

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

Int64 , doppelt

Xoder zwischen unteren und oberen 32 Bits der 64-Bit-Nummer

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

UInt64 , DateTime , TimeSpan

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

Dezimal

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

Objekt

RuntimeHelpers.GetHashCode(this);

Die Standardimplementierung ist der Sync-Block-Index .

String

Die Hash-Code-Berechnung hängt vom Plattformtyp (Win32 oder Win64) ab, der Funktion der Verwendung von randomisiertem String-Hashing und dem Debug- / Release-Modus. Im Falle einer 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);

Werttyp

Das erste nicht statische Feld sucht und erhält seinen Hashcode. Wenn der Typ keine nicht statischen Felder hat, wird der Hashcode des Typs zurückgegeben. Der Hashcode eines statischen Mitglieds kann nicht verwendet werden, da das Berechnen in einer Endlosschleife endet, wenn es sich um denselben Typ wie der ursprüngliche Typ handelt.

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

Verweise

• GitHub .Net Core CLR