How C# HashSet Guarantees Fast Uniqueness Checks

In C#, the HashSet<T> collection provides high-performance uniqueness checks by leveraging hash-based indexing, allowing it to determine whether an element exists in near constant time—an average time complexity of \(O(1)\). Instead of performing linear scans across every element, HashSet<T> uses an internal array of buckets alongside an array of entries. By transforming elements into numerical hash codes, mapping those codes to bucket indices, and performing targeted equality checks only when hash collisions occur, HashSet<T> reliably enforces element uniqueness with minimal overhead.

The Internal Structure: Buckets and Slots

Internally, HashSet<T> is built on two primary arrays:

  • buckets (integer array): Stores indices that point to the first entry in a particular hash chain within the entries array.
  • entries (struct array): Stores the actual values, the computed hash code for each item, and a next pointer (index) to handle collisions.

This separated array architecture allows the collection to maintain cache locality while minimizing the memory overhead of reference-heavy node structures.

Step 1: Computing the Hash Code

When you call Add or Contains, HashSet<T> starts by obtaining the object's 32-bit signed integer hash code via IEqualityComparer<T>.GetHashCode(item) (or the object's default GetHashCode() implementation).

This numerical value acts as a condensed digital fingerprint of the item. To ensure the index is always valid, the implementation removes the sign bit using a bitwise mask:

\[\text{positiveHashCode} = \text{hashCode} \ \& \ \text{0x7FFFFFFF}\]

Step 2: Mapping Hash Codes to Buckets

Once the hash code is positive, HashSet<T> maps it to a valid index in the buckets array using the modulo operator against the total bucket length:

\[\text{bucketIndex} = \text{positiveHashCode} \pmod{\text{buckets.Length}}\]

Because array indexing is instantaneous, determining which bucket could possibly contain the target value takes \(O(1)\) time. If the value at buckets[bucketIndex] is -1 (indicating empty), the element is definitively new and unique, requiring no further comparisons.

Step 3: Resolving Collisions with Separate Chaining

Different objects can produce identical bucket indices—either because they produced the exact same hash code or because the modulo operation mapped different hash codes to the same bucket index. This is known as a hash collision.

HashSet<T> resolves collisions using an array-based variation of separate chaining:

  1. It navigates to the entry index specified in the bucket.
  2. It compares the target item's stored hash code against the entry's hash code.
  3. If the hash codes match, it calls IEqualityComparer<T>.Equals(item, entry.Value) to verify actual equality.
  4. If they are equal, a duplicate is found, and Add returns false without modifying the set.
  5. If they are not equal, it follows the entry's next field to examine the next element in the collision chain.

Because well-distributed hash codes produce very short collision chains, the number of actual Equals evaluations rarely exceeds one or two iterations.

Step 4: Dynamic Resizing and Rehashing

As elements are added, the ratio of elements to bucket capacity (the load factor) increases. High load factors lead to longer collision chains, which degrade lookup performance toward \(O(n)\).

To avoid this, HashSet<T> automatically resizes when it reaches capacity:

  1. It allocates new buckets and entries arrays, scaling up to the next available prime number from an internal lookup table. Prime sizes are critical because they significantly reduce clustering when using the modulo operator.
  2. It rehashes every existing item to recalculate its position in the newly sized bucket array.

While resizing is an \(O(n)\) operation, it happens infrequently enough that the amortized insertion time remains \(O(1)\).

Requirements for Fast Guarantees

The \(O(1)\) uniqueness guarantee depends on two developer-controlled rules:

  • Consistent Equals and GetHashCode: If two items are considered equal by Equals, they must return identical values from GetHashCode.
  • Immutability of Key State: If an item is modified while inside a HashSet<T> in a way that alters its hash code, its bucket location becomes invalid, breaking future uniqueness and lookup checks.