Hashtabelle < Datenbanken < Praktische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 16:47 Di 28.12.2010 | | Autor: | bobbert |
| Aufgabe | Betrachten sie die Hashfunktion h(x) = (2*x +5) mod 11
Außerdem ist folgende Hashtabelle gegeben:
[mm] \vmat{h_(x) & Element x \\ 0 & \\ 1 & 7 \\ 2 & 51 \\ 3 & \\ 4 & 16 \\ 5 & 5 \\ 6 & 40 \\ 7 & \\ 8 & 71 \\ 9 & 18 \\ 10 & }
[/mm]
a) Geben Sie die Art des Hashings an , mit der diese Hashtabelle erzeugt wurde.
b) Geben Sie die Reihenfolge an , in der die Elemente eingefügt wurden.
c) Geben Sie den Hashwert für die Zahl 42 an und fügen SIe sie in die Tabelle oben ein . |
Hi Leider,
1. kennt jemand eine gute Quelle in der ich mich in das Thema Hashtabelle am besten einlesen kann?
2.) Bei a) würde ich sagen , dass es geschlossenes Hashing ist , da sich lediglich ein Element in den Buckets befindet. In der Musterlösung wird außerdem noch gesagt, dass es sich um ein quadratisches Sondieren handelt.
Warum kann man es nicht auch als lineares Sondieren bezeichnen?
3.) Wie werden letztendlich die Haswerte in die Tabelle eingetragen ? Denn bei c) dem Wert 42 erhalte ich den Haswert = 1 // ( 89 mod 11 = 8 Rest 1)
Da der Bucket 1 bereits blockiert ist und es sich um ein geschlossenes Hashing handelt muss ich mir einen anderen Bucket suchen . Doch wie?
Vielen Dank im Voraus!
P.S. Ich habe diese Frage in keinem anderen Forum gepostet.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:52 Di 28.12.2010 | | Autor: | rainerS |
Hallo!
> Betrachten sie die Hashfunktion h(x) = (2*x +5) mod 11
>
> Außerdem ist folgende Hashtabelle gegeben:
> [mm]\vmat{h_(x) & Element x \\ 0 & \\ 1 & 7 \\ 2 & 51 \\ 3 & \\ 4 & 16 \\ 5 & 5 \\ 6 & 40 \\ 7 & \\ 8 & 71 \\ 9 & 18 \\ 10 & }[/mm]
>
>
> a) Geben Sie die Art des Hashings an , mit der diese
> Hashtabelle erzeugt wurde.
>
>
> b) Geben Sie die Reihenfolge an , in der die Elemente
> eingefügt wurden.
>
> c) Geben Sie den Hashwert für die Zahl 42 an und fügen
> SIe sie in die Tabelle oben ein .
> Hi Leider,
>
> 1. kennt jemand eine gute Quelle in der ich mich in das
> Thema Hashtabelle am besten einlesen kann?
Donald E. Knuth: The Art of Computer Programming. Vol. 3: Sorting and Searching
>
> 2.) Bei a) würde ich sagen , dass es geschlossenes Hashing
> ist , da sich lediglich ein Element in den Buckets
> befindet. In der Musterlösung wird außerdem noch gesagt,
> dass es sich um ein quadratisches Sondieren handelt.
> Warum kann man es nicht auch als lineares Sondieren
> bezeichnen?
>
> 3.) Wie werden letztendlich die Haswerte in die Tabelle
> eingetragen ? Denn bei c) dem Wert 42 erhalte ich den
> Haswert = 1 // ( 89 mod 11 = 8 Rest 1)
> Da der Bucket 1 bereits blockiert ist und es sich um ein
> geschlossenes Hashing handelt muss ich mir einen anderen
> Bucket suchen . Doch wie?
Du machst den zweiten Schritt vor dem ersten. Rechne dir erst einmal den Wert der Hashfunktion für alle einsortierten Elemente aus. Die, die an dieser Stelle stehen, wurden zuerst einsortiert.
Z.B. ist $h(7)=8$. Da bei 8 die 71 steht, wurde sie vor der 7 einsortiert. Ebenso: $h(71)=4$. Da dort die 16 steht, wurde sie vor der 71 einsortiert. Usw.
Viele Grüße
Rainer
|
|
|
| |
|
| Status: |
(Frage) überfällig  | | Datum: | 18:22 Mi 29.12.2010 | | Autor: | bobbert |
Klasse, vielen Dank Rainer! Deine Antwort hat mich ein ganzes Stück weitergebracht!
Noch zur Ergänzung: die übrigen Zahlen werden dann nach dem Prinzip der quadratischen Sondierung (y + 1, y + 4, y + 9, y + 16, . . .) in die Hashtabelle eingetragen:
$ [mm] \vmat{h_(x) & Element x \\ 0 & \\ 1 & 7 // da (y+(2)^2) \\ 2 & 51 (y+4^2) \\ 3 & \\ 4 & 16 \\ 5 & 5 \\ 6 & 40 (y + 3^2) \\ 7 & \\ 8 & 71 \\ 9 & 18 (y+1) \\ 10 & 42 (y+3^2) } [/mm] $
Beispiel:
18 hat den Rest 8. Da der Bucket 8 leider schon besetzt ist , verwende ich das quadratische sondieren um einen freien Bucket zu finden. [mm] y+1^1= [/mm] y+1. Ich gehe daher eins weiter.
7 hat auch den rest 8. Bucket y+0 & [mm] y+1^1 [/mm] sind schon besetzt daher gehe ich [mm] y+2^2 [/mm] Buckets weiter. Die Liste ist wie eine Loop, da es bei der Bucketsuche nach dem Ende wieder am Anfang weiter geht .
Frage: Die Sondierung kann ich mir also nicht aus der Hashfunktion erschließen, sondern sie ist irgendwo im Programmcode versteckt. Der einzige Weg herauszufinden welche Sondierung verwandt wurde ist, indem ich mir die Liste anschaue und gucke ob die Sortierung nach dem Muster einer linearen oder einer quadratischen Sondierung geschehen ist.
Wie finde ich heraus -und wie sortiere ich, wenn nach einem Double Hashing , d.h. durch eine 2. Funktion sondiert wurde?
(Im Skript steht: y + f2 (x), y + 2· f2 (x), ... Double Hashing (Schrittweite wird durch 2. Hashfunktion bestimmt))
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 19:20 Fr 31.12.2010 | | Autor: | matux |
$MATUXTEXT(ueberfaellige_frage)
|
|
|
|
