Flashcards
Cuckoo Hashing
Cards in this deck (5)
- 1What is Perfect Hashing?We call a hashing technique perfect if O(1) memory accesses are required to perform a search in the worst case.
- 2Explain the insert procedure of cuckoo hashingAttempt to put x in position h1(x), if empty stop. Let y be key currently in position h1(x). Evict y and replace with x. Let pos be the other position y's allowed in. Attempt to put y in pos. If empty stop. Else, x = y.
- 3If the worst case time complexity of performing any n operations is O(n), what is the amortised worst-cast time complexity of one operation?O(1)
- 4What are the complexities of the Cuckoo Hashing scheme?Lookup/Delete takes O(1) worst case time. Space required is O(n). An insert takes amortised expected O(1) time.
- 5What do we do if we still have an evicted key after moving around keys n times?Rehash the table