News for hackers. Stuff that matters.
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.
Re:Mapping Strings in C++ by ot on Wednesday April 12, 2017 @06:38PM (#14102387)
Unless you're talking about extremely long strings, computing a hash takes far less time than a cache miss.
Re:Mapping Strings in C++ by jnordwick on Wednesday April 12, 2017 @06:53PM (#14102494)
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.