Dictionary and HashSet

Both are built on a hash table, so their typical cost is O(1). See the Big O noteBig O notationHow run time or memory grows as the input grows.Opens in a new tab for the notation.

Dictionary (System.Collections.Generic.Dictionary<TKey, TValue>)

A collection of key-value pairs, implemented using a hash table. Keys must be unique.

• Access (by key): O(1) on average
• Search (by key): O(1) on average
• Add or remove (by key): O(1) on average
• Worst case, due to hash collisions: O(n)

Use it for fast lookups, additions and deletions based on a unique key. For example caching, symbol tables, and associating data. A poor GetHashCode() implementation for TKey can degrade performance to O(n).

HashSet (System.Collections.Generic.HashSet<T>)

An unordered collection of unique elements, implemented using a hash table.

• Add or remove: O(1) on average
• Contains (search): O(1) on average
• Worst case: O(n)

Use it to store a set of unique items where order doesn’t matter, to check quickly whether an item exists, to remove duplicates from a collection, and to perform set operations (union, intersection, difference).