2
$\begingroup$

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!

$\endgroup$
3
  • $\begingroup$ What are you looking up, just their existence? Or a mapping, and if yes, to what? Do you need to support dynamic updates, and if yes which (adding/removing/etc)? $\endgroup$
    – orlp
    Feb 1, 2021 at 8:16
  • $\begingroup$ Hi orlp! Yes I need mapping (to a structure in memory (void *)). Dynamic updates would be done by looking up that pointer to my entry structure and changing the status from free to allocated, for example. But it would be nice to be able to add and remove items from the structure. $\endgroup$ Feb 1, 2021 at 8:23
  • $\begingroup$ As a rule of thumb, hash-based dictionaries tend to be much faster than tree-based ones in practice, especially if you keep occupancy fairly low. $\endgroup$ Feb 2, 2021 at 23:14

2 Answers 2

1
$\begingroup$

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.

$\endgroup$
2
  • 1
    $\begingroup$ en.wikipedia.org/wiki/Judy_array $\endgroup$
    – Pseudonym
    Feb 2, 2021 at 5:34
  • $\begingroup$ Decent but potentially burns a lot of memory -- each distinct 3-byte prefix stored requires its own 256-entry table (1KB on a 32-bit system), only 1 entry of which might be in use. Consider using smaller-way tries at the lower levels -- e.g. 3 256-way levels, then 2 16-way levels. $\endgroup$ Feb 2, 2021 at 23:21
1
$\begingroup$

It sounds like the only operations you need to do are lookup, insert, and delete. If so, a simple data structure is a hashtable. It should achieve constant-time access on average.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.