Labb 7: Hashtabeller

□  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

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

def main():
    hashtable = None
    
    while True:
        line = input()
        key, *value = line.split()
        if key == '#':
            print('#')
            break
        elif key == 'init' and len(value) > 0:
            size = int(value[0])
            hashtable = Hashtable(size)
            print('New size:', size)
        elif len(value) > 0:
            hashtable.store(key, value[0])
            print(key, '<-', value[0])
        else:
            try:
                value = hashtable.search(key)
                print(f'{key}: {value}')
            except KeyError:
                print('KeyError:', key)


if __name__ == "__main__":
    main()

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,