Föreläsning 11: Hashning
Mål | Läs i kursboken |
Hashning |
Idag:
- Hashfunktioner
- Pythons dictionary
- Idén med hashning
- Komplexiteten för sökning
- Krockhantering
- Klassen Hashtable
- Användningsaspekter
- Bloomfilter
Hashfunktioner
Vi har sett att hashfunktioner kan användas både för att lagra lösenord säkert och vid textsökning (Rabin-Karp).
Men hur ser en hashfunktion ut? Det finns många olika varianter.
Oftast gäller det att först räkna om en sträng till ett 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 ett tal genom att multiplicera den första bokstaven med 10000, den andra med 100, den tredje med 1 och slutligen addera talen, alltså 65*104 + 66*102 + 67*100 = 656667
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]*32n-1 + s[1]*32n-2 + ... + s[n-1] for c in s: result = result*32 + ord(c) return result
Om strängen bara består av siffror, t ex ett datum eller personnummer, så kan vi använda siffrorna direkt. Här är två exempel:
- Att "vika" talet genom att dela upp det i lika stora delar som sedan summeras, t ex 20+17+09+11 = 57,
- Att kan kvadrera talet: 20020911² = 400836877269921 och sen plocka ut de mittersta siffrorna: 877.
Olika funktioner ger olika fördelning
Tre hashfunktioner plottade med statistikHash.py Download statistikHash.py
return len(h)%n
for c in string:
h = h + ord(c)
return h%n
for c in string:
h = 32*h + ord(c)
return h%n
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["IT-support"] = "08-790 6600"
---
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 "Pokémon 4ever" i en hashtabell av längd 1000. Då räknar vi först fram hashfunktionen för ordet "Pokémon 4ever" och det ger detta resultat.
hash("Pokémon 4ever") -> 8338994912692548419
Hashvärdets rest vid division med 1000 beräknas nu
8338994912692548419 % 1000 -> 419
och när vi kollar hashtabellens index 419 hittar vi "Pokémon 4ever" just där!
Hur kan detta vara möjligt? Ja, det är inte så konstigt egentligen. När "Pokémon 4ever" skulle läggas in i hashtabellen gjordes samma beräkning och det är därför den lagts in just på 419. 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.
"Pokémon 4ever" |
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.
Hur minskar man risken för krockar?
Välj en bra hashfunktion. Hashfunktion bör ha god spridning - vi vill inte att många nycklar ska ge samma hashvärde. Med programmet barchart_hash.py Download barchart_hash.py med tillhörande datafil slumpnamn30.txt Download slumpnamn30.txt kan du experimentera med fördelningen för olika hashfunktioner.
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
Då kommer krockarna att bli få.
Krockhantering
Vi måste ändå kunna ta hand om de krockar som uppstår. Hur?
Krocklistor
En idé är att lägga alla namn som hashar till ett visst index som en krocklista. Om man har femtio procents luft i sin hashtabell blir krocklistorna i regel mycket korta.
Iron Man 3 | Engaged | Star Trek | Hitta Nemo |
Tokyo Godfathers | Tjuven på Kgale Hill |
Fantasia |
Linjär probning
En annan metod är att vid krock lägga noden på första lediga plats. Är det upptaget 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.
Iron Man 3 | Engaged | Tokyo Godfathers | Fantasia | Star Trek | Hitta Nemo | Tjuven på Kgale Hill |
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 h1 tittar man i ordning på platserna: h1+1, h1+4, h1+9, ... . Överstiger värdena hashtabellens storlek använder man resten vid heltalsdivision precis som vid beräkningen av h1. Om tabellstorleken är ett primtal. och tabellen är som mest halvfull, så riskerar man inte att fastna i en evig hopprunda. (Bevis Links to an external site. för den som är intresserad)
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.
h1 = hash(x)
h2 = hash2(h1)
h3 = hash2(h2)
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.
animation Links to an external site.
Klassen Hashtable
I laboration 7 ska du implementera den abstrakta datastrukturen hashtabell genom att skriva en klass Hashtable med operationerna store och search.
class Hashtable: def __init__(self, size): self.size = size ... def store(self, key, data): ... def search(self, key): """Hämtar det objekt som finns lagrat med nyckeln "key" och returnerar det. Om "key" inte finns ska vi få en Exception, KeyError.""" ... else: raise KeyError def hashfunction(self, key): ...
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 KeyError.
from hashtable import Hashtable table = Hashtable(7) table.store(p1.namn,p1) table.store(p2.namn,p2) table.store(p3.namn,p3) kontrollnamn = "xxx" while kontrollnamn != "": kontrollnamn = input("Ge namnet på den du söker: ") try: print(table.search(kontrollnamn)) except KeyError: print(kontrollnamn, "fanns inte i hashtabellen") print("Försök igen!")
Hashtabellen ska åtminstone ha följande operationer:
store(key, data) Lägg in data med nyckeln key i hashtabellen.
data = search(key) Hämta data som hör till key.
f = hashfunction(key) Beräkna hashfunktionen för key.
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.
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. Flera olika noder i hashtabellen kan ju peka ut samma informationsnod.
Hur ska hashtabellen hantera det fall när man försäker stoppa in ett nytt värde för en nyckel som redan finns? För binärträdet i labb 3 smög vi runt problemet genom att vägra ta emot dubbletter. Men en rimligare lösning här vore att byta ut det lagrade värdet mot det nya.
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 f0(ord),f1(ord), f2(ord),...,f13(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)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å webben på http://www.csc.kth.se/stava/ (hjälp finns via Stavas webbsida)
Här är de stordiabilder Download stordiabilder som visades under Stava-föreläsningen.
För den som tycker det här verkar intressant finns kursen DD1418 Språkteknologi med introduktion till maskininlärning