LoginSignup
2
0

More than 3 years have passed since last update.

@kob58im

C# - Dictionary<TKey,TValue>のKey一致判定の内部構造を調べてみた（途中）

Last updated at Posted at 2019-11-11

調査の動機

Dictionary<string, XXX>のように、Keyとしてstringを使うことはよくやると思うが、
Dictionary<自作クラス, XXX>みたいに、Keyとしてstringやintなど以外を使いたい場面があり、落とし穴がありそうな気がしたので調べてみた。

（C#ではstringは==で内容比較をするが、通常のクラスは==は（演算子をoverrideしなければ）C言語でいうポインタを比較しているようなイメージになる。とかでKeyの一意性に問題がでそうな予感がしたため。）

結果だけ知りたい場合は、結論もしくは参考サイト参照

.NETの内部処理を確認する

Step1 - KeyからValueを取り出す処理

this[TKey]で取得設定するときに、Keyの一致性をどう判定しているか。
ILSpyで内部処理を覗いてみる。

Dictionary<TKey,TValue>クラス内部

    [__DynamicallyInvokable]
    public TValue this[TKey key]
    {
        [__DynamicallyInvokable]
        get
        {
            int num = FindEntry(key);
            if (num >= 0)
            {
                return entries[num].value;
            }
            ThrowHelper.ThrowKeyNotFoundException();
            return default(TValue);
        }
        [__DynamicallyInvokable]
        set
        {
            Insert(key, value, add: false);
        }
    }

内部では、entries[num] (numはint型)に格納されるらしい。
numを算出しているFindEntry(key)を調べればよさそう。

Step2 - KeyからHash値を取って検索する処理

Dictionary<TKey,TValue>クラス内部

private int FindEntry(TKey key)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    if (buckets != null)
    {
        int num = comparer.GetHashCode(key) & int.MaxValue;
        for (int num2 = buckets[num % buckets.Length]; num2 >= 0; num2 = entries[num2].next)
        {
            if (entries[num2].hashCode == num && comparer.Equals(entries[num2].key, key))
            {
                return num2;
            }
        }
    }
    return -1;
}

int num = comparer.GetHashCode(key) & int.MaxValue;で設定しているので、まずはcomparerを調べる。

Step3 - comparer

Dictionaryクラスの
メンバcomparerの宣言は、
private IEqualityComparer<TKey> comparer;であり、


var hoge = new Dictionary<Keyの型,Valueの型>();

のようにした場合、以下のようにコンストラクタで設定される。

Dictionary<TKey,TValue>クラス内部

public Dictionary() : this(0, (IEqualityComparer<TKey>)null)
{ /* この中は処理がない */ }

つまり、下記のコンストラクタが、capacityが0で、comparerがnullとして実行される。

Dictionary<TKey,TValue>クラス内部

    [__DynamicallyInvokable]
    public Dictionary(int capacity, IEqualityComparer<TKey> comparer) {
        ・・中略(capacityに関する処理)・・
        this.comparer = (comparer ?? EqualityComparer<TKey>.Default);
    }

つまり、（引数なしのコンストラクタを使った場合は、）
comparerには、EqualityComparer<TKey>.Default が設定される。

EqualityComparer<T>クラス

public static EqualityComparer<T> Default {
    [__DynamicallyInvokable]
    get{ return defaultComparer; }
}

private static readonly EqualityComparer<T> defaultComparer = CreateComparer();

えぐいコードきた。。

EqualityComparer<T>クラス内部

[SecuritySafeCritical]
private static EqualityComparer<T> CreateComparer()
{
    RuntimeType runtimeType = (RuntimeType)typeof(T);
    if (runtimeType == typeof(byte))
    {
        return (EqualityComparer<T>)new ByteEqualityComparer();
    }
    if (typeof(IEquatable<T>).IsAssignableFrom(runtimeType))
    {
        return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(GenericEqualityComparer<int>), runtimeType);
    }
    if (runtimeType.IsGenericType && runtimeType.GetGenericTypeDefinition() == typeof(Nullable<>))
    {
        RuntimeType runtimeType2 = (RuntimeType)runtimeType.GetGenericArguments()[0];
        if (typeof(IEquatable<>).MakeGenericType(runtimeType2).IsAssignableFrom(runtimeType2))
        {
            return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(NullableEqualityComparer<int>), runtimeType2);
        }
    }
    if (runtimeType.IsEnum)
    {
        switch (Type.GetTypeCode(Enum.GetUnderlyingType(runtimeType)))
        {
        case TypeCode.Int16:
            return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(ShortEnumEqualityComparer<short>), runtimeType);
        case TypeCode.SByte:
            return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(SByteEnumEqualityComparer<sbyte>), runtimeType);
        case TypeCode.Byte:
        case TypeCode.UInt16:
        case TypeCode.Int32:
        case TypeCode.UInt32:
            return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(EnumEqualityComparer<int>), runtimeType);
        case TypeCode.Int64:
        case TypeCode.UInt64:
            return (EqualityComparer<T>)RuntimeTypeHandle.CreateInstanceForAnotherGenericParameter((RuntimeType)typeof(LongEnumEqualityComparer<long>), runtimeType);
        }
    }
    return new ObjectEqualityComparer<T>();
}

ちゃんと解析できてないけど、
DictionaryのKeyとする自作クラスが、以下
- IEquatable<T>を実装している（Stringは実装しているようである。）
- ジェネリックを使用している
- 数値型
のいずれでもない場合は、
return new ObjectEqualityComparer<T>();
が呼ばれると思われる。ちょっと自信がないが。

Step4 - GetHashCode()

■おさらい
Step2で、int num = comparer.GetHashCode(key) & int.MaxValue;を調査対象としていた。
Step3で、comparerがObjectEqualityComparer<T>らしいことを見た。

なので、ここでは、comparer.GetHashCode(key)が何を返すかを見る。

ObjectEqualityComparer<T>クラス内部

public override int GetHashCode(T obj)
{
    return obj?.GetHashCode() ?? 0;
}

結局、KeyのクラスのGetHashCode()が呼ばれる。

いったん結論

飛躍している感が否めないが、Step2の処理の以下の部分が肝であり、


if (entries[num2].hashCode == num && comparer.Equals(entries[num2].key, key))
{
    return num2;
}

以下２点を満たせればよい。

KeyのクラスのGetHashCode()が、
【１】. 「同じ」とみなしたいデータのGetHashCode()が、同じ値を返すこと1。かつ、Equals()が同じ結果を返すこと。
【２】. 「違う」とみなしたいデータのEquals()が、異なる値を返すこと。

GetHashCode()の計算内容はどういう点を考えてつくればよいのか？
→ Equalsより処理が軽くて、できるだけ衝突しないようにするのがよい。参考サイト参照。。。

続き

Step5 - buckets

引数なしのコンストラクタを呼んだだけではnullのままであり、
Key(とValue)が追加されるときに初期化されるっぽい。

Dictionary<TKey,TValue>クラス内部

private void Insert(TKey key, TValue value, bool add)
{
    if (key == null)
    {
        ThrowHelper.ThrowArgumentNullException(ExceptionArgument.key);
    }
    if (buckets == null)
    {
        Initialize(0);
    }
    int num = comparer.GetHashCode(key) & int.MaxValue;
    int num2 = num % buckets.Length;
    int num3 = 0;
    for (int num4 = buckets[num2]; num4 >= 0; num4 = entries[num4].next)
    {
        if (entries[num4].hashCode == num && comparer.Equals(entries[num4].key, key))
        {
            if (add)
            {
                ThrowHelper.ThrowArgumentException(ExceptionResource.Argument_AddingDuplicate);
            }
            entries[num4].value = value;
            version++;
            return;
        }
        num3++;
    }
    int num5;
    if (freeCount > 0)
    {
        num5 = freeList;
        freeList = entries[num5].next;
        freeCount--;
    }
    else
    {
        if (count == entries.Length)
        {
            Resize();
            num2 = num % buckets.Length;
        }
        num5 = count;
        count++;
    }
    entries[num5].hashCode = num;
    entries[num5].next = buckets[num2];
    entries[num5].key = key;
    entries[num5].value = value;
    buckets[num2] = num5;
    version++;
    if (num3 > 100 && HashHelpers.IsWellKnownEqualityComparer(comparer))
    {
        comparer = (IEqualityComparer<TKey>)HashHelpers.GetRandomizedEqualityComparer(comparer);
        Resize(entries.Length, forceNewHashCodes: true);
    }
}

private void Initialize(int capacity)
{
    int prime = HashHelpers.GetPrime(capacity);
    buckets = new int[prime];
    for (int i = 0; i < buckets.Length; i++)
    {
        buckets[i] = -1;
    }
    entries = new Entry[prime];
    freeList = -1;
}

HashHelpers.GetPrime(capacity)
HashHelpersクラス内部

    [ReliabilityContract(Consistency.WillNotCorruptState, Cer.Success)]
    public static int GetPrime(int min)
    {
        if (min < 0)
        {
            throw new ArgumentException(Environment.GetResourceString("Arg_HTCapacityOverflow"));
        }
        for (int i = 0; i < primes.Length; i++)
        {
            int num = primes[i];
            if (num >= min)
            {
                return num;
            }
        }
        for (int j = min | 1; j < int.MaxValue; j += 2)
        {
            if (IsPrime(j) && (j - 1) % 101 != 0)
            {
                return j;
            }
        }
        return min;
    }

    public static readonly int[] primes = new int[72]
    {
        3,
        7,
        11,
        17,
        23,
        29,
        37,
        47,
        59,
        71,
        89,
        107,
        131,
        163,
        197,
        239,
        293,
        353,
        431,
        521,
        631,
        761,
        919,
        1103,
        1327,
        1597,
        1931,
        2333,
        2801,
        3371,
        4049,
        4861,
        5839,
        7013,
        8419,
        10103,
        12143,
        14591,
        17519,
        21023,
        25229,
        30293,
        36353,
        43627,
        52361,
        62851,
        75431,
        90523,
        108631,
        130363,
        156437,
        187751,
        225307,
        270371,
        324449,
        389357,
        467237,
        560689,
        672827,
        807403,
        968897,
        1162687,
        1395263,
        1674319,
        2009191,
        2411033,
        2893249,
        3471899,
        4166287,
        4999559,
        5999471,
        7199369
    };

ハッシュのテーブルの処理が結構複雑で、見る気力がなくなった。。

参考サイト

内部構造調べた後に見つけた。まだ見きれていない。
http://mocotan.hatenablog.com/entry/2017/10/31/064738

  1. GetHashCode()はObject型であればメンバとして持っているので、これをoverrideしてやればよい。 ↩

2
0
2

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
2
0