Is a HashSet<T> the same as List<T> but with uniqueness?

Question

I need to have an ability to have unique items in a collection.

I was going to use a Dictionary so I could use the ContainsKey method but I thought it would be a waste as I wouldnt use the Value property of the Key/Value pair.

I came across the HashSet<T> which looks very promising. The only thing I can find that I can't find in the List<T> docs is that HashSet<T> is unordered. I think that is fine, I assume it means its not ordered using a IEqualityComparer. As long as the order in which items are added are in the same index position I think it will be ok as I have to do duplicate checking hence the hashset and then check all entries are sequential.

Is there anything else I have missed comparing the two types?

Answer 1

No, importantly HashSet<T> doesn't have any concept of ordering or indexing - a list conceptually has slots 0....n-1, whereas a set is "just a set".

I think that is fine, I assume it means its not ordered using a IEqualityComparer.

IEqualityComparer isn't used for ordering anyway - it only talks about equality and hash codes. HashSet<T> isn't ordered by either an element comparison (as, say, SortedSet<T> is) or insertion order.

As long as the order in which items are added are in the same index position I think it will be ok.

There is no index position, and when you iterate over a HashSet<T> there's no guarantee you'll get them back in the order in which you added them. If you're even thinking about ordering, HashSet<T> isn't what you're after.

Then again, all of this is also true of Dictionary<TKey, TValue> - you shouldn't make any assumptions about ordering there, either.

Answer 2

This is a 'picture' of what a List<T> looks like:

List:  |a|b|r|t|i|p|c|y|z|...
Index: |0|1|2|3|4|5|6|7|8|...

The List<T> represents, well, a list of items. You can refer to an item by its position in the list.

This is a 'picture' of what a HashSet<T> looks like:

Set:    |a|b|c| | | | | |i| | | | | | |p| |r| |t| | | | |y|z|
Bucket: |a|b|c|d|e|f|g|h|i|j|k|l|m|n|o|p|q|r|s|t|u|v|w|x|y|z|

The HashSet<T> represents a set of unique items. Every item has its own 'bucket'. You can refer to an item by its bucket. The bucket that an item belongs in is calculated directly from an item.

One of the advantages of using a HashSet over a List is constant-time searches. In a List, an item could be anywhere in the List, so to find it, you need to look at every item in the List. In a HashSet, there is only one possible location for any given item. Therefore, to search for an item, all you need to do is look in its bucket. If it's there, it's there, if it's not, it's not.

The illustrations may not be 100% accurate (for simplicity's sake). Especially the HashSet example.