Case Insensitive Access for Generic Dictionary

Case insensitive access for generic dictionary

There's no way to specify a StringComparer at the point where you try to get a value. If you think about it, "foo".GetHashCode() and "FOO".GetHashCode() are totally different so there's no reasonable way you could implement a case-insensitive get on a case-sensitive hash map.

You can, however, create a case-insensitive dictionary in the first place using:-

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

Or create a new case-insensitive dictionary with the contents of an existing case-sensitive dictionary (if you're sure there are no case collisions):-

var oldDictionary = ...;
var comparer = StringComparer.OrdinalIgnoreCase;
var newDictionary = new Dictionary<string, int>(oldDictionary, comparer);

This new dictionary then uses the GetHashCode() implementation on StringComparer.OrdinalIgnoreCase so comparer.GetHashCode("foo") and comparer.GetHashcode("FOO") give you the same value.

Alternately, if there are only a few elements in the dictionary, and/or you only need to lookup once or twice, you can treat the original dictionary as an IEnumerable<KeyValuePair<TKey, TValue>> and just iterate over it:-

var myKey = ...;
var myDictionary = ...;
var comparer = StringComparer.OrdinalIgnoreCase;
var value = myDictionary.FirstOrDefault(x => String.Equals(x.Key, myKey, comparer)).Value;

Or if you prefer, without the LINQ:-

var myKey = ...;
var myDictionary = ...;
var comparer = StringComparer.OrdinalIgnoreCase;
int? value;
foreach (var element in myDictionary)
{
  if (String.Equals(element.Key, myKey, comparer))
  {
    value = element.Value;
    break;
  }
}

This saves you the cost of creating a new data structure, but in return the cost of a lookup is O(n) instead of O(1).

Case-INsensitive Dictionary with string key-type in C#

This seemed related, but I didn't understand it properly: c# Dictionary: making the Key case-insensitive through declarations

It is indeed related. The solution is to tell the dictionary instance not to use the standard string compare method (which is case sensitive) but rather to use a case insensitive one. This is done using the appropriate constructor:

var dict = new Dictionary<string, YourClass>(
        StringComparer.InvariantCultureIgnoreCase);

The constructor expects an IEqualityComparer which tells the dictionary how to compare keys.

StringComparer.InvariantCultureIgnoreCase gives you an IEqualityComparer instance which compares strings in a case-insensitive manner.

O(1) Dictionary both case sensitive and insensitive

I recently ran across this question since I needed to solve for the same scenario, with the following guidelines:

• Both types of lookups should be fast (avoid O(n) for case-sensitive path).
• Use a single dictionary rather than two separate dictionaries (avoid double the space requirement).
• Avoid needless allocations via string conversion (.ToLower()) when performing lookups.
• Trade a reasonable amount of additional needed memory for satisfying the above.

I didn't feel that any of the current answers met the above and, as a result, I came up with the following dictionary definition:

Dictionary<string, (string Key, T Value)> _dict = 
    new Dictionary<string, (string Key, T Value)>(StringComparer.OrdinalIgnoreCase);

This allows for case-insensitive hashing of the key, while using a ValueTuple to store the actual key in its raw string form for additional case-sensitive comparisons, if need be, alongside the value. The full implementation looks like the following:

public class MultiCaseDictionary<T>
{
    public MultiCaseDictionary() : this(0) { }

    public MultiCaseDictionary(int capacity)
    {
        _dict = new(capacity, StringComparer.OrdinalIgnoreCase);
    }

    private readonly Dictionary<string, (string Key, T Value)> _dict;

    public bool TryGetValue(string key, out T value, bool isCaseInsensitive = true)
    {
        if (_dict.TryGetValue(key, out (string Key, T Value) match))
        {
            if (isCaseInsensitive)
            {
                value = match.Value;
                return true;
            }

            if (key.Equals(match.Key))
            {
                value = match.Value;
                return true;
            }
        }

        value = default;
        return false;
    }

    public void Add(string key, T value)
    {
        _dict[key] = (key, value);
    }
}

This structure results in excellent performance for both the case sensitive and insensitive paths, and the case-sensitive path is slightly slower than the case-sensitive (optimal) path in the accepted answer due to needing to perform extra work.

However, it is orders of magnitude faster for the case-insensitive path, due to the accepted answer having a runtime complexity of O(n). In addition, the case-insensitive search of MultiCaseDictionary is actually faster than the case-sensitive search of CaseSensitiveDictionary.

Finally, the Add path is slower in the MultiCaseDictionary due to needing to construct a ValueTuple. The following benchmark demonstrates both implementations, running on .NET 6:

Implementations

public class MultiCaseDictionary<T>
{
    public MultiCaseDictionary() : this(0) { }

    public MultiCaseDictionary(int capacity)
    {
        _dict = new(capacity, StringComparer.OrdinalIgnoreCase);
    }

    private readonly Dictionary<string, (string Key, T Value)> _dict;

    public bool TryGetValue(string key, out T value, bool isCaseInsensitive = true)
    {
        if (_dict.TryGetValue(key, out (string Key, T Value) match))
        {
            if (isCaseInsensitive)
            {
                value = match.Value;
                return true;
            }

            if (key.Equals(match.Key))
            {
                value = match.Value;
                return true;
            }
        }

        value = default;
        return false;
    }

    public void Add(string key, T value)
    {
        _dict[key] = (key, value);
    }
}

public class CaseSensitiveDictionary<T>
{
    public CaseSensitiveDictionary() : this(0) { }

    public CaseSensitiveDictionary(int capacity)
    {
        _dict = new(capacity);
    }

    private readonly Dictionary<string, T> _dict;

    public bool TryGetValue(string key, out T value, bool isCaseInsensitive = true)
    {
        if (!isCaseInsensitive)
        {
            if (_dict.TryGetValue(key, out value))
            {
                return true;
            }
        }
        else
        {
            key = _dict.Keys.FirstOrDefault(k =>
                string.Compare(key, k, StringComparison.OrdinalIgnoreCase) == 0);
            if (key == null)
            {
                value = default;
                return false;
            }

            value = _dict[key];
            return true;
        }

        value = default;
        return false;
    }

    public void Add(string key, T value)
    {
        _dict[key] = value;
    }
} 

Benchmarks

The benchmarks preload 1000 entries for TryGetValue tests to demonstrate O(n) behavior. In addition, they insert 10 entries for Add tests to check space requirements and add performance degradation.

[SimpleJob(RuntimeMoniker.Net60, invocationCount: 50000)]
[MemoryDiagnoser]
[GroupBenchmarksBy(BenchmarkLogicalGroupRule.ByCategory)]
[CategoriesColumn]
public class CaseSensitiveDictionaryBenchmarks
{
    // use longer key to simulate expected hash costs
    private const string Key = "100000500";
    private const int Capacity = 1000;
    private const int Iterations = 9;

    private MultiCaseDictionary<int> _multiCaseDictionary;
    private CaseSensitiveDictionary<int> _caseSensitiveDictionary;

    [IterationSetup(Targets = new string[] {
        nameof(MultiCaseDictionary_Search),
        nameof(MultiCaseDictionary_InsensitiveSearch)
    })]
    public void SetupMultiCase()
    {
        _multiCaseDictionary = new MultiCaseDictionary<int>(Capacity);
        for (int i = 100000000; i < 100001000; i++)
        {
            _multiCaseDictionary.Add(i.ToString(), i);
        }
    }

    [IterationSetup(Targets = new string[] {
        nameof(CaseSensitiveDictionary_Search),
        nameof(CaseSensitiveDictionary_InsensitiveSearch),
    })]
    public void SetupCaseSensitive()
    {
        _caseSensitiveDictionary = new CaseSensitiveDictionary<int>(Capacity);
        for (int i = 100000000; i < 100001000; i++)
        {
            _caseSensitiveDictionary.Add(i.ToString(), i);
        }
    }

    [Benchmark(Baseline = true), BenchmarkCategory("TryGetValue")]
    public int CaseSensitiveDictionary_Search()
    {
        int result;
        for (int i = 0; i < Iterations; i++)
        {
            _caseSensitiveDictionary.TryGetValue(Key, out result, false);
        }
        _caseSensitiveDictionary.TryGetValue(Key, out result, false);
        return result;
    }

    [Benchmark, BenchmarkCategory("TryGetValue")]
    public int CaseSensitiveDictionary_InsensitiveSearch()
    {
        int result;
        for (int i = 0; i < Iterations; i++)
        {
            _caseSensitiveDictionary.TryGetValue(Key, out result, true);
        }
        _caseSensitiveDictionary.TryGetValue(Key, out result, true);
        return result;
    }

    [Benchmark, BenchmarkCategory("TryGetValue")]
    public int MultiCaseDictionary_Search()
    {
        int result;
        for (int i = 0; i < Iterations; i++)
        {
            _multiCaseDictionary.TryGetValue(Key, out result, false);
        }
        _multiCaseDictionary.TryGetValue(Key, out result, false);
        return result;
    }

    [Benchmark, BenchmarkCategory("TryGetValue")]
    public int MultiCaseDictionary_InsensitiveSearch()
    {
        int result;
        for (int i = 0; i < Iterations; i++)
        {
            _multiCaseDictionary.TryGetValue(Key, out result, true);
        }
        _multiCaseDictionary.TryGetValue(Key, out result, true);
        return result;
    }

    [Benchmark(Baseline = true), BenchmarkCategory("Add")]
    public CaseSensitiveDictionary<int> CaseSensitiveDictonary_Add()
    {
        _caseSensitiveDictionary = new CaseSensitiveDictionary<int>(Capacity);
        for (int i = 100000000; i < 100000010; i++)
        {
            _caseSensitiveDictionary.Add(i.ToString(), i);
        }

        return _caseSensitiveDictionary;
    }

    [Benchmark, BenchmarkCategory("Add")]
    public MultiCaseDictionary<int> MultiCaseDictionary_Add()
    {
        _multiCaseDictionary = new MultiCaseDictionary<int>(Capacity);
        for (int i = 100000000; i < 100000010; i++)
        {
            _multiCaseDictionary.Add(i.ToString(), i);
        }

        return _multiCaseDictionary;
    }
} 

Results

BenchmarkDotNet=v0.13.2, OS=macOS Catalina 10.15.7 (19H1417) [Darwin 19.6.0]
Intel Core i5-1038NG7 CPU 2.00GHz, 1 CPU, 8 logical and 4 physical cores
.NET SDK=6.0.400
  [Host]     : .NET 6.0.8 (6.0.822.36306), X64 RyuJIT AVX2
  Job-NQOSHT : .NET 6.0.8 (6.0.822.36306), X64 RyuJIT AVX2

Runtime=.NET 6.0  InvocationCount=50000  

public struct Key : IEquatable<Key>
{
    private readonly int hashCode;

    public Key(int key1, string key2)
    {
        this.Key1 = key1;
        this.Key2 = key2;
        this.hashCode = HashCode.Combine(key1, StringComparer.OrdinalIgnoreCase.GetHashCode(Key2));
    }

    public int Key1 { get; }
    public string Key2 { get; }

    public bool Equals(Key other)
        => this.hashCode == other.hashCode
            && this.Key1 == other.Key1
            && string.Equals(this.Key2, other.Key2, StringComparison.OrdinalIgnoreCase);

    public override bool Equals(object obj)
        => obj is Key key && this.Equals(key);

    public override int GetHashCode() => this.hashCode;
    
    public static implicit operator (int key1, string key2)(Key key)
        => (key1: key.Key1, key2: key.Key2);
    
    public static implicit operator Key((int key1, string key2) key)
        => new Key(key.key1, key.key2);
    
    public void Deconstruct(out int key1, out string key2)
        => (key1, key2) = (this.Key1, this.Key2);
}

var key = new Key(1, "one");
var (k1, k2) = key;
(int key1, string key2) t = key;
t.key1 = 2;
t.key2 = "two";
key = t;

public class MyTupleComparer : IEqualityComparer<(int key1, string key2)>
{
    public bool Equals((int key1, string key2) x, (int key1, string key2) y)
        => x.key1 == y.key1
            && string.Equals(x.key2, y.key2, StringComparison.OrdinalIgnoreCase);

    public int GetHashCode((int key1, string key2) obj)
    => HashCode.Combine(obj.key1, StringComparer.OrdinalIgnoreCase.GetHashCode(obj.key2));
}

public static class DictionaryExtension
{
    public static bool ContainsKeyIgnoreCase<TKey, TValue>(this Dictionary<TKey, TValue> dictionary, TKey key)
    {
        bool? keyExists;

        var keyString = key as string;
        if (keyString != null)
        {
            // Key is a string.
            // Using string.Equals to perform case insensitive comparison of the dictionary key.
            keyExists =
                dictionary.Keys.OfType<string>()
                .Any(k => string.Equals(k, keyString, StringComparison.InvariantCultureIgnoreCase));
        }
        else
        {
            // Key is any other type, use default comparison.
            keyExists = dictionary.ContainsKey(key);
        }

        return keyExists ?? false;
    }
}

var foo = new Foo();
var dictionary =
    new Dictionary<dynamic, string>
    {
        { 1, "One" },     // key is numeric
        { "Two", "Two" }, // key is string
        { foo, "Foo" }    // key is object
    };

dictionary.ContainsKeyIgnoreCase("two");     // Returns true
dictionary.ContainsKeyIgnoreCase("TwO");     // Returns true
dictionary.ContainsKeyIgnoreCase("aBc");     // Returns false
dictionary.ContainsKeyIgnoreCase(1);         // Returns true
dictionary.ContainsKeyIgnoreCase(2);         // Returns false
dictionary.ContainsKeyIgnoreCase(foo);       // Returns true
dictionary.ContainsKeyIgnoreCase(new Foo()); // Returns false

// definition 
Dictionary<string, PIPoint> PointsDictionary = new Dictionary<string, PIPoint>(StringComparer.CurrentCultureIgnoreCase);

// later *reassignment*
PointsDictionary = RegisteredPoints.ToDictionary(x => x.Name, x => x);

PointsDictionary = RegisteredPoints.ToDictionary(x => x.Name, x => x, StringComparer.CurrentCultureIgnoreCase);

PointsDictionary = RegisteredPoints.ToDictionary(x => x.Name, StringComparer.CurrentCultureIgnoreCase);

PointsDictionary = RegisteredPoints.ToDictionary(x => x.Name, PointsDictionary.Comparer);

PointsDictionary.Clear():
foreach(var p in RegisteredPoints) 
   PointsDictionary[p.Name] = p: