-
För att snabbt kunna avgöra om ett ord finns i SAOL vill man
använda en hashvektor med krocklistor (separate chaining).
Följande hashfunktioner har föreslagits. Är någon av dom
klart bättre än den andra? Motivera!
Som exempel ges hashvärdet för "AB".
- ASCII-värdenas produkt modulo 158773.
f(AB) = 65*66
- ASCII-värdena hopsatta till ett tal, modulo 158773.
f(AB) = 6566
Den första funktionen skiljer inte "AB" från "BA" och
är därför sämre.
-
Utför en algoritm som är O(1) alltid exakt en operation?
Nej, man vet bara att det finns en konstant övre gräns oberoende
av indatas storlek.
Sökning i en hashtabell är O(1) men man kan behöva göra flera
jämförelser (krocklista/probning) innan man hittar rätt.
-
I Brookhavendatabanken finns bokstavssekvenser för cirka hundratusen
gener, där varje gen består av något tusental bokstäver. För snabb
sökning används en hashtabell. Föreslå hashfunktion och storlek på
hashtabellen.
Det tar för lång tid att räkna ut ett hashvärde som beror på
varenda bokstav. Ta till exempel var hundrade bokstav och
använd i en slinga.
h = 4*h+tkn där tkn räknas som 0,1,2,3 för A,C,G,T.
Index blir h % size, där lämpligen size = 150001.
-
Under gulfkriget var det väldigt svårt för armestaben att hålla reda
på alla TV-bolag som for omkring och rapporterade i öknen. För att
hålla reda på dem användes en hashvektor. Koden fungerade inte som
avsett: vissa TV-bolag gick inte att hitta i tabellen!
from string import find
p = 100;
hashvektor = [0]*p
alfabet = "abcdefghijklmnopqrstuvxyz"
def put(tvbolagsnamn, tvbolag):
hashcode = 0
for i in range(len(tvbolagsnamn)):
alfanum = find(alfabet, tvbolagsnamn[i])+1
hashcode += alfanum
hashcode = hashcode % p
hashvektor[hashcode] = tvbolag
Vad är det för fel på koden? Beskriv hur man kan förbättra den.
Namnen på TV-bolagen kan antas bestå av högst tre bokstäver.
Det kommer inte att förekomma mer än 75 TV-bolag.
Det som gör att koden inte fungerar är att det inte finns någon
krockhantering.
hashvektor[hashcode] = tvbolag;
För att lösa det kan man använda t.ex. krocklistor eller
linjär/kvadratisk probning. Linjär probning fungerar så
att om det är upptaget på den givna positionen så söker
man tills man antingen hittar nyckeln (den var redan
instoppad sedan tidigare) eller tills man hittar ett
tomt element i vektorn.
Hashkoden är ganska korkat implementerad. Strängarna "AB" och
"BA" får samma värde.
alfanum = find(alfabet, tvbolagsnamn[i])+1
hashcode += alfanum
För att lösa det kan man vikta genom att multiplicera med
t.ex. 1, 100 och 10000.
Längden på hashvektorn är lite för liten och dessutom inget
primtal. Välj istället hashvektorns storlek till exempelvis 151
(dubbelt så stor som förväntade antalet element).
-
Hitta på en perfekt hashfunktion för atomer. Hur stor blir
hashtabellen?
Låt a=1, b=2, ..., z=26 och A=0, B=27, ..., Z=675 (25*27)
Då blir hash("A")=0 och hash("Zz")=701, så det behövs
702 platser i hashtabellen (dvs ca sex gånger mer än antalet
element).
Ingen extra luft - det blir inga krockar!
-
Linda har svårt att hitta i sitt gigantiska manga-register
och vill införa hashning för att få snabbare sökning. Hur ska hon göra för
att det ska gå lika snabbt att söka på titel (t ex Love Hina) och
författare (t ex Ken Akamatsu) utan att skapa två separata
hashtabeller? Rita och förklara!
Linda köper ännu mer manga och utökar hashtabellens storlek
till det dubbla. Måste hon modifiera
hashfunktionen? Måste all gammal manga hashas om?
Svara med motivering!
- Hasha in mangan på två ställen, en gång på titel
och en på författare
Med pekare till noderna slösar man inte minnesutrymme.
Krockar fixas med krocklistor. Söker man på en författare
kan man då gå igenom krocklistan för att hitta alla
dennes manga.
- Om hashtabellens storlek ändras måste modulo-delen av
hashningen ändras. Och då måsta de gamla värdena hashas om,
annars hittar man dom inte. Exempel: 14%13=1 men 14%26=14
-
Speljätten Cawr Games har 1073741824 olika spel i sin databas.
Hittills har man använt binärträd för att få snabb sökning, men man
vill byta till hashning, med en hashtabell som rymmer
en miljon objekt.
a) Vilken krockhanteringsmetod skulle du använda?
Motivera ditt val, och rita en bild som visar hur det går till.
b) Hur snabb skulle hashsökningen bli jämfört
med binärsökningen? Anta att antalet jämförelser
bestämmer tiden.
a) Eftersom hashtabellen är mindre än antalet spel som ska
hashas in är krocklistor det rimligaste alternativet.
b) Binärsökning är O(logn) och log(1073741824) = 30, dvs
30 jämförelser.
Hashning är O(1), dvs vi hamnar direkt på rätt index. Men
vi måste gå igenom en krocklista som är i genomsnitt 1000
lång vid varje sökning!