The contribution of this thesis is a mathematical analysis a high performance hashing scheme called cuckoo hashing when combined with two very simple and efficient classes of functions that we refer to as the multiplicative class and the linear class, respectively. We prove that cuckoo hashing tends to work badly with these classes. In order to show this, we investigate how the inner structure of such functions influences the behavior of the cuckoo scheme when a set $S$ of keys is inserted into initially empty tables. Cuckoo Hashing uses two tables of size $m$ each. It is known that the insertion of an arbitrary set $S$ of size $n = (1 - \delta)m$ for an arbitrary constant $\delta \in (0,1)$ (which yields a \emph{load factor} $n/(2m)$ of up to $1/2$) fails with probability $O(1/n)$ if the hash functions are chosen from an $\Omega(\log n)$-wise independent class. This leads to the result of expected amortized constant time for a single insertion. In contrast to this we prove lower bounds of the following kind: If $S$ is a uniformly random chosen set of size $n = m/2$ (leading to a load factor of only $1/4$ (!)) then the insertion of $S$ fails with probability $\Omega(1)$, or even with probability $1 - o(1)$, if the hash functions are either hosen from the multiplicative or the linear class. This answers an open question that was already raised by the inventors of cuckoo hashing, Pagh and Rodler, who observed in experiments that cuckoo hashing exhibits a bad behavior when combined with the multiplicative class. Our results implicitly show that the quality of pairwise independence is not sufficient for a hash class to work well with cuckoo hashing. Moreover, our work exemplifies that a recent result of Mitzenmacher and Vadhan, who prove that under certain constraints simple universal functions yield values that are highly independent and very lose to uniform random, has to be applied with care: It may not hold if the constraints are not satisfied.
Der Beitrag dieser Dissertation ist die mathematische Analyse eines Hashing-Verfahrens namens Cuckoo Hashing in Kombination mit einfachen, effizient aus\-wertbaren Funktionen zweier Hashklassen, die wir die multiplikative Klasse bzw. die lineare Klasse nennen. Cuckoo Hashing hat die deutliche Tendenz, mit Funktionen dieser beiden Klassen schlecht zu funktionieren. Um dies zu beweisen, untersuchen wir den Einfluss der inneren Struktur solcher Funktionen auf das Verhalten des Cuckoo-Verfahrens, wenn der Versuch unternommen wird, eine Schlüsselmenge $S$ in anfangs leere Tabellen einzufügen. Cuckoo Hashing verwendet zwei Tabellen der jeweiligen Größe $m$. Man weiß, dass die Einfügung einer beliebigen Menge $S$ der Größe $n = (1 - \delta)m$ für eine beliebige Konstante $\delta \in (0,1)$ (was einen Lastfaktor $n/(2m)$ von bis zu $1/2$ liefert) mit Wahrscheinlichkeit $O(1/n)$ fehlschlägt, falls die Hashfunktionen aus einer $\Omega(\log n)$-fach unabhängigen Klasse gewählt werden. Damit läßt sich beweisen, dass die erwarteten amortisierten Kosten einer einzelnen Einfügung konstant sind. Demgegenüber beweisen wir untere Schranken der folgenden Art: Wenn $S$ eine uniform zufällig gewählte Schlüsselmenge der Größe $m/2$ ist (Lastfaktor $1/4$ (!)), dann schlägt die Einfügung von $S$ mit großer Wahrscheinlichkeit $\Omega(1)$, oder sogar $1 - o(1)$, fehl, falls Funktionen der multiplikativen bzw. der linearen Klasse gewählt werden. Damit beantworten wir eine Frage, die bereits von Pagh und Rodler aufgeworfen wurde, als sie mit Hilfe von Experimenten feststellten, dass es riskant ist, Cuckoo Hashing mit Funktionen der multiplikativen Klasse zu kombinieren. Unsere Resultate zeigen, dass paarweise Unabhängigkeit und uniforme Vertei\-lung der Hashwerte keine Garantie dafür ist, dass Cuckoo Hashing gut funktioniert. Zudem machen unsere Ergebnisse exemplarisch deutlich, dass bei der Anwendung eines kürzlich veröffentlichten Resultates von Mitzenmacher und Vadhan, welches besagt, dass selbst Funktionen aus einfachen, schwach universellen Klassen unter gewissen Bedingungen zu hochgradig unabhängigen und fast uniform zufälligen Werten führen können, Vorsicht geboten ist: Falls dessen Bedingungen nicht erfüllt sind, gilt es unter Umständen nicht.