Hashfunktionen < Datenstrukturen < Schule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 21:57 Di 20.09.2005 | | Autor: | Jacek |
Ich habe diese Frage in keinem Forum auf anderen Internetseiten gestellt.
Guten Tag,
ich habe in nächster Zeit eine Prüfung in Informatik, dabei könnte viellciht folgende Frage gestellt werden:
"Ist die Funktion h(x)=erste Dezimalstelle von x eine gute Hashfunktion?"
Könnten Sie mir dabei vielleicht helfen eine Antwort (kurz) zu finden.
Ich wäre zum Dank verpflichtet.
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 22:23 Di 20.09.2005 | | Autor: | Marc |
Hallo Jacek,
![[willkommenvh]](/images/smileys/willkommenvh.png "[willkommenvh]")
> ich habe in nächster Zeit eine Prüfung in Informatik,
> dabei könnte viellciht folgende Frage gestellt werden:
> "Ist die Funktion h(x)=erste Dezimalstelle von x eine gute
> Hashfunktion?"
>
> Könnten Sie mir dabei vielleicht helfen eine Antwort (kurz)
> zu finden.
Was sind denn deine Gedanken dazu?
Mein erster Gedanke war: Falls nur Integer-Werte gehasht werden sollen, wäre es wohl keine gute Hashfunktion...
Viele Grüße,
Marc
|
|
|
| |
|
Hallo Jacek,
![[willkommenir]](/images/smileys/willkommenir.png "[willkommenir]")
> dabei könnte viellciht folgende Frage gestellt werden:
> "Ist die Funktion h(x)=erste Dezimalstelle von x eine gute
> Hashfunktion?"
Ich denke nicht. Marc, hat dir ja schon gezeigt, was passieren würde, wenn wir nur Werte der Form: [mm] $\pm X.\red{0}c_1c_2\cdots$ [/mm] abspeichern; Sie werden alle an der selben Stelle gespeichert. Die Ineffizienz von [mm] $h\!$ [/mm] wird aber (z.B.) auch schon für die Zahlen [mm] $0.0,0.1,0.2,\dotsc,9.9$ [/mm] deutlich. Du hättest sogar hier schon 100 Zahlen, die Du auf 10 Speicherplätze zu verteilen hättest. Ob das gut ist?
Viele Grüße
Karl
|
|
|
| |
|
| Status: |
(Antwort) fertig | | Datum: | 09:58 Do 22.09.2005 | | Autor: | bazzzty |
> "Ist die Funktion h(x)=erste Dezimalstelle von x eine gute
> Hashfunktion?"
Mein erster Gedanke: Das kommt darauf an. Die wichtigen Fragen wären:
* Aus welcher Menge stammen die zu hashenden Schlüssel? Welche Verteilung nimmt man an, d.h. wie wahrscheinlich ist es, daß ein bestimmter Wert in der Eingabe vorkommt?
* Welche Hashwerte sind zulässig?
Unter diesen Rahmenbedingungen ist eine Hashfunktion 'gut', wenn sie den Erwartungswert für die Anzahl der Kollisionen minimiert, was dasselbe ist, wie die Wahrscheinlichkeit zu minimieren, daß es zwischen *zwei* zufällig gemäß der Verteilung gezogenen Schlüssel zu einer Kollision kommt. Anders ausgedrückt: Eine Hashfunktion ist gut, wenn die Wahrscheinlichkeit, daß ein beliebiges nach der Verteilung gezogenes Element einen bestimmten Hashwert hat, für alle Hashwerte gleich groß ist.
Wenn nun z.B. die Schlüssel alle natürlichen Zahlen sind, aus denen gleichverteilt Zahlen ausgewählt werden, und als Hashwerte nur die Zahlen 1-9 in Frage kommen, dann ist das Auswählen der ersten Ziffer optimal, denn die Wahrscheinlichkeit einer Kollision ist genau 1/9, geringer geht es nicht. Auch bei Schlüsseln zwischen 1 und 99 ist das noch so, aber sobald man die Schlüsselmenge falsch einschränkt, z.B. auf 1 bis 2^16-1, oder die Verteilung ungeschickt asymmetrisch wird, verliert die Hashfunktion diese Eigenschaft.
Genauso falsch wäre die Hashfunktion, wenn mehr als 9 Hashwerte zur Verfügung stünden, die dann einfach nicht genutzt werden.
|
|
|
|
