Cuckoo Hashing交獻分析

Rasmus Pagh 1
IT University of Copenhagen, Rued Langgaardsvej 7, 2300 Kobenhavn S, Denmark
Flemming Friche Rodler 2
ON-AIR A/S, Digtervejen 9, 9200 Aalborg SV, Denmark.

===========================================================
1. 作者所做實驗的內容:

We present a simple dictionary with worst case constant lookup time, equaling the
theoretical performance of the classic dynamic perfect hashing scheme of Dietzfelbinger
et al. (Dynamic perfect hashing: Upper and lower bounds. SIAM J. Comput.,
23(4):738–761, 1994). The space usage is similar to that of binary search trees.
Besides being conceptually much simpler than previous dynamic dictionaries with
worst case constant lookup time, our data structure is interesting in that it does
not use perfect hashing, but rather a variant of open addressing where keys can be
moved back in their probe sequences. An implementation inspired by our algorithm,
but using weaker hash functions, is found to be quite practical. It is competitive
with the best known dictionaries having an average case (but no nontrivial worst
case) guarantee on lookup time.
2. 實驗方案及所用到的方法、手段
3. 實驗結論與分析
4. 實驗中存在的不足 (按: 找到人家實驗中存在的問題與不足，也就找到了自己努力的方向)
5. 作者的實驗思想  (按: 當你透過字裡行間把握了作者的實驗主導思想，就可以對實驗方案進行高屋建瓴地分析與取捨了)
===========================================================
The Dynamic Dictionary problem is considered: provide an algorithm for storing a dynamic set, allowing the operation insert, delete and look up. A Dynamic Perfect Hashing Strategy is given:  a randomized algorithm for the dynamic perfect dictionary problem that takes O(1) worst case , time for lookups, and O(1) amortized expected time for insertions and deletions; it uses