Hash bord
Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 12. oktober 2019; checks kræver 9 redigeringer .| Hash bord | ||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| Type | associativ array | |||||||||||||||
| Opfindelsens år | 1953 | |||||||||||||||
| Kompleksitet i O-symboler | ||||||||||||||||
|
||||||||||||||||
| Mediefiler på Wikimedia Commons | ||||||||||||||||
En hash-tabel er en datastruktur, der implementerer den associative array -grænseflade , nemlig den giver dig mulighed for at gemme par (nøgle, værdi) og udføre tre operationer: operationen med at tilføje et nyt par, søgeoperationen og operationen med at slette en par for nøgle.
Introduktion
Der er to hovedvarianter af hashtabeller: lænket og åben adressering. Hash-tabellen indeholder et array , hvis elementer er par (en åben adresse-hash-tabel) eller lister over par (en kædet hash-tabel).
Udførelsen af en operation i en hash-tabel begynder med beregningen af nøglens hashfunktion . Den resulterende hash-værdi fungerer som et indeks i arrayet . Derefter bliver den handling, der udføres (tilføj, slet eller find), omdirigeret til objektet, som er gemt i den tilsvarende celle i arrayet .
![Hej]](https://wikimedia.org/api/rest_v1/media/math/render/svg/c3e0d1e646ae278fb8ce6fc87c85e9cf2f61fcd0)
Den situation, hvor den samme hashværdi opnås for forskellige nøgler, kaldes en kollision . Sådanne hændelser er ikke så sjældne - for eksempel, når man kun indsætter 23 elementer i en hash-tabel med 365 celler, vil sandsynligheden for en kollision allerede overstige 50% (hvis hvert element kan falde ind i en hvilken som helst celle med lige stor sandsynlighed) - se fødselsdagen paradoks . Derfor er kollisionsopløsningsmekanismen en vigtig del af enhver hash-tabel.
I nogle særlige tilfælde er det muligt helt at undgå kollisioner. For eksempel, hvis alle nøglerne til elementerne er kendt på forhånd (eller ændres meget sjældent), så er det for dem muligt at finde en perfekt hash-funktion , der vil fordele dem mellem cellerne i hash-tabellen uden kollisioner. Hash-tabeller, der bruger disse hash-funktioner, behøver ikke en kollisionsopløsningsmekanisme og kaldes direkte adresse- hash-tabeller .
Antallet af lagrede elementer divideret med størrelsen af arrayet (antallet af mulige hash-værdier) kaldes hash-tabellens belastningsfaktor og er en vigtig parameter, der bestemmer den gennemsnitlige udførelsestid for operationer.
Hash-tabelegenskaber
En vigtig egenskab ved hash-tabeller er, at under nogle rimelige antagelser fuldføres alle tre operationer (søgning, indsættelse, sletning af elementer) i gennemsnit i tid . Dette garanterer dog ikke, at udførelsestiden for en enkelt operation er lille. Dette skyldes det faktum, at når en vis værdi af fyldfaktoren er nået, er det nødvendigt at genopbygge hash-tabelindekset: øg array -størrelsesværdien og genføje alle par til den tomme hash-tabel.
Kollisionsopløsning
Der er flere måder at løse kollisioner på .
Kædemetode
Hver celle i arrayet H er en pegepind til en sammenkædet liste (kæde) af nøgle-værdi-par, der svarer til den samme nøglehashværdi. Kollisioner resulterer simpelthen i kæder, der er længere end ét element.
At finde eller slette et element kræver søgning gennem alle elementerne i den tilsvarende kæde for at finde et element med en given nøgle i. For at tilføje et element, skal du tilføje et element til slutningen eller begyndelsen af den tilsvarende liste, og hvis fyldfaktoren bliver for stor, skal du øge størrelsen af array H og genopbygge tabellen.
Hvis man antager, at hvert element kan falde i en hvilken som helst position i tabellen H med lige stor sandsynlighed, og uanset hvor et hvilket som helst andet element endte, er den gennemsnitlige tid for elementsøgningsoperationen Θ (1 + α ), hvor α er tabelfyldningsfaktoren.
Åbn adressering
Arrayet H gemmer selve nøgleværdi-parrene. Elementindsættelsesalgoritmen kontrollerer cellerne i array H i en eller anden rækkefølge, indtil den første frie celle er fundet, hvori det nye element vil blive skrevet. Denne rækkefølge beregnes på et øjeblik, hvilket sparer på hukommelsen til de pointere, der kræves i kædede hashtabeller.
Rækkefølgen, hvori hash-tabelcellerne slås op, kaldes probesekvensen . I det generelle tilfælde afhænger det kun af elementnøglen, det vil sige, det er en sekvens h 0 ( x ), h 1 ( x ), ..., h n - 1 ( x ), hvor x er elementnøglen , og h i ( x ) - vilkårlige funktioner, der knytter hver nøgle til en celle i hash-tabellen. Det første element i sekvensen er som regel lig med værdien af en eller anden hashfunktion fra nøglen, og resten beregnes ud fra den på en af følgende måder. For at søgealgoritmer skal fungere med succes, skal sekvensen af sonder være sådan, at alle celler i hashtabellen scannes nøjagtigt én gang.
Søgealgoritmen søger i cellerne i hash-tabellen i samme rækkefølge som ved indsættelse, indtil enten et element med den ønskede nøgle eller en ledig celle (hvilket betyder, at der ikke er noget element i hash-tabellen) findes.
At fjerne elementer i en sådan ordning er noget vanskeligt. Normalt gør de dette: De opsætter et boolesk flag for hver celle, der markerer, om et element i den er blevet slettet eller ej. Så består fjernelsen af et element i at sætte dette flag for den tilsvarende celle i hash-tabellen, men samtidig er det nødvendigt at ændre proceduren for at søge efter et eksisterende element, så det betragter de slettede celler som optaget, og proceduren for at tilføje dem, så det betragter dem som frie og nulstiller flagværdien, når de tilføjes.
Prøvesekvenser
Følgende er nogle almindelige typer prøvesekvenser. Lad os med det samme specificere, at nummereringen af elementer i sekvensen af prøver og celler i hash-tabellen er fra nul, og N er størrelsen af hash-tabellen (og, som nævnt ovenfor, også længden af sekvensen af prøver).
- Lineær sondering : celler i hash-tabellen scannes sekventielt med et fast interval k mellem celler (normalt k = 1), dvs. det i -te element i sonderingssekvensen er cellen nummereret (hash( x ) + ik ) mod N . For at alle celler skal scannes én gang, er det nødvendigt, at k er coprime med størrelsen af hash-tabellen.
- Kvadratisk sondering : intervallet mellem celler øges med en konstant for hvert trin. Hvis størrelsen af hashtabellen er en potens af to ( N = 2 p ), så er et eksempel på en sekvens, hvor hvert element vil blive slået op én gang: 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 , … er trekantede tal .
- Dobbelt hashing : intervallet mellem celler er fast, som ved lineær sondering, men i modsætning til det, beregnes størrelsen af intervallet af den anden hjælpehash-funktion, hvilket betyder, at det kan være forskelligt for forskellige nøgler. Værdierne af denne hash-funktion skal være ikke-nul og coprime med størrelsen af hash-tabellen, hvilket lettest opnås ved at tage et primtal som størrelse og kræve, at hash-hjælperen tager værdier mellem 1 og N - 1.
Nedenfor er en kode, der demonstrerer dobbelt hashing:
Se også
Litteratur
- Kormen, T. , Leizerson, C. , Rivest, R. , Stein, K. Kapitel 11. Hash-tabeller. // Algoritmer: konstruktion og analyse = Introduktion til algoritmer / Red. I. V. Krasikova. - 2. udg. - M. : Williams, 2005. - 1296 s. — ISBN 5-8459-0857-4 .
| Datastrukturer | |
|---|---|
| Lister | |
| Træer | |
| Tæller | |
| Andet | |