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

  1. Put the words of a sentence into a HashSet and print the count. How many duplicates were there?
  2. Intersect two sets and then subtract one from the other. Which values survive each operation?
  3. Fill a SortedDictionary in reverse key order and print it. Which order comes out?
  4. 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.

  1. 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.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. 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.

  7. 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.

  8. 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.

  9. 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.

  10. 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