On Dictionary<TKey, TValue> in .NET

geelawdicttkeytvaluedotnet.cs

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace TestDict
{
    struct SampleStructIS
    {
        int i;
        string s;
        public SampleStructIS(int i_, string s_) { i = i_; s = s_; }
    }
    struct SampleStructSI
    {
        string s;
        int i;
        public SampleStructSI(string s_, int i_) { s = s_; i = i_; }
    }
    struct SampleStructISEquatable : IEquatable<SampleStructISEquatable>
    {
        int i;
        string s;
        public SampleStructISEquatable(int i_, string s_) { i = i_; s = s_; }
        public bool Equals(SampleStructISEquatable other) { return i == other.i && s == other.s; }
    }
    struct SampleStructISCustomizedHashCode
    {
        int i;
        string s;
        public SampleStructISCustomizedHashCode(int i_, string s_) { i = i_; s = s_; }
        public override int GetHashCode()
        {
            return i ^ s.GetHashCode();
        }
    }
    struct SampleStructISCHCIE : IEquatable<SampleStructISCHCIE>
    {
        int i;
        string s;
        public SampleStructISCHCIE(int i_, string s_) { i = i_; s = s_; }
        public override int GetHashCode()
        {
            return i ^ s.GetHashCode();
        }
        public bool Equals(SampleStructISCHCIE other) { return i == other.i && s == other.s; }
    }
    class Program
    {
        static void Test<T>(Func<int, string, T> construct)
        {
            DateTime dt = DateTime.UtcNow;
            Dictionary<T, int> dict = new Dictionary<T, int>();
            for (int i = 0; i < (1 << 7); ++i)
                for (int j = 0; j < (1 << 7); ++j)
                    dict[construct(i, j.ToString())] = i + j;
            for (int i = 0; i < (1 << 7); ++i)
                for (int j = 0; j < (1 << 7); ++j)
                    dict[construct((i ^ 12), (j ^ 21).ToString())] = i + j;
            if (dict.Count == ((1 << 7) * (1 << 7)))
                Console.WriteLine("{0}", DateTime.UtcNow - dt);
            else
                Console.WriteLine("Doesn't work.");
        }
        /*
         * IS:                         00:00:02.4531267
         * SI:                         00:00:02.4522465
         * ISEquatable:                00:00:00.1406311
         * ISCustomizedHashCode:       00:00:00.1249934
         * ISCHCIE:                    00:00:00.0312505
         * anonymous type:             00:00:00.0312516
         * 结论：直接使用虽然可以正常工作，但是性能损失较大，性能损失分为两方面：
         * 1. GetHashCode 的自动实现不好，导致大量重复的 HashCode
         * （实际上似乎 HashCode 只和第一个成员有关系？）
         * 2. 由于没有实现 IEquatable<TKey> 而使用了 bool TKey.Equals(Object other)
         * 装箱和拆箱（这个实现要检查类型和拆箱）
         * 
         * 提供较好的 int TKey.GetHashCode() 并实现 IEquatable<TKey> 有助于改善性能。
         * 匿名类型（似乎是引用类型）从数据上看，帮我们实现了值语义的比较（包括实现 IEquatable<T>），
         * 并提供了较好的 GetHashCode，这是因为匿名类型的对象是 immutable 的（和 string 一个道理）。
         */
        static void Main(string[] args)
        {
            Console.Write("IS:\t\t\t");
            Test((int i, string s) => new SampleStructIS(i, s));
            Console.Write("SI:\t\t\t");
            Test((int i, string s) => new SampleStructSI(s, i));
            Console.Write("ISEquatable:\t\t");
            Test((int i, string s) => new SampleStructISEquatable(i, s));
            Console.Write("ISCustomizedHashCode:\t");
            Test((int i, string s) => new SampleStructISCustomizedHashCode(i, s));
            Console.Write("ISCHCIE:\t\t");
            Test((int i, string s) => new SampleStructISCHCIE(i, s));
            Console.Write("anonymous type:\t\t");
            Test((int i, string s) => new { i, s });
            Console.ReadLine();
        }
    }
}

更正：并不能得出“匿名类型 T 实现了 IEquatable”，因为这里不存在拆箱时间，再做一个引用类型的测试可以看到即使不实现 IEquatable 也可以很快。但是后来观察到匿名类型比较慢，原因不明。

显然匿名类型会慢，原生的引用类型无论是GetHashCode还是Equals都是最快的。