Labb 7: Hashtabeller
- Inlämningsdatum 13 okt 2023 av 18:00
- Poäng 10
- Lämnar in en filuppladdning
Mål | Läs i kursboken |
Kunna använda och implementera en hashtabell. Kunna använda unittest för att testa program. Repetera Föreläsning 6: Hashning | Kapitel 6.5 Links to an external site. |
□ Hashning med Pythons inbyggda dictionary
Minns du hur du i labb 2 gjorde en enkel kö med Pythons array? Nu ska du göra en egen hashtabell med Pythons dictionary!
Skriv en klass DictHash som använder Pythons inbyggda dictionary Links to an external site.. Den måste ha metoderna
- store(nyckel, data) som lagrar data som value i din dictionary, med nyckel som key.
- x = search(nyckel) som slår upp nyckel i din dictionary.
Dessutom får du om du vill lägga till två extra metoder:
- Vill du kunna skriva d[nyckel] istället för d.search(nyckel)? Definiera då metoden __getitem__(self, nyckel) Links to an external site.som anropar din search-metod.
- Vill du kunna skriva if nyckel in d ? Definiera då metoden __contains__(self, nyckel) Links to an external site.som returnerar True om nyckel finns i d, False annars.
Testkör din klass DictHash med datafilen från första labben: Apoorvas fil med koreanska dramer eller den förenklade filen kdramaMini.txt
- Skapa Drama-objekt på samma sätt som i labb 1. Lägg in objekten i hashtabellen, med namnet som nyckel.
- Sök efter ett drama i hashtabellen.
- Testa också att söka efter ett namn som inte finns med.
□ En egen implementation av hashtabellen
Nu ska du även göra hashningen själv, i din nya klass Hashtable med samma gränssnitt och funktionalitet som DictHash. Krav:
- Definiera en klass HashNode för hashtabellens noder. Noderna måste innehålla både nyckel och värde.
- Definiera en klass Hashtable som representerar hashtabellen. Hashtable ska ha samma funktionalitet som DictHash.
- Du måste skriva en egen hashfunktion, som ger en bra fördelning över hela 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.
Använd följande kodskelett. Ändra inte i gränssnittet - metoderna ska fortfarande ha samma parametrar.
class HashNode:
"""Noder till klassen Hashtable """
def __init__(self, key = "", data = None):
"""key är nyckeln som anvands vid hashningen
data är det objekt som ska hashas in"""
self.key = key
self.data = data
#Fyll i kod här nedan för att initiera hashtabellen
class Hashtable:
def __init__(self, size):
"""size: hashtabellens storlek"""
self.size = size
def store(self, key, data):
"""key är nyckeln
data är objektet som ska lagras
Stoppar in "data" med nyckeln "key" i tabellen."""
#Fyll i kod här!
def search(self, key):
"""key är nyckeln
Hamtar det objekt som finns lagrat med nyckeln "key" och returnerar det.
Om "key" inte finns ska det bli KeyError """
#Fyll i kod här!
#...
else:
raise KeyError
def hashfunction(self, key):
"""key är nyckeln
Beräknar hashfunktionen för key"""
#Fyll i kod här!
Testning del 1
Prova med datafilen: Apoorvas fil med koreanska dramer eller den förenklade filen kdramaMini.txt Se till att du skapar en lagom stor hashtabell i huvudprogrammet (det ska fortfarande stå self.size = size i klassen).
Testning del 2
Programmet hashtest.py Download hashtest.py innehåller data om alla atomer (namn och atomvikt). Läs om unittest Links to an external site. så att du kan lista ut vad det gör och hur det anropar hashtabellen.
Testning del 3
Gå på Kattis: https://kth.kattis.com/problems/kth.tilda.hashtabell2
Links to an external site. och testa att din hashtabell fungerar. OBS! Filen du skickar in måste heta hashtable.py
Testa först att köra detta huvudprogram och se till att det ger samma utmatning som visas i Kattis-uppgiften för Sample Input 1 och Sample Input 2.
from hashtable import Hashtable |
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.
Redovisning
Labben lämnas in individuellt med "Lämna in uppgift"-knappen högst upp på sidan, och ska redovisas muntligt av bägge gruppmedlemmarna. Skriv gruppmedlemmarnas namn i kommentarsfältet!
Vid redovisningen ska du kunna
- förklara varför hashning ger snabb sökning,
- skissa hashtabellen,
- motivera ditt val av hashfunktion, krockhantering och tabellstorlek genom att
- redogöra för hur bra fördelningen är, t.ex. genom att mäta hur många krockar det är som mest vid insättning,
- beskriva och rita hur din krockhantering fungerar,