Informatiker Board (http://www.informatikerboard.de/board/index.php)
- Themengebiete (http://www.informatikerboard.de/board/board.php?boardid=1)
--- Praktische Informatik (http://www.informatikerboard.de/board/board.php?boardid=6)
---- Algorithmen (http://www.informatikerboard.de/board/board.php?boardid=17)
----- Suche bei universellen hashing (http://www.informatikerboard.de/board/thread.php?threadid=1829)
Geschrieben von Hasher am 17.03.2014 um 18:23:
Suche bei universellen hashing
Meine Frage:
Wie sucht man bei universellen hashing in der hashtabelle nach einem Schlüssel? Ist dann die hashfunktion bekannt, die eigentlich zufällig ist oder wie funktioniert das, dass man nicht im worstcase bei m hashtabellenelementen o (n) für Suche hat.
Meine Ideen:
Bei c universellen hashing wählt man meines Wissens eine zufällige hashfunktion aus einer Menge von hashfunktionen, sodass die kollisionswahrscheinlichkeit für zwei Schlüssel die kardinalität der hashfunktionen durch die Anzahl der Elemente in der hashtabelle ist
Geschrieben von Karlito am 19.03.2014 um 15:45:
Hallöchen,
soweit ich weiß ist es so, dass wenn die Hashtabelle vergrößert wird, wird eine neue Hashfunktion verwendet, welche für den Umfang der Hashtabelle geeignet ist.
D.h. mit jeder Größenänderung wird eine neue Tabelle angelegt, wobei die alte Hastabelle bestehen bleibt. Idealisiert ist der Zugriff auf eine Hash-Tabelle (suche) in der Komplexitätsklasse O(1), d.h. konstant. Somit wäre der Zugriff auf einen Datensatz bei n Hashtabellen O(n) im worst case....
VG,
Karlito
Forensoftware: Burning Board, entwickelt von WoltLab GmbH