3 ms·

HashSets are using a HashMap behind the scenes, they put a "present" placeholder value in the map when adding an element to the set: https://github.com/openjdk-

by rzzzt 5y ago

HashSets are using a HashMap behind the scenes, they put a "present" placeholder value in the map when adding an element to the set: https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89a19a29bb9f9807d2a28351ed7f7df/src/share/classes/java/util/HashSet.java#L204-L218 https://github.com/openjdk-mirror/jdk7u-jdk/blob/f4d80957e89...

elric 5y ago
I'm not sure I understand your point. Yes, HashSet uses HashMap internally. But that's an implementation detail. I could have a Set<Foo> without knowing what the implementation is. If it's a TreeSet, things will work fine (as those use Comparators internally, and those don't usually rely on hashcode). If it's a HashMap, you can be boned without ever knowing why. IMO people are aware of the "mutable hashcode" issue when using maps, because you have to think about what the key of a map is when you're defining it, which is a good opportunity to remember that Foo is mutable. When you're using a Set, there's no key, only a value, which can sometimes be used as a key as an implementation detail, but there's no mental trigger.
- rzzzt 5y ago
  You mentioned HashSets as another, distinct source of problems; I wanted to highlight that these two are the same thing behind the scenes, as the backing map's key set is doing the heavy lifting. It definitely is an implementation detail, and I can't say that all JDK variants employ the same trick, but a fair few of them do, given that most of them share the same set of java.lang classes.
  - rzzzt 5y ago
    Just an addendum, sorry for the double post: I checked two additional implementations in the meantime. Apache Harmony: https://github.com/apache/harmony-classlib/blob/ee663b95e84093405985d9557a925b651a0f69b3/modules/luni/src/main/java/java/util/HashSet.java#L85-L96 https://github.com/apache/harmony-classlib/blob/ee663b95e840... GNU Classpath: https://github.com/ingelabs/classpath/blob/a96698f67357fddbe2026409d0113a35504bf6ab/java/util/HashSet.java#L142-L152 https://github.com/ingelabs/classpath/blob/a96698f67357fddbe...

by rzzzt 5y ago

elric 5y ago

I'm not sure I understand your point. Yes, HashSet uses HashMap internally. But that's an implementation detail. I could have a Set<Foo> without knowing what the implementation is. If it's a TreeSet, things will work fine (as those use Comparators internally, and those don't usually rely on hashcode). If it's a HashMap, you can be boned without ever knowing why. IMO people are aware of the "mutable hashcode" issue when using maps, because you have to think about what the key of a map is when you're defining it, which is a good opportunity to remember that Foo is mutable. When you're using a Set, there's no key, only a value, which can sometimes be used as a key as an implementation detail, but there's no mental trigger.

rzzzt 5y ago
You mentioned HashSets as another, distinct source of problems; I wanted to highlight that these two are the same thing behind the scenes, as the backing map's key set is doing the heavy lifting. It definitely is an implementation detail, and I can't say that all JDK variants employ the same trick, but a fair few of them do, given that most of them share the same set of java.lang classes.
- rzzzt 5y ago
  Just an addendum, sorry for the double post: I checked two additional implementations in the meantime. Apache Harmony: https://github.com/apache/harmony-classlib/blob/ee663b95e84093405985d9557a925b651a0f69b3/modules/luni/src/main/java/java/util/HashSet.java#L85-L96 https://github.com/apache/harmony-classlib/blob/ee663b95e840... GNU Classpath: https://github.com/ingelabs/classpath/blob/a96698f67357fddbe2026409d0113a35504bf6ab/java/util/HashSet.java#L142-L152 https://github.com/ingelabs/classpath/blob/a96698f67357fddbe...