The standard library design choices are influenced not only by algorithm performance, but also by the use cases, existing contracts etc. You did not answer my question. Why do you think choosing alternative algorithm and breaking existing hash contract would be better?
> You did not answer my question. Why do you think choosing alternative algorithm and breaking existing hash contract would be better?
But I don't think Java should go break all this stuff. I'm just explaining why - in fact - we might want some cryptographic properties for hash algorithms. It can be true both that Java made reasonable tradeoffs at the time (in the 1990s) and that you shouldn't copy those choices today.
There's a long list of things Java picked that in hindsight weren't a good idea and in many cases it would have been really hard to guess that when Java was invented - however today you should not choose what Java did. Biggest example: 16-bit char. Java was invented when UCS-2 might happen, and in that light a 16-bit char makes sense. A few years later it's obvious UCS-2 is not possible and so you're choosing UTF-8 or UTF-16 and that's easy, pick UTF-8. People who'd already bought into the 16-bit char, such as Microsoft and Sun's Java team, were stuck with UTF-16 as a booby prize.
I think I lost you here actually. Hash by definition is just a mapping of arbitrary sets to large integers. Cryptographic hash adds computational complexity requirement so that it is prohibitively hard to find collisions (i.e. slow by design - bad choice for collections, which need fast hashing). Unstable hash is simply the one that is not guaranteed to persist between two different executions of a program (but it obviously has to be the same for equal objects in the same execution). Neither of collision resolution techniques requires cryptographic or even unstable hash. Collections only need hash to be sufficiently random on typical datasets for optimal performance. I would even question if unstable hash can mitigate the hash flooding attacks at all or it is possible to determine the hashing parameters of a black box somehow. Limit on number of parameters and efficiency at high load factors/high collisions is more important for security.
Many programming languages do not use open addressing and prefer chaining (Java, C#, Golang, std::unordered_map in C++) for simplicity and flexibility. There are certain trade offs to be considered, it is not a simple choice of absolutely the best known algorithms. I don't think Java made the wrong choice here. Notably, there was always a possibility to introduce a specific collection with some modern algorithm as an alternative to HashMap. It did not happen not least because it was not considered that important. I'm sure that in cases where open addressing offers substantial benefits, developers make conscious choice and use the appropriate data structures.
Regarding strings, since Java 9 (released long time ago) they can be stored in byte arrays if they contain only Latin-1 characters and core team is open for further enhancements.
No, the cryptographic hash functions are not slow by design. This is a nasty misunderstanding which leads to stuff like MD5(password) in PHP [not the PHK MD5 crypt() algorithm used in Unix systems in the 1990s, this was literally MD5(password) and it's a bad idea, do not do]
The cryptographic hash functions such as the SHA-2 family resist construction of a second pre-image, given N and H(N) there's no way for me to make M such that H(M) == H(N) but M != N that'll be faster than brute force trying all possible values for M. So far everything we have which achieves this is markedly slower than say FNV-1 which would once have been the most likely hashing algorithm for a hash table.
The one way password hashes, some of which are based on the cryptographic hashes, are slow by design. You should not use passwords, but on HN this seems like a lost cause so, assuming you insist on using passwords these algorithms are specifically what you need. Fighting about which one to use ("oh no, PBKDF2 isn't memory hard, blah blah blah") is also a bottomless hole of HN nonsnse, so, fine, pick whichever of them you're certain is the only correct one.
But we do ideally want some cryptographic properties for a hash to be used in a hash table and your instinct that just using a random factor and hoping won't work was correct. You need a correctly designed function, which is what SipHash is. What you want is some keyed function with a key K such that if I know N and H(K,N) but not K, I can't guess an M such that H(K,M) = H(K,N) but M != N except by brute force.
> Many programming languages do not use open addressing and prefer chaining (Java, C#, Golang, std::unordered_map in C++) for simplicity
This was true in Golang but today the map in Go is a modified Swiss Table which of course delivers improved performance. We've seen why Java is stuck where it is. The C++ std::unordered_map is known to have poor performance, C++ programmers have many alternatives [including of course Swiss Tables], such as a really nice modern offering from Boost.
I'm actually not sure about the guts of the C# hash tables at all, it's a complicated beast full of conditionally defined elements because it's reused by CLR internals as well as provided as a type for us users. It's not a conventional design of any sort, there seems to have been (which is common for Microsoft) some degree of Not Invented Here - just make it up as we go along. It's storing pre-calculated hashes with each key->value pair, it's tracking how many collisions it has, I dunno, I wouldn't do this, don't copy it without seeing hard numbers for why this is good.
