Hashing

Et map, eller en mapping, er en abstrakt datatype. Helt generelt assosierer en nøkkel \(k\) med nøyaktig én verdi \(v\).

Den abstrakte datatypen for map krever at vi kan sette inn, slå opp og slette elementer. Dette kan oppnås med lineær tid på alle operasjoner dersom vi implementerer et map ved hjelp av ordinære lenkede lister, der hvert element i listen er et par \((k, v)\). Vi har sett at binære søketrær kan gi oss logaritmisk tid på samtlige operasjoner, dersom vi antar at nøklene er totalt ordnet. Ved hjelp av hashing kan vi gjøre disse operasjonene enda raskere.

Det er verdt å merke seg at vi kan implementere mengder som maps, der hver nøkkel mapper til en vilkårlig verdi (for eksempel null).

En funksjon returner samme output for et gitt input hver gang.¹ En hashfunksjon \(h\) får en nøkkel \(k\) og et positivt heltall \(N\) som input, og returnerer et positivt heltall slik at \(0 \leq h(k, N) < N\). Kravene til denne funksjonen er:

• Den må være konsistent (altså være en funksjon). Det vil si at samme input gir alltid samme output.
• Den må gi få kollisjoner (altså være godt distribuert). Det vil si at ulike input bør hashe til ulike output så ofte som mulig.

Det vi ønsker er en funksjon som oppfører seg tilsynelatende tilfeldig (altså som et kall på random), men som garanterer samme svar hver gang. Ulike datastrukturer kan trenge egne hashfunksjoner. For heltall er det ganske enkelt; et tall hasher til seg selv. For strenger må vi tenke litt hardere.

Den overordnede idéen for å implementere en hashmap er å la hashmapet være representert som et array \(A\) av størrelse \(N\), og bruke en hashfunksjon \(h(k, N)\) til å angi indeksen for en gitt nøkkel \(k\). Selv hvis vi lar \(N\) være mye større enn antall elementer \(n\) som er lagret i hashmapet, så vil det kunne oppstå kollisjoner (altså to nøkler som sogner til samme indeks). Vi skal se to måter å håndtere slike konflikter på. Den ene går ut på å la hver posisjon i arrayet peke til en liste av nøkkel- og verdipar \((k, v)\). Denne teknikken kalles «separate chaining». Den andre teknikken går ut på å først forsøke å plassere \((k, v)\) på indeksen som er gitt av hashfunksjonen; dersom det ikke er ledig på den plassen, så prøver vi neste plass, og neste helt frem til vi finner en ledig plass. Denne teknikken kalles «linear probing».

Felles for begge teknikkene er at effektiviteten blir svært dårlig dersom det oppstår mange kollisjoner. I det ekstreme (og helt usannsynlige) tilfellet der alle nøkler hasher til samme posisjon, så får vi lineær tid på alle operasjoner. Dette håndteres ved å sørge for at det til enhver tid er godt med plass i arrayet. Hvis \(n\) er antall elementer som lagres, og \(N\) er størrelsen på arrayet, så gir \(\frac{n}{N}\) det vi kaller en load factor. En vanlig strategi for å sørge for at det alltid er godt med plass er å doble størrelsen på arrayet når \(\frac{n}{N}\) overstiger \(0.75\).

Vi kan lage en klasse MyMap som inneholder oppførselen som er felles for begge varianter. Den eksponerer en metode ensurecapacity, som dobler størrelsen på arrayet dersom det er for fullt. En slik størrelsesendring kalles en rehash, fordi alle nøkler må hashes på nytt med hensyn til en større \(N\), og plasseres tilbake i arrayet.

class MyMap:
    LOAD_FACTOR_THRESHOLD = 0.75

    def __init__(self):
        self.n = 0
        self.N = 1
        self.A = [None] * self.N

    def __loadfactor(self):
        return self.n / self.N

    def __rehash(self):
        kvs = [(k, v) for k, v in self]
        self.n = 0
        self.N *= 2
        self.A = [None] * self.N
        for k, v in kvs:
            self[k] = v

    def ensurecapacity(self):
        if self.__loadfactor() >= self.LOAD_FACTOR_THRESHOLD:
            self.__rehash()

    def __repr__(self):
        kv_strs = [f'{k} ↦ {v}' for k, v in self]
        return '{' + ', '.join(kv_strs) + '}'

Merk at vi her antar at vi også implementerer en iterator for klassene som arver fra MyMap (i Java ville MyMap vært implementert som en abstrakt klasse, som hadde vært noe bedre objektorientert stil). Vi implementerer også __repr__, som får Python til å printe vår implementasjon av hashmap på et mer lesbart format.

I implementasjonene under vil vi bruke Python sin innebygde hashfunksjon hash, som fungerer på (nesten²) alle typer i Python, til fordel for de som ble implementert i forrige seksjon. Denne returnerer et tall uten hensyn til \(N\), så vi må selv ta modulo \(N\) av resultatet.

Husk at idéen er å la hver posisjon i arrayet peke til en liste, og plassere nøkkel-/​verdiparene i den listen. Lister i denne konteksten kalles ofte bøtter. I stedet for å opprette mange tomme lister, lar vi heller hver posisjon i arrayet peke på None, og opprette en liste ved behov. Dersom det allerede finnes en verdi med samme nøkkel, så skal vi erstatte verdien.

La oss lage et skall for et hashmap basert på separate chaining.

class SeparateChainingMap(MyMap):

    <<separate_chaining_insert>>


    <<separate_chaining_get>>


    <<separate_chaining_delete>>


    <<separate_chaining_iter>>

Syntaksen eksemplifisert ved <<separate_chaining_insert>> brukes som plassholder for kodeblokker vi skal skrive. Metodene kommer i de neste delseksjonene, og siste delseksjon for separate chaining inneholder den fulle implementasjonen.

Idéen bak linear probing er å se på \(i = h(k, N)\) som den ideelle posisjonen for en nøkkel \(k\), og hvis denne posisjonen er opptatt, så prøver vi neste posisjon \(i + 1 \mod N\), og så neste helt frem vi når en ledig posisjon. Merk at den siste posisjonen \(N - 1\) i arrayet sin neste er \(0\); vi modulo \(N\) for å alltid sørge for at vi holder oss innenfor grensene av arrayet. Når vi skal hente ut en verdi med nøkkel \(k\) vil vi igjen starte å lete på posisjonen \(i = h(k, N)\). Dersom vi finner et nøkkel-/verdipar med \(k\) som nøkkel kan vi returnere verdien \(v\). Dersom plassen er ledig kan vi konkludere med at nøkkelen ikke er i hashmapet. Dersom vi finner en nøkkel som er ulik \(k\), så kan vi lete videre på neste plass, og fortsette slik frem til vi finner \(k\) (og i så fall returnerer verdien) eller vi finner en ledig plass, og i så fall konkludere med at nøkkelen ikke er i hashmapet.

Både insetting og oppslag er egentlig ganske rett frem med linear probing. Strategien med å starte på plass \(i = h(k, N)\) og lete etter neste frem til vi finner \(k\) eller en ledig plass er i grunn litt naiv. Det fungerer fordi at den eneste grunnen til at \(k\) ligger på en plass etter \(i\) er at det allerede lå en verdi på plass \(i\) da \(k\) ble lagt til; hvis de elementene som lå mellom \(i\) og der \(k\) ble lagt til fremdeles ligger der når vi skal søke etter \(k\), så fungerer alt som det skal. Et problem oppstår dersom vi skulle fjerne verdien som ligger på plass \(i\); da vil et oppslag på \(k\) avslutte, fordi plass \(i\) er ledig. Det betyr at ved sletting, så er vi nødt til å tette eventuelle «hull» som oppstår ved å fjerne et element. Vi ønsker å tette hullet med det første nøkkel-/​verdiparene etter \(i\) som ville blitt plassert på plass \(i\) dersom det ble plassert i hashmapet nå som plass \(i\) er ledig. Det er nøyaktig de nøklene som \(k\) som hasher til en posisjon \(i\) eller «tidligere». Vi vil konkretisere hva «tidligere» betyr når vi jobber med modulo \(N\) i delseksjonen om sletting nedenfor.

Denne interaktive visualiseringen kan hjelpe for å bygge intuisjon for algoritmene for linear probing. Kort bruker-guide:

• Implementasjonen viser et hashset (altså lagrer vi kun nøkler, og ikke verdier).
• Nøklene er heltall.
• Hashfunksjonen som brukes er \(h(k, N) = k \mod N\).
• Feltet random kan overskrives med et heltall.
• Hver knapp operasjon har en én-bokstavs keybinding, indikert med en u​nderstrek under bokstaven det gjelder.

La oss igjen lage et skall for et hashmap basert på linear probing. Den også arver fra MyMap.

class LinearProbingMap(MyMap):

    <<linear_probing_insert>>


    <<linear_probing_get>>


    <<linear_probing_delete>>


    <<linear_probing_fill_hole>>


    <<linear_probing_iter>>

Testing er ikke en del av pensum i IN2010, og denne seksjonen er mest for de spesielt interesserte.

For å teste hashmapimpementasjonene, kan vi bruke et bibliotek som heter Hypothesis. I stedet for å skrive mange tester for hånd, der vi prøver å finne på mulige grensetilfeller, kan vi bruke Hypothesis til å generere tester for oss. Dette kalles «property-based testing». Våre hashmapimpementasjoner kan testes opp mot Python's innebygde dict siden de skal støtte de samme operasjonene.

For hashmap ligger alle utfordringene i hvordan nøklene behandles. Verdiene som lagres sammen med nøkkelen spiller ingen rolle for algoritmene, og derfor er det logikken rund nøklene som har behov for testing.

Vi setter opp et enkelt testscenario:

• Ta en liste med nøkler som input, der nøklene er heltall.
• Sett inn hver nøkkel i hashmapet med verdi \(1\) (valgt vilkårlig).
• Slett hver hver nøkkel fra hashmapet.

Vi gjør dette for en SeparateChainingMap, en LinearProbingMap og en dict. Mellom hvert steg sjekker vi at alle hashmapene inneholder de samme nøklene.

import hypothesis as hyp
import hypothesis.strategies as st

@hyp.given(st.lists(st.integers()))
@hyp.settings(max_examples=1000)
def test_hashmaps(keys):
    ds = SeparateChainingMap()
    dl = LinearProbingMap()
    reference = dict()

    for key in keys:
        ds[key] = 1
        dl[key] = 1
        reference[key] = 1
        ds_ks = set(k for k, v in ds)
        dl_ks = set(k for k, v in dl)
        reference_ks = set(reference.keys())
        assert ds_ks == dl_ks == reference_ks

    for key in keys:
        del ds[key]
        del dl[key]
        if key in reference_ks:
            del reference[key]
        ds_ks = set(k for k, v in ds)
        dl_ks = set(k for k, v in dl)
        reference_ks = set(reference.keys())
        assert ds_ks == dl_ks == reference_ks

Etter vi har definert denne testfunksjonen (med litt Hypothesis-magi), får vi en randomisert testfunksjon test_hashmaps. Når vi kaller på denne vil den generere 1000 tester, som er langt flere enn vi ville klart å skrive for hånd.

test_hashmaps()

Hvis funksjonen kjører uten å klage, så betyr det at det ikke ble funnet noe feil. Da kan vi være langt mer sikre på at denne implementasjonen er korrekt!

Det er viktig å legge til at første gang koden ble testet, så ble det funnet et moteksempel. Hypothesis genererte listen [0, 1, 4] som trigget en feil i __fill_hole i linear probing. Feilen lå på siste linje, der i ble inkrementert i stedet for s. Slike feil er fort gjort, og ikke alltid så lett å finne. En ofte større utfordring er å finne en liten test som trigger feilen. Hypothesis bruker strategier for å finne et så lite eksempel som mulig.

Ved å gjøre en ordinær kjøretidsanalyse vil vi se på hvor mange steg algoritmene vil bruke under verst tenkelige omstendigheter (altså, en verste tilfelle analyse). Hvis vi gjør det for separate chaining og linear probing, så er det ganske enkelt å se at alle operasjoner har \(O(n)\) kjøretid, der \(n\) er antall elementer i datastrukturen. Det er tilstrekkelig å anta at alle \(n\) elementer hasher til samme posisjon; for separate chaining vil det bety at vi essesielt har implementert hashmaps som en lenket liste; for linear probing betyr det at vi essensielt har implementert et hashmap som et uordnet array (som dynamisk øker størrelsen på arrayet ved behov).

Allikevel påstår vi at hashmaps er en svært effektiv implementasjon av mappinger (og mengder). Den eneste måten det kan stemme på er at en verste tilfelle analyse med store \(O\)-notasjon ikke alltid gir et fullstendig bilde. Det har vi også prøvd å formidle: Store \(O\)-notasjon gir ofte en god indikasjon på om en algoritme er effektiv eller ikke, men notasjonen lar oss også abstrahere vekk detaljer som kan være vesentlige.

For å gjøre en formell analyse av datastrukturer som bruker hashing snakker man ofte om forventet amortisert tid. Å utføre formelle analyser som dette er utenfor pensum i IN2010, men vi skal nå en forståelse av hva det betyr på et overordnet nivå.

Det verste tilfellet for alle operasjoner kan lett fremprovoseres ved å velge en forferdelig dårlig hashfunksjon; det kan også fremprovoseres med en god hashfunksjon og helt vanvittig uflaks. Men vi har sett at vi kan lage hashfunksjoner som distribuerer svært godt, så la oss heller anta at vi har en god hashfunksjon og at nøklene vi skal lagre er tilfeldig distribuert.

Da har vi at sjansen for at en nøkkel \(k\) hasher til \(i\) er \(\frac{1}{N}\) (altså er det like stor sjanse for at \(k\) hasher til \(i\) som til alle andre posisjoner). Sjansen for at vi har mange nøkler \(k_1, k_2, \dots, k_n\) som alle hasher til \(i\) blir \(\overbrace{\frac{1}{N} \cdot \frac{1}{N} \cdots \frac{1}{N}}^n = (\frac{1}{N})^n\). Dette tallet blir veldig lite veldig fort, som er en annen måte å si at sjansen for at dette skjer er forsvinnende liten.

Generelt så er sjansen for kollisjoner liten så lenge det er god plass i arrayet; ethvert som arrayet fylles opp, så er sjansen for kollisjon stor, men sjansen for at kollisjonene oppstår på de samme posisjonene er fremdeles liten. Med andre ord kan vi bruke statistiske metoder for å gi svært gode argumenter for at listene i separate chaining vil være svært korte, og for linear probing er avstanden mellom der en nøkkel hashes til og posisjonen den lagres på er svært kort (og reduseres til en konstant hvis setter en begrensning på load factoren). Det siste som gjenstår for å forstå hvorfor hashmaps er raske, er å snakke om rehashing.

Når arrayet blir for fullt gjør vi en rehash, altså konstruerer et nytt array og setter inn alle elementene på nytt. Dette er jo definitivt lineær tid! Det er ingen måte å argumentere for at vi kan slippe unna med noe lavere enn det. Siden vi vil ha kall på insert som bruker lineær tid, vil igjen en verste tilfelle analyse tilsi at innsetting i hashmaps er i \(O(n)\).

En amortisert analyse ber deg heller ta følgende perspektiv: Ja, vi har et lineært antall operasjoner som må gjøres hver gang arrayet blir dobblet så stort. Anta nå at det krever \(c \cdot n\) operasjoner for en rehashing, der \(c\) er en konstant. Men hva hvis vi heller sier at hvert av kallene som ledet opp til fordoblingen deler på resursene som brukes på å gjennomføre en rehash. Det er ca. \(n\) kall på insert som ledet til fordoblingen, så hva hvis hvert av de kallene gjorde \(c\) flere operasjoner enn de opprinnelig gjorde? Jo, da hadde de gjort et konstant antall flere operasjoner, og fra store \(O\) analyse kjenner vi at \(O(1 + c) = O(1)\) når \(c\) er en konstant. Altså vil hvert av kallene på insert fremdeles være i konstant tid!

En viktig konsekvens av dette er at en innsetting i et hashmap vil være ineffektiv en sjelden gang, og det blir sjeldnere og sjeldnere ettersom antall elementer vokser. For noen applikasjoner kan dette være vesentlig; i et spill for eksempel, kan en rehash kan føre til at ting stopper opp i et lite øyeblikk. I slike settinger kan det kanskje være bedre å heller bruke en trestruktur (som AVL eller rød-svarte trær), som kanskje er tregere i sum, men er til gjengjeld jevn.

For å oppsummere kan vi si at alle operasjoner for hashmaps har \(O(n)\) i en verste tilfelle kjøretidsanalyse. Men ved å anta en god hashfunsjon får vi at gjennomsnittlig er hver operasjon i \(O(1)\), med unntak av kall som fører til rehashing. Hvis vi videre tenker at vi kan fordele ressursbruken på alle kallene som leder til en rehashing, så får vi gjennomsnittlig \(O(1)\) amortisert kjøretidskompleksitet på alle operasjoner.