GRUDAT, ÖVNING 6

Hashning

1 PERSONDATABAS
Ni tänker lägga upp en databas över deltagarna i övningsgruppen.
Man ska kunna söka på personnumrets sex första siffror och man
ska sedan få fram namn, personnummer och en massa annat.

* En hashtabell ska användas. Föreslå storlek!

* Föreslå en enkel hashfunktion som beror av år, månad och dag och
  som ger index i rätt intervall.

* Alla i gruppen ska nu räkna fram sitt hashindex. Hur många krockar
  uppstår? 

2 KROCKTESTPROGRAM
Alla 138 kursdeltagares personnummer och namn finns på filen grudat03.reg
som alltså har 138 rader. Skriv ett program hash1.py som testar hur 
många krockar det maximalt blir för viss storlek på hashtabellen. 
Personnumret hashas med pythons inbyggda hash(pnr). Körexempel:

   python hash1 grudat03.reg
   Hashtabellens storlek: 200     <---användarinmatning
   Krockmax: 4                    <---programmets svar

3 HASHAD DATABAS

Anta att ni bestämt er för tabellstorleken 209. Skriv nu färdigt 
databasprogrammet hash2 som fungerar enligt följande exempel.

   python hash2 grudat03.reg
   Personnummer: 420119-0818      <---användarinmatning
   Eriksson, Henrik               <---programmets svar
   Personnummer: 123456-7890
   Finns inte!

4 SÖKTIDER

I labbarna används en ordfil med cirka 2000 ord. Hur många
jämförelser går det åt för att söka efter ordet värst i
* en ordnad vektor
* en kö
* ett binärträd
* en hashtabell

Och hur många behövs det för att konstatera att väscht är felstavat?

5 ORDLISTIG HASHNING

För att snabbt kunna avgöra om ett ord finns i Svenska Akademiens
ordlista vill man använda en hashtabell med krocklistor. Följande
hashfunktioner har föreslagits. Vilken är bäst? Motivera!
* ASCII-numrens produkt modulo 158773       AB-->65*66
* ASCII-numren hopsatta modulo 158773       AB-->6566