Collection Performance

Collection performance is important when working with large datasets in .NET applications. Choosing the correct collection helps improve searching, insertion, deletion, memory usage, and application response time.

1. What is the time complexity of searching in List<T>, Dictionary<TKey, TValue>, and HashSet<T>?

What is Time Complexity?

Time complexity describes how the number of operations grows as the number of elements increases.

Common time complexities:

Searching Performance

Note: Dictionary and HashSet have average O(1) lookups because they use hash tables. Hash collisions can make lookups slower.

Diagram

List<T> - Linear Search
-----------------------

[10] [20] [30] [40] [50]
                  ^
Search 40

Check 10 -> 20 -> 30 -> 40

Time Complexity: O(n)


Dictionary<TKey, TValue> - Hash Lookup
--------------------------------------

Search Key = 103
       |
       v
Calculate Hash
       |
       v
Locate Bucket
       |
       v
Find Value

Average Time Complexity: O(1)


HashSet<T> - Hash Lookup
------------------------

Search Value = 30
       |
       v
Calculate Hash
       |
       v
Locate Bucket
       |
       v
Check Value Exists

Average Time Complexity: O(1)

Example Program

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        List<int> list = new() { 10, 20, 30 };

        Dictionary<int, string> dictionary = new()
        {
            { 1, "John" },
            { 2, "David" },
            { 3, "Peter" }
        };

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

        Console.WriteLine(list.Contains(20));

        Console.WriteLine(dictionary.ContainsKey(2));

        Console.WriteLine(hashSet.Contains(20));
    }
}

Output:

True
True
True

Explanation

• List.Contains(20) searches elements sequentially until a match is found.

• Dictionary.ContainsKey(2) uses hashing to locate the key.

• HashSet.Contains(20) uses hashing to check membership.

Key Points

• List<T> searching takes O(n) time.

• Dictionary<TKey,TValue> key lookup takes O(1) on average.

• HashSet<T> membership lookup takes O(1) on average.

• Dictionary is suitable for key-value lookups.

• HashSet is suitable for checking whether an element exists.

2. Which collection is faster for searching: List or Dictionary?

Explanation

For large datasets, Dictionary is generally faster than List for key-based searching.

• List<T> performs a linear search using Contains() or Find().

• Dictionary<TKey,TValue> uses a hash table to find values by key.

Comparison

Example Program

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        List<Employee> employees = new()
        {
            new Employee { Id = 1, Name = "John" },
            new Employee { Id = 2, Name = "David" },
            new Employee { Id = 3, Name = "Peter" }
        };

        // List search
        Employee? emp1 =
            employees.FirstOrDefault(x => x.Id == 2);

        // Create dictionary
        Dictionary<int, Employee> employeeDict =
            employees.ToDictionary(x => x.Id);

        // Dictionary search
        employeeDict.TryGetValue(2, out Employee? emp2);

        Console.WriteLine(emp1?.Name);
        Console.WriteLine(emp2?.Name);
    }
}

class Employee
{
    public int Id { get; set; }
    public string Name { get; set; } = "";
}

Output:

David
David

Explanation

List Search:

employees.FirstOrDefault(x => x.Id == 2);

• Checks employees sequentially.

• Time complexity: O(n).

Dictionary Search:

employeeDict.TryGetValue(2, out Employee? emp2);

• Uses employee ID as the key.

• Average time complexity: O(1).

Creating the dictionary initially costs O(n) on average. Therefore, converting a list to a dictionary is most beneficial when you perform repeated key lookups.

Real-Time Scenario

Suppose an ASP.NET Core application loads 100,000 employee records and frequently searches employees by ID.

Employee Records
      |
      v
Dictionary<int, Employee>
      |
      v
Search EmployeeId
      |
      v
Return Employee

Using a dictionary can significantly improve repeated searches compared with scanning the list each time.

Key Points

• Dictionary is generally faster for repeated key-based lookups.

• List is suitable for small datasets and sequential processing.

• Dictionary requires unique keys.

• Dictionary consumes additional memory for hash-table storage.

• Use TryGetValue() to safely retrieve a value without throwing an exception for a missing key.

3. When should you choose List, Dictionary, or HashSet?

Explanation

Choose a collection based on your application's requirements.

Diagram

Collection Requirement
         |
         v
Need Key-Value Lookup?
         |
    Yes  +----> Dictionary<TKey,TValue>
         |
         No
         |
         v
Need Unique Elements?
         |
    Yes  +----> HashSet<T>
         |
         No
         |
         v
Need Ordered Sequence
or Index Access?
         |
         v
       List<T>

Example Program

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        // List - Ordered sequence
        List<string> employees = new()
        {
            "John", "David", "John"
        };

        // Dictionary - Key-value lookup
        Dictionary<int, string> employeeDict = new()
        {
            { 101, "John" },
            { 102, "David" }
        };

        // HashSet - Unique elements
        HashSet<string> departments = new()
        {
            "IT", "HR", "IT"
        };

        Console.WriteLine(employees.Count);
        Console.WriteLine(employeeDict[101]);
        Console.WriteLine(departments.Count);
    }
}

Output:

3
John
2

Explanation

• List<T> allows duplicate employee names.

• Dictionary<TKey,TValue> stores employee names against unique IDs.

• HashSet<T> automatically prevents duplicate department names according to its equality comparer.

Key Points

• Use List for sequential and index-based operations.

• Use Dictionary for fast key-value lookup.

• Use HashSet for uniqueness and membership checking.

• All three collections are mutable.

• HashSet<T> does not guarantee sorted order.

4. How do you improve collection performance for large datasets?

Explanation

When handling thousands or millions of records, collection performance can be improved by choosing appropriate data structures and reducing unnecessary processing.

Important Optimization Techniques

Example Program: Optimize Repeated Searches

Without Optimization:

List<int> employeeIds = Enumerable.Range(1, 100000).ToList();

List<int> searchIds = new() { 100, 50000, 99999 };

foreach (int id in searchIds)
{
    if (employeeIds.Contains(id))
    {
        Console.WriteLine($"Found: {id}");
    }
}

Each Contains() operation can take O(n) time.

With Optimization:

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        List<int> employeeIds =
            Enumerable.Range(1, 100000).ToList();

        HashSet<int> employeeSet =
            employeeIds.ToHashSet();

        List<int> searchIds = new()
        {
            100, 50000, 99999
        };

        foreach (int id in searchIds)
        {
            if (employeeSet.Contains(id))
            {
                Console.WriteLine($"Found: {id}");
            }
        }
    }
}

Output:

Found: 100
Found: 50000
Found: 99999

Explanation

Without HashSet:

List (100,000 elements)
         |
         v
Search 100
Search 50000
Search 99999
         |
         v
Each Search = O(n)

For m searches = O(m * n)

With HashSet:

List (100,000 elements)
         |
         v
Create HashSet = O(n) average
         |
         v
Search 100    = O(1) average
Search 50000  = O(1) average
Search 99999  = O(1) average

Total = O(n + m) average

For many repeated searches, HashSet can be significantly faster.

Additional Example: List Capacity

List<int> numbers = new(capacity: 100000);

for (int i = 0; i < 100000; i++)
{
    numbers.Add(i);
}

Explanation:

• The list reserves space for 100,000 elements.

• This reduces repeated internal array reallocations.

• It is useful when the approximate number of elements is known.

Real-Time Scenario

In an ASP.NET Core Web API using EF Core:

var employees = await dbContext.Employees
    .AsNoTracking()
    .Where(e => e.IsActive)
    .Skip(0)
    .Take(100)
    .ToListAsync();

This improves efficiency by:

• Filtering records in the database.

• Returning only 100 records.

• Avoiding EF Core change tracking for read-only results.

Key Points

• Select the correct collection before optimizing individual operations.

• Avoid repeated linear searches in large lists.

• Use pagination for large database results.

• Use AsNoTracking() for read-only EF Core queries.

• Avoid unnecessary collection conversions.

• Measure performance using profiling or benchmarking before making complex optimizations.

5. What is the difference between Any() and Count() > 0?

What is Any()?

Any() checks whether a collection or sequence contains at least one element.

numbers.Any();

It returns true or false.

What is Count() > 0?

Count() > 0 checks whether the number of elements is greater than zero.

numbers.Count() > 0;

Both can check whether a sequence contains elements, but their performance can differ.

Comparison

Diagram

Collection:
[10] [20] [30] [40] [50]

Any()
-----
Check first element
      |
      v
Element exists?
      |
      v
Return True


Count() > 0
-----------
Count elements
      |
      v
Count = 5
      |
      v
5 > 0
      |
      v
Return True

For arrays and lists, LINQ can obtain the count directly without enumerating every element. The diagram illustrates the potential difference for general sequences.

Example Program

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        List<int> numbers = new()
        {
            10, 20, 30
        };

        bool result1 = numbers.Any();

        bool result2 = numbers.Count() > 0;

        bool result3 = numbers.Count > 0;

        Console.WriteLine(result1);
        Console.WriteLine(result2);
        Console.WriteLine(result3);
    }
}

Output:

True
True
True

Explanation

numbers.Any();

Checks whether any element exists.

numbers.Count() > 0;

Uses LINQ to determine the count and compare it with zero.

numbers.Count > 0;

Uses the List<T>.Count property directly.

For List<T>, all three are efficient O(1) operations for this example.

Real-Time Scenario: EF Core

Recommended for existence checking:

bool exists = await dbContext.Employees
    .AnyAsync(e => e.Id == 101);

Typically generates SQL similar to:

SELECT CASE
    WHEN EXISTS (
        SELECT 1
        FROM Employees
        WHERE Id = 101
    )
    THEN CAST(1 AS bit)
    ELSE CAST(0 AS bit)
END;

Using Count:

bool exists = await dbContext.Employees
    .CountAsync(e => e.Id == 101) > 0;

Typically uses SQL COUNT(*) to count matching rows.

For checking existence, AnyAsync() is generally preferable because the database can stop once a matching row is found.

Key Points

• Use Any() to check whether elements exist in an IEnumerable<T>.

• Use Count property for arrays/lists when you already have a collection.

• Avoid Count() when you only need existence, especially for deferred sequences.

• Use Any(predicate) to check whether at least one matching element exists.

• In EF Core, prefer AnyAsync() for existence queries.

6. What is the difference between ToArray() and ToList()?

What is ToArray()?

ToArray() converts an IEnumerable<T> sequence into an array.

int[] numbers = source.ToArray();

Arrays have a fixed length after creation.

What is ToList()?

ToList() converts an IEnumerable<T> sequence into a List<T>.

List<int> numbers = source.ToList();

Lists support dynamic resizing and allow elements to be added or removed.

Diagram

          IEnumerable<int>
                 |
         -----------------
         |               |
         v               v
      ToArray()        ToList()
         |               |
         v               v
      int[]           List<int>
         |               |
    Fixed Length     Dynamic Size
         |               |
    Index Access     Index Access
         |               |
    No Add/Remove    Add/Remove

Comparison

Example Program

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main()
    {
        IEnumerable<int> source =
            Enumerable.Range(1, 3);

        // Convert to Array
        int[] array = source.ToArray();

        // Convert to List
        List<int> list = source.ToList();

        // Modify existing array element
        array[0] = 100;

        // Add element to List
        list.Add(4);

        Console.WriteLine("Array:");
        Console.WriteLine(string.Join(", ", array));

        Console.WriteLine("List:");
        Console.WriteLine(string.Join(", ", list));
    }
}

Output:

Array:
100, 2, 3

List:
1, 2, 3, 4

Explanation

ToArray():

int[] array = source.ToArray();

• Creates an array containing the source elements.

• Array length cannot be changed.

• Existing elements can still be updated.

ToList():

List<int> list = source.ToList();

• Creates a new list containing the source elements.

• Elements can be added, removed, or updated.

• The list automatically manages its capacity.

Both methods immediately enumerate the source and materialize its elements.

Real-Time Scenario

Use ToArray when the result is fixed:

string[] roles = users
    .Select(u => u.Role)
    .ToArray();

Use ToList when additional elements may be added:

List<string> roles = users
    .Select(u => u.Role)
    .ToList();

roles.Add("Admin");

Key Points

• ToArray() returns a fixed-length array.

• ToList() returns a dynamically resizable list.

• Both support index-based access.

• Both materialize an IEnumerable<T> immediately.

• Both are generally O(n) for n elements.

• Prefer ToArray() when no resizing is required.

• Prefer ToList() when adding or removing elements is necessary.

• Neither method makes mutable objects inside the collection immutable.

Final Summary: Collection Performance

Important Interview Takeaways

Q1. Which collection provides the fastest lookup?

Dictionary<TKey,TValue> and HashSet<T> provide average O(1) lookups. Dictionary is used for key-value searching, while HashSet is used for membership checks.

Q2. Is Dictionary always faster than List?

No. Dictionary is generally faster for repeated key-based searches, but List may be more efficient for small datasets, sequential iteration, or index-based access.

Q3. How can you optimize searching one million records?

Use Dictionary for key-based lookup or HashSet for membership checks. If records are stored in SQL Server, use indexed database queries and pagination instead of loading all records into memory unnecessarily.

Q4. Is Any() faster than Count() > 0?

For general sequences and EF Core existence queries, Any() is usually preferable. For List<T>, the Count property is already O(1).

Q5. Which is faster: ToArray() or ToList()?

Neither is universally faster. Both are O(n) for materialization. Arrays generally use less memory, while lists provide dynamic resizing.

Q6. What is the most important collection performance rule?

Choose the collection based on its most frequent operation:

Need Fast Key Lookup?
        |
        +----> Dictionary<TKey, TValue>

Need Fast Membership Check?
        |
        +----> HashSet<T>

Need Index Access / Sequential Processing?
        |
        +----> List<T>

Need Fixed-Length Data?
        |
        +----> Array

For .NET technical interviews, focus particularly on O(1) vs O(n), Dictionary vs List, HashSet membership checks, Any vs Count, and avoiding repeated LINQ enumeration.