Suche bei universellen hashing |
| 17.03.2014, 18:23 | Auf diesen Beitrag antworten » |
| Hasher | 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 |
|
|
|
| 19.03.2014, 15:45 | Auf diesen Beitrag antworten » |
| Karlito | 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 |
|
|
Verwandte Themen
| Die Beliebtesten » |
|
| Die Größten » |
| Die Neuesten » |
|
