On 1 Dec 2014 at 13:45, Gottlob Frege wrote:
Why should the lack of a cryptographically safe hash matter when you are not doing cryptography?
It doesn't really matter what hash is used in internal data structures. (Although obviously there are desirable properties such as having uniform spread to minimise bucket collisions and improve lookup speed.)
Denial of Service attack - I carefully force the input data such that the hashes collide and you get worse-case hash-table performance. This is a real attack. Python and a few other languages have already fixed their hashes, we have not.
Actually we need a new std::safe_hash<> I think, one explicitly prohibited from being a trivial hash. I'd personally like to see that become the default hash for unordered_map et al, and let the programmer choose std::hash where safe. BTW I think MSVC/Dinkumware *has* fixed their std::hash<>, theirs is several orders of magntitude more complex than the trivial hash libstdc++ uses. Indeed this leads to MSVC's apparent poor unordered_map performance when compared to GCC (about a 12-40% performance loss). Stephan can probably confirm or refute this claim of MSVC/Dinkumware having a safe hash though. It may just be he uses a well distributed hash instead of a trivial hash, not one cryptographically safe.
As I said,the hash was only one reason. There were others, IIRC. I do agree that unordered_map will become more popular in the future, so that the issue is lessened. (Also, map should have been called ordered_map, and unordered_map called 'map'...)
FYI my proposed concurrent_unordered_map is particularly collision resistant, and therefore much less prone to DDoS attacks. I use a linear table scan of 16 byte items to resolve collision, so it takes quite a while for that to become a serious performance issue. Note I didn't choose this design for DDoS attacks, rather due to the proposed design having an extremely costly rehash(), so much so that you'd put up with a lot of collision before expending the enormous cost of rehashing. Niall -- ned Productions Limited Consulting http://www.nedproductions.biz/ http://ie.linkedin.com/in/nialldouglas/