Cuckoo Hashing

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

Description

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
Show full summary Hide full summary

Similar

Hash Functions
msladey
Static Perfect Hashing
msladey
Lowest Common Ancestor
msladey
Data Structures & Algorithms
Reuben Caruana
Data Structures & Algorithms
Martyn Haigh
Computer science unit 2
Somto Ibeme
Algorithms ♡
lauren ♥
Computational Thinking ♡
lauren ♥
Searching and Sorting Algorithms
Josh Calvert
Systems Software Revision
cocacolai
Grafy I.
Michal Roch