Wir betrachten randomisierte Algorithmen, die bei Eingabe einer Menge S von n Schlüsseln aus einem Universum U,oder einer Menge von n Schlüssel-Wert-Paaren eine Datenstruktur für eine der folgenden Aufgaben bauen.Bei Aufruf der Operation lookup für einen Schlüssel x aus U: * Entscheide, ob x Element von S ist (Mengenzugehörigkeitstester [MZT]). * Falls x aus S ist, gib den Wert zurück welcher x zugeordnet ist. Ansonsten gib einen Wert mit der Interpretation „x ist nicht aus S“ zurück (Wörterbuch [WB]) oder gib einen beliebigen Wert zurück (Retrieval-Datenstruktur [RDS]). * Falls x aus S ist, gib eine von x abhängige natürliche Zahl zurück, wobei für alle x aus S diese Zahlen paarweise verschieden sind und ihr Wertebereich in etwa die Größe n hat (perfekte Hashfunktion [PHF]). Die Datenstrukturen die wir behandeln sind Varianten von Cuckoo-Hashing und des Bloomier-Filters, welchen die gleiche einfache Struktur zu Grunde liegt. Sie bestehen aus einer Tabelle mit m Zellen der Breite r Bitssowie einer konstanten Anzahl an Hashfunktionen, welche benutzt werden, um die Elemente aus U auf eine konstante Anzahl an Tabellenzellen abzubilden.Unter der Annahme voll zufälliger Hashfunktionen beschäftigen wir uns damit, wie diese Datenstrukturen in Linearzeit (bezüglich n) konstruiert werden können und welche Ladung n/m bzw. welcher Platzverbrauch m·r in Abhängigkeit vom Zeitbedarf für lookup erreicht werden kann.Dies führt zu der Frage, ob ein bipartiter Zufallsgraph mit n Knoten (Schlüsseln) links und m Knoten (Zellen) rechts und Kanten bestimmt über die Hashfunktionenein Matching eines bestimmten Typs hat und darüber hinaus, wie solch ein Matching effizient berechnet werden kann. Schwerpunkte der Dissertation sind: * die Optimierung der Lookup-Zeit für WB und MZT (basierend auf Cuckoo-Hashing) bezüglich: (i) einer Beschränkung der durchschnittlichen Anzahl an Zellenzugriffen, (ii) der erwarteten Anzahl an Seitenzugriffen unter der Annahme, dass die Tabelle (Speicher) in Speicherseiten gleicher Größe unterteilt ist. * die Minimierung des Platzbedarfs von RDS und PHF (basierend auf dem Bloomier-Filter), wobei für jeden Schlüssel die Anzahl der Zellenzugriffe nach oben durch eine Konstante beschränkt ist. * eine effiziente Simulation voll zufälliger Hashfunktionen, welche von allen behandelten Datenstrukturen vorausgesetzt werden.
We study randomized algorithms that take as input a set S of n keys from some large universe Uor a set of n key-value pairs, associating each key from S with a specific value, and build a data structure that solves one of the following tasks. On calling the operation lookup for a key x from U: * Decide set membership with respect to S (membership tester). * If x is in S, then return the value associated with x. If x is in U-S, then return either some specific value interpreted as “x is not in S” (dictionary), or some arbitrary value (retrieval data structure). * If x is in S, then return a natural number associated with x, from a range with size close to n, where for all elements of S the numbers are pairwise distinct. The numbers for elements x from U-S are arbitrary (perfect hash function). The data structures that we cover are variations of cuckoo hashing and Bloomier filterwhich have the same simple structure. They consist of a table with m cells, each capable of holding entries of size r bits, as well as a constant number of hash functions, which are used to map the elements from U to a constant number of table cells.Assuming fully random hash functions, we will discuss how the data structures can be constructed in time linear in n, and what load n/mor space consumption m·r can be achieved in trade-off with the time for lookup. This leads to the question whether a random bipartite graph with n nodes (keys) on the left, m nodes (cells) on the right,and edges determined by the hash functions, asymptotically almost surely hasa matching of a certain type, and furthermore, how such a matching can be calculated efficiently. The focus of this thesis concerns: * optimizing the lookup time for dictionary and membership tester (based on cuckoo hashing) with respect to: (i) a bound on the average number of cell probes, (ii) the expected number of page accesses in a setting where the table (memory) is subdivided into pages of the same size. * minimizing the space usage of the retrieval data structure and perfect hash function (based on Bloomier filter), when for each key the number of cell probes for lookup is upper bounded by a constant. * an efficient simulation of fully random hash functions as needed by the data structures.