Earlier quoted context omitted.
Each cache entry needs a hash bucket so we can look up the entry in O(1), and we need more hash buckets than entries to minimize cache look up time. The hash bucket needs a copy of the element for each hit (to verify we hit the correct hash bucket), and a possible link to the next hash bucket, just in case we got a hash collision (we still need to store that link in memory as a null pointer regardless). [1] The strin…
Instead of building hash tables with buckets (and a linked list in case of hash collision), why not use a flat array based hash table and open addressing?
The problem is that it works really great for static data, but doesn’t work for dynamic data as cleanly as using a linked list to handle collisions.
The one thing I would do differently is that Deadwood (MaraDNS’s recursive/blacklist DNS server) adds individual elements with malloc() and removes them with free(); doing things that way is OK for relatively small data sets on a desktop class computer, but some embedded systems don’t handle the stress of a lot of malloc() and free()s very well, and doing it that way uses a significant amount of memory per element.