4 ms·
If you don't need sorted search (lower/upper bound) or prefix search I doubt even a good trie would beat a good hash table. Have you tried google::dense_hash_ma
by ot 10y ago
If you don't need sorted search (lower/upper bound) or prefix search I doubt even a good trie would beat a good hash table. Have you tried google::dense_hash_map? std::unordered_map is slower because it uses chaining to resolve collisions.
- jnordwick 10y agoTries have the incredibly useful feature that they fail fast and match fast when you get to a unique prefix. Hash you always need to process the full string though.
- ot 10y agoUnless you're talking about extremely long strings, computing a hash takes far less time than a cache miss.
- jnordwick 10y agoYeah, the most cache-friendly structure is going to win, but failing fast means no strcmp test if you happen to get a collision, which is potential miss to fetch the characters. And if the hash uses bucket chaining, the programming gods help you. On an interview I was once asked to calculate the latency on a hash fetch in Java with the JDK String, hit and miss. It all basically boils down to how many caches misses are you going to have. I literally just counted up the memory accesses and counted up the hits and misses then gave an answer for cold and hot cache. Then we worked on rewriting it.