algorithm
Hash-functies

Inleiding tot hashfuncties

Hash-functie h() is een willekeurige functie die gegevens x ∈ X van willekeurige grootte heeft toegewezen aan waarde y ∈ Y van vaste grootte: y = h(x) . Goede hash-functies hebben de volgende beperkingen:

• hashfuncties gedragen zich als een uniforme verdeling

• hashfuncties zijn deterministisch. h(x) moet altijd dezelfde waarde teruggeven voor een gegeven x

• snelle berekening (heeft runtime O (1))

In het algemeen is de grootte van de hash-functie kleiner dan de grootte van de invoergegevens: |y| < |x| . Hash-functies zijn niet omkeerbaar of met andere woorden, het kan een botsing zijn: ∃ x1, x2 ∈ X, x1 ≠ x2: h(x1) = h(x2) . X kan eindig of oneindig ingesteld zijn en Y is eindig ingesteld.

Hash-functies worden in veel delen van de informatica gebruikt, bijvoorbeeld in software-engineering, cryptografie, databases, netwerken, machine learning enzovoort. Er zijn veel verschillende soorten hash-functies, met verschillende domeinspecifieke eigenschappen.

Hash is vaak een geheel getal. Er zijn speciale methoden in programmeertalen voor het berekenen van hash. In de methode C# GetHashCode() retourneert de methode bijvoorbeeld voor alle typen de Int32 waarde (32-bits geheel getal). In Java biedt elke klasse de methode hashCode() die int retourneert. Elk gegevenstype heeft eigen of door de gebruiker gedefinieerde implementaties.

Hash-methoden

Er zijn verschillende benaderingen voor het bepalen van de hashfunctie. Zonder verlies van algemeenheid, laat x ∈ X = {z ∈ ℤ: z ≥ 0} positieve gehele getallen zijn. Vaak is m prime (niet te dicht bij een exacte macht van 2).

Hash tafel

Hash-functies die worden gebruikt in hashtabellen voor het berekenen van de index in een reeks slots. Hash-tabel is gegevensstructuur voor het implementeren van woordenboeken (sleutel / waardestructuur). Goed geïmplementeerde hashtabellen hebben O (1) tijd voor de volgende bewerkingen: gegevens invoegen, zoeken en verwijderen met de sleutel. Meerdere sleutels kunnen dezelfde hash gebruiken. Er zijn twee manieren om een botsing op te lossen:

1. Chaining: gekoppelde lijst wordt gebruikt voor het opslaan van elementen met dezelfde hash-waarde in slot

2. Open adressering: er wordt nul of één element opgeslagen in elke sleuf

De volgende methoden worden gebruikt om de probesequenties te berekenen die nodig zijn voor open adressering

Waar i ∈ {0, 1, ..., m-1} , h'(x), h1(x), h2(x) zijn hashfuncties, c1, c2 zijn positieve hulpconstanten.

Voorbeelden

Laat x ∈ U{1, 1000}, h = x mod m . De volgende tabel toont de hash-waarden in het geval van niet prime en prime. Vetgedrukte tekst geeft dezelfde hash-waarden aan.

Links

• Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Inleiding tot algoritmen.

• Overzicht van hashtabellen

• Wolfram MathWorld - Hash-functie

Hash-codes voor veel voorkomende typen in C #

De hash-codes geproduceerd door GetHashCode() methode van ingebouwde en gemeenschappelijke C # types van het System naamruimte hieronder getoond.

Boolean

1 als waarde waar is, anders 0.

Byte , UInt16 , Int32 , UInt32 , Single

Waarde (indien nodig gecast op Int32).

SByte

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

verkolen

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

Int16

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

Int64 , dubbel

Xor tussen onderste en bovenste 32 bits van 64 bits

(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];

Voorwerp

RuntimeHelpers.GetHashCode(this);

De standaardimplementatie wordt gebruikt sync block index .

Draad

Hash-codeberekening is afhankelijk van het platformtype (Win32 of Win64), functie van het gebruik van gerandomiseerde string-hashing, Debug / Release-modus. In het geval van Win64-platform:

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

Waarde type

Het eerste niet-statische veld is zoeken naar en krijgt de hashcode. Als het type geen niet-statische velden heeft, wordt de hashcode van het type geretourneerd. De hashcode van een statisch lid kan niet worden gebruikt, omdat als dat lid van hetzelfde type is als het oorspronkelijke type, de berekening eindigt in een oneindige lus.

Nullable <T>

return hasValue ? value.GetHashCode() : 0;

reeks

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

Referenties

• GitHub .Net Core CLR