Hash-Funktion
-
Hash-Tabellen sind ja sehr schnell, wenn es darum geht Elemnte anhand eines bekannten Schlüssel zu finden. Was sich jedoch bei den meisten Hash Tabellen als schwierig heraustellt, ist es das Objekt mit dem kleinsten Schlüssel (davon ausgehend, dass der Schlüssel ein numerischer Wert ist) zu finden.
Daherf ist meine Frage: Ist es möglich eine Hashfunktion zu konstruieren, die für kleine Schlüssel kleine Hashwerte liefert und für große Schlüssel große Hashwerte liefert?Viel dank im Voraus.
-
Welchen Sinn sollte das haben? Normalerweise sollten Hash-Funktionen gleichverteilte Werte liefern unabhaengig von der Groesse der Objekte.
-
Ist es je nach Methode nicht eigentlich am schwierigsten/langwierigsten die zuletzt eingetragenen Schlüssel zu finden, da die Berechnung bei einer besetzten Hashzelle wiederholt wird(mit Parameteränderung) und das solange bis eine freie Zelle gefunden wird oder der Algorithmus wieder die Zelle der ersten Berechnung findet(=>Voll)?
-
DaRe schrieb:
Ist es je nach Methode nicht eigentlich am schwierigsten/langwierigsten die zuletzt eingetragenen Schlüssel zu finden, da die Berechnung bei einer besetzten Hashzelle wiederholt wird(mit Parameteränderung) und das solange bis eine freie Zelle gefunden wird oder der Algorithmus wieder die Zelle der ersten Berechnung findet(=>Voll)?
Da gibt es verschiedene Wege. Mit einem recht schnellen new kann man zum Beispiel die Überläufer ruhig damit anlegen, also die Hashtable nur die ersten Knoten (oder sogar nur Zeiger drauf) vieler verketteter Listen sein lassen.
-
Anonymer_Typ schrieb:
Hash-Tabellen sind ja sehr schnell, wenn es darum geht Elemnte anhand eines bekannten Schlüssel zu finden. Was sich jedoch bei den meisten Hash Tabellen als schwierig heraustellt, ist es das Objekt mit dem kleinsten Schlüssel (davon ausgehend, dass der Schlüssel ein numerischer Wert ist) zu finden.
Daherf ist meine Frage: Ist es möglich eine Hashfunktion zu konstruieren, die für kleine Schlüssel kleine Hashwerte liefert und für große Schlüssel große Hashwerte liefert?Viel dank im Voraus.
Es gibt glaub ich ordnungserhaltene Hashfunktion... oder halt Suchbäume.