I'm trying to answer this leetcode problem:

https://leetcode.com/problems/group-anagrams/

I understand it's hashmap problem, and I've elected to do something as follows:

IList<IList<string>> GroupAnagrams(string[] strs)
{
    Dictionary<SortedDictionary<char, int>, List<string>> history = new Dictionary<SortedDictionary<char, int>, List<string>>();
    foreach (string phrase in strs)
    {
        SortedDictionary<char, int> signature = new SortedDictionary<char, int>();
        foreach (char c in phrase.ToCharArray())
        {
            if (signature.ContainsKey(c))
            {
                signature[c]  = 1;
            }
            else
            {
                signature.Add(c, 1);
            }
        }
        if (history.ContainsKey(signature))
        {
            history[signature].Add(phrase);
        }
        else
        {
            history[signature] = new List<string>();
            history[signature].Add(phrase);
        }
    }

    IList<IList<string>> result = new List<IList<string>>();
    foreach (var pair in history)
    {
        result.Add(pair.Value);
    }

    return list;
}

The idea being that signature is a counter for characters. If two phrases have the same signature then they are an anagram. However, I noticed while stepping through the code via the debugger that the method call history.ContainsKey(signature) never returns true. Even when monitoring the locals in the debugger across iterations. I wondered if this was because signature should have been a SortedDictionary, but that didn't seem to have an effect. In fact, when I look at the locals for history, it seemingly has duplicate keys. Can anyone explain what's going on?

CodePudding user response：

Can anyone explain what's going on?

Dictionaries (and sorted dictionaries) are not compared by value but by reference equality. The only way ContainsKey will return true is if the actual object passed as its argument is present in the dictionary.

In other words, this code prints "false" twice:

Console.WriteLine(new Dictionary<char, int>() == new Dictionary<char, int>());
Console.WriteLine(new Dictionary<char, int> { 'a', 1 } == new Dictionary<char, int> { 'a', 1 });