Laboration 7
Laboration 7: Implementera hashtabell
Läsning
Läs i Miller-Ranum om Hashing.
1. Hashning med Pythons inbyggda dictionary
Minns du hur du i labb 2 gjorde en enklel kö med Pythons array? Nu ska du göra en egen hashtabell med Pythons dictionary!
Skriv en klass DictHash som använder dictionary. Den ska ha metoderna
- store(nyckel, data)
- x = search(nyckel)
Prova din dictionary med datafilen från förra labben. Tar det lika lång tid att köra?
Vill du kunna skriva d[nyckel] istället för d.search(nyckel)? Definiera då metoden __getitem__(self, nyckel)
Om du vill kunna skriva if nyckel in d definierar du metoden __contains__(self, nyckel)
2. En egen implementation av hashtabellen
Nu ska du även göra hashningen själv, i din nya klass Hashtabell med samma gränssnitt och funktionalitet som DictHash. Krav:
- Definiera en klass HashNode för hashtabellens noder. Noderna måste innehålla både nyckel och värde.
- Hashtabellen ska vara lagom stor
- Du måste skriva en egen hashfunktion, som ger en bra fördelning över hela tabellen
- Redogöra för hur bra fördelningen är. T.ex. med en teoretisk analys av din algoritm eller genom att mäta hur många krockar det är som mest vid insättning.
- Någon krockhantering måste ingå, t ex krocklistor eller probning
- Du ska använda KeyError för att tala om att en nyckel inte finns
Testkörning 1
Prova med datafilen från förra labben. Du behöver inte använda enbart artist som nyckel.
Testkörning 2
Programmet hashtest.py innehåller data om alla atomer (namn och atomvikt). Lista ut vad det gör och hur det anropar hashtabellen. Modifiera det sedan för att kontrollera om din hashtabell fungerar.
Redovisning
Labben lämnas in på git och redovisas muntligt av bägge gruppmedlemmarna.
Vid redovisningen ska du kunna
- motivera ditt val av hashfunktion, krockhantering och tabellstorlek,
- skissa hashtabellen,
- förklara varför hashning ger snabb sökning
Betyg
Denna labb kan endast ge betyg E. Du måste lämna in den och redovisa den i tid för att få göra labbarna för högre betyg i period 2.