On risks of using a high performance hashing scheme with common universal classes [Elektronische Ressource] / von Ulf Schellbach

On Risks of Using aHigh Performance Hashing SchemeWith Common Universal ClassesDissertation zur Erlangung des akademischen GradesDoctor rerum naturalium (Dr. rer. nat.)¨ ¨vorgelegt der Fakultat fur Informatik und Automatisierungder Technischen Universitat¨ IlmenauvonDipl.-Inform. Ulf SchellbachVorgelegt am: 27. Marz¨ 2009Verteidigt am: 3. Juli 2009Gutachter:1. Univ.-Prof. Dr. rer. nat. (USA) M. Dietzfelbinger, TechnischeUniversitat¨ Ilmenau2. Associate Prof. Rasmus Pagh, IT University of Copenhagen3. Assistant Prof. Philipp Woelfel, University of Calgaryurn:nbn:de:gbv:ilm1-2009000150Dedicated to LifeiSummaryThe contribution of this thesis is a mathematical analysis a high performancehashing scheme called cuckoo hashing when combined with two very simpleand efficient classes of functions that we refer to as the multiplicative class andthe linear class, respectively. We prove that cuckoo hashing tends to work badlywith these classes. In order to show this, we investigate how the inner structureof such functions influences the behavior of the cuckoo scheme when a set S ofkeys is inserted into initially empty tables.Cuckoo Hashing uses two tables of size m each. It is known that the insertion ofan arbitrary set S of size n=(1 d)m for an arbitrary constantd2(0, 1) (whichyields a load factor n/(2m) of up to 1/2) fails with probability O(1/n) if the hashfunctions are chosen from anW(log n)-wise independent class.