4 ms·
Until recently I don't think any major hash table implementation (e.g. not Java, STL, Python, Ruby, etc) used a cryptographically secure hashing algorithm. They
by tibbe 13y ago
Until recently I don't think any major hash table implementation (e.g. not Java, STL, Python, Ruby, etc) used a cryptographically secure hashing algorithm. They're just too slow. Slow enough that you might as well use a tree-based data structure, which doesn't suffer from hash-collision based attacks.
This is changing a bit now when SipHash is available. Unfortunately SipHash still is a bit too slow and forces an uncomfortable trade-off.
- mcguire 13y ago"Unfortunately SipHash still is a bit too slow and forces an uncomfortable trade-off." 2.6x slower than DJB2 in my recent Rust trial. (SipHash is the hashing function in Rust's standard library.)
- aweisberg 13y agoI would be really surprised to find that a tree is faster then a fast cryptographic hash function like SIP hash. Cache misses to main memory are worth 10s of instructions and that number is going up in many cases. Hash functions can be pretty efficient at allowing the processor to run multiple instructions in parallel. If you know the tree will be cached and/or the keys you have to hash are large then sure a tree might be a win, but hashing a small key might only be the same as two or three cache misses. Comparing tree nodes is not instruction free either. I think it is really a case by case sort of thing, but there is no substitute for measuring (and nailing down the comparison to specific hash functions).