Informatiker Board | Algorithmen | Suche bei universellen hashing

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Suche bei universellen hashing

» Hallo Gast [Anmelden|Registrieren]

Letzter Beitrag | Erster ungelesener Beitrag

Druckvorschau | An Freund senden | Thema zu Favoriten hinzufügen

Suche bei universellen hashing

Autor

Beitrag

« Vorheriges Thema | Nächstes Thema »

Hasher
unregistriert

Suche bei universellen hashing

Zitatantwort auf diesen Beitrag erstellen

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

17.03.2014 18:23

Karlito Karlito ist männlich

Kaiser

Dabei seit: 11.04.2011
Beiträge: 1.461

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

19.03.2014 15:45

Nehmen Sie Karlito in Ihre Freundesliste auf

Baumstruktur | Brettstruktur

Informatiker Board » Themengebiete » Praktische Informatik » Algorithmen » Suche bei universellen hashing