Hash Tables (Dictionaries)

A hash table maps keys to values using a hash function, providing O(1) average lookup, insertion, and deletion.

Dictionary

C#'s Dictionary is the standard hash table implementation:

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

// Add entries
ages["Alice"] = 30;
ages["Bob"] = 25;
ages.Add("Charlie", 35);  // throws if key exists

// Lookup
Console.WriteLine(ages["Alice"]); // 30

// Safe lookup with TryGetValue
if (ages.TryGetValue("Dave", out int age))
    Console.WriteLine(age);
else
    Console.WriteLine("Dave not found");

Iterating a Dictionary

foreach (KeyValuePair<string, int> kvp in ages)
{
    Console.WriteLine($"{kvp.Key}: {kvp.Value}");
}

// Deconstruct syntax (cleaner)
foreach (var (name, a) in ages)
{
    Console.WriteLine($"{name}: {a}");
}

Common Patterns

Word frequency counter:

string[] words = "the cat sat on the mat the cat".Split(' ');
var freq = new Dictionary<string, int>();

foreach (string word in words)
{
    if (freq.ContainsKey(word))
        freq[word]++;
    else
        freq[word] = 1;
}

foreach (var (word, count) in freq)
    Console.WriteLine($"{word}: {count}");
// the: 3, cat: 2, sat: 1, on: 1, mat: 1

Hash Collisions

When two keys hash to the same bucket, a collision occurs. C#'s Dictionary handles this automatically using chaining. You rarely need to worry about it, but:

• Override GetHashCode() and Equals() for custom key types
• Poor hash functions degrade performance to O(n)

Related Collections