iset - set collection c#




C# Set collection? (7)

If you're using .NET 4.0 or later:

In the case where you need sorting then use SortedSet<T>. Otherwise if you don't, then use HashSet<T> since it's O(1) for search and manipulate operations. Whereas SortedSet<T> is O(log n) for search and manipulate operations.

Does anyone know if there is a good equivalent to Java's Set collection in C#? I know that you can somewhat mimic a set using a Dictionary or a HashTable by populating but ignoring the values, but that's not a very elegant way.


The HashSet<T> data structure:

The Framework Class Library's HashSet<T> data structure was introduced in the .NET Framework 3.5. A full list of its members can be found at the MSDN reference page for HashSet<T>.

HashSet<T> is more or less modeled after a mathematical set, which means that:

  1. It may contain no duplicate values.

  2. Its elements are in no particular order; therefore the type does not implement the IList<T> interface, but the more basic ICollection<T>. As a consequence, elements inside a hash set cannot be randomly accessed through indices; they can only be iterated over through an enumerator.

  3. Certain set functions such as Union, Intersection, IsSubsetOf, IsSupersetOf are available. These can come in handy when working with multiple sets.

Another difference between HashSet<T> and List<T> is that calling a hash set's Add(item) method returns a Boolean value: true if the item was added, and false otherwise (because it was already found in the set).

Why not List<T>?

Since a HashSet<T> is simply a collection of unique objects, you might wonder why it has to be a data structure. A normal List<T> could have the same behavior by checking if an object is found in the list before adding it.

The short answer is speed. Searching through a normal List<T> gets very slow very fast as more elements are added. A HashSet<T> requires a structure design that will allow for fast searching and insertion speeds.

Benchmarks:

Let's compare the performance speed of a HashSet<T> vs. a List<T>.

Each trial consisted of adding integers from 0 to 9,999 to each collection. However, mod 25 was applied to each integer. Mod 25 makes the maximum types of items 25. Since 10,000 elements were added, this forced 400 collisions to occur, giving the data structures a chance to use their searching algorithms. Times were measured 3 times after 10,000 trials and averaged out.

Don't pay too much attention to the specific running times of the tests since they are dependent on my hardware, but look at how they compare to each other.

           Average time [ms]
----------------------------
HashSet<T>             2,290
List<T>                5,505

Now let's make elements objects instead of primitive types. I wrote a quick Person class with three fields: Name, LastName, and ID. Since I did not include any specific way to compare objects, all the elements will be added without collisions. This time 1,000 Person objects were added to each collection for a single trial. The total times of 3 sets of 1,000 trials were averaged out.

           Average time [ms]
----------------------------
HashSet<Person>          201
List<Person>           3,000

As you can see, the difference in running times becomes astronomical when using objects, making the HashSet<T> advantageous.


Have a look at PowerCollections over at CodePlex. Apart from Set and OrderedSet it has a few other usefull collection types such as Deque, MultiDictionary, Bag, OrderedBag, OrderedDictionary and OrderedMultiDictionary.

For more collections, there is also the C5 Generic Collection Library.


I know this is an old thread, but I was running into the same problem and found HashSet to be very unreliable because given the same seed, GetHashCode() returned different codes. So, I thought, why not just use a List and hide the add method like this

public class UniqueList<T> : List<T>
{
    public new void Add(T obj)
    {
        if(!Contains(obj))
        {
            base.Add(obj);
        }
    }
}

Because List uses the Equals method solely to determine equality, you can define the Equals method on your T type to make sure you get the desired results.


I use a wrapper around a Dictionary<T, object>, storing nulls in the values. This gives O(1) add, lookup and remove on the keys, and to all intents and purposes acts like a set.







set