Hacker News Reader

Comment by Sniffnoy | Hacker News Reader

A set, the abstract interface, is simpler conceptually than a list. A hash set, the particular implementation of a set, is more complex.

View on HN

Fortunately 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.

Lots of code is written in C :)

Or Go.

In 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.

This 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.

One 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.

I'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.

Low 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?

Reply on news.ycombinator.com