Bij een bordspel hebben spelers steeds zeven vierkante steentjes. Op elk van deze steentjes staat één van de letters van het alfabet. Met deze steentjes worden woorden gemaakt. De spelers kunnen ook letters die al op het bord liggen gebruiken; we nemen hier aan dat ze hoogstens drie andere letters gebruiken, en dat woorden dus hoogstens tien letters lang zijn. Niet alle woorden zijn toegestaan. De woorden moeten aan een aantal regels voldoen. Hoofdstuk 9. Hashtabellen 136 Voor het maken van een computerspelversie van dit bordspel willen we controleren of een bepaald woord toegestaan is. Hiervoor wordt een hashtabel gebruikt. In deze hashtabel worden alle toegestane woorden opgeslagen. Als de speler dan een bepaald woord opgeeft, dan wordt opgezocht of het woord in de tabel voorkomt. Er worden 100 000 woorden opgeslagen. De tabelgrootte N is ook 100 000. Als hashfunctie wordt het volgende genomen. Elke letter wordt ‘vertaald’ naar een getal tussen 1 en 26, naar gelang de positie in het alfabet; met andere woorden, we nemen vertaling(”A”) = 1, vertaling(”B”) = 2, . . . , vertaling(”Z”) = 26. Voor een gegeven woord nemen we van elk van de letters de vertaling en die getallen tellen we bij elkaar op. Dit geeft de hashwaarde van het woord. Voorbeeld: Het woord ”BY” heeft als hashwaarde 2+25=27. De hash- waarde van ”AA” is 1+1=2. Welke nadelen zie je voor het op deze manier (met deze tabelgrootte en deze hashfunctie) gebruiken van hashing voor deze toepassing? Leg kort uit.
- Hashcode is niet goed gekozen, je kan maar maximum een hashcode van 260 hebben
- Je kan veel te veel dubbele hebben
- ABBA: hashcode: 6
- BAAB: hashcode: 6
Voeg alle (verschillende) letters uit het woord ‘DEMOCRATISCH’ toe aan een hashtabel. De grootte van de hashtabel wordt bepaald door N = 5, dus er zijn vijf plaatsen (buckets) in de hashtabel. In de hashtabel wordt er geen waarde opgeslagen corresponderend met de letters. De te gebruiken hashcode is 11 � k met k de positie van de letter in het alfabet. Hoe evolueert de hashtabel?
Het alfabet:
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | |
|---|---|---|---|---|---|---|---|---|---|---|
| 0 | A | B | C | D | E | F | G | H | I | |
| 1 | J | K | L | M | N | O | P | Q | R | S |
| 2 | T | U | V | W | X | Y | Z |
D -> 11 x 4 = 44 ~> 44 MOD 5 = 4
E -> 11 x 5 = 55 ~> 55 MOD 5 = 0
M -> 11 x 13 = 143 ~> 143 MOD 5 = 3
O -> 11 x 15 = 165 ~> 165 MOD 5 = 0
C -> 11 x 3 = 33 ~> 33 MOD 5 = 3
R -> 11 x 18 = 198 ~> 198 MOD 5 = 3
A -> 11 x 1 = 11 ~> 11 MOD 5 = 1
T -> 11 x 20 = 220 ~> 220 MOD 5 = 0
I -> 11 x 9 = 99 ~> 99 MOD 5 = 4
S -> 11 x 19 = 209 ~> 209 MOD 5 = 4
C -> 11 x 3 = 33 ~> 33 MOD 5 = 3
H -> 11 x 8 = 88 ~> 88 MOD 5 = 3