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__()

2. En egen implementation av hashtabellen

Nu ska du även göra hashningen själv, i din nya klass Hashtabell. 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 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 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å kurswebbsidan (se Inlämningsuppgifter i vänstermenyn) 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.

1. Vad gäller för artister som har flera låtar, behöver man lagra alla dess låtarna i hashtabellen eller räcker det med en? Såg att för denna lab förra året skrev du att "Ni behöver inte ta hänsyn till att en artist kan ha flera låtar. Er egen hashtabell kan göra som Pythons dictionary." Gäller det även i år?
2. Går det bra att sätta en fix storlek på hashtabellen när den initieras eller är det krav att den ökar vartefter fler värden läggs in?

1. Er hashtabell kan skriva över precis som Pythons dictionary.

2. Ja, det är tänkt att ni ska sätta hashtabellens storlek när den skapas. Låt __init__ beräkna en lämplig storlek givet inparameter. Tabellen behöver inte utökas dynamiskt.