C# Set collection?
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.
Try HashSet:
The HashSet(Of T) class provides high-performance set operations. A set is a collection that contains no duplicate elements, and whose elements are in no particular order...
The capacity of a HashSet(Of T) object is the number of elements that the object can hold. A HashSet(Of T) object's capacity automatically increases as elements are added to the object.
The HashSet(Of T) class is based on the model of mathematical sets and provides high-performance set operations similar to accessing the keys of the Dictionary(Of TKey, TValue) or Hashtable collections. In simple terms, the HashSet(Of T) class can be thought of as a Dictionary(Of TKey, TValue) collection without values.
A HashSet(Of T) collection is not sorted and cannot contain duplicate elements...
If you're using .NET 3.5, you can use HashSet<T>
. It's true that .NET doesn't cater for sets as well as Java does though.
The Wintellect PowerCollections may help too.
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:
It may contain no duplicate values.
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.
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.
上一篇: 返回null还是空集合更好?
下一篇: C#集合集合?