# Cuckoo Hashing

Flashcards by msladey, updated more than 1 year ago
 Created by msladey almost 6 years ago
7
0

Cuckoo Hashing

## Resource summary

 Question Answer What is Perfect Hashing? We call a hashing technique perfect if O(1) memory accesses are required to perform a search in the worst case. Explain the insert procedure of cuckoo hashing Attempt 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. If 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) What 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. What do we do if we still have an evicted key after moving around keys n times? Rehash the table

### Similar

Hash Functions
Static Perfect Hashing
Lowest Common Ancestor
Data Structures & Algorithms
Data Structures & Algorithms
Computer science unit 2
Algorithms ♡
Computational Thinking ♡
Searching and Sorting Algorithms
Systems Software Revision
Grafy I.