information:extraction, structural:expansion
Cuckoo hashing

Cuckoo hashing is a form of open addressing collision resolution technique which guarantees O (1) {\displaystyle O(1)} worst-case lookup complexity and constant amortized time for insertions. The collision is resolved through maintaining two hash tables, each having its own hashing function, and collided slot gets replaced with the given item, and the preoccupied element of the slot gets displaced into the other hash table. The process continues until every key has its own spot in the empty buckets of the tables; if the procedure enters into infinite loop —which is identified through maintaining a threshold loop counter—both hash tables get rehashed with newer hash functions and the procedure continues.