ListT.Contains is very slow?

performance

List<T>

Contains method

optimization

ListT.Contains is very slow?

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

Complexity & Performance C# & .NET

Introduction

List<T>.Contains() is O(n) because it performs a linear search, comparing each element sequentially. For small lists (under ~100 items), this is fast enough. For large lists or frequent lookups, switch to HashSet<T> which provides O(1) average-time Contains(). If you need both ordered access and fast lookup, maintain a HashSet<T> alongside the List<T>, or use SortedSet<T> for O(log n) lookups with sorted iteration.

Why List Contains Is Slow

List<T>.Contains() calls EqualityComparer<T>.Default.Equals() on each element from start to end:

csharp

1// Internal behavior of List<T>.Contains
2public bool Contains(T item)
3{
4    for (int i = 0; i < _size; i++)
5    {
6        if (EqualityComparer<T>.Default.Equals(_items[i], item))
7            return true;
8    }
9    return false;
10}

For a list with 1 million items, the worst case checks all 1 million elements.

csharp

1var list = Enumerable.Range(0, 1_000_000).ToList();
2
3// O(n) — slow for large lists
4bool found = list.Contains(999_999);  // Checks ~1M elements
5bool missing = list.Contains(-1);      // Checks ALL 1M elements

Fix: Use HashSet for Fast Lookups

HashSet<T> uses a hash table for O(1) average-time lookups:

csharp

1var list = Enumerable.Range(0, 1_000_000).ToList();
2var hashSet = new HashSet<int>(list);  // O(n) to build, once
3
4// O(1) lookup
5bool found = hashSet.Contains(999_999);  // Near-instant
6bool missing = hashSet.Contains(-1);      // Near-instant

Benchmark Comparison

csharp

1using System.Diagnostics;
2
3var list = Enumerable.Range(0, 1_000_000).ToList();
4var set = new HashSet<int>(list);
5
6var sw = Stopwatch.StartNew();
7for (int i = 0; i < 10_000; i++)
8    list.Contains(i);
9Console.WriteLine($"List.Contains: {sw.ElapsedMilliseconds}ms");
10
11sw.Restart();
12for (int i = 0; i < 10_000; i++)
13    set.Contains(i);
14Console.WriteLine($"HashSet.Contains: {sw.ElapsedMilliseconds}ms");
15
16// Typical results:
17// List.Contains: ~3000ms
18// HashSet.Contains: ~1ms

Collection Comparison Table

Collection	Contains	Add	Order	Duplicates
`List<T>`	O(n)	O(1) amortized	Insertion order	Yes
`HashSet<T>`	O(1)	O(1)	No order	No
`SortedSet<T>`	O(log n)	O(log n)	Sorted	No
`Dictionary<K,V>`	O(1) by key	O(1)	No order	Keys unique
`SortedList<K,V>`	O(log n)	O(n)	Sorted by key	Keys unique

Pattern: List + HashSet Together

When you need both ordered access and fast lookups:

csharp

1public class IndexedCollection<T>
2{
3    private readonly List<T> _list = new();
4    private readonly HashSet<T> _set = new();
5
6    public void Add(T item)
7    {
8        if (_set.Add(item))  // O(1) duplicate check
9            _list.Add(item);
10    }
11
12    public bool Contains(T item) => _set.Contains(item);  // O(1)
13
14    public T this[int index] => _list[index];  // O(1) by index
15
16    public int Count => _list.Count;
17
18    public IReadOnlyList<T> Items => _list;
19}
20
21var collection = new IndexedCollection<string>();
22collection.Add("apple");
23collection.Add("banana");
24collection.Add("apple");  // Duplicate — not added
25
26Console.WriteLine(collection.Count);            // 2
27Console.WriteLine(collection.Contains("banana")); // True (O(1))
28Console.WriteLine(collection[0]);               // "apple" (O(1))

Using LINQ Contains Efficiently

csharp

1var ids = new List<int> { 1, 2, 3, 4, 5 };
2
3// SLOW: List.Contains inside LINQ — O(n*m)
4var results = database.Where(item => ids.Contains(item.Id)).ToList();
5
6// FAST: Convert to HashSet first — O(n+m)
7var idSet = new HashSet<int>(ids);
8var results = database.Where(item => idSet.Contains(item.Id)).ToList();

This is especially important when filtering a large collection against another large collection.

Custom Equality

For custom objects, implement IEquatable<T> and override GetHashCode:

csharp

1public class Product : IEquatable<Product>
2{
3    public int Id { get; set; }
4    public string Name { get; set; }
5
6    public bool Equals(Product other)
7    {
8        if (other is null) return false;
9        return Id == other.Id;
10    }
11
12    public override bool Equals(object obj) => Equals(obj as Product);
13
14    public override int GetHashCode() => Id.GetHashCode();
15}
16
17// Now both List and HashSet use your equality logic
18var products = new HashSet<Product>();
19products.Add(new Product { Id = 1, Name = "Widget" });
20products.Contains(new Product { Id = 1, Name = "Different" }); // True (matches by Id)

Without GetHashCode, HashSet<T> falls back to reference equality and loses its O(1) performance.

Binary Search on Sorted Lists

If the list is sorted, use BinarySearch for O(log n) lookups:

csharp

1var sortedList = Enumerable.Range(0, 1_000_000).ToList();
2
3// O(log n) — much faster than Contains for sorted data
4int index = sortedList.BinarySearch(500_000);
5bool found = index >= 0;  // True
6
7// Note: list must be sorted for BinarySearch to work correctly

Common Pitfalls

Calling Contains in a loop on a large list: If you check list.Contains(x) for each element of another collection, the total complexity is O(n*m). Convert the lookup collection to a HashSet<T> once (O(n)) and then each lookup is O(1).
Not implementing GetHashCode for custom types in HashSet: HashSet<T> relies on GetHashCode to distribute items into buckets. If GetHashCode always returns the same value, all items land in one bucket and lookups degrade to O(n). Always implement GetHashCode to match Equals.
Using HashSet when order matters: HashSet<T> does not preserve insertion order. If you need both fast lookup and ordered access, maintain a List<T> and HashSet<T> side by side.
Premature optimization for small collections: For lists under ~100 elements, List<T>.Contains is fast enough and avoids the overhead of hash computation. Profile before switching to HashSet<T>.
Assuming Dictionary.ContainsValue is fast: Dictionary<K,V>.ContainsKey is O(1), but ContainsValue is O(n) because values are not hashed. If you need fast value lookups, create a reverse Dictionary<V,K> or a HashSet<V>.

Summary

List<T>.Contains() is O(n) — it scans every element sequentially
HashSet<T>.Contains() is O(1) — use it for frequent lookups on large collections
Convert a list to HashSet<T> before using Contains in loops or LINQ queries
For sorted data, use List<T>.BinarySearch() for O(log n) lookups
Implement IEquatable<T> and GetHashCode for custom types to enable efficient hashing

DSA Fundamentals

Master algorithmic patterns and data structures through hands-on LeetCode-style problems - from arrays and hashing to dynamic programming and advanced graphs.

View the course

Track what you have practised

A free account saves your progress, solutions and study plan across every problem on Codemia.

Data Structures & Algorithms practice on Codemia

Step through 300 algorithm problems with animated visualisers that show the data structure changing as the code runs.

Practice algorithms

ListT.Contains is very slow?

Data Structures & Algorithms practice on Codemia

Introduction

Why List Contains Is Slow

Fix: Use HashSet for Fast Lookups

Benchmark Comparison

Collection Comparison Table

Pattern: List + HashSet Together

Using LINQ Contains Efficiently

Custom Equality

Binary Search on Sorted Lists

Common Pitfalls

Summary

Related reading

DSA Fundamentals

Track what you have practised

Data Structures & Algorithms practice on Codemia