Dictionary in C#

1. Internal Structure

A Dictionary internally maintains two main arrays

Each Entry looks like this

struct Entry<TKey, TValue> {
    public int hashCode;   // Hash code of the key
    public int next;       // Index of next entry (for collision chain)
    public TKey key;       // Actual key
    public TValue value;   // Actual value
}

2. Hashing and Bucket Index Calculation

When you insert a key

dict.Add("apple", 10);

The following happens internally

• GetHashCode() is called on the key ("apple".GetHashCode()).
• Dictionary ensures the hash is non-negative

  int hash = key.GetHashCode() & 0x7FFFFFFF;

• It finds the bucket index

  int bucketIndex = hash % buckets.Length;

• This decides where the entry should be stored.

3. Insertion Process

Add new entry and store its index in buckets[bucketIndex].

Traverse the chain (linked through next pointer) and

• If the key already exists : throw exception (ArgumentException).
• Otherwise, append the new entry at the start of the chain.

Note :- C# Dictionary uses separate chaining to handle collisions, not open addressing.

4. Collision Handling

A collision occurs when two different keys generate the same hash bucket index.

dict.Add("CAT", 1);
dict.Add("TAC", 2); // May hash to the same bucket

• Both "CAT" and "TAC" map to the same bucket index.
• The new entry ("TAC") links to the existing entry ("CAT") using the next pointer, forming a short chain.
• During lookups or deletions, the dictionary traverses this chain sequentially to find the correct key.

• Average lookup time remains O(1) due to efficient hashing.
• However, if many keys collide in the same bucket, performance can degrade toward O(n) in the worst case.

Note : The C# Dictionary uses separate chaining (linked entries) to handle collisions, not open addressing.

5. Lookup Process

When you access a value using a key, such as

dict["apple"];

• The dictionary computes the hash code for "apple" and determines the corresponding bucket index.
• It looks inside that bucket and follows any linked entries (via the next pointer).
• For each entry in the chain: If both the hash code and key equality (Equals) match, the value is returned immediately.
• This ensures fast key lookups typically O(1) time on average and if many keys hash to the same bucket (e.g., due to poor hash distribution or hash flooding), performance can degrade toward O(n) in the worst case.

In .NET, the dictionary mitigates worst-case scenarios by using a high-quality hash algorithm and rehashing when necessary, keeping lookups extremely fast in practice.

6. Rehashing & Resizing

When a dictionary grows close to its capacity (typically at ~75% load factor), it automatically resizes and rehashes its entries to maintain performance.

• A larger, prime-sized internal array of buckets is created.
• All existing entries are rehashed (their hash codes are recalculated and redistributed into new buckets).
• The dictionary updates its internal references to the new arrays.

Purpose :- This minimizes collisions and preserves O(1) average-time complexity for lookups and insertions.

threshold = (int)(buckets.Length * 0.75);
if (count >= threshold)
    Resize();

Rehashing ensures that even as data grows, the dictionary remains efficient and evenly balanced across buckets.

7. Removing an Element

When you remove an entry, such as:

dict.Remove("apple");

• The dictionary calculates the hash code for "apple" and finds the corresponding bucket.
• It walks through the chain of entries in that bucket (via the next pointer).
• Once the matching key is found, the dictionary adjusts the next pointer of the previous entry to bypass the one being removed.
• The removed entry’s slot is marked as free and can be reused for future insertions.

The Remove() operation maintains the dictionary’s structure while ensuring efficient memory reuse and keeping average performance at O(1).

8. Equality Compare

A Dictionary uses an IEqualityComparer<TKey> to determine key equality and compute hash codes.

• Default Behavior : Uses EqualityComparer<TKey>.Default, which relies on the key type’s built-in Equals() and GetHashCode() methods.
• Custom Comparers : You can supply a custom comparer to control how keys are compared for example, to make lookups case-insensitive for strings.

var dict = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

Now, both "Cat" and "cat" are treated as the same key, since the comparer ignores case differences.

Custom equality comparers are powerful when working with case-insensitive strings, complex objects or keys that require domain-specific comparison logic.

9. Thread Safety

• A standard Dictionary<TKey, TValue> is not thread-safe for write operations (add, remove or update).
• It is thread-safe for read-only access but only if no thread modifies the dictionary during reading.
• For safe concurrent access in multi-threaded environments, use: ConcurrentDictionary<TKey, TValue>.
• ConcurrentDictionary provides built-in synchronization, allowing multiple threads to read and modify data safely without explicit locks.

1. Dictionary<TKey, TValue>()

Creates a new empty dictionary with the default initial capacity and default equality comparer for keys. Use when you want a simple dictionary with default settings.

var dict = new Dictionary<string, int>();

2. Dictionary<TKey, TValue>(IDictionary<TKey, TValue> dictionary)

Initializes a new dictionary that contains elements copied from the specified IDictionary. Use when you want to create a dictionary as a copy of another dictionary.

var oldDict = new Dictionary<string, int> { { "A", 1 }, { "B", 2 } };
var newDict = new Dictionary<string, int>(oldDict);

3. Dictionary<TKey, TValue>(IDictionary<TKey, TValue> dictionary, IEqualityComparer<TKey> comparer)

Creates a dictionary with elements copied from another dictionary and uses a specified equality comparer for keys. Use when copying a dictionary but want a custom key comparison (e.g., case-insensitive strings).

var oldDict = new Dictionary<string, int> { { "A", 1 } };
var newDict = new Dictionary<string, int>(oldDict, StringComparer.OrdinalIgnoreCase);

4. Dictionary<TKey, TValue>(IEqualityComparer<TKey> comparer)

Creates an empty dictionary using a specified equality comparer for keys. Use when you need a custom comparison for keys (case-insensitive, culture-specific, etc.) but don’t have an initial dictionary.

var dict = new Dictionary<string, int>(StringComparer.OrdinalIgnoreCase);

5. Dictionary<TKey, TValue>(Int32 capacity)

Creates an empty dictionary with the specified initial capacity. Use when you know approximately how many elements the dictionary will hold, improving performance by reducing internal resizing.

var dict = new Dictionary<string, int>(100); // Initial capacity = 100

6. Dictionary<TKey, TValue>(Int32 capacity, IEqualityComparer<TKey> comparer)

Creates an empty dictionary with a specified initial capacity and custom key comparer. Use optimizing performance while using custom key comparison.

var dict = new Dictionary<string, int>(50, StringComparer.OrdinalIgnoreCase);

7. Dictionary<TKey, TValue>(SerializationInfo info, StreamingContext context)

Initializes a dictionary from serialized data (used for deserialization). Use when deserializing a dictionary (e.g., from a file, network or other storage).

// Used internally during deserialization
protected Dictionary(SerializationInfo info, StreamingContext context) { }

1. Initialize with Initial Values

You can create a dictionary and assign key-value pairs directly during declaration using collection initializer

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<string, string> dict = new Dictionary<string, string> {
            {"language", "C#"},
            {"topic", "Dictionary"},
            {"label", "Beginner"}
        };
        Console.WriteLine("We are learning " + dict["language"] + " " + dict["topic"] + " and level: " + dict["label"]);
    }
}

2. Direct Assignment

You can create an empty dictionary and add elements by assigning values to keys:

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<string, string> dict = new Dictionary<string, string>();
        dict["language"] = "C#";
        dict["topic"] = "Dictionary";
        dict["label"] = "Beginner";
        Console.WriteLine("We are learning " + dict["language"] + " " + dict["topic"] + " and level: " + dict["label"]);
    }
}

3. Using Add() Method

You can add elements to a dictionary using the Add() method

using System;
using System.Collections.Generic;

class Program
{
    static void Main()
    {
        Dictionary<string, string> dict = new Dictionary<string, string>();
        dict.Add("language", "C#");
        dict.Add("topic", "Dictionary");
        dict.Add("label", "Beginner");
        Console.WriteLine("We are learning " + dict["language"] + " " + dict["topic"] + " and level: " + dict["label"]);
    }
}