3 ms·

> But with open addressing we can avoid that. In risk management there exist several different approaches: accept, mitigate, transfer, avoid. What makes you th

> But with open addressing we can avoid that. In risk management there exist several different approaches: accept, mitigate, transfer, avoid. What makes you think that this design must avoid certain risks? The developers of standard libraries like Java usually base their decisions on industry feedback, IIRC, Oracle team did have a lot of telemetry data and they are good engineers. Do you have any insights proving that their approach is wrong?

tialaramex 1y ago
> IIRC, Oracle team did have a lot of telemetry data and they are good engineers. Do you have any insights proving that their approach is wrong? Time's arrow Java is a Sun (Microsystems) language, Oracle just bought the entire company much later. So one problem here is that you're imagining this like it's a decision somebody made this century but it isn't, it's a decision from the early 1990s. Computer Science is a young discipline. In the early 1990s the Open Addressed hash tables do exist but it's very usual to write the simple chained hash table with Closed Addressing and as I understand it that's exactly what is provided in Java 1.0. This data structure is today known to be a bad idea, and I've criticised the choice in say C++ to standardize the exact same data structure (as std::unordered_map) in 2011. But that's twenty years later. At some point (I believe this century?) Java engineers went back and improved their hash table to use trees not chains, but they were constrained by the baked in hash, so they could not have picked radically modern data structures which require a different hash strategy without significant disruption. When I got a CS degree the Introspective sort was so new I'd have to have read bleeding edge research papers to know about it. Today it's very silly if you claim you provide a standard library sort and it's not at least as good as Introsort. The Swiss Table is from the 2010s, it's new enough that there's a Youtube video of them introducing this data structure, not because they did that specifically on purpose but because they're giving a talk and obviously all talks are filmed and uploaded to Youtube these days. Hopskotch hashing - another popular Open Addressing strategy - is from 2008. So, the question isn't "Is this the best idea today?" but only "Given what they knew 30+ years ago, was this reasonable back then?" and yeah, of course it was reasonable back then but that doesn't magically mean it's the best choice now. Edited: Added paragraph about the later choice to use trees.
- ivan_gammel 1y ago
  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?
  - tialaramex 1y ago
    > 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.
    - ivan_gammel 1y ago
      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. See https://openjdk.org/jeps/254 https://openjdk.org/jeps/254

tialaramex 1y ago

> IIRC, Oracle team did have a lot of telemetry data and they are good engineers. Do you have any insights proving that their approach is wrong? Time's arrow Java is a Sun (Microsystems) language, Oracle just bought the entire company much later. So one problem here is that you're imagining this like it's a decision somebody made this century but it isn't, it's a decision from the early 1990s. Computer Science is a young discipline. In the early 1990s the Open Addressed hash tables do exist but it's very usual to write the simple chained hash table with Closed Addressing and as I understand it that's exactly what is provided in Java 1.0. This data structure is today known to be a bad idea, and I've criticised the choice in say C++ to standardize the exact same data structure (as std::unordered_map) in 2011. But that's twenty years later. At some point (I believe this century?) Java engineers went back and improved their hash table to use trees not chains, but they were constrained by the baked in hash, so they could not have picked radically modern data structures which require a different hash strategy without significant disruption. When I got a CS degree the Introspective sort was so new I'd have to have read bleeding edge research papers to know about it. Today it's very silly if you claim you provide a standard library sort and it's not at least as good as Introsort. The Swiss Table is from the 2010s, it's new enough that there's a Youtube video of them introducing this data structure, not because they did that specifically on purpose but because they're giving a talk and obviously all talks are filmed and uploaded to Youtube these days. Hopskotch hashing - another popular Open Addressing strategy - is from 2008. So, the question isn't "Is this the best idea today?" but only "Given what they knew 30+ years ago, was this reasonable back then?" and yeah, of course it was reasonable back then but that doesn't magically mean it's the best choice now. Edited: Added paragraph about the later choice to use trees.

ivan_gammel 1y ago
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?
- tialaramex 1y ago
  > 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.
  - ivan_gammel 1y ago
    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. See https://openjdk.org/jeps/254 https://openjdk.org/jeps/254