Föreläsningar

Föreläsning 7

Hashtabeller

[kapitel 8]
OH-bilder från denna föreläsning

Vad innebär datatypen Dictionary?
Lagring av element som identifieras genom sina nycklar
Man kan betrakta nycklarna som generaliserade index

Vad är det som behöver gå fort i en effektiv implementation?
Som vanligt: att lagra, hitta samt ta bort element

Använder man en sorterad intern lagring?
Ja, eller också kan man utnyttja s.k. hashning

Hur fungerar en Hash-tabell?
Man gör om nyckeln till ett heltal som används som vanligt index

Men vad gör man om flera nycklar ger samma heltal?
Detta behandlar man som ett specialfall
Om det händer tillräckligt sällan så gör det inte så mycket

Kan man gå igenom elementen i ordning i en Hash-tabell?
Nej. Då måste man ta till t.ex. en SkipList

Vad är en SkipList
En sorterad lista med "genvägar" för att snabbt hitta ungefär rätt