3 ms·
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 tho
by jnordwick 10y ago
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.
- 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.