According to Wikipedia,
A coucal is one of about 30 species of birds in the cuckoo family. All of them belong in the subfamily Centropodinae and the genus Centropus. Unlike many Old World cuckoos, coucals are not brood parasites.
The idea is to have a smarter open-addressing strategy based on kicking an existing entry if a collision occurs. This is why the name Cuckoo hashtable was chosen.
Note that the name is a bit misleading: a typical cuckoo will not only kick an existing foe, but will consequently kill it (nature, you scary!). Here, we only relocate it, reason why I choose the Coucal, a nicer cuckoo member who does not destroy existing entries – I mean, existing eggs!
This implementation has the following features:
- guaranteed constant time (Θ(1)) lookup
- guaranteed constant time (Θ(1)) delete or replace
- average constant time (O(1)) insert
- one large memory chunk for table (and one for the key pool)
- simple enumeration
This implementation has been tested since July 2013 in HTTrack, and so far, no bugs were reported (the only issues spotted were bugs in upstream code that was corrupting existing keys)
Please have a look at this library implementation: https://github.com/xroche/coucal
TL;DR: cuckoo hashtables are both efficient and smart!