Wear Minimization for Cuckoo Hashing: How Not to Throw a Lot of Eggs into One Basket

الأصل · EN

We study wear-leveling techniques for cuckoo hashing, showing that it is possible to achieve a memory wear bound of n+O(1) after the insertion of n items into a table of size Cn for a suitable constant C using cuckoo hashing. Moreover, we study our cuckoo hashing method empirically, showing that it significantly improves on the memory wear performance for classic cuckoo hashing and linear probing in practice.