But a lot depends on the algorithm. If the algorithm can be parallelized using SIMD or MIMD instructions--or just operating on longer words than a single (char)--then it doesn't necessarily matter that the hash is more complex; all that matters is whether the CPU can finish the job as fast as a simpler algorithm that updates state on every character.
The reason why universal hashes, etc, are competitive with brain-dead hashes for longish strings is because of cache locality--it takes longer to move data back-and-forth from cache then it does to compute even the more complex operations. So, again, you might still be able to compete with simpler algorithms if you still share the same bottleneck. There may be exploitable bottlenecks even for short, cache-local strings.
I don't think there has been enough work in this area. People have continued using the same hashes invented in the 1990s, in particular DJB's algorithm. As an aside, DJB fawns over "crit-bit" trees: http://cr.yp.to/critbit.html
Copyright © 2017, Eklektix, Inc.
Comments and public postings are copyrighted by their creators.
Linux is a registered trademark of Linus Torvalds