What data structure to use for large scale DHCP server What data structure would one use to keep a large number of IP addresses (v4 and v6, but not at the same time if that makes a difference), and I'm talking about millions, preferably hundreds of millions at a time for fast look-up.
The preference would be for fast look-up. Initial filling of the data structure is not too big of a concern. To have a small memory footprint is not also a big concern, but it would be nice to have that part as small as possible.
I was thinking in lines of using some sort of binary tree, but don't know if hash map would suffice...
Thanks in advance!
A good data structure for IPv4 translation is a 256-way trie, this means any lookup always requires exactly 4 memory accesses, and shared prefixes will be hot in cache.
You can do the same for IPv6 but implementing a unique suffix check (instead of always expanding trie nodes) is probably worth it.