Övning 7
Hashning
Genomgång Labb 7
- https://kth.kattis.com/problems/kth.tilda.hashtabell2 Länkar till en extern sida.
- Unit test Länkar till en extern sida.
- Exception Länkar till en extern sida. - särfall
Hashfunktioner på högstadiet (Tildatenta 181022)
Redan andra dagen på ditt nya jobb på en högstadieskola blir du uppkallad till rektorn. Det går rykten om att du sprider drogpropaganda. Du förklarar att du undervisat om ”bra hashfunktioner”, inte ”bra funktioner hos hasch”. För att rektorn (som är geografilärare) ska förstå tar du följande exempel:
Vi har befolkningsdata för 250 000 orter, och vill snabbt kunna slå upp ett ortsnamn, t ex ”Korpilombolo” och få ut folkmängden (522).
Vilka av följande hashfunktioner skulle fungera för detta exempel? Vilka skulle fungera dåligt?
a) summan av bokstävernas nummer, dvs 65+66+67 för ’ABC’
b) produkten av bokstävernas nummer, dvs 65*66*67 för ’ABC’
c) bokstävernas nummer skrivna efter varann som ett tal, dvs 656667 för ’ABC’
Motivera dina svar för rektorn!
lösning Länkar till en extern sida.
Skriv en hashfunktion
Implementera den bästa av de tre hashfunktionerna ovan.
hashfunktion181022.py Ladda ner hashfunktion181022.py
Hasha pappor (Tildatenta 171020)
BVC ordnar pappagrupper för nyblivna fäder. Papporna ska hashas in i en hashtabell på följande vis:
– Hashtabellen har 13 platser
– Vid krock används krocklistor
– Hashfunktionen är summan av siffrorna i pappans födelsedag och månad.
Den som är född 23/10 får alltså hashvärdet 2 + 3 + 1 + 0 = 6.
Rita upp hashtabellen, med eventuella krocklistor, för följande åtta pappor:
– Amir 28/10
– Bedrich 1/6
– Calvin 15/5
– Dubaku 11/11
– Ejvind 21/12
– Filip 23/2
– Gus 2/5
– Henrik 19/1
Perfekt hashfunktion
Hitta på en perfekt hashfunktion för atomer. Hur stor blir hashtabellen?
lösning
Håll reda på media (Tildatenta 030308)
Under gulfkriget var det väldigt svårt för armestaben att hålla reda på alla TV-bolag som for omkring och rapporterade i öknen. För att hålla reda på dem användes en hashvektor. Koden fungerade inte som avsett och man har nu gett i uppdrag åt en f.d. tildastudent att titta på en misstänkt del av koden:
p = 100 hashvektor = [0] * p alfabet = "abcdefghijklmnopqrstuvxyz" def put(tvbolagsnamn, tvbolag): hashcode = 0 for i in range(len(tvbolagsnamn)): alfanum = alfabet.find(tvbolagsnamn[i]) + 1 hashcode += alfanum hashcode = hashcode % p hashvektor[hashcode] = tvbolag
Vad är det för fel på koden? Beskriv hur man kan förbättra den. Namnen på TV-bolagen kan antas bestå av högst tre bokstäver. Det kommer inte att förekomma mer än 75 TV-bolag.
lösning
Nix till telefonförsäljning (Tilda-tenta 000603)
Föreningen för konsumentskydd vid marknadsföring per telefon har startat ett register dit den som inte vill bli uppringd av telefonförsäljare kan anmäla sig.
Till att börja kommer kontrollen att ske genom att företaget sänder sin telefonlista till nix och får tillbaka en lista där de nixade numren markerats.
Vilka av följande metoder kan föreningen använda sig av? Vilken är bäst? Binärträd, bloomfilter, hashtabell.
Ett framtida mål är att kontroll också skall kunna ske över internet. Då måste kontrollen ske snabbt men man vill också försäkra sig om att ingen ska kunna få ut en lista över alla nixade telefonnummer.
Vilken metod passar bäst för internet-kontrollen?