Laboration 5 del 2 (under arbete)

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? (se https://docs.python.org/3/reference/datamodel.html#emulating-container-types för att byta ut "search" mot [])¶ 2. En egen implementation av hashtabellen Nu ska du göra en egen hashtabell! Skriv klassen Hashtabell där du använder en Python-lista för att implementera en egen hVill 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
* NÃ¥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
* AnvändDu ska använda KeyError föör att tala om att en nyckel inte finns
* Skriv en egen hashfunktion
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öå göra labbarna föör höögre betyg i pe\ riod 2.

¶

¶