Is a HashSet the same as List 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.

Answer 3

No. A HashSet doesn’t allow access via index because the items aren’t ordered. This does not mean, as you suspect, that they aren’t ordered according to some IEqualityComparer. It means that they are not stored inside the hash set in the order of adding them.

So if you need an order preserving or random access container, HashSet is not for you.

Answer 4

It sounds like this is what you're after:

class UniqueList<T> : Collection<T>
{
    protected override void InsertItem(int index, T item)
    {
        if (!base.Contains(item))
        {
            base.InsertItem(index, item);
        }
        else
        {
            // whatever
        }
    }
}

Calling UniqueList.Add will add an item to the end of the list, and will not add duplicate values.

Answer 5

You got it slightly wrong. Neither Dictionary nor HashSet preserves the order of the items, this means you can't rely on the item index. Theoretically you can use LINQ ElementAt() to access item by index, but again both collections do not gurantee that order is preserved.

.NET provides an OrderedDictionary class, but it is not generic so you would not have a type safety at compile time. Anyways it allows accessing items by index.

Here is a custom implementation of the generic one: OrderedDictionary(of T): A generic implementation of IOrderedDictionary. The key point: it persists two collections -- List and Dictionary at the same time; List provides access by index and Dictionary provides fast access by a key.

Answer 6

Well HashSet conceptually is a List of unique values, but in difference from List<T> it doesn't actually implements IList interface, but implements ICollection. Plus it has a set of special functions, like :

Intersection, IsSubsetOf, IsSupersetOf, Union, which List<T> doesn't have.

These functions, naturally, are handy in operations on multiple HasSets.