2806378
| 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 |
Want to create your own Flashcards for free with GoConqr? Learn more.