Till KTH:s startsida Till KTH:s startsida

Laboration 5 del 2

Laboration 5 del 2: Implementera hashtabell

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:

  • 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.

Teacher Linda Kann created page 23 September 2015

commented 28 September 2015

Hej Kann!

Hur länge kommer denna sida att vara "under arbete"?

Teacher commented 28 September 2015

Tills nån påminner mig, tack!

Nu har den rätt teckenkodning.

commented 7 October 2015

Hej! finns det möjlighet att öppna upp inlämningarna tidigare?
vi skulle gärna vilja lämna in lab5del2 nu :)

Teacher commented 7 October 2015

@Linnea

Räcker det om jag öppnar kl 20 ikväll? När det finns flera inlämningar uppe samtidigt så hamnar labbarna lätt på fel ställe :-o

commented 12 October 2015

Hej Linda, det går inte att boka labb5 del 2 för redovisning. När kommer bokningslistan upp?

Mvh

Teacher commented 12 October 2015

Oops, nu finns tiderna uppe!

commented 12 October 2015

Behöver vi ta hänsyn till att artisterna har flera låtar? Det gjorde vi i del 1 men det verkar inte  vara uttänkt så eftersom vi testade Texta som uppkom tidigare i filen än på sista platsen och linjärsökningen gick då väldigt snabbt om man inte tog hänsyn till det.

I denna del blir det mycket att hålla reda på krockar mellan olika artister och samma artist med en ny låt.

Teacher commented 12 October 2015

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.

commented 14 October 2015

Hej Linda, i lydelsen står det att vår egen hashtabell ska använda sig av KeyError. Stämmer det? Som vi fattat det ska vi skapa hashtabellen med hjälp av en lista, och då är det AttributeError som kommer fram. 

Mvh 

Teacher commented 14 October 2015

Ja, ni ska själva se till att det är KeyError som skickas om nyckeln inte finns med.

Att ni får AttributeError beror nog på att ni inte kollar om det finns något på platsen...

commented 14 October 2015

Okej, vi hajar läget. Tack