Laboration 5 del 2

Läsning Läs i kapitel 4 i kursboken om Hashing.

1. Hashning med Pythons inbyggda dictionary Minns du hur du i labb 2 gjorde en enklel kö med Pythons lista? 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__()

2. En egen implementation av hashtabellen Nu ska du även göra hashningen själv, i din nya klass Hashtabell. Krav:

* 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 tabellen
* 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.

Testkörning 2 Programmet hashtest.py innehåller data o\ m alla atomer (namn och atomvikt). Lista ut vad det gör och hur det anropar hashtabellen. Modifiera det sedan för att kontrollera om di\ n hashtabell fungerar.

Redovisning Labben lämnas in på kurswebbsidan (se Inlämningsuppgifter i vänstermenyn) och redovisas muntligt av bägge gru\ ppmedlemmarna.

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.