3 ms·

Can you give a reference for that? It sounds very unlikely to me, although I've only read/gone through two relevant standard library implementations: F# and OCa

Can you give a reference for that? It sounds very unlikely to me, although I've only read/gone through two relevant standard library implementations: F# and OCaml. Neither of them use dummy values as you suggest. They have similar implementations (both are AVL trees) but sets really do contain only one value while maps contain two. I would be surprised if many other languages did as you suggest.

djur 3y ago
Python, Ruby, Perl. Languages where hashmaps are a builtin.
- eesmith 3y ago
  Python has its own set type not based on hashmap/dict, and that's been the case for years. The set implementation points out some of the differences, at https://github.com/python/cpython/blob/main/Objects/setobject.c https://github.com/python/cpython/blob/main/Objects/setobjec... : Unlike the dictionary implementation, the lookkey function can return NULL if the rich comparison returns an error. Use cases for sets differ considerably from dictionaries where looked-up keys are more likely to be present. In contrast, sets are primarily about membership testing where the presence of an element is not known in advance. Accordingly, the set implementation needs to optimize for both the found and not-found case.
- brabel 3y ago
  Java as well: https://github.com/pengisgood/jdk-source-code/blob/master/src/java/util/HashSet.java#L106 https://github.com/pengisgood/jdk-source-code/blob/master/sr... EDIT : and Rust: https://docs.rs/hashbrown/latest/hashbrown/hash_set/index.html https://docs.rs/hashbrown/latest/hashbrown/hash_set/index.ht... (this is used by the default implementation of HashSet).
alpaca128 3y ago
Rust's HashSet is a HashMap mapping to "()", which is Rust's equivalent to "void".
- progbits 3y ago
  That is true for the internal implementation details but HashSet provides a different API, it is not just a type alias. So you don't have to worry about semantics of what the values mean (like the bools in Go), and it has no size overhead.
zogrodea 3y ago
Update: Looks like I had good reason to be surprised. Thanks everyone for the examples.

djur 3y ago

Python, Ruby, Perl. Languages where hashmaps are a builtin.

eesmith 3y ago
Python has its own set type not based on hashmap/dict, and that's been the case for years. The set implementation points out some of the differences, at https://github.com/python/cpython/blob/main/Objects/setobject.c https://github.com/python/cpython/blob/main/Objects/setobjec... : Unlike the dictionary implementation, the lookkey function can return NULL if the rich comparison returns an error. Use cases for sets differ considerably from dictionaries where looked-up keys are more likely to be present. In contrast, sets are primarily about membership testing where the presence of an element is not known in advance. Accordingly, the set implementation needs to optimize for both the found and not-found case.
brabel 3y ago
Java as well: https://github.com/pengisgood/jdk-source-code/blob/master/src/java/util/HashSet.java#L106 https://github.com/pengisgood/jdk-source-code/blob/master/sr... EDIT : and Rust: https://docs.rs/hashbrown/latest/hashbrown/hash_set/index.html https://docs.rs/hashbrown/latest/hashbrown/hash_set/index.ht... (this is used by the default implementation of HashSet).

alpaca128 3y ago

Rust's HashSet is a HashMap mapping to "()", which is Rust's equivalent to "void".

progbits 3y ago
That is true for the internal implementation details but HashSet provides a different API, it is not just a type alias. So you don't have to worry about semantics of what the values mean (like the bools in Go), and it has no size overhead.

zogrodea 3y ago

Update: Looks like I had good reason to be surprised. Thanks everyone for the examples.