HashSet and SortedDictionary
HashSet: a set of values
A HashSet<T> is a dictionary without values: it answers "is this value in the set" and refuses a duplicate. Adding the same value twice leaves one copy, which is what makes it the tool for a uniqueness check.
var set = new HashSet<int> { 3, 1, 3, 2 };
Console.WriteLine(set.Count);
Console.WriteLine(set.Contains(2));
set.Add(1);
Console.WriteLine(set.Count);
Console.WriteLine(set.SetEquals(new[] { 1, 2, 3 }));
foreach (var value in set.OrderBy(v => v))
{
Console.WriteLine($"value: {value}");
}
dotnet run
3
True
3
True
value: 1
value: 2
value: 3
The initialiser wrote 3 twice and the set holds three values, not four: the
second 3 was a duplicate. The second
Add(1) changed nothing either, and
SetEquals compares the elements regardless of
order.
Like a dictionary, a set has no promised iteration order, and the loop
sorts the values before printing them. A program that prints a set in the
order it was filled is relying on an accident.
Set operations
The set algebra is in the type: intersection, union, difference and the subset test all have a method that changes the set in place.
var left = new HashSet<string> { "a", "b", "c" };
var right = new HashSet<string> { "b", "c", "d" };
left.IntersectWith(right);
Console.WriteLine(string.Join(",", left.OrderBy(x => x)));
Console.WriteLine(left.Count);
left.UnionWith(new[] { "z" });
Console.WriteLine(string.Join(",", left.OrderBy(x => x)));
Console.WriteLine(left.IsSubsetOf(new[] { "b", "c", "z", "q" }));
dotnet run
b,c
2
b,c,z
True
IntersectWith keeps the values that are in both
sets, UnionWith adds the values of the other
collection, and IsSubsetOf asks whether every value
of this set is in the other. ExceptWith takes away
what the other collection holds and
SymmetricExceptWith keeps what is in exactly one of
the two.
Each of them changes the set it is called on. The methods that return a new
sequence instead — Intersect,
Union, Except — are the LINQ
operators of the next part, and they work on any collection.
SortedDictionary and SortedSet
A sorted collection keeps its elements in the order of their comparison, so an iteration is ordered without a sort, and a range can be read in one piece. The cost is a tree instead of a hash table: a lookup is log n comparisons rather than one.
var sorted = new SortedDictionary<string, int> { ["b"] = 2, ["a"] = 1 };
foreach (var pair in sorted)
{
Console.WriteLine($"{pair.Key}={pair.Value}");
}
Console.WriteLine(sorted.Keys.First());
var sortedSet = new SortedSet<int> { 5, 1, 3 };
Console.WriteLine(string.Join(",", sortedSet));
Console.WriteLine(sortedSet.Min);
dotnet run
a=1
b=2
a
1,3,5
1
The pairs came out in key order although they were inserted in the other
order, and Min is the first element of the order.
SortedSet<T> is the set with the same
guarantee, and it can answer a range question:
GetViewBetween(2, 4) returns the part of the set
between two values.
A sorted collection needs a comparison. A type without one throws at the
first insert, and a set of a custom type takes an
IComparer<T> in its constructor.
Exercises
- Put the words of a sentence into a HashSet and print the count. How many duplicates were there?
- Intersect two sets and then subtract one from the other. Which values survive each operation?
- Fill a SortedDictionary in reverse key order and print it. Which order comes out?
- Time a hundred thousand lookups in a HashSet and in a SortedSet with a stopwatch. Which is faster, and why?
Questions
A new set of questions in a new order every time. Choose one answer for each, then check.
-
What does a HashSet refuse?
Answer
A second copy of a value it already holds
A set is about membership, so an Add of a value that is already there changes nothing and returns false.
-
What does this program print?
var set = new HashSet<int> { 1, 1, 2 }; Console.WriteLine(set.Count);Answer
2
The second 1 is a duplicate and the set holds two distinct values.
-
What does this program print?
var a = new HashSet<int> { 1, 2, 3 }; var b = new HashSet<int> { 2, 3, 4 }; a.IntersectWith(b); Console.WriteLine(a.Count); Console.WriteLine(a.Contains(4));Answer
2 / False
The intersection holds 2 and 3, so the count is two and 4 never belonged to a.
-
Which collection keeps its keys in order without a sort?
Answer
SortedDictionary
A sorted dictionary is a tree ordered by the comparison of its keys; a Dictionary and a HashSet promise no order.
-
What does this program print?
var set = new SortedSet<int> { 5, 1, 3 }; Console.WriteLine(string.Join(",", set));Answer
1,3,5
A sorted set enumerates in ascending order, and the join prints that order.
-
What does UnionWith do?
Answer
Adds every value of the other collection that is not there yet
UnionWith changes the set in place; the method that returns a new sequence is the LINQ Union.
-
What is the cost of a lookup in a HashSet against a SortedSet?
Answer
About one hash against about log n comparisons
The hash set jumps to a bucket, while the sorted set walks a tree, which is why the sorted one is slower per lookup.
-
What does this program print?
var set = new HashSet<string> { "a", "b" }; set.Add("a"); Console.WriteLine(set.Contains("a")); Console.WriteLine(set.Count);Answer
True / 2
The duplicate Add changed nothing, so the value is still there and the count is still two.
-
Which method keeps the values that are in exactly one of two sets?
Answer
SymmetricExceptWith
The symmetric difference drops the values in both and keeps the rest; ExceptWith drops only the other set values.
-
What does a sorted collection need that a hash collection does not?
Answer
A comparison of its elements
The tree is ordered by comparisons, so the element type must be comparable or the collection needs an IComparer.
The code on this page was built with the .NET SDK 10.0.303 and run on Alpine Linux 3.24.3 (x86_64) in a Docker container.
Article author: Arthur Isaev