d2

Mål: Kunna använda och implementera en hashtabell. Kunna använda unittest för att testa program.

Läs i Miller-Ranum om Hashing, och repetera Föreläsning 7

1. Hashning med Pythons inbyggda dictionary

Nu ska du göra en egen hashtabell med Pythons dictionary!

Skriv en klass DictHash som använder Pythons inbyggda dictionary . 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) som anropar din search-metod.
• Vill du kunna skriva if nyckel in d ? Definiera då metoden __contains__(self, nyckel) som returnerar True om nyckel finns i d, False annars.

Testkör din klass  DictHash med datafilen unique_tracks.txt. Du får själv välja vad du vill ha som nyckel, t ex artist eller låtnamn. Tips: split()

2. En egen implementation av hashtabellen

Nu ska du även göra hashningen själv, i din nya klass Hashtabell med samma gränssnitt och funktionalitet som DictHash.

Krav:

1. Definiera en klass HashNode för hashtabellens noder. Noderna måste innehålla både nyckel och värde.
2. Hashtabellen ska vara lagom stor.
3. Du måste skriva en egen hashfunktion.
4. Någon krockhantering måste ingå, t ex krocklistor eller probning.
5. Du ska använda KeyError för att tala om att en nyckel inte finns.

Testning

Det kan vara en god idé att först prova med liten hashtabell för att se så att krockhanteringen fungerar.

När du har förvissat dig om det är det läge att prova med mer data. Filen unique_tracks.txt innehåller bland annat artist och titel för en miljon låtar. Du kan hämta den via din webbläsare, men eftersom den är så stor kan det vara smidigare att hämta den via kommandoraden:

$ curl https://www.csc.kth.se/~lk/unique_tracks.txt > unique_tracks.txt

Läs in den i ditt program och lägg in låtarna i din hashtabell, förslagsvis med artister som nycklar och deras respektive låtar som värden. Tänk på att varje nyckel har precis ett värde, och att gamla värden ska skrivas över om man anropar store med en nyckel som redan finns i hashtabellen.

Redovisning

Vid redovisningen ska du kunna

• skissa principerna för insättning och sökning i hashtabeller,
• visa hur man söker i din hashtabell med de från unqiue_tracks.txt inlagda låtarna,
• förklara varför hashtabeller ger snabb sökning.