Hash bord - Hash table

Hash bord
Hash bord
Type	Uordnet associeret array
Opfundet	1953
Tidskompleksitet i stor O -notation

En lille telefonbog som et hashbord

I computing er en hashtabel ( hashkort ) en datastruktur, der implementerer en associeret array abstrakt datatype , en struktur, der kan kortlægge nøgler til værdier . En hashtabel bruger en hashfunktion til at beregne et indeks , også kaldet en hashkode , til en række spande eller slots , hvorfra den ønskede værdi kan findes. Under opslag hascheres nøglen, og den resulterende hash angiver, hvor den tilsvarende værdi er gemt.

Ideelt set vil den hash-funktion tildele hver tast til en unik spand, men de fleste hash table design ansætte en ufuldkommen hash-funktion, som kan forårsage hash kollisioner , hvor hash-funktionen genererer det samme indeks i mere end én nøgle. Sådanne kollisioner er typisk indkvarteret på en eller anden måde.

I en veldimensioneret hashtabel er den gennemsnitlige pris (antal instruktioner ) for hvert opslag uafhængigt af antallet af elementer, der er gemt i tabellen. Mange hash -borddesigner tillader også vilkårlige indsættelser og sletninger af nøgleværdi -par til ( amortiseret ) konstant gennemsnitlig pris pr. Operation.

I mange situationer, hash tabeller viser sig at være i gennemsnit mere effektiv end søgetræer eller enhver anden tabel opslag struktur. Af denne grund, er de meget udbredt i mange former for edb -software , især for associative arrays , database indeksering , caches , og sæt .

Hashing

Ideen med hashing er at distribuere posterne (nøgle/værdipar) på tværs af en række spande . På grund af en nøgle beregner algoritmen et indeks, der foreslår, hvor posten kan findes:

index = f(key, array_size)

Ofte gøres dette i to trin:

hash = hashfunc(key)
index = hash % array_size

I denne metode er hash uafhængig af arraystørrelsen, og den reduceres derefter til et indeks (et tal mellem 0og array_size − 1) ved hjælp af modulo -operatoren ( %).

I tilfælde af at matrixstørrelsen er en effekt på to , reduceres den resterende operation til maskering , hvilket forbedrer hastigheden, men kan øge problemer med en dårlig hashfunktion.

Valg af en hash -funktion

Et grundlæggende krav er, at funktionen skal give en ensartet fordeling af hashværdier. En ikke-ensartet fordeling øger antallet af kollisioner og omkostningerne ved at løse dem. Ensartethed er undertiden vanskeligt at sikre ved design, men kan evalueres empirisk ved hjælp af statistiske tests, f.eks. En Pearsons chi-squared-test for diskrete ensartede fordelinger.

Fordelingen behøver kun at være ensartet for bordstørrelser, der forekommer i applikationen. Især hvis man bruger dynamisk størrelse med nøjagtig fordobling og halvering af bordstørrelsen, skal hash -funktionen kun være ensartet, når størrelsen er en effekt på to . Her kan indekset beregnes som nogle bits af hashfunktionen. På den anden side foretrækker nogle hash -algoritmer, at størrelsen er et primtal . Moduloperationen kan tilvejebringe en vis yderligere blanding; dette er især nyttigt med en dårlig hash -funktion.

For åbne adresseringsordninger bør hashfunktionen også undgå klynger , kortlægning af to eller flere nøgler til på hinanden følgende slots. En sådan klynge kan få opslagsomkostningerne til at stige i vejret, selvom belastningsfaktoren er lav, og kollisioner er sjældne. Den populære multiplikative hash hævdes at have særlig dårlig klyngeadfærd.

Kryptografiske hashfunktioner menes at give gode hashfunktioner til enhver bordstørrelse, enten ved moduloreduktion eller ved bitmaskering . De kan også være passende, hvis der er risiko for ondsindede brugere, der forsøger at sabotere en netværkstjeneste ved at indsende anmodninger, der er designet til at generere et stort antal kollisioner i serverens hashtabeller. Risikoen for sabotage kan dog også undgås ved billigere metoder (f.eks. At anvende et hemmeligt salt på dataene eller bruge en universel hash -funktion ). En ulempe ved kryptografiske hashfunktioner er, at de ofte er langsommere at beregne, hvilket betyder, at i tilfælde, hvor ensartetheden for enhver størrelse ikke er nødvendig, kan en ikke-kryptografisk hashfunktion være at foretrække.

K-uafhængig hashing tilbyder en måde at bevise, at en bestemt hash-funktion ikke har dårlige nøglesæt til en given type hashtabel. En række sådanne resultater er kendt for kollisionsopløsningsordninger, såsom lineær sondering og gøge -hashing. Da K-uafhængighed kan bevise, at en hash-funktion virker, kan man derefter fokusere på at finde den hurtigst mulige sådan hash-funktion.

Perfekt hash -funktion

Hvis alle nøgler kendes på forhånd, kan en perfekt hash -funktion bruges til at oprette en perfekt hash -tabel, der ikke har nogen kollisioner. Hvis der bruges minimal perfekt hash , kan hvert sted i hashtabellen også bruges.

Perfekt hashing giver mulighed for konstant tidssøgninger i alle tilfælde. Dette er i modsætning til de fleste kæde- og åbne adresseringsmetoder, hvor tiden for opslag i gennemsnit er lav, men kan være meget stor, O ( n ), for eksempel når alle nøgler hash til et par værdier.

Vigtig statistik

En kritisk statistik for en hashtabel er belastningsfaktoren , defineret som

{\ displaystyle {\ text {load factor}} = {\ frac {n} {k}}}

,

hvor

n er antallet af poster optaget i hashtabellen.
k er antallet af spande.

Når belastningsfaktoren vokser sig større, bliver hashtabellen langsommere, og den kan endda ikke fungere (afhængigt af den anvendte metode). Den forventede konstante tidsejendom for en hashtabel forudsætter, at belastningsfaktoren holdes under en vis grænse. For et fast antal spande vokser tiden for et opslag med antallet af poster, og derfor opnås den ønskede konstante tid ikke. I nogle implementeringer er løsningen automatisk at vokse (normalt, dobbelt) størrelsen på tabellen, når den indskrænkede belastningsfaktor er nået og dermed tvinge til at hash-hash alle poster igen. Som et eksempel fra den virkelige verden er standardbelastningsfaktoren for en HashMap i Java 10 0,75, hvilket "giver en god afvejning mellem tid og rumomkostninger."

For det andet efter belastningsfaktoren kan man undersøge variansen af antallet af indgange pr. Spand. For eksempel har to tabeller begge 1.000 poster og 1.000 spande; den ene har præcis en post i hver spand, den anden har alle poster i den samme spand. Det er klart, at hashing ikke fungerer i den anden.

En lav belastningsfaktor er ikke særlig fordelagtig. Når belastningsfaktoren nærmer sig 0, stiger andelen af ubrugte områder i hashtabellen, men der er ikke nødvendigvis nogen reduktion i søgeomkostningerne. Dette resulterer i spild af hukommelse.

Kollisionsopløsning

Hashkollisioner er praktisk talt uundgåelige, når man hascher en tilfældig delmængde af et stort sæt mulige nøgler. For eksempel, hvis 2.450 nøgler er hash i en million spande, selv med en helt ensartet tilfældig fordeling, er der i henhold til fødselsdagsproblemet cirka 95% chance for, at mindst to af tasterne bliver hasket til det samme slot.

Derfor har næsten alle hashtabelimplementeringer en strategi for kollisionsopløsning til håndtering af sådanne hændelser. Nogle fælles strategier er beskrevet nedenfor. Alle disse metoder kræver, at nøglerne (eller henvisninger til dem) gemmes i tabellen sammen med de tilhørende værdier.

Separat kæde

Hashkollision løst ved separat kæde

I metoden kendt som separat kæde er hver spand uafhængig og har en slags liste over poster med samme indeks. Tiden for hashtabeloperationer er tiden til at finde spanden (som er konstant) plus tiden for listeoperationen.

I de fleste implementeringer vil spande have få poster, hvis hashfunktionen fungerer korrekt. Derfor foretrækkes strukturer, der er effektive i tid og rum til disse sager. Strukturer, der er effektive til et ret stort antal poster pr. Spand, er ikke nødvendige eller ønskelige. Hvis disse tilfælde sker ofte, skal hashfunktionen rettes.

Der er nogle implementeringer, der giver fremragende ydeevne for både tid og rum, hvor det gennemsnitlige antal elementer pr. Spand ligger mellem 5 og 100.

Separat kæde med sammenkædede lister

Kædede hashtabeller med sammenkædede lister er populære, fordi de kun kræver grundlæggende datastrukturer med enkle algoritmer og kan bruge enkle hashfunktioner, der er uegnede til andre metoder.

Omkostningerne ved en bordoperation er omkostningerne ved at scanne posterne i den valgte spand efter den ønskede nøgle. Hvis fordelingen af nøgler er tilstrækkeligt ensartet , afhænger de gennemsnitlige omkostninger ved et opslag kun af det gennemsnitlige antal nøgler pr. Spand - det vil sige, at det er nogenlunde proportionalt med belastningsfaktoren.

Af denne grund forbliver lænkede hashtabeller effektive, selv når antallet af tabelposter n er meget højere end antallet af slots. For eksempel er et kædet hashbord med 1000 slots og 10.000 lagrede nøgler (belastningsfaktor 10) fem til ti gange langsommere end et bord med 10.000 pladser (belastningsfaktor 1); men stadig 1000 gange hurtigere end en almindelig sekventiel liste.

Ved separat kæde er det værste tilfælde, når alle poster indsættes i den samme spand, i hvilket tilfælde hashtabellen er ineffektiv, og omkostningerne er ved at søge i skovldatastrukturen. Hvis sidstnævnte er en lineær liste kan opslag procedure nødt til at scanne alle sine poster, så det værst tænkelige omkostninger er proportional med antallet n af poster i tabellen.

Spandkæderne søges ofte i rækkefølge ved hjælp af den rækkefølge posterne blev føjet til spanden. Hvis belastningsfaktoren er stor, og nogle nøgler er mere tilbøjelige til at komme op end andre, kan omarrangering af kæden med en heuristisk bevægelse til front være effektiv. Mere sofistikerede datastrukturer, såsom afbalancerede søgetræer, er kun værd at overveje, hvis belastningsfaktoren er stor (ca. 10 eller mere), eller hvis hashfordelingen sandsynligvis er meget uensartet, eller hvis man selv skal garantere god ydeevne i værste fald. Imidlertid kan brug af et større bord og/eller en bedre hash -funktion være endnu mere effektiv i disse tilfælde.

Chained hash -tabeller arver også ulemperne ved sammenkædede lister. Når du gemmer små nøgler og værdier, kan pladsen overhead for nextmarkøren i hver postpost være betydelig. En yderligere ulempe er, at krydsning af en linket liste har dårlig cache -ydeevne , hvilket gør processorens cache ineffektiv.

Separat kæde med listehovedceller

Hashkollision ved separat kæde med hovedrekorder i bucket -arrayet.

Nogle kædeimplementeringer gemmer den første registrering af hver kæde i selve slot -arrayet. Antallet af markørkrydsninger reduceres med en i de fleste tilfælde. Formålet er at øge cache -effektiviteten af hash -bordadgang.

Ulempen er, at en tom spand tager samme plads som en spand med én indgang. For at spare plads har sådanne hashtabeller ofte omtrent lige så mange slots som lagrede poster, hvilket betyder, at mange slots har to eller flere poster.

Separat sammenkædning med andre strukturer

I stedet for en liste kan man bruge enhver anden datastruktur, der understøtter de nødvendige operationer. For eksempel ved at bruge et selvbalancerende binært søgetræ kan den teoretiske værst tænkelige tid for almindelige hashtabeloperationer (indsættelse, sletning, opslag) bringes ned til O (log n ) frem for O ( n ). Dette introducerer imidlertid ekstra kompleksitet i implementeringen og kan forårsage endnu dårligere ydeevne for mindre hashtabeller, hvor tiden brugt på at indsætte og balancere træet er større end den tid, der er nødvendig for at udføre en lineær søgning på alle elementer i en liste . Et virkeligt eksempel på en hashtabel, der bruger et selvbalancerende binært søgetræ til spande, er HashMapklassen i Java version 8 .

Varianten kaldes array -hashtabellen bruger et dynamisk array til at gemme alle de poster, der hash, til den samme slot. Hver ny indsat post bliver tilføjet til slutningen af den dynamiske matrix, der er tildelt pladsen. Det dynamiske array ændres i en præcis måde, hvilket betyder, at det kun vokser med så mange bytes som nødvendigt. Alternative teknikker såsomat udvidearrayet med blokstørrelser eller sider viste sig at forbedre indsættelsesydelsen, men til en pris i rummet. Denne variation gør mere effektiv brug af CPU -caching og translation lookaside buffer (TLB), fordi slotsposter gemmes i sekventielle hukommelsespositioner. Det undgår også denextpointer, der kræves af sammenkædede lister, hvilket sparer plads. På trods af hyppig matrixændring viste det sig, at der var små omkostninger forbundet med operativsystemet, f.eks. Hukommelsesfragmentering.

En uddybning af denne tilgang er den såkaldte dynamiske perfekte hashing , hvor en spand, der indeholder k- poster, er organiseret som et perfekt hashbord med k ² slots. Selvom den bruger mere hukommelse ( n ² slots til n poster, i værste fald og n × k slots i det gennemsnitlige tilfælde), har denne variant garanteret konstant worst-case opslagstid og lav amortiseret tid for indsættelse. Det er også muligt at bruge et fusionstræ til hver spand, der opnår konstant tid for alle operationer med stor sandsynlighed.

Åben adressering

Hashkollision løst ved åben adressering med lineær sondering (interval = 1). Bemærk, at "Ted Baker" har en unik hash, men ikke desto mindre kolliderede med "Sandra Dee", der tidligere var kollideret med "John Smith".

I en anden strategi, kaldet åben adressering, gemmes alle indgangsposter i selve bucket -arrayet. Når en ny post skal indsættes, undersøges spandene, startende med den hasched-to slot og fortsætter i en eller anden probesekvens , indtil en ledig slot er fundet. Når man søger efter en post, scannes skovlene i samme sekvens, indtil enten målposten er fundet, eller der findes et ubrugt array -slot, hvilket indikerer, at der ikke er en sådan nøgle i tabellen. Navnet "åben adressering" refererer til det faktum, at elementets placering ("adresse") ikke bestemmes af dets hashværdi. (Denne metode kaldes også lukket hash , den skal ikke forveksles med "åben hashing" eller "lukket adressering", der normalt betyder separat kæde.)

Kendte probesekvenser omfatter:

Lineær sondering , hvor intervallet mellem prober er fast (normalt 1). På grund af god CPU -cacheudnyttelse og høj ydeevne er denne algoritme mest udbredt på moderne computerarkitekturer i hashtabelimplementeringer.
Kvadratisk sondering , hvor intervallet mellem prober øges ved at tilføje de successive output af et kvadratisk polynom til startværdien givet af den originale hashberegning
Dobbelt hash , hvor intervallet mellem prober beregnes af en anden hash -funktion

En ulempe ved alle disse åbne adresseringsskemaer er, at antallet af gemte poster ikke kan overstige antallet af slots i bucket -arrayet. Faktisk, selv med gode hashfunktioner, forringes deres ydeevne dramatisk, når belastningsfaktoren vokser ud over 0,7 eller deromkring. For mange applikationer kræver disse begrænsninger brug af dynamisk størrelse, med tilhørende omkostninger.

Åbne adresseringsordninger stiller også strengere krav til hashfunktionen: Udover at nøglerne fordeles mere ensartet over spandene, skal funktionen også minimere gruppering af hashværdier, der er på hinanden følgende i sonderækkefølgen. Ved hjælp af separat kæde er den eneste bekymring, at for mange objekter kortlægger den samme hashværdi; om de er tilstødende eller i nærheden er fuldstændig irrelevant.

Åben adressering gemmer kun hukommelse, hvis posterne er små (mindre end fire gange størrelsen på en markør), og belastningsfaktoren ikke er for lille. Hvis belastningsfaktoren er tæt på nul (det vil sige, at der er langt flere spande end gemte poster), er åben adressering spild, selvom hver post kun er to ord .

Denne graf sammenligner det gennemsnitlige antal CPU -cache -savner, der kræves for at slå elementer op i store hashtabeller (langt over cachens størrelse) med kæde og lineær sondering. Lineær sondering klarer sig bedre på grund af bedre lokalitet , men efterhånden som tabellen bliver fuld, forringes dens ydeevne drastisk.

Åben adressering undgår tidsomkostningerne ved tildeling af hver ny postpost og kan implementeres selv i mangel af en hukommelsesallokator. Det undgår også den ekstra indirektion, der kræves for at få adgang til den første indtastning af hver spand (det vil sige normalt den eneste). Det har også en bedre referencelokalitet , især med lineær sondering. Med små rekordstørrelser kan disse faktorer give bedre ydeevne end kæde, især for opslag. Hashtabeller med åben adressering er også lettere at serialisere , fordi de ikke bruger pointer.

På den anden side er normal åben adressering et dårligt valg for store elementer, fordi disse elementer fylder hele CPU -cachelinjer (negerer cachefordelen), og der spildes en stor mængde plads på store tomme bordpladser. Hvis den åbne adressetabel kun gemmer referencer til elementer (ekstern lagring), bruger den plads, der kan sammenlignes med kæder, selv for store poster, men mister sin hastighedsfordel.

Generelt bruges åben adressering bedre til hashtabeller med små poster, der kan gemmes i tabellen (intern lagring) og passer i en cachelinje. De er især velegnede til elementer af et ord eller mindre. Hvis tabellen forventes at have en høj belastningsfaktor, er posterne store, eller dataene er af variabel størrelse, kædet hash-tabeller fungerer ofte lige så godt eller bedre.

Samlet hashing

En hybrid af chaining og open addressing, coalesced hashing forbinder kæder af noder i selve tabellen. Ligesom åben adressering opnår den pladsforbrug og (noget formindskede) cache -fordele i forhold til kædeforbindelse. Ligesom kædning udviser den ikke klyngeeffekter; faktisk kan bordet effektivt fyldes til en høj densitet. I modsætning til kæde kan den ikke have flere elementer end bordspor.

Gøg hashing

En anden alternativ løsning til åben adressering er gøge-hashing , som sikrer konstant opslag og sletningstid i værste tilfælde og konstant amortiseret tid for indsættelser (med lav sandsynlighed for, at det værste tilfælde vil blive stødt). Den bruger to eller flere hashfunktioner, hvilket betyder, at ethvert nøgle/værdipar kan være to eller flere steder. Til opslag bruges den første hash -funktion; hvis nøglen/værdien ikke findes, bruges den anden hash -funktion osv. Hvis der sker et sammenstød under indsættelsen, hascheres nøglen igen med den anden hash-funktion for at kortlægge den til en anden spand. Hvis alle hashfunktioner bruges, og der stadig er en kollision, fjernes nøglen, den kolliderede med, for at give plads til den nye nøgle, og den gamle nøgle re-hashes med en af de andre hashfunktioner, som kortlægger den til en anden spand. Hvis dette sted også resulterer i en kollision, gentages processen, indtil der ikke er nogen kollision, eller processen krydser alle spande, på hvilket tidspunkt tabellen ændres. Ved at kombinere flere hashfunktioner med flere celler pr. Spand kan der opnås meget høj pladsudnyttelse.

Hopscotch hashing

En anden alternativ open-addressing-løsning er hopscotch-hashing , som kombinerer tilgange til gøgshashing og lineær sondering , men alligevel synes generelt at undgå deres begrænsninger. Især fungerer det godt, selv når belastningsfaktoren vokser ud over 0,9. Algoritmen er velegnet til implementering af en resizable samtidig hash -tabel .

Hopscotch hashing -algoritmen fungerer ved at definere et kvarter med spande nær den originale hashed -spand, hvor en given post altid findes. Således er søgning begrænset til antallet af poster i dette kvarter, hvilket i værste tilfælde er logaritmisk, konstant i gennemsnit og med korrekt tilpasning af kvarteret typisk kræver en cache -miss. Når man indsætter en post, prøver man først at tilføje den til en spand i nabolaget. Men hvis alle spande i dette kvarter er besat, krydser algoritmen spande i rækkefølge, indtil der findes en åben spalte (en ledig spand) (som ved lineær sondering). På det tidspunkt, da den tomme spand er uden for kvarteret, forskydes genstande gentagne gange i en række humle. (Dette ligner gøg -hashing, men med den forskel, at den tomme plads i dette tilfælde flyttes til kvarteret, i stedet for at genstande flyttes ud med håb om i sidste ende at finde en tom slot.) Hvert hop bringer den åbne slot tættere på til det oprindelige kvarter uden at ugyldiggøre naboskabsejendommen for nogen af spandene undervejs. I sidste ende er den åbne slot blevet flyttet ind i nabolaget, og posten, der indsættes, kan tilføjes til den.

Robin Hood hashing

En variant af dobbelt-hashing kollisionsopløsning er Robin Hood hashing. Ideen er, at en ny nøgle kan fortrænge en nøgle, der allerede er indsat, hvis dens sondeantal er større end nøglen på den aktuelle position. Nettoeffekten af dette er, at det reducerer worst case -søgetider i tabellen. Dette ligner bestilte hashtabeller bortset fra at kriteriet for at støde på en nøgle ikke afhænger af et direkte forhold mellem tasterne. Da både det værste tilfælde og variationen i antallet af prober reduceres dramatisk, er en interessant variation at undersøge tabellen, der starter ved den forventede vellykkede sondeværdi og derefter udvide fra denne position i begge retninger. Ekstern Robin Hood-hashing er en udvidelse af denne algoritme, hvor tabellen er gemt i en ekstern fil, og hver bordposition svarer til en side eller en spand med fast størrelse med B- poster.

2-valgs hashing

2-valgshashing anvender to forskellige hashfunktioner, h ₁ ( x ) og h ₂ ( x ), til hashtabellen. Begge hashfunktioner bruges til at beregne to bordplaceringer. Når et objekt indsættes i tabellen, placeres det på bordplaceringen, der indeholder færre objekter (med standard er bordplaceringen h ₁ ( x ), hvis der er lighed i skovlstørrelse). 2-valgshashing anvender princippet om kraften i to valg.

Dynamisk størrelse

Når der indsættes sådan, at antallet af indtastninger i en hashtabel overstiger produktet af belastningsfaktoren og den nuværende kapacitet, skal hashtabellen genopfriskes . Rehashing omfatter forøgelse af størrelsen på den underliggende datastruktur og kortlægning af eksisterende varer til nye skovlplaceringer. I nogle implementeringer, hvis den indledende kapacitet er større end det maksimale antal poster divideret med belastningsfaktoren, vil der aldrig blive foretaget genopskylningsoperationer.

For at begrænse andelen af spild af hukommelse på grund af tomme spande, krymper nogle implementeringer også bordets størrelse - efterfulgt af en genopfriskning - når elementer slettes. Fra afvejningen mellem rum og tid ligner denne operation til deallokationen i dynamiske arrays.

Tilpas størrelse ved at kopiere alle poster

En almindelig tilgang er automatisk at udløse en fuldstændig ændring af størrelsen, når belastningsfaktoren overskrider en grænseværdi r _max . Derefter tildeles en ny større tabel , hver post fjernes fra den gamle tabel og indsættes i den nye tabel. Når alle poster er blevet fjernet fra det gamle bord, returneres det gamle bord til den gratis opbevaringspulje. På samme måde, når belastningsfaktoren falder under en anden tærskel r _min , flyttes alle poster til et nyt mindre bord.

For hashtabeller, der krymper og vokser ofte, kan størrelsen nedad springes helt over. I dette tilfælde er bordstørrelsen proportional med det maksimale antal poster, der nogensinde var i hashtabellen ad gangen, snarere end det aktuelle nummer. Ulempen er, at hukommelsesforbruget vil være højere, og dermed kan cacheadfærd være værre. For den bedste kontrol kan der leveres en "krymp-til-pas" -operation, der kun gør dette efter anmodning.

Hvis bordstørrelsen stiger eller falder med en fast procentdel ved hver udvidelse, er de samlede omkostninger ved disse størrelser, amortiseret over alle indsætnings- og sletningsoperationer, stadig en konstant, uafhængig af antallet af poster n og af antallet m udførte operationer .

Overvej f.eks. En tabel, der blev oprettet med den mindst mulige størrelse og fordobles hver gang belastningsforholdet overstiger en eller anden tærskel. Hvis der indsættes m- elementer i tabellen, er det samlede antal ekstra genindsættelser, der forekommer i alle dynamiske resizings i tabellen, højst m -1. Med andre ord fordobler dynamisk størrelse stort set omkostningerne ved hver indsættelse eller sletning.

Alternativer til genopfriskning på én gang

Nogle hashtabelimplementeringer, især i realtidssystemer , kan ikke betale prisen for at forstørre hashtabellen på én gang, fordi det kan afbryde tidskritiske operationer. Hvis man ikke kan undgå dynamisk størrelse, er en løsning at udføre størrelsen gradvist.

Diskbaserede hashtabeller bruger næsten altid et eller andet alternativ til at genoprette alt på én gang, da omkostningerne ved at genopbygge hele tabellen på disken ville være for høje.

Stigende størrelse

Et alternativ til at forstørre bordet på én gang er at udføre genopfriskningen gradvist:

Under tilpasningen skal du tildele den nye hashtabel, men beholde den gamle tabel uændret.
Kontroller begge tabeller i hver opslag eller sletning.
Udfør kun indsættelsesoperationer i den nye tabel.
Ved hver indsættelse flyttes også r -elementer fra det gamle bord til det nye bord.
Når alle elementer er fjernet fra den gamle tabel, skal du lokalisere den.

For at sikre, at det gamle bord kopieres fuldstændigt, før det nye bord selv skal forstørres, er det nødvendigt at øge bordets størrelse med en faktor på mindst ( r + 1)/ r under størrelse.

Monotone nøgler

Hvis det er kendt, at nøgler vil blive gemt i monotonisk stigende (eller faldende) rækkefølge, kan der opnås en variation af konsekvent hash .

Givet nogle indledende nøgle $k 1$ , en efterfølgende nøgle $k jeg$ opdeler den centrale domæne $[k 1, \infty)$ i sæt ${[k 1, k i), [k i, \infty)$ }. Generelt giver gentagelse af denne proces en finere partition ${[k 1, k i 0), [k i 0, k i 1), ..., [k i n - 1, k i n), [k i n, \infty)$ } for en række sekvenser af monotonisk stigende nøgler $(k i 0, ..., k i n)$ , hvor $n$ er antallet af forfininger . Den samme proces gælder mutatis mutandis for monotont faldende nøgler. Ved at tildele hver delinterval af denne partition en anden hashfunktion eller hashtabel (eller begge) og ved at forfine partitionen, når hashtabellen ændres, garanterer denne tilgang, at enhver nøgles hash, når den er udstedt, aldrig ændres, selv når hashbordet er vokset.

Da det er almindeligt at vokse det samlede antal poster ved at fordoble, vil der kun være O (log ( N )) subintervaller, der skal kontrolleres, og binær søgetid for omdirigering vil være O (log (log ( N ))).

Lineær hashing

Lineær hash er en hashtabelalgoritme, der tillader inkrementel hashtabeludvidelse. Det implementeres ved hjælp af en enkelt hashtabel, men med to mulige opslagsfunktioner.

Hashing for distribuerede hashtabeller

En anden måde at reducere omkostningerne ved tabellens størrelse på er at vælge en hash -funktion på en sådan måde, at hashes af de fleste værdier ikke ændres, når tabellen ændres i størrelse. Sådanne hashfunktioner er udbredt i diskbaserede og distribuerede hashtabeller , hvor genopkald er uoverkommeligt dyrt. Problemet med at designe en hash, så de fleste værdier ikke ændres, når tabellen ændres, kaldes det distribuerede hashtabelproblem . De fire mest populære tilgange er rendezvous hash , konsekvent hash , indholdsadresserbar netværksalgoritme og Kademlia -afstand.

Ydeevne

Hastighedsanalyse

I den enkleste model er hashfunktionen helt uspecificeret, og tabellen ændrer ikke størrelsen. Med en ideel hashfunktion har en størrelsestabel med åben adressering ingen kollisioner og holder op til elementer med en enkelt sammenligning for vellykket opslag, mens en tabel med størrelse med kæde og nøgler har minimumskollisioner og sammenligninger for opslag. Med den værst mulige hashfunktion forårsager hver indsættelse et sammenstød, og hashtabeller degenererer til lineær søgning med amortiserede sammenligninger pr. Indsættelse og op til sammenligninger for et vellykket opslag. ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle k}$ ${\ displaystyle n}$ ${\ displaystyle \ max (0, nk)}$ ${\ displaystyle \ Theta ({\ frac {n} {k}})}$ ${\ displaystyle \ Theta (n)}$ ${\ displaystyle n}$

Tilføjelse af rehashing til denne model er ligetil. Som i et dynamisk array indebærer geometrisk størrelse ved hjælp af en faktor, at kun nøgler indsættes eller flere gange, så det samlede antal indsættelser er afgrænset ovenfor af , hvilket er . Ved at bruge rehashing til at vedligeholde kan tabeller, der bruger både kæde og åben adressering, have ubegrænsede elementer og udføre vellykket opslag i en enkelt sammenligning for det bedste valg af hash -funktion. ${\ displaystyle b}$ ${\ displaystyle {\ frac {n} {b^{i}}}}$ ${\ displaystyle i}$ ${\ displaystyle {\ frac {bn} {b-1}}}$ ${\ displaystyle \ Theta (n)}$ ${\ displaystyle n <k}$

I mere realistiske modeller er hashfunktionen en tilfældig variabel over en sandsynlighedsfordeling af hashfunktioner, og ydelsen beregnes i gennemsnit over valget af hashfunktion. Når denne fordeling er ensartet , kaldes antagelsen "simpel ensartet hashing", og det kan påvises, at hashing med kæde kræver gennemsnitlige sammenligninger for et mislykket opslag, og hashing med åben adressering kræver . Begge disse grænser er konstante, hvis vi opretholder ' ved hjælp af tabelstørrelse, hvor er en fast konstant mindre end 1. ${\ displaystyle \ Theta \ venstre (1+{\ frac {n} {k}} \ højre)}$ ${\ displaystyle \ Theta \ venstre ({\ frac {1} {1-n/k}} \ højre)}$ ${\ displaystyle {\ frac {n} {k}} <c}$ ${\ displaystyle c}$

To faktorer påvirker betydeligt latensen af operationer på et hashtabel:

Cachen mangler. Med stigende belastningsfaktor kan søge- og indsættelsesydelsen for hashtabeller forringes meget på grund af stigningen i den gennemsnitlige cache, der mangler.
Omkostninger ved at ændre størrelse. Ændring af størrelse bliver en ekstrem tidskrævende opgave, når hashtabeller vokser massive.

I latensfølsomme programmer skal tidsforbruget af operationer i både gennemsnittet og de værste tilfælde være lille, stabilt og endda forudsigeligt. K hash-tabellen er designet til et generelt scenario med applikationer med lav latens, der sigter mod at opnå omkostningstabile operationer på et voksende bord i stor størrelse.

Hukommelsesudnyttelse

Nogle gange skal hukommelseskravet til et bord minimeres. En måde at reducere hukommelsesforbruget i kædemetoder er at fjerne nogle af kædepegene eller at erstatte dem med en eller anden form for forkortede pointer.

En anden teknik blev introduceret af Donald Knuth, hvor den kaldes forkortede nøgler . (Bender et al. Skrev, at Knuth kaldte det kvotientering .) For denne diskussion antages det, at nøglen eller en reversibelt hash-version af denne nøgle er et helt tal m fra {0, 1, 2, ..., M-1 } og antallet af skovle er N . m er divideret med N for at producere en kvotient q og en rest r . Resten r bruges til at vælge spanden; i spanden skal kun kvoten q opbevares. Dette gemmer log ₂ (N) bits pr. Element, hvilket kan være vigtigt i nogle applikationer.

Kvotering fungerer let med at kæde hashborde eller med enkle gøg -hash -borde. For at anvende teknikken med almindelige open-addressing hashtabeller introducerede John G. Cleary en metode, hvor to bits (en jomfrubit og en ændringsbit ) er inkluderet i hver spand, så det originale skovlindeks ( r ) kan rekonstrueres.

I det netop beskrevne skema bruges log ₂ (M/N) + 2 bits til at gemme hver nøgle. Det er interessant at bemærke, at den teoretiske minimumslagring ville være log ₂ (M/N) + 1,4427 bits, hvor 1,4427 = log ₂ (e).

Funktioner

Fordele

Den største fordel ved hashtabeller frem for andre borddatastrukturer er hastighed. Denne fordel er mere tydelig, når antallet af poster er stort. Hashtabeller er særligt effektive, når det maksimale antal poster kan forudsiges, så bucket -arrayet kan tildeles en gang med den optimale størrelse og aldrig ændre størrelsen.
Hvis sættet med nøgle -værdipar er fast og kendt på forhånd (så indsættelser og sletninger ikke er tilladt), kan man reducere de gennemsnitlige opslagsomkostninger ved et omhyggeligt valg af hash -funktionen, bucket -bordstørrelse og interne datastrukturer. Især kan man være i stand til at udtænke en hashfunktion, der er kollisionsfri eller endda perfekt. I dette tilfælde behøver nøglerne ikke at blive gemt i tabellen.

Ulemper

Selvom operationer på et hashtabel i gennemsnit tager konstant tid, kan omkostningerne ved en god hash -funktion være betydeligt højere end opslagsalgoritmens indre sløjfe for en sekventiel liste eller søgetræ. Således er hashtabeller ikke effektive, når antallet af poster er meget lille. (I nogle tilfælde kan de høje omkostninger ved at beregne hashfunktionen dog reduceres ved at gemme hashværdien sammen med nøglen.)
For visse strengbehandlingsapplikationer, f.eks. Stavekontrol , kan hashtabeller være mindre effektive end forsøg , endelige automater eller Judy-arrays . Hvis der ikke er for mange mulige nøgler til at gemme - det vil sige, hvis hver nøgle kan repræsenteres af et lille nok antal bits - så kan man i stedet for en hashtabel bruge nøglen direkte som indeks i en matrix af værdier. Bemærk, at der ikke er nogen kollisioner i dette tilfælde.
De poster, der er gemt i en hashtabel, kan opregnes effektivt (til konstant pris pr. Post), men kun i en vis pseudo-tilfældig rækkefølge. Derfor er der ingen effektiv måde at lokalisere en post, hvis nøgle er tættest på en given nøgle. At liste alle n -poster i en bestemt rækkefølge kræver generelt et separat sorteringstrin, hvis pris er proportional med log ( n ) pr. Post. Til sammenligning har bestilte søgetræer opslag og indsættelsesomkostninger, der er proportionelle med log ( n ), men gør det muligt at finde den nærmeste nøgle til omtrent samme pris og ordnet optælling af alle poster til konstant pris pr. Post. Imidlertid kan en LinkingHashMap laves for at oprette en hashtabel med en ikke-tilfældig sekvens.
Hvis nøglerne ikke er gemt (fordi hash-funktionen er kollisionsfri), er der muligvis ingen nem måde at opregne de nøgler, der er til stede i tabellen på et givet tidspunkt.
Selvom den gennemsnitlige pris pr. Operation er konstant og temmelig lille, kan omkostningerne ved en enkelt operation være ret høje. Især hvis hashtabellen anvender dynamisk størrelse , kan en indsætning eller sletning lejlighedsvis tage tid, der er proportional med antallet af poster. Dette kan være en alvorlig ulempe i realtid eller interaktive applikationer.
Hashtabeller udviser generelt dårlig lokalitet - det vil sige, at de data, der skal tilgås, distribueres tilsyneladende tilfældigt i hukommelsen. Fordi hashtabeller forårsager adgangsmønstre, der springer rundt, kan dette udløse mikroprocessor -cachefejl, der forårsager lange forsinkelser. Kompakte datastrukturer, f.eks. Arrays, der søges med lineær søgning, kan være hurtigere, hvis tabellen er relativt lille, og nøglerne er kompakte. Det optimale ydelsespunkt varierer fra system til system.
Hashtabeller bliver ret ineffektive, når der er mange kollisioner. Selvom ekstremt ujævne hashfordelinger ekstremt usandsynligt vil opstå ved en tilfældighed, kan en ondsindet modstander med kendskab til hashfunktionen muligvis levere information til en hash, der skaber værste adfærd ved at forårsage overdrevne kollisioner, hvilket resulterer i meget dårlig ydeevne, f.eks. et denial of service -angreb . I kritiske applikationer kan en datastruktur med bedre værst tænkelige garantier bruges; imidlertid universel hashing eller en indtastet hashfunktion kan, som begge forhindrer angriberen fra forudsige, hvilke indgange forårsager worst case adfærd, være at foretrække.
- Den hashfunktion, der blev brugt af hashtabellen i Linux -routingtabelcachen, blev ændret med Linux -version 2.4.2 som modforanstaltning mod sådanne angreb. Den ad-hoc -tastede hashkonstruktion blev senere opdateret til at bruge en "jhash" og derefter SipHash .

Anvendelser

Associative arrays

Hashtabeller bruges ofte til at implementere mange typer in-memory-tabeller. De bruges til at implementere associative arrays (arrays, hvis indekser er vilkårlige strenge eller andre komplicerede objekter), især i fortolkede programmeringssprog som Ruby , Python og PHP .

Når en ny vare gemmes i et multimap, og der opstår en hashkollision, gemmer multimap ubetinget begge varer.

Når du gemmer et nyt element i et typisk associativt array, og der opstår en hashkollision, men de faktiske nøgler i sig selv er forskellige, gemmer det associative array ligeledes begge elementer. Men hvis nøglen til det nye element nøjagtigt matcher nøglen til et gammelt element, sletter det associerede array typisk det gamle element og overskriver det med det nye element, så hvert element i tabellen har en unik nøgle.

Databaseindeksering

Hashtabeller kan også bruges som diskbaserede datastrukturer og databaseindeks (f.eks. I dbm ), selvom B -træer er mere populære i disse applikationer. I multi-node databasesystemer bruges hashtabeller sædvanligvis til at distribuere rækker mellem noder, hvilket reducerer netværkstrafik for hash joins .

Cacher

Hashtabeller kan bruges til at implementere caches , hjælpedatatabeller, der bruges til at fremskynde adgangen til data, der primært er lagret i langsommere medier. I denne applikation kan hashkollisioner håndteres ved at kassere en af de to kolliderende poster - normalt slette det gamle element, der aktuelt er gemt i tabellen, og overskrive det med det nye element, så hvert element i tabellen har en unik hashværdi.

Sæt

Udover at gendanne posten, der har en given nøgle, kan mange hashtabelimplementeringer også fortælle, om en sådan post findes eller ej.

Disse strukturer kan derfor bruges til at implementere en sæt datastruktur , der blot registrerer, om en given nøgle tilhører et bestemt sæt nøgler. I dette tilfælde kan strukturen forenkles ved at fjerne alle dele, der har at gøre med indtastningsværdierne. Hashing kan bruges til at implementere både statiske og dynamiske sæt.

Objektrepræsentation

Flere dynamiske sprog, såsom Perl , Python , JavaScript , Lua og Ruby , bruger hashtabeller til at implementere objekter . I denne repræsentation er nøglerne navnene på objektets medlemmer og metoder, og værdierne er pejlemærker til det tilsvarende medlem eller den tilsvarende metode.

Unik datarepræsentation

Hashtabeller kan bruges af nogle programmer for at undgå at oprette flere tegnstrenge med det samme indhold. Til dette formål, er alle strengene i brug af programmet er lagret i en enkelt snor pulje implementeret som en hash tabel, som kontrolleres, hver gang en ny streng skal oprettes. Denne teknik blev introduceret i Lisp tolke under navnet hash consing , og kan bruges med mange andre former for data ( udtryk træer i et symbolsk algebra -system, poster i en database, filer i et filsystem, binært beslutningsdiagram, etc.) .

Transpositionstabel

En transponeringstabel til en kompleks hashtabel, der gemmer oplysninger om hver sektion, der er blevet søgt efter.

Implementeringer

I programmeringssprog

Mange programmeringssprog giver hashtabel funktionalitet, enten som indbygget associative arrays eller som standard bibliotek moduler. I C ++ 11unordered_map giver klassen for eksempel hashtabeller til nøgler og værdier af vilkårlig type.

Den Java- programmeringssproget (herunder variant, som bruges på Android ) omfatter HashSet, HashMap, LinkedHashSetog LinkedHashMap generiske samlinger.

I PHP 5 og 7 bruger Zend 2 -motoren og Zend 3 -motoren (henholdsvis) en af hashfunktionerne fra Daniel J. Bernstein til at generere de hashværdier, der bruges til at styre kortlægninger af datapunkter, der er gemt i en hashtabel. I PHP -kildekoden er den mærket som DJBX33A(Daniel J. Bernstein, Times 33 with Addition).

Pythons indbyggede hashtabelimplementering i form af dicttypen samt Perls hashtype (%) bruges internt til at implementere navnerum og skal derfor være mere opmærksom på sikkerhed, dvs. kollisionsangreb. Python -apparater bruger også hashes internt, for hurtig opslag (selvom de gemmer kun nøgler, ikke værdier). CPython 3.6+ bruger en indsættelsesordnet variant af hashtabellen, implementeret ved at opdele værdilagringen i et array og få vanilje-hashtabellen til kun at gemme et sæt indekser.

I .NET Framework ydes der understøttelse af hashtabeller via de ikke-generiske Hashtableog generiske Dictionaryklasser, der gemmer nøgle-værdipar , og den generiske HashSetklasse, der kun gemmer værdier.

I Ruby bruger hashtabellen den åbne adressemodel fra Ruby 2.4 og fremefter.

I Rusts standardbibliotek bruger generikken HashMapog HashSetstrukturen lineær sondering med Robin Hood spandstjæling.

ANSI Smalltalk definerer klasserne Set/ IdentitySetog Dictionary/ IdentityDictionary. Alle Smalltalk implementeringer give yderligere (endnu ikke standardiseret) versioner af WeakSet, WeakKeyDictionaryog WeakValueDictionary.

Tcl -array -variabler er hashtabeller, og Tcl -ordbøger er uforanderlige værdier baseret på hash. Funktionaliteten er også tilgængelig som C -biblioteksfunktioner Tcl_InitHashTable et al. (for generiske hashtabeller) og Tcl_NewDictObj et al. (for ordbogsværdier). Ydeevnen er uafhængigt blevet benchmarket som ekstremt konkurrencedygtig.

Den Wolfram Sprog understøtter hash tabeller siden version 10. De er implementeret under navnet Association.

Common Lisp leverer hash-tableklassen til effektive kortlægninger. På trods af dens navngivning foreskriver sprogstandarden ikke den faktiske overholdelse af nogen hash -teknik til implementeringer.

Historie

Ideen om hashing opstod uafhængigt forskellige steder. I januar 1953 skrev Hans Peter Luhn et internt IBM -memorandum, der brugte hashing med kæde. Gene Amdahl , Elaine M. McGraw , Nathaniel Rochester og Arthur Samuel implementerede et program ved hjælp af hash på omtrent samme tid. Åben adressering med lineær sondering (relativt primær trin) krediteres Amdahl, men Ershov (i Rusland) havde den samme idé.

Se også

Relaterede datastrukturer

Der er flere datastrukturer, der bruger hashfunktioner, men kan ikke betragtes som særlige tilfælde af hashtabeller:

Bloom-filter , en hukommelseseffektiv datastruktur designet til omtrentlige opslag i konstant tid; bruger hash -funktion (er) og kan ses som en omtrentlig hashtabel.
Distribueret hashtabel (DHT), en elastisk dynamisk tabel spredt over flere noder i et netværk.
Hash -array kortlagt trie , en trie -struktur, der ligner array -mapped trie , men hvor hver nøgle først er hash.

Referencer

Yderligere læsning

Tamassia, Roberto; Goodrich, Michael T. (2006). "Kapitel ni: Kort og ordbøger". Datastrukturer og algoritmer i Java: [opdateret til Java 5.0] (4. udgave). Hoboken, NJ: Wiley. s. 369 –418. ISBN 978-0-471-73884-8.
McKenzie, BJ; Harries, R .; Bell, T. (februar 1990). "Valg af en hash -algoritme". Software praksis og erfaring . 20 (2): 209–224. doi : 10.1002/spe.4380200207 . HDL : 10092/9691 . S2CID 12854386 .

eksterne links

En hash -funktion til hash -tabelopslag af Bob Jenkins.
Hash -funktioner af Paul Hsieh
Design af kompakte og effektive hashtabeller til Java
NIST -indtastning på hashborde
Foredrag om hashtabeller fra Stanfords CS106A
Åbn datastrukturer - Kapitel 5 - Hashtabeller , Pat Morin
MIT's Introduction to Algorithms: Hashing 1 MIT OCW foredrag Video
MIT's Introduction to Algorithms: Hashing 2 MIT OCW forelæsningsvideo

Languages

In other projects