Logo Questions Linux Laravel Mysql Ubuntu Git Menu
 

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

Tags:

c#

.net

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?

like image 975
Jon Avatar asked Mar 19 '12 20:03

Jon


People also ask

How does a HashSet T differ from a List t?

Duplicates : ArrayList allows duplicate values while HashSet doesn't allow duplicates values. Ordering : ArrayList maintains the order of the object in which they are inserted while HashSet is an unordered collection and doesn't maintain any order.

Which is faster HashSet or List?

The result clearly shows that the HashSet provides faster lookup for the element than the List. This is because of no duplicate data in the HashSet. The HashSet maintains the Hash for each item in it and arranges these in separate buckets containing hash for each character of item stored in HashSet.

Is HashSet more efficient than List?

HashSet becomes faster for 10% only if we List is without specified capacity and checks each value before adding through whole list. If items count reduced to 4 then List again wins even in worst scenario (with 10% difference).

Is HashSet a List C#?

The main difference between HashSet and List is that the list can contain duplicate elements, though both are used to store unique values. HashSet is much faster than List collection because HashSet lazily initializes underlying data structures.


2 Answers

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.

like image 196
Jon Skeet Avatar answered Oct 13 '22 00:10

Jon Skeet


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.

like image 42
Kendall Frey Avatar answered Oct 12 '22 23:10

Kendall Frey