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

# 調査の動機

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

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

結果だけ知りたい場合は、[結論](https://qiita.com/kob58im/items/a2b8b695c5553f77151f#%E3%81%84%E3%81%A3%E3%81%9F%E3%82%93%E7%B5%90%E8%AB%96)もしくは[参考サイト](https://qiita.com/kob58im/items/a2b8b695c5553f77151f#%E5%8F%82%E8%80%83%E3%82%B5%E3%82%A4%E3%83%88)参照


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

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

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

```csharp:Dictionary&lt;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値を取って検索する処理

```csharp:Dictionary&lt;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;`であり、

```csharp

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

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

```csharp:Dictionary&lt;TKey,TValue>クラス内部

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

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

```csharp:Dictionary&lt;TKey,TValue>クラス内部

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

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


```csharp:EqualityComparer&lt;T>クラス

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

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

えぐいコードきた。。

```csharp:EqualityComparer&lt;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`は実装しているようである。）
- ジェネリックを使用している
- 数値型
の<b>いずれでもない場合</b>は、
`return new ObjectEqualityComparer<T>();`
が呼ばれると思われる。ちょっと自信がないが。

## Step4 - GetHashCode()

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

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

```csharp:ObjectEqualityComparer&lt;T>クラス内部

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

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

# いったん結論

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

```csharp

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)が追加されるときに初期化されるっぽい。

```csharp:Dictionary&lt;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;
}
```


<details><summary> HashHelpers.GetPrime(capacity) </summary><div>

```csharp: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
	};
```

</div></summary>


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

# 参考サイト

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

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