2 ms·
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?
by kccqzy 7y ago
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?
- strenholme 7y agoI actually tried that with MaraDNS in the pre-1.0 days (in case of collision, go forward in hash array N elements until there is no collision). 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.
- GekkePrutser 7y agoBut the data is fairly static isn't it? You're not constantly updating the blacklists?
- strenholme 7y agoWe’re using the same hash to both store blacklist data and cache dynamic DNS data. Yes, we could put the blacklist in a separate data structure, but doing it this way made adding blacklist support a one-day instead of a two-month (shorter, if I use something like sqlite) project.