Re:Mapping Strings in C++
by jnordwick on Wednesday April 12, 2017 @05:01PM
(#14101711)
Tries 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.
[ Parent
| on HN ]
Unless you're talking about extremely long strings, computing a hash takes far less time than a cache miss.
Yeah, 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.