DD1320 Tillämpad Datalogi

Föreläsning 6: Hashning

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-7906292"
  telefonnummer["CSC-exp"] = "08-7908077"
  ---
Sedan kan man slå upp i listan: 
   namn = raw_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 femtio procents luft i tabellen, dvs att λ=(antal inlagda värden)/(hashtabellens storlek) inte är större än 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. Datorn gör ingen skillnad på en bokstav och dess nummer i ASCII-alfabetet, därför kan ABC uppfattas som 656667. Det man då gör är 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):             # Beräknar hashkoden för en sträng enligt
    result = 0            # s[0]*32^[n-1] + s[1]*32^[n-2] + ... + s[n-1]
    for c in s:                    
        result = result*32 + ord(c) 
    return result
Om man vill söka på datum eller personnummer kan man använda det som stort heltal utan särskild hashfunktion. Exempel: åttasiffriga datum kan hashas in i hashtabellen med 20080919 % size.

Man kan också "vika" talet genom att dela upp det i lika stora delar som sedan summeras, t ex 20+08+09+19=56, eller kvadrera det: 20080919²=403243307884561 och plocka ut de mittersta siffrorna: 307.

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 bör behandlas som stackar, och hashtabellen innehåller då bara topp-pekarna till stackarna.

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.

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, ... . Överstiger värdena hashtabellens storlek använder man resten vid heltalsdivision precis som vid beräkningen av h. En regel är att tabellstorleken bör vara ett primtal. Då ser man till att alla platser i tabellen utnyttjas.

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 Hashtable

I labb 5 ska du implementera den abstrakta datastrukturen hashtabell genom att skriva en klass Hashtable 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 hashtable import Hashtable, ElementNotFoundException
table = Hashtable(7)
table.put("one",1)
table.put("two",2)
table.put("three",3)

while True:
    word = raw_input("Ett engelskt räkneord:")
    try:
        print table.get(word)
    except ElementNotFoundException, x:
        print x
	print "Försök igen!"
Hashtable 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, hasKey(key) för att se om något finns lagrat med nyckeln key, getSize() för att få ut hashtabellens storlek mm.
Tips till labb 5: Ett kodskelett att börja med.

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 LINUX 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. 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. 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 f0(ord),f1(ord), f2(ord),...,f13(ord). Ett ord godkänns bara om alla dessa 14 hashfunktioner samtidigt ger index till platser i tab 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)14=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.

Programmet Stava kan köras på Nadas Unixdatorer med kommandot

stava filnamn

(hjälp finns via webbsidan) och stava går att köra på webben på http://www.nada.kth.se/stava/

För den som tycker det här verkar intressant finns kursen 2D1418, Språkteknologi.