Dictionary and Key-Value Collections

1. What is Dictionary<TKey, TValue>, and how does it work internally?

What is Dictionary?

Dictionary<TKey, TValue> is a generic collection in C# that stores data as key-value pairs.

• TKey – Type of the key.

• TValue – Type of the value.

• Each key must be unique.

• Values can be duplicated.

• Provides very fast searching using keys.

Example: Store employee IDs and employee names.

Example Program

Dictionary<int, string> employees = new()
{
    { 101, "John" },
    { 102, "David" },
    { 103, "Peter" }
};

// Access value using key
Console.WriteLine(employees[102]);

// Add new employee
employees.Add(104, "Robert");

// Update employee
employees[101] = "Michael";

// Check key
Console.WriteLine(employees.ContainsKey(103));

// Iterate
foreach (var employee in employees)
{
    Console.WriteLine($"{employee.Key} - {employee.Value}");
}

Output:

David
True
101 - Michael
102 - David
103 - Peter
104 - Robert

How does Dictionary work internally?

A Dictionary uses a hash table internally.

When adding a key-value pair:

1. Calculates a hash code for the key using its configured equality comparer.

2. Uses the hash code to locate a bucket.

3. Stores the key-value entry.

4. When searching, calculates the hash code again to locate the appropriate bucket.

5. Compares keys to find the correct entry.

Dictionary<int, string>
          |
          v
     Hash Function
          |
          v
      Bucket Array
          |
     +----+----------------+
     |                     |
     v                     v
  Bucket 1              Bucket 2
     |                     |
     v                     v
  101 = John            102 = David
                           |
                           v
                       103 = Peter
                   (Hash Collision)

The diagram is conceptual. Actual bucket assignments depend on hash codes and bucket count.

What is a hash collision?

A hash collision occurs when different keys map to the same bucket.

Dictionary handles collisions by maintaining chains of entries associated with the bucket and comparing keys to identify the correct entry.

Key Points

• Uses a hash table internally.

• Average lookup, insertion and deletion: O(1).

• Worst-case lookup can be O(n) when many keys collide.

• Keys must be unique.

• Uses GetHashCode() and Equals() through an equality comparer.

• Not thread-safe for concurrent modifications.

• Does not guarantee sorted key order.

2. What is the difference between Dictionary and Hashtable?

Both collections store data as key-value pairs, but the main difference is type safety.

Comparison

Example Program

Dictionary:

Dictionary<int, string> employees = new();

employees.Add(101, "John");
employees.Add(102, "David");

// employees.Add("ABC", 500); // Compile-time error

Console.WriteLine(employees[101]);

Hashtable:

using System.Collections;

Hashtable employees = new();

employees.Add(101, "John");
employees.Add(102, "David");

employees.Add("ABC", 500); // Allowed

Console.WriteLine(employees[101]);

Output:

John
John

How does it work?

Dictionary<int, string>
         |
         v
  Compile-time Check
         |
         v
  Only int keys and
  string values


Hashtable
         |
         v
  Stores Object References
         |
         v
  Different types allowed
         |
         v
  Runtime casting may be needed

Key Points

• Prefer Dictionary<TKey, TValue> in modern C#.

• Hashtable is a legacy non-generic collection.

• Dictionary avoids unnecessary boxing/unboxing for value-type keys and values.

• Dictionary provides better compile-time type safety.

• Both use hashing for fast lookup.

Interview Tip: Use Dictionary unless you are maintaining legacy code that requires Hashtable.

3. What is the difference between Dictionary and List?

Explanation

List<T> stores a collection of elements accessed primarily by index.

Dictionary<TKey, TValue> stores key-value pairs and supports fast lookup using keys.

Comparison

Example Program

Using List:

List<string> employees = new()
{
    "John",
    "David",
    "Peter"
};

Console.WriteLine(employees[1]);

Using Dictionary:

Dictionary<int, string> employees = new()
{
    { 101, "John" },
    { 102, "David" },
    { 103, "Peter" }
};

Console.WriteLine(employees[102]);

Output:

David
David

Internal Difference

List<string>
-------------------
Index       Value
-------------------
0           John
1           David
2           Peter

Access: employees[1]
           |
           v
         David


Dictionary<int, string>
-------------------
Key         Value
-------------------
101         John
102         David
103         Peter

Access: employees[102]
           |
           v
       Hash Lookup
           |
           v
         David

Real-World Scenario

Use List when:

You want to display all employees in a table.

Use Dictionary when:

You want to quickly retrieve employee details using EmployeeId.

Key Points

• List<T> is ideal for sequential data.

• Dictionary is ideal for key-based searching.

• List provides direct access by index.

• Dictionary provides average O(1) key lookup.

• Choose based on how your application accesses the data.

4. Can a Dictionary contain duplicate keys or null keys?

Explanation

A Dictionary does not allow duplicate keys or null keys.

However, duplicate values are allowed.

Example Program

Dictionary<int, string?> employees = new();

employees.Add(101, "John");
employees.Add(102, "John"); // Duplicate value allowed

// Duplicate key
// employees.Add(101, "David");
// Throws ArgumentException

// Null value
employees.Add(103, null); // Allowed

foreach (var item in employees)
{
    Console.WriteLine($"{item.Key} - {item.Value}");
}

Output:

101 - John
102 - John
103 -

Duplicate Key vs Duplicate Value

Dictionary
-----------------------
Key          Value
-----------------------
101          John
102          John    ✓ Allowed
103          David
101          Peter   X Duplicate Key
-----------------------

What happens when we use the indexer?

Dictionary<int, string> employees = new();

employees.Add(101, "John");

// Existing key is updated
employees[101] = "David";

Console.WriteLine(employees[101]);

Output:

David

The difference:

• Add() throws an exception if the key already exists.

• dictionary[key] = value updates the value if the key exists; otherwise, it inserts a new entry.

• TryAdd() returns false for an existing key without throwing.

Key Points

• Duplicate keys are not allowed.

• Duplicate values are allowed.

• Null keys are not allowed.

• Null values are allowed when the value type supports null.

• Add() throws ArgumentException for duplicate keys.

• TryAdd() safely handles duplicate keys.

5. What is the difference between ContainsKey() and TryGetValue()?

Explanation

Both methods are used to work with dictionary keys.

ContainsKey() checks whether a key exists.

TryGetValue() checks whether a key exists and retrieves its value in a single lookup.

Comparison

Example Program

Dictionary<int, string> employees = new()
{
    { 101, "John" },
    { 102, "David" }
};

// ContainsKey
if (employees.ContainsKey(101))
{
    Console.WriteLine(employees[101]);
}

// TryGetValue
if (employees.TryGetValue(102, out string? name))
{
    Console.WriteLine(name);
}
else
{
    Console.WriteLine("Employee not found");
}

Output:

John
David

Internal Working

Using ContainsKey():

ContainsKey(101)
       |
       v
   Key Lookup
       |
       v
   Key Exists?
       |
       v
employees[101]
       |
       v
   Key Lookup Again
       |
       v
     John

Using TryGetValue():

TryGetValue(101, out name)
          |
          v
      Key Lookup
          |
          v
      Key Exists?
          |
     +----+----+
     |         |
    Yes        No
     |         |
     v         v
 Return true  Return false
 Set name     Default value

Which is better?

When you need the value, prefer TryGetValue().

if (employees.TryGetValue(101, out var name))
{
    Console.WriteLine(name);
}

This avoids performing two dictionary lookups.

Key Points

• Use ContainsKey() when you only need to check existence.

• Use TryGetValue() when you need the value.

• TryGetValue() avoids KeyNotFoundException for missing keys.

• TryGetValue() performs one lookup.

• Both have average O(1) lookup complexity.

Interview Tip: For safe retrieval, TryGetValue() is generally preferred over ContainsKey() followed by indexer access.

6. What is the difference between Dictionary, SortedDictionary, and SortedList?

Explanation

All three collections store key-value pairs, but their internal data structures and sorting behavior differ.

• Dictionary<TKey, TValue> – Uses a hash table; does not maintain sorted order.

• SortedDictionary<TKey, TValue> – Uses a balanced binary search tree; maintains keys in sorted order.

• SortedList<TKey, TValue> – Uses sorted arrays; maintains keys in sorted order.

Comparison

Example Program

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

// SortedDictionary
SortedDictionary<int, string> sortedDict = new()
{
    { 3, "Peter" },
    { 1, "John" },
    { 2, "David" }
};

// SortedList
SortedList<int, string> sortedList = new()
{
    { 3, "Peter" },
    { 1, "John" },
    { 2, "David" }
};

Console.WriteLine("SortedDictionary:");

foreach (var item in sortedDict)
{
    Console.WriteLine($"{item.Key} - {item.Value}");
}

Console.WriteLine("SortedList:");

foreach (var item in sortedList)
{
    Console.WriteLine($"{item.Key} - {item.Value}");
}

Output:

SortedDictionary:
1 - John
2 - David
3 - Peter

SortedList:
1 - John
2 - David
3 - Peter

A normal Dictionary is not guaranteed to enumerate entries in sorted order.

Internal Working

1. Dictionary
   ----------
   Hash Table
       |
       +-- Bucket -> Key 3
       +-- Bucket -> Key 1
       +-- Bucket -> Key 2

   No automatic sorting


2. SortedDictionary
   ----------------
      Balanced Tree

           2
          / \
         1   3

   Sorted traversal: 1, 2, 3


3. SortedList
   ----------
   Sorted Arrays

   Keys:   [1] [2] [3]
   Values: [John] [David] [Peter]

   Keys maintained in sorted order

Real-World Scenarios

Dictionary:

Employee lookup by EmployeeId.

Dictionary<int, string> employees = new();

SortedDictionary:

Maintain dynamically changing records ordered by key.

SortedDictionary<DateTime, string> events = new();

SortedList:

Maintain relatively static configuration values sorted by key.

SortedList<int, string> priorities = new();

Key Points

• Dictionary is generally best for fast key-based lookup.

• SortedDictionary is suitable when you need sorted keys and frequent insertions/deletions.

• SortedList is suitable when you need sorted keys with relatively infrequent modifications.

• SortedList provides index-based access through its Keys and Values collections.

• All three require unique keys.

Quick Interview Revision

Most important for interviews: Understand Dictionary's internal hashing, collision handling, duplicate-key behavior, TryGetValue(), and the differences among the three dictionary collections.