Hashbord

En hashtabell  är en datastruktur som implementerar det associativa array -gränssnittet , nämligen den låter dig lagra par (nyckel, värde) och utföra tre operationer: operationen att lägga till ett nytt par, sökoperationen och operationen att ta bort en par för nyckel.

Introduktion

Det finns två huvudvarianter av hashtabeller: kedjad och öppen adressering. Hashtabellen innehåller någon array vars element är par (en öppen adresshashtabell) eller listor med par (en kedjad hashtabell).

Utförandet av en operation i en hashtabell börjar med beräkningen av nyckelns hashfunktion . Det resulterande hashvärdet fungerar som ett index i arrayen . Sedan omdirigeras operationen som utförs (lägg till, ta bort eller hitta) till objektet, som lagras i motsvarande cell i arrayen .

Situationen när samma hashvärde erhålls för olika nycklar kallas en kollision . Sådana händelser är inte så sällsynta - till exempel när du infogar bara 23 element i en hashtabell med 365 celler, kommer sannolikheten för en kollision redan att överstiga 50% (om varje element kan falla in i vilken cell som helst med lika sannolikhet) - se födelsedagen paradox . Därför är kollisionsupplösningsmekanismen en viktig del av alla hashtabeller.

I vissa speciella fall är det möjligt att undvika kollisioner helt. Till exempel, om alla nycklar till elementen är kända i förväg (eller ändras mycket sällan), så är det för dem möjligt att hitta någon perfekt hashfunktion som kommer att fördela dem mellan cellerna i hashtabellen utan kollisioner. Hashtabeller som använder dessa hashfunktioner behöver ingen kollisionsupplösningsmekanism, utan kallas direktadresshashtabeller .

Antalet lagrade element dividerat med storleken på arrayen (antalet möjliga hash-värden) kallas för hashtabellens belastningsfaktor och är en viktig parameter som bestämmer den genomsnittliga exekveringstiden för operationer.

Hash-tabellegenskaper

En viktig egenskap hos hashtabeller är att, under några rimliga antaganden, alla tre operationerna (sökning, infogning, radering av element) slutförs i genomsnitt i tid . Detta garanterar dock inte att exekveringstiden för en enskild operation är kort. Detta beror på det faktum att när ett visst värde på fyllfaktorn uppnås är det nödvändigt att bygga om hashtabellindexet: öka arraystorleksvärdet och lägg till alla par igen i den tomma hashtabellen.

Kollisionsupplösning

Det finns flera sätt att lösa kollisioner .

Kedjemetod

Varje cell i arrayen H är en pekare till en länkad lista (kedja) av nyckel-värdepar som motsvarar samma nyckelhashvärde. Kollisioner resulterar helt enkelt i kedjor som är längre än ett element.

Att hitta eller ta bort ett element kräver att man söker igenom alla element i motsvarande kedja för att hitta ett element med en given nyckel i den. För att lägga till ett element måste du lägga till ett element i slutet eller början av motsvarande lista, och om fyllningsfaktorn blir för stor, öka storleken på arrayen H och bygga om tabellen.

Om man antar att varje element kan hamna i vilken position som helst i tabellen H med lika stor sannolikhet och oavsett var vilket annat element som helst hamnade, är medeltiden för elementsökningsoperationen Θ (1 + α ), där α  är tabellens fyllningsfaktor.

Öppna adressering

Arrayen H lagrar själva nyckel-värdeparen. Algoritmen för elementinsättning kontrollerar cellerna i arrayen H i någon ordning tills den första fria cellen hittas, i vilken det nya elementet kommer att skrivas. Denna ordning beräknas i farten, vilket sparar minne för de pekare som krävs i kedjade hashtabeller.

Sekvensen i vilken hashtabellcellerna slås upp kallas sondsekvensen . I det allmänna fallet beror det bara på elementnyckeln, det vill säga det är en sekvens h 0 ( x ), h 1 ( x ), ..., h n  - 1 ( x ), där x  är elementnyckeln , och h i ( x ) - godtyckliga funktioner som mappar varje nyckel till en cell i hashtabellen. Det första elementet i sekvensen är som regel lika med värdet av någon hashfunktion från nyckeln, och resten beräknas utifrån det på ett av följande sätt. För att sökalgoritmer ska fungera framgångsrikt måste söksekvensen vara sådan att alla celler i hashtabellen skannas exakt en gång.

Sökalgoritmen söker igenom cellerna i hashtabellen i samma ordning som vid infogning, tills antingen ett element med önskad nyckel eller en ledig cell (vilket betyder att det inte finns något element i hashtabellen) hittas.

Att ta bort element i ett sådant schema är något svårt. Vanligtvis gör de så här: de sätter upp en boolesk flagga för varje cell, som markerar om ett element i den har tagits bort eller inte. Då består borttagningen av ett element i att ställa in denna flagga för motsvarande cell i hashtabellen, men samtidigt är det nödvändigt att ändra proceduren för att söka efter ett befintligt element så att den anser att de raderade cellerna är upptagna och proceduren för att lägga till dem så att den anser dem vara fria och återställer flaggvärdet när de läggs till.

Provsekvenser

Följande är några vanliga typer av exempelsekvenser. Låt oss genast specificera att numreringen av element i sekvensen av sampel och celler i hashtabellen är från noll, och N  är storleken på hashtabellen (och, som nämnts ovan, även längden på sekvensen av sampel).

• Linjär sondering : celler i hashtabellen skannas sekventiellt med något fast intervall k mellan celler (vanligtvis k = 1), dvs. det i -te elementet i sonderingssekvensen är cellen numrerad (hash( x ) +  ik ) mod  N . För att alla celler ska skannas en gång är det nödvändigt att k är coprime med storleken på hashtabellen.
• Kvadratisk sondering : intervallet mellan celler ökar med en konstant för varje steg. Om storleken på hashtabellen är en potens av två ( N = 2 p ), är ett exempel på en sekvens där varje element kommer att slås upp en gång: hash( x ) mod N , (hash( x ) + (1+1*1)/2) mod N , (hash( x ) + (2+2*2)/2) mod N , (hash( x ) + (3+3*3)/2) mod N , … är triangulära tal .
• Dubbelhashning : intervallet mellan celler är fast, som vid linjär sondering, men till skillnad från det, beräknas storleken på intervallet av den andra extra hashfunktionen, vilket innebär att det kan vara olika för olika nycklar. Värdena för denna hashfunktion måste vara icke-noll och samprima med storleken på hashtabellen, vilket enklast uppnås genom att ta ett primtal som storlek och kräva att hashhjälparen tar värden mellan 1 och N  - 1.

Nedan finns en kod som visar dubbel hash: