Hashtable
hash("Lyckan") -> 1076540772
Hashvärdets rest vid division med 10000 beräknas nu 1076540772 % 10000 -> 772och 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 stora 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.
string 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) 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:
def hash(): # Returns a hashcode for this string, computed as
result = 0 # s[0]*32^(n-1) + s[1]*32^(n-2) + ... + s[n-1]
for c in s: # where n is the length of the string, and ^ indicates exponentiation.
result = result*32 + ord(c)
return result # When the number becomes too big to fit in an integer
Om man vill söka på datum eller personnummer kan man använda det
som stort heltal utan särskild hashfunktion. Exempel: sexsiffriga datum
kan hashas in i hashvektorn med
031202 % size. En olämplig storlek är 10000, ty 031202 % 10000 --> 1202
och vi ser att endast 366 av de 10 000 platserna kommer att utnyttjas.
Det säkraste sättet att undvika sådan snedfördelning är att byta 10000
mot ett närliggande primtal, till exempel 10007.
Det visar sej nämligen att primtalsstorlek ger bäst spridning.
Den andra idén är att vid krock lägga posten på första lediga plats. En nackdel blir att man sedan inte enkelt kan ta bort poster utan att förstöra hela systemet. En fördel är att man slipper alla pekare. En annan nackdel är att om det börjat klumpa ihop sej någonstans har klumpen en benägenhet att växa. 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 och kan till exempel räknas fram med en annan hashfunktion. Det kallas för dubbelhashning.
Hashtable
from hashtable import Hashtable
table = Hashtable()
table.put("one", 1)
table.put("two", 2)
table.put("three", 3)
n=table.get("two") # Nu blir n=2
Om det är risk att nyckeln inte finns skriver man så här:
while True:
word=raw_input("Ett engelskt räkneord:")
try:
print table.get(word)
except Exception:
print "Tyvärr okänt, försök igen!"
Klassen Hashtable finns inte inbyggd i Python. Vill man ha den
får man programmera den själv och i så fall bör man förse den med ett par anrop
till.
class Node: # På varje plats i tabellen finns en stack
key="" # av såna här noder.
value=None
next=None
class Hashtable:
size=17
table=[None]*17
def setsize(self,n):
- - -
def getsize(self):
print self.size
def has_key(self,key):
i=hash(key) % self.size
p=self.table[i]
while p!=None:
if p.key==key: return True
p=p.next
return False
def put(self,key,value):
- - -
def get(self,key):
- - -
raise Exception,key+" finns inte"
tal={} # Tomt lexikon skapas
tal["one"] = 1
tal["two"] = 2
tal["three"]=3
n=tal["two"] # Nu blir n=2
Anropet tal.has_key("två") fungerar som förut och
om man skriver tal["två"] uppstår ett särfall.
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 informationsposten finns alltid bara i ett exemplar. Många noder i hashtabellen kan ju peka ut samma post.
När man vill kunna skriva ut registret i bokstavsordning är hashtabellen oduglig. Binärträdet skrivs lätt ut i inordning, men är inte så bra när man vill kunna stega sej framåt och bakåt från en aktuell nod. Risken för att det ska bli obalanserat har lett till algoritmer för automatisk ombalansering av binärträd när poster läggs till och tas bort. Kända begrepp är B-träd, AVL-träd och rödsvarta träd. För femton år sedan gjordes en uppfinning som löser problemen på ett enklare sätt, nämligen skipplistan.