4 ms·
A set, the abstract interface, is simpler conceptually than a list. A hash set, the particular implementation of a set, is more complex.
by Sniffnoy 9y ago
A set, the abstract interface, is simpler conceptually than a list. A hash set, the particular implementation of a set, is more complex.
- tatterdemalion 9y agoFortunately there are many languages which will provide a generic abstraction for you, so you don't have to deal with any of the complexity of implementing a hash set and you can just treat it like a set.
- jopsen 9y agoLots of code is written in C :)
- tatterdemalion 9y agoOr Go.
- jzelinskie 9y agoIn Go, it's idiomatic to use map[T]struct{} for a HashSet. In fact, the compiler optimises struct{} so that it doesn't even allocate.
- tatterdemalion 9y agoThis is also how HashSet is implemented in Rust (internally its a HashMap<T, ()>, and zero sized structs are optimized out just like Go). But by providing a set type, Rust is able to provide for users various set operations which Go requires you to write by hand. It becomes hard to argue that a set is simpler than a slice when you have to write your own methods dealing with union, disjunction, intersection, difference, subsets/supersets, etc every time.
- deleted 9y ago[deleted]
- seanmcdirmid 9y agoOne could easily implement a hash set with an array, the reverse is not true at all. From the outside, arrays are extremely flexible, powerful, and complex constructs; a set, even a hash set, is not. If it is easy to procure a set (as a hash set), then sets should be used when they could be used instead of arrays (unless there are performance concerns to using sets). In languages that do not include batteries (e.g. C), it makes sense to use an array simply because procuring a set isn't easy.
- DamonHD 9y agoI'm probably missing something, but eg awk implements its 'arrays' at least logically with something like a hash set, and indeed hash sets can be great for (say) sparse arrays. Lots of low-level data structures can be implemented in terms of one another, and which makes sense depends on circumstance.
- seanmcdirmid 9y agoLow level doesn't mean simple. In this case, arrays provide a lot of flexibility with manual indexing. They are a low level hammer that can do anything. Sets are much more restricted, they don't have manual indexing, they don't garaunteed iteration ordering without special semantics, they don't do as much as arrays even if they might be implemented with arrays. Then why use an array when you only need a set and an array would be overkill?
- deleted 9y ago[deleted]