Mål	Läs i kursboken
Hashning	6.5. Hashing

Idag:

Pythons dictionary
Idén med hashning
Komplexiteten för sökning
Dimensionering av hashtabellen
Hashfunktionen
Krockhantering
Klassen Hashtable
Användningsaspekter
Hashning i Språkteknologi

Pythons dictionary

Med Pythons inbyggda dictionary har man möjlighet att skapa en uppslagslista. Man bygger upp den genom att lägga in nycklar och tillhörande värden:

  telefonnummer={}
  telefonnummer["Linda Kann"] = "08-7909276"
  telefonnummer["CSC-service"] = "08-790 7146"
  ---

Sedan kan man slå upp i listan:

   namn = input("Vem vill du ringa till? ")
   try:
       print("Telefonnumret är ", telefonnummer[namn])
   except KeyError:
       print(namn,"finns inte med i telefonlistan")

Här är det varken linjärsökning eller binärsökning som används för att hitta nyckeln, utan en ännu snabbare sökmetod: hashning.

Idén med hashning

Binärsökning i en sorterad lista går visserligen snabbt, men sökning i en hashtabell är oöverträffat snabbt. Och ändå är tabellen helt oordnad (hash betyder ju hackmat, röra). Låt oss säga att vi söker efter Lyckan i en hashtabell av längd 10000. Då räknar vi först fram hashfunktionen för ordet Lyckan och det ger detta resultat.

   hash("Lyckan") -> 1076540772

Hashvärdets rest vid division med 10000 beräknas nu

   1076540772 % 10000 -> 772

och när vi kollar hashtabellens index 772 hittar vi Lyckan just där!

Hur kan detta vara möjligt? Ja, det är inte så konstigt egentligen. När Lyckan skulle läggas in i hashtabellen gjordes samma beräkning och det är därför hon lagts in just på 772. Hur hashfunktionen räknar fram sitt tal spelar just ingen roll. Huvudsaken är att det går fort, så att inte den tid man vinner på inbesparade jämförelser äts upp av beräkningstiden för hashfunktionen.

Komplexiteten för sökning

Linjär sökning i en oordnad lista av längd N tar i genomsnitt N/2 jämförelser, binär sökning i en sorterad lista log N men hashning går direkt på målet och kräver bara drygt en jämförelse. Varför drygt? Det beror på att det är svårt att undvika krockar, där två olika namn hamnar på samma index.

Dimensionering av hashtabellen

Ju större hashtabell man har, desto mindre blir risken för krockar. En tumregel är att man bör ha minst femtio procents luft i tabellen, dvs att

$λ = \frac{a n t a l i n l a g d a o b j e k t}{h a s h t a b e l l e n s s t o r l e k} = 0.5$

Då kommer krockarna att bli få.

Hashfunktioner

Oftast gäller det först att räkna om en sträng till ett stort tal. Funktionen ord(tkn) i Python konverterar ett tecken till motsvarande ordningsnummer.

T ex är
ord("A") = 65
ord("B") = 66
ord("C") = 67
Då kan vi räkna om strängen "ABC" till talet 656667, genom att multiplicera den första bokstaven med 10000, den andra med 100, den tredje med 1 och slutligen addera talen. På liknande sätt gör metoden hash(key) i Python men den använder 32 i stället för 100. För en binär dator är det nämligen mycket enklare att multiplicera med 32 än med 100. Här är en förenklad variant:

def hash2(s):
    result = 0
    for c in s:                    
        result = result*32 + ord(c) 
    return result

Om nyckeln är ett datum eller personnummer behöver vi inte konvertera till tal.

Man kan "vika" talet genom att dela upp det i lika stora delar som sedan summeras, t ex 20+17+09+11 = 57,
Eller kvadrera det:20170911² = 406865650569921 och plocka ut de mittersta siffrorna: 650.

En hashfunktion bör ha god spridning - vi vill inte att många nycklar ska ge samma hashvärde. Med programmet barchart.py med tillhörande datafil slumpnamn30.txt kan du experimentera med fördelningen för olika hashfunktioner.

Modulo

I kursen använder vi modulo för att få hashfunktionens tal att passa in i vektorn.

Exempel: Datum kan hashas in i hashtabellen med 20170911 % size

Krockhantering

En idé är att lägga alla namn som hashar till ett visst index som en länkad krocklista. Om man har femtio procents luft i sin hashtabell blir krocklistorna i regel mycket korta. Krocklistorna behandlas enklast som stackar, och hashtabellen innehåller då bara topp-pekarna till stackarna.

Linjär probning

En annan metod är att vid krock lägga noden på första lediga plats. Är det tomt där, tittar man på nästa, osv. Detta kallas linjär probning. En fördel med denna metod är att man slipper alla pekare. En stor nackdel är att om det börjat klumpa ihop sej någonstans har klumpen en benägenhet att växa. Detta kallas för klustring.

Kvadratisk probning

I stället för att leta lediga platser som ligger tätt ihop kan man därför göra större hopp. Hopplängden bör då variera. Ett sätt är att "hoppa fram" i jämna kvadrater, så kallad kvadratisk probning. Om hashfunktionen gav värdet h tittar man i ordning på platserna: h+1, h+4, h+9,h+2^4 ... . Överstiger värdena hashtabellens storlek använder man resten vid heltalsdivision precis som vid beräkningen av h. Om tabellstorleken är ett primtal. och tabellen är som mest halvfull, så riskerar man inte att fastna i en evig hopprunda.

Dubbelhashning

Ytterligare ett sätt att lösa krockproblemet är dubbelhashning. I denna variant räknas nästa värde fram med en annan hashfunktion som tar som indata den första hashfunktionens värde. För att hitta efterföljande platser låter man den andra hashfunktionen få sitt förra värde som indata.

Både kvadratisk probning och dubbelhashning ger goda prestanda om hashtabellen har femtio procent luft. En nackdel med båda metoderna är att man inte enkelt kan ta bort noder utan att förstöra hela systemet.

Klassen Hashtabell

I en senare laboration ska du implementera den abstrakta datastrukturen hashtabell genom att skriva en klass Hashtabell med operationerna put och get. Första parametern till put är söknyckeln, till exempel personens namn. Andra parametern är ett objekt med alla tänkbara data om personen. Metoden get har söknyckeln som indata och returnerar dataobjektet om nyckeln finns i hashtabellen, annars skickar vi ett särfall.

from hashtabell import Hashtabell, FannsInte
table = Hashtabell(7)
table.put("one",1)
table.put("two",2)
table.put("three",3)

kontrollord = "xxx"
while kontrollord != "":
    kontrollord = input("Ett engelskt räkneord:")
    try:
        print(table.get(kontrollord))
    except FannsInte:
        print(kontrollord, "fanns inte i hashtabellen")
	print("Försök igen!")

Hashtabellen ska åtminstone ha följande operationer:

put(key, data) Lägg in data med nyckeln key i hashtabellen.
data = get(key) Hämta data som hör till key.
f = hashfunction(key) Beräkna hashfunktionen för key.

Men man kan lägga till fler operationer, t ex __str__() för att skriva ut hashtabellen, __contains__(key) för att se om något finns lagrat med nyckeln key, __len__() för att få ut hashtabellens storlek mm.

Användningsaspekter

I nästan alla sammanhang där snabb sökning krävs är det hashtabeller som används. Krockar hanteras bäst med länkade listor, men i vissa programspråk är det svårt att spara länkade strukturer på fil, så därför är dubbelhashning fortfarande mycket använt i stora databaser.

I Ubuntu och andra UNIX-system skriver användaren namn på kommandon, program och filer och räknar med att datorn snabbt ska hitta dom. Vid inloggning byggs därför en hashtabell upp med alla sådana ord. Men under sessionens förlopp kan många nya ord tillkomma och dom läggs bara i en lista som söks linjärt. Så småningom kan det bli ganska långsamt, och då är det värt att ge kommandot rehash. Då tillverkas en ny större hashtabell där alla gamla och nya ord hashas in. Hur stor tabellen är för tillfället ger kommandot hashstat besked om.

Om man vill kunna söka dels på namn, dels på personnummer kan man ha en hashtabell för varje sökbegrepp, men det går också att ha en enda tabell. En viss person hashas då in med flera nycklar, men själva informationsnoden finns alltid bara i ett exemplar. Många noder i hashtabellen kan ju peka ut samma nod.

Hashning i Språkteknologi

Hashning används i många olika sammanhang. Här betraktar vi ett exempel från ämnesområdet Språkteknologi, dvs behandling av naturliga språk (mänskliga språk, till skillnad från tex programmeringsspråk) med datorer.

Stavningskontroll

Ett stavningskontrollprogram ska läsa en text och markera alla ord som är felstavade. Om man har tillgång till en ordlista som innehåller alla riktiga svenska ord kan man använda följande enkla algoritm för att stavningskontrollera en text.

Läs in ordlistan i en lämplig datastruktur.
Öppna textfilen.
Så länge filslut inte nåtts:

Läs in nästa ord från filen.
Slå upp ordet i ordlistan och skriv ut det på skärmen om det inte finns med.

Enda problemet är hur man ska välja datastruktur för lagring av ordlistan. Svenska akademiens ordlista innehåller ungefär 200000 ord. Förutom dessa ord finns en hel del böjningsformer och oändligt många tänkbara sammansättningar. Låt oss bortse från detta och anta att vi har köpt en ordlista med dom 200000 vanligaste orden i svenskan. Om vi snabbt ska kunna stavningskontrollera en stor text med en normal persondator måste följande krav på datastrukturen vara uppfyllda.

Uppslagning måste gå jättesnabbt.
Datastrukturen får inte ta så mycket minne (helst inte ens så mycket minne som orden i klartext).
Orden måste vara kodade (eftersom ordlistan är köpt och inte får spridas till andra).
Vi kan tillåta att uppslagningen gör fel någon gång ibland.

Den sista punkten är inte ett krav utan en egenskap hos vårt problem som vi kan utnyttja. Det är nämligen inte hela världen om programmet missar något enstaka felstavat ord i en jättestor text.

Vanliga datastrukturer (sorterad array, sökträd, hashtabell) faller alla på något av kraven ovan.

Försök med datastruktur: boolesk hashtabell

Låt oss först försöka med hashning där vi inte lagrar själva orden och inte tar hand om eventuella krockar. Vi har en hashfunktion f(ord)=index som för varje ord anger en position i en boolesk hashtabell tab. Den booleska variabeln tab[f(ord)] låter vi vara sann då ord ingår i ordlistan. Detta ger en snabb, minnessnål och kodad datastruktur, men den har en stor brist: Om det råkar bli så att hashfunktionen antar samma värde för ett ord i ordlistan som för ett felstavat ord så kommer det felstavade ordet att godkännas. Om hashtabellen exempelvis är fylld till häften med ettor så är sannolikheten för att ett felstavat ord ska godkännas ungefär 50% vilket är alldeles för mycket.

Bloomfilter

Lösningen är att använda många hashfunktioner som alla ger index i samma hashtabell tab. I Viggos stavningskontrollprogram Stava används till exempel 14 olika hashfunktioner f₀(ord),f₁(ord), f₂(ord),...,f₁₃(ord). Ett ord godkänns bara om alla dessa 14 hashfunktioner samtidigt ger index till platser itab som innehåller sant.

Uppslagning av ett ord kan då ske på följande sätt:

    for i in range(14):
       if not tab[f(i, ord)]: return False
    return True

Om hashtabellen är till hälften fylld med ettor blir sannolikheten för att ett felstavat ord godkänns så liten som (1/2)¹⁴=0.006%.

Denna datastruktur kallas bloomfilter efter en datalogiforskare vid namn Bloom. Ett abstrakt bloomfilter har bara två operationer: insert(x) som stoppar in x i datastrukturen och isIn(x) som kollar ifall x finns med i datastrukturen.