HashSet in C#

1. Internal Components

Internally, a HashSet maintains two core data structures

• Buckets Array (int[] buckets)

  Each element in this array represents a bucket index that points to a chain of entries with the same hash code.

• Entries Array (Entry[] entries)

  Each entry stores the actual data item along with its hash and a pointer to the next entry in case of collisions.

  struct Entry
  {
      public int hashCode;   // Hash code of the element
      public int next;       // Index of the next entry in the same bucket
      public T value;        // The stored element
  }

2. Hashing Process

When you call Add(item)

• Compute the hash code : The HashSet calculates the hash code of the item using its GetHashCode() method.
• Transform the hash code: The raw hash code is typically masked (e.g. hashCode & 0x7FFFFFFF) to ensure a non-negative index.
• After that computes the bucket index, by
  int bucketIndex = hashCode % buckets.Length;

• The item is placed in the corresponding bucket.
• If two items have the same hash index (a collision), HashSet uses linked chaining. it links the new entry to the previous one via the next field.

3. Collision Handling (Chaining)

If multiple elements hash to the same bucket

• They are stored as a linked list in the entries array.
• The next field in each Entry points to the next entry with the same bucket index.

buckets: [-1, -1, 0, -1, -1]
entries:
[0] -> hash=12, value="apple", next=-1
[1] -> hash=17, value="banana", next=-1

If a new item "grape" hashes to the same bucket as "apple", it gets linked

buckets[2] = 2 (grape)
entries[2] = { hash=12, value="grape", next=0 }  // points to apple

4. Lookup (Contains)

When you call Contains(item)

• Compute the hash code -> find the bucket.
• Traverse the linked entries in that bucket to find a match using Equals().
• Time complexity :- Average case : O(1), Worst case (many collisions) : O(n)

5. Resizing & Load Factor

To maintain performance, HashSet<T> will resize its internal storage when the number of items grows beyond a certain threshold (load factor * buckets count). Although .NET doesn’t publicly document the exact threshold, the general pattern is

• When Count exceeds _buckets.Length * LoadFactor (often ~0.75), allocate a new buckets array (typically a larger prime or next appropriate size) plus a new slots array.
• Rehash all existing elements (i.e. recompute bucket index using new size) and copy them into the new structure, re-linking chains.
• This ensures the average bucket chain length remains small (hence average O(1) operations).
• Resize cost is O(n) (for rehashing), but amortised over many inserts remains efficient.

This ensures operations remain efficient even as data grows.

6. Equality Comparer

HashSet can also use a custom equality comparer for flexible comparison and hashing logic

HashSet<string> set = new HashSet<string>(StringComparer.OrdinalIgnoreCase);

This controls how items are compared and how their hash codes are computed.

1. HashSet<T>()

Initializes a new empty HashSet<T> using the default equality comparer for the element type.

var set = new HashSet<string>();

Usage: Use when you want a simple, empty set with default settings.

2. HashSet<T>(IEnumerable<T> collection)

Initializes a new HashSet<T> that contains elements copied from the specified collection, using the default equality comparer. Duplicates in the collection are ignored.

var list = new List<int> { 1, 2, 2, 3 };
var set = new HashSet<int>(list);

Usage: Use when you want to create a set from an existing collection, ensuring uniqueness.

3. HashSet<T>(IEnumerable<T> collection, IEqualityComparer<T> comparer)

Initializes a new HashSet<T> that contains elements copied from the specified collection, using the specified equality comparer. Duplicates in the collection are ignored.

var list = new List<string> { "apple", "Apple", "banana" };
var set = new HashSet<string>(list, StringComparer.OrdinalIgnoreCase);

Usage: Use when you want to create a set from an existing collection with a custom equality comparer.

4. HashSet<T>(IEqualityComparer<T> comparer)

Initializes a new empty HashSet<T> using the specified equality comparer.

var set = new HashSet<string>(StringComparer.OrdinalIgnoreCase);

Usage: Use when you want an empty set with a custom equality comparer.

5. HashSet<T>(int capacity)

Initializes a new empty HashSet<T> with a specified initial capacity, using the default equality comparer.

var set = new HashSet<int>(100);

Usage: Use when you know the approximate number of elements in advance to optimize performance.

6. HashSet<T>(int capacity, IEqualityComparer<T> comparer)

Initializes a new empty HashSet<T> with a specified initial capacity and a specified equality comparer.

var set = new HashSet<string>(50, StringComparer.OrdinalIgnoreCase);

Usage: Use when you know the approximate number of elements and want a custom equality comparer.

1. Count

Gets the number of elements contained in the set. This property provides the current size of the HashSet<T>.

var set = new HashSet<int> { 1, 2, 3 };
Console.WriteLine(set.Count); // Output: 3

Usage : Use when you need to determine how many unique elements are present in the set.

2. Comparer

Gets the IEqualityComparer<T> object used to determine equality for the values in the set. This property indicates how equality comparisons are performed within the HashSet<T>.

var set = new HashSet<string>(StringComparer.OrdinalIgnoreCase);
Console.WriteLine(set.Comparer.Equals("apple", "APPLE")); // Output: True

Usage : Use when you need to understand or customize the equality logic used by the set.

1. Using Collection Initializer

You can initialize a HashSet with elements directly at the time of creation using curly braces {}.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var languages = new HashSet<string> { "C#", "Java", "C++", "Python", "React" };
        Console.WriteLine("Languages in HashSet:");
        foreach (var lang in languages)
        {
            Console.WriteLine(lang);
        }
    }
}

C#
Java
C++
Python
React

2. Using Add() Method

You can also create an empty HashSet and add elements one by one using the Add() method.

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        var frameworks = new HashSet<string>();
        frameworks.Add("ASP.NET");
        frameworks.Add("Spring Boot");
        frameworks.Add("Django");
        frameworks.Add("Flask");
        frameworks.Add("ASP.NET"); // duplicate ignored
        Console.WriteLine("Frameworks in HashSet:");
        foreach (var f in frameworks)
        {
            Console.WriteLine(f);
        }
    }
}

ASP.NET
Spring Boot
Django
Flask