3 ms·

In many languages (including Python & Scala), sets are not much more than syntactic sugar on a hashmap-like datatype.

by darkr 5y ago

nynx 5y ago
In rust, hashsets are just hashmaps with a zero-sized type as the value, which results in all the extra getting optimized away.
- BenTheElder 5y ago
  A zero-sized type + hashmap for sets is also done in Go with a `struct{}`. [1][2] But without generics it must be implemented again for each entry type ... Kubernetes uses a code generator to automate this, but it's a bit kludge. [3] [1]: https://pkg.go.dev/k8s.io/apimachinery/pkg/util/sets#Empty https://pkg.go.dev/k8s.io/apimachinery/pkg/util/sets#Empty [2]: https://dave.cheney.net/2014/03/25/the-empty-struct https://dave.cheney.net/2014/03/25/the-empty-struct [3]: https://github.com/kubernetes/code-generator/blob/master/cmd/set-gen/main.go https://github.com/kubernetes/code-generator/blob/master/cmd...
cmckn 5y ago
This is true for Java as well, a `HashSet` is just a `HashMap<T, Object>` where the value is: // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashSet.java#L97 https://github.com/openjdk/jdk/blob/master/src/java.base/sha... A thread-safe implementation is available with `ConcurrentHashMap.newKeySet()`, which uses a similar approach: public static <K> KeySetView<K,Boolean> newKeySet() { return new KeySetView<K,Boolean> (new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE); } https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashSet.java#L97 https://github.com/openjdk/jdk/blob/master/src/java.base/sha...
masklinn 5y ago
There probably aren't many languages where that's different, whether a hashset on a hashmap or a treeset on a treemap. However sets tend to provide support for… set operations. Which currently can't be done generically in go except through interface{} or specialised, neither of which is a great option.
Philip-J-Fry 5y ago
Even if that's the case, the thing we want is syntactic sugar. It'd be nice to just do `sets.New[int]()` rather than manipulate maps manually or create bespoke types.

In many languages (including Python & Scala), sets are not much more than syntactic sugar on a hashmap-like datatype.

by darkr 5y ago

In many languages (including Python & Scala), sets are not much more than syntactic sugar on a hashmap-like datatype.

nynx 5y ago

In rust, hashsets are just hashmaps with a zero-sized type as the value, which results in all the extra getting optimized away.

BenTheElder 5y ago
A zero-sized type + hashmap for sets is also done in Go with a `struct{}`. [1][2] But without generics it must be implemented again for each entry type ... Kubernetes uses a code generator to automate this, but it's a bit kludge. [3] [1]: https://pkg.go.dev/k8s.io/apimachinery/pkg/util/sets#Empty https://pkg.go.dev/k8s.io/apimachinery/pkg/util/sets#Empty [2]: https://dave.cheney.net/2014/03/25/the-empty-struct https://dave.cheney.net/2014/03/25/the-empty-struct [3]: https://github.com/kubernetes/code-generator/blob/master/cmd/set-gen/main.go https://github.com/kubernetes/code-generator/blob/master/cmd...

cmckn 5y ago

This is true for Java as well, a `HashSet` is just a `HashMap<T, Object>` where the value is: // Dummy value to associate with an Object in the backing Map private static final Object PRESENT = new Object(); https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashSet.java#L97 https://github.com/openjdk/jdk/blob/master/src/java.base/sha... A thread-safe implementation is available with `ConcurrentHashMap.newKeySet()`, which uses a similar approach: public static <K> KeySetView<K,Boolean> newKeySet() { return new KeySetView<K,Boolean> (new ConcurrentHashMap<K,Boolean>(), Boolean.TRUE); } https://github.com/openjdk/jdk/blob/master/src/java.base/share/classes/java/util/HashSet.java#L97 https://github.com/openjdk/jdk/blob/master/src/java.base/sha...

masklinn 5y ago

There probably aren't many languages where that's different, whether a hashset on a hashmap or a treeset on a treemap. However sets tend to provide support for… set operations. Which currently can't be done generically in go except through interface{} or specialised, neither of which is a great option.

Philip-J-Fry 5y ago

Even if that's the case, the thing we want is syntactic sugar. It'd be nice to just do `sets.New[int]()` rather than manipulate maps manually or create bespoke types.