search

martinus / robin-hood-hashing

Fast & memory efficient hashtable based on robin hood hashing for C++11/14/17/20
https://gitter.im/martinus/robin-hood-hashing
MIT License
1.5k stars 142 forks source link

Quick Question #123

Closed Fr3DBr closed 3 years ago

Fr3DBr commented 3 years ago

Hey, would you recommend your unordered_map, for fast ipv4 matching ? I'm currently using std::unordered_map, however at 30~60k random IP addresses (4 byte integers) the lookup time starts to increase badly, so my question is, if your version would be recommended instead ? :)

chipsethan commented 3 years ago

Hash table is NOT the best data structure to handle IP addresses. I think you can compare some type of other data structures such as tries, suffix/prefix trees etc on Wikipedia.

martinus commented 3 years ago

I'd use something like robin_hood::unordered_flat_set<uint32_t> and represent the IP as an uint32_t. It should be faster, but better try the benchmark first.

Fr3DBr commented 3 years ago

In my tests, the fastest stl container for my case, was the std::unordered_map, however at a certain point, the lookup time increases exponentially hehe, anyways it seems robin_hood will be faster against most of the standard containers right ?