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.