Hashing < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 17:57 Mo 24.05.2010 | | Autor: | matheja |
| Aufgabe | Hallo leute, ich habe ein paar probleme folgende aufgabe zu verstehen.Vll koennt ihr mir helfen.
aufgabe:
Fügen Sie die Schlüsselfolge 38, 26, 35, 48, 29, 20, 4, 22, 42, 17 in eine zu Beginn leere Hashtabelle der Länge 11 ein und verwenden Sie die Hashfunktion h(k) = k MOD m mit m = 11. Als Kollisionsstrategie wird lineares Sondieren angewandt, d.h. hi(k) = (h(k) + i) MOD 11. |
Mein Loesungsansatz:
Muss die Tabelle nicht die Laenge 10 haben, weil sie doch auch nur mit 10 zahlen gefuellt wird?
hashtabelle:
0 38
1 26
2 35
3 48
4 29
5 20
6 4
7 22
8 42
9 17
nun wende ich die funktion h(k) an.
ich bin so vorgegangen beispiel 38 mod 11 => 38:11=3 rest 5
0 5
1 4
2 2
3 4
4 7
5 9
6 4
7 0
8 9
9 6
soll ich linear sondieren und hier happerts, weil ich nicht genau weis, wie ich die funktion hi(k) uebertragen kann.
also:
h0(h(k)=h(k) mod 11
h1(h(k)=h(k)+1 mod 11
h2(h(k)=h(k)+2 mod 11
....
mir dieser strategie will man kollisionen vermeiden.
wie geht es dann weiter bzw.ist es bis hierhin richtig?
meine vermutung:
ich wende das ganze auf die tabelle: =>5+0 mod 11 = 5 mod 11=5...
0 5
1 4
2 2
3 4
4 7
5 9
6 4
7 0
8 9
9 6
=>
0 5
1 5
2 4
3 7
4 0
5 3
6 10
7 7
8 4
9 4
das waer auch mein endergebnis.aber so ganz glaube ich nicht an die richtigkeit
danke fuer hilfe
matheja
|
|
| |
|
Hallo matheja,
> Fügen Sie die Schlüsselfolge 38, 26, 35, 48, 29, 20, 4,
> 22, 42, 17 in eine zu Beginn leere Hashtabelle der Länge
> 11 ein und verwenden Sie die Hashfunktion h(k) = k MOD m
> mit m = 11. Als Kollisionsstrategie wird lineares Sondieren
> angewandt, d.h. hi(k) = (h(k) + i) MOD 11.
So wie ich '![[]](/images/popup.gif) lineares Sondieren' verstanden habe, wendet man einfach [mm]h_i(k)[/mm] auf den Datensatz [mm]k\![/mm] an, wobei [mm]i\![/mm] beginnend bei 0 erhöht wird bis die Einfügeoperation erfolgreich ist. Das Ganze sollte man wohl abbrechen, wenn [mm]i\![/mm] größer ist als die Größe der Hashtabelle (eigentlich könnte man vielleicht auch früher abbrechen, aber im Moment ist mir das egal).
Ich habe mal ein kurzes Python-Programm zur Demonstration geschrieben:
| 1: | data = [38, 26, 35, 48, 29, 20, 4, 22, 42, 17]
| | 2: |
| | 3: | hashtable = [-1]*11
| | 4: |
| | 5: | f = open('logbuch.txt', 'w')
| | 6: |
| | 7: | def h(k):
| | 8: | ergebnis = k % 11
| | 9: | print('h(%d) = %d %% 11 = %d'%(k, k, ergebnis),file=f)
| | 10: | return k % 11
| | 11: |
| | 12: | def hi(k):
| | 13: | i = 0
| | 14: | while True:
| | 15: | hk = h(k)
| | 16: | itestpos = (hk + i) % 11
| | 17: | print('h%d(%d) = (%d + %d) %% 11 = %d'%(i, k, hk, i, itestpos),file=f)
| | 18: | if i < 11:
| | 19: | if hashtable[itestpos] == -1:
| | 20: | print('-= EINFUEGEN bei %d! =-'%itestpos, file=f)
| | 21: | hashtable[itestpos] = k
| | 22: | break
| | 23: | else:
| | 24: | i = i+1
| | 25: | else:
| | 26: | break
| | 27: |
| | 28: |
| | 29: | for z in data:
| | 30: | hi(z)
| | 31: |
| | 32: | print(hashtable,file=f) |
Und hier ist die Ausgabe des Programms:
h(38) = 38 % 11 = 5
h0(38) = (5 + 0) % 11 = 5
-= EINFUEGEN bei 5! =-
h(26) = 26 % 11 = 4
h0(26) = (4 + 0) % 11 = 4
-= EINFUEGEN bei 4! =-
h(35) = 35 % 11 = 2
h0(35) = (2 + 0) % 11 = 2
-= EINFUEGEN bei 2! =-
h(48) = 48 % 11 = 4
h0(48) = (4 + 0) % 11 = 4
h(48) = 48 % 11 = 4
h1(48) = (4 + 1) % 11 = 5
h(48) = 48 % 11 = 4
h2(48) = (4 + 2) % 11 = 6
-= EINFUEGEN bei 6! =-
h(29) = 29 % 11 = 7
h0(29) = (7 + 0) % 11 = 7
-= EINFUEGEN bei 7! =-
h(20) = 20 % 11 = 9
h0(20) = (9 + 0) % 11 = 9
-= EINFUEGEN bei 9! =-
h(4) = 4 % 11 = 4
h0(4) = (4 + 0) % 11 = 4
h(4) = 4 % 11 = 4
h1(4) = (4 + 1) % 11 = 5
h(4) = 4 % 11 = 4
h2(4) = (4 + 2) % 11 = 6
h(4) = 4 % 11 = 4
h3(4) = (4 + 3) % 11 = 7
h(4) = 4 % 11 = 4
h4(4) = (4 + 4) % 11 = 8
-= EINFUEGEN bei 8! =-
h(22) = 22 % 11 = 0
h0(22) = (0 + 0) % 11 = 0
-= EINFUEGEN bei 0! =-
h(42) = 42 % 11 = 9
h0(42) = (9 + 0) % 11 = 9
h(42) = 42 % 11 = 9
h1(42) = (9 + 1) % 11 = 10
-= EINFUEGEN bei 10! =-
h(17) = 17 % 11 = 6
h0(17) = (6 + 0) % 11 = 6
h(17) = 17 % 11 = 6
h1(17) = (6 + 1) % 11 = 7
h(17) = 17 % 11 = 6
h2(17) = (6 + 2) % 11 = 8
h(17) = 17 % 11 = 6
h3(17) = (6 + 3) % 11 = 9
h(17) = 17 % 11 = 6
h4(17) = (6 + 4) % 11 = 10
h(17) = 17 % 11 = 6
h5(17) = (6 + 5) % 11 = 0
h(17) = 17 % 11 = 6
h6(17) = (6 + 6) % 11 = 1
-= EINFUEGEN bei 1! =-
[22, 17, 35, -1, 26, 38, 48, 29, 4, 20, 42]
Viele Grüße
Karl
|
|
|
|
