HashSet and Sorted Collections

1. What is HashSet<T>, and how does it prevent duplicates?

What is HashSet?

HashSet<T> is a generic collection in C# that stores only unique elements.

It uses a hash-based data structure internally to provide fast insertion, searching, and deletion.

Main Features:

• Stores only unique values.

• Automatically prevents duplicate elements.

• Does not support index-based access.

• Does not guarantee insertion or sorted order.

• Provides average O(1) searching, insertion, and deletion.

Example Program

HashSet<int> numbers = new()
{
    10, 20, 30, 20, 40, 10
};

foreach (int number in numbers)
{
    Console.WriteLine(number);
}

Console.WriteLine($"Count: {numbers.Count}");

Output (one possible enumeration order):

10
20
30
40
Count: 4

Program Explanation

1. HashSet<int> creates a collection of unique integers.

2. The first 10, 20, and 30 are added.

3. The second 20 is ignored because it already exists.

4. 40 is added.

5. The second 10 is ignored.

6. Count returns 4 because only four unique values exist.

How does HashSet prevent duplicates internally?

HashSet uses hash codes and equality comparisons.

When inserting an element:

1. Calculates its hash code using GetHashCode() through an equality comparer.

2. Uses the hash code to identify a bucket.

3. Checks existing elements in that bucket.

4. Uses equality comparison to determine whether the element already exists.

5. If it exists, insertion is rejected.

6. Otherwise, the element is added.

HashSet<int>

Add(10)
   |
   v
Calculate Hash Code
   |
   v
Find Bucket
   |
   v
10 Does Not Exist
   |
   v
Insert 10


Add(10) Again
   |
   v
Calculate Hash Code
   |
   v
Find Bucket
   |
   v
Compare Existing Values
   |
   v
10 Already Exists
   |
   v
Ignore Duplicate

What does Add() return?

Unlike List<T>.Add(), HashSet<T>.Add() returns a Boolean.

HashSet<int> numbers = new();

Console.WriteLine(numbers.Add(10));
Console.WriteLine(numbers.Add(20));
Console.WriteLine(numbers.Add(10));

Output:

True
True
False

• true means the element was successfully inserted.

• false means an equal element already exists.

Key Points

• HashSet stores unique elements.

• Uses hashing for fast lookup.

• Uses GetHashCode() and equality comparison.

• Duplicate elements are ignored.

• Add() returns false for duplicates.

• Average insertion and lookup complexity is O(1).

• For custom classes, use an appropriate IEqualityComparer<T> or implement consistent equality and hash-code behavior.

Interview Tip: HashSet is commonly used to remove duplicate values or check membership efficiently.

2. What is the difference between List<T> and HashSet<T>?

Explanation

Both are generic collections, but they serve different purposes.

List<T> stores elements in a dynamic array and allows duplicate values.

HashSet<T> stores unique elements using hashing and automatically prevents duplicates.

Comparison

Example Program

// List Example
List<int> list = new()
{
    10, 20, 30, 20, 10
};

Console.WriteLine("List:");

foreach (int number in list)
{
    Console.WriteLine(number);
}


// HashSet Example
HashSet<int> hashSet = new()
{
    10, 20, 30, 20, 10
};

Console.WriteLine("HashSet:");

foreach (int number in hashSet)
{
    Console.WriteLine(number);
}

Output (typical):

List:
10
20
30
20
10

HashSet:
10
20
30

HashSet's enumeration order is not guaranteed.

Program Explanation

List:

1. Stores all five elements.

2. Allows duplicate values 10 and 20.

3. Preserves their positions.

4. Supports accessing elements using list[0].

HashSet:

1. Stores only unique elements.

2. Duplicate 10 and 20 are ignored.

3. Contains three elements.

4. Does not support accessing elements using an index.

Internal Working

List<int>
-----------------------------

Index:   0   1   2   3   4
       +---+---+---+---+---+
Value: |10 |20 |30 |20 |10 |
       +---+---+---+---+---+

Duplicates Allowed
Index Access Available


HashSet<int>
-----------------------------

Add: 10, 20, 30, 20, 10

        Hashing
           |
           v
      Unique Values
           |
           v
      +----+----+----+
      | 10 | 20 | 30 |
      +----+----+----+

Duplicates Removed
No Index Access

Real-World Scenario

Suppose you receive a list of employee IDs containing duplicates.

List<int> employeeIds = new()
{
    101, 102, 103, 101, 102
};

HashSet<int> uniqueIds = new(employeeIds);

Console.WriteLine(uniqueIds.Count);

Output:

3

HashSet automatically removes duplicate employee IDs.

Key Points

• Use List<T> when duplicates and index access are required.

• Use HashSet<T> when uniqueness is required.

• List searches normally take O(n).

• HashSet searches take O(1) on average.

• List maintains element order.

• HashSet does not guarantee order.

• HashSet<T> is especially useful for duplicate detection.

Interview Tip: If your requirement is to store only unique employee IDs and perform frequent existence checks, choose HashSet<int>.

3. What is the difference between HashSet<T> and Dictionary<TKey, TValue>?

Explanation

Both HashSet and Dictionary use hashing internally, but they store data differently.

HashSet<T> stores only unique elements.

Dictionary<TKey, TValue> stores key-value pairs, where each key must be unique.

Comparison

Example Program

HashSet Example:

HashSet<int> employeeIds = new()
{
    101, 102, 103
};

Console.WriteLine(employeeIds.Contains(102));

employeeIds.Add(104);

Dictionary Example:

Dictionary<int, string> employees = new()
{
    { 101, "John" },
    { 102, "David" },
    { 103, "Peter" }
};

Console.WriteLine(employees.ContainsKey(102));

Console.WriteLine(employees[102]);

Output:

True
True
David

Program Explanation

HashSet:

• Stores employee IDs only.

• Contains(102) checks whether employee ID 102 exists.

• Does not store additional employee details.

Dictionary:

• Stores employee IDs as keys and names as values.

• ContainsKey(102) checks whether employee ID 102 exists.

• employees[102] retrieves the employee name.

Internal Working

HashSet<int>
------------------------

       Unique Values
            |
            v
      +-----+-----+
      | 101 |     |
      | 102 |     |
      | 103 |     |
      +-----+-----+

Contains(102)
      |
      v
     True


Dictionary<int, string>
------------------------

    Key          Value
  ---------------------
    101          John
    102          David
    103          Peter

employees[102]
      |
      v
    David

Real-World Scenario

HashSet: Track unique users who logged in today.

HashSet<int> loggedInUsers = new();

loggedInUsers.Add(101);
loggedInUsers.Add(102);
loggedInUsers.Add(101);

Console.WriteLine(loggedInUsers.Count);

Output:

2

Dictionary: Store user IDs and their login counts.

Dictionary<int, int> loginCounts = new()
{
    { 101, 5 },
    { 102, 3 }
};

Console.WriteLine(loginCounts[101]);

Output:

5

Key Points

• Both use hashing internally.

• HashSet stores unique elements.

• Dictionary stores unique keys mapped to values.

• HashSet uses Contains().

• Dictionary uses ContainsKey() and TryGetValue().

• Both provide average O(1) lookup.

• Choose HashSet for membership checks and Dictionary for retrieving associated data.

Interview Tip: Use HashSet when you only need to know whether an item exists. Use Dictionary when you also need information associated with that item.

4. What is the difference between HashSet<T> and SortedSet<T>?

Explanation

Both collections store only unique elements.

The main difference is sorting.

• HashSet<T> uses hashing and does not maintain sorted order.

• SortedSet<T> uses a balanced binary search tree (red-black tree) and automatically maintains sorted order.

Comparison

Example Program

// HashSet
HashSet<int> hashSet = new()
{
    50, 10, 40, 20, 30
};

// SortedSet
SortedSet<int> sortedSet = new()
{
    50, 10, 40, 20, 30
};

Console.WriteLine("HashSet:");

foreach (int number in hashSet)
{
    Console.WriteLine(number);
}

Console.WriteLine("SortedSet:");

foreach (int number in sortedSet)
{
    Console.WriteLine(number);
}

Output:

HashSet:
50
10
40
20
30

SortedSet:
10
20
30
40
50

The HashSet output above is illustrative; its order is not guaranteed.

Program Explanation

HashSet:

1. Adds the numbers using hashing.

2. Prevents duplicates.

3. Does not automatically sort the elements.

4. Provides fast average O(1) searching.

SortedSet:

1. Adds the numbers into a balanced tree.

2. Prevents duplicates.

3. Maintains the elements in ascending order by default.

4. Provides O(log n) searching and insertion.

Internal Working

HashSet:

HashSet<int>
--------------------------

Add(50, 10, 40, 20, 30)
           |
           v
       Hash Function
           |
           v
       Hash Buckets
           |
           v
     Unique Elements

No Sorted Order Guaranteed

SortedSet:

SortedSet<int>
--------------------------

       Red-Black Tree
       (Simplified)

             30
            /  \
          20    40
         /        \
       10          50


Sorted Traversal:

10 -> 20 -> 30 -> 40 -> 50

The diagram illustrates sorted tree traversal, not the exact internal red-black tree layout.

Real-World Scenario

HashSet: Store unique product IDs.

HashSet<int> productIds = new()
{
    105, 101, 103, 101
};

Console.WriteLine(productIds.Count);

Output:

3

SortedSet: Store unique product prices in ascending order.

SortedSet<decimal> prices = new()
{
    500, 100, 300, 200, 100
};

foreach (decimal price in prices)
{
    Console.WriteLine(price);
}

Output:

100
200
300
500

Additional Feature of SortedSet

SortedSet<T> provides useful operations such as Min, Max, and GetViewBetween().

SortedSet<int> numbers = new()
{
    10, 20, 30, 40, 50
};

Console.WriteLine(numbers.Min);
Console.WriteLine(numbers.Max);

foreach (int number in numbers.GetViewBetween(20, 40))
{
    Console.WriteLine(number);
}

Output:

10
50
20
30
40

Key Points

• Both HashSet and SortedSet prevent duplicates.

• HashSet uses hashing.

• SortedSet uses a red-black tree.

• HashSet provides O(1) average lookup.

• SortedSet provides O(log n) lookup.

• SortedSet automatically maintains sorted order.

• SortedSet supports range queries using GetViewBetween().

• HashSet is generally preferable when sorting is unnecessary.

Interview Tip: Choose HashSet<T> for fast uniqueness checks. Choose SortedSet<T> when unique values must always remain sorted.

Quick Interview Revision

Final Comparison: List vs HashSet vs Dictionary vs SortedSet

Most important for interviews: Understand how HashSet prevents duplicates, how it differs from List and Dictionary, and why SortedSet uses a balanced tree instead of hashing.