【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。
- 2013.01.15 Tuesday
- 20:10
JUGEMテーマ:コンピュータ
Dictionary<T, TKey>の実装が、前々から気になっていたので、調べてみました。今回は、リフレクションを利用して、公開されていないフィールドの状態を観察することで、Dictionaryの内部で扱われているデータ構造やアルゴリズムを想像してみました。非公開な部分なので、バージョンによって差異がある可能性もあり、また、そもそも想像なので、不正確なことこの上ないことは、あらかじめご了承ください。
Dictionary<T, TKey>の実装が、前々から気になっていたので、調べてみました。今回は、リフレクションを利用して、公開されていないフィールドの状態を観察することで、Dictionaryの内部で扱われているデータ構造やアルゴリズムを想像してみました。非公開な部分なので、バージョンによって差異がある可能性もあり、また、そもそも想像なので、不正確なことこの上ないことは、あらかじめご了承ください。
Dictionary<T, TKey>を観察するとpublicでないフィールドに
private int[] buckets;
private Entry<TKey, TValue>[] entries;
private Entry<TKey, TValue>[] entries;
というのがあります。他にも沢山ありますが、アルゴリズムに関連しそうなネーミングなので、この二つを観察することにしてます。ちなみにEntry<T, TValue>構造体は以下の定義となっているようです。
private struct Entry
{
public int hashCode;
public int next;
public TKey key;
public TValue value;
}
{
public int hashCode;
public int next;
public TKey key;
public TValue value;
}
この構造体のメンバーの名前から想像するに、hashCodeはハッシュコード、nextは次を示す何かのインデックス?、keyはおそらくDictinaryのKey、valueはおそらくDictionaryのValueという具合に予測できます。
それでは、bucketsとentriesをリフレクションを使って状態の変化を見ていきたいと思います。
書いたコードは以下の通り、
using System;
using System.Collections.Generic;
using System.Reflection;
namespace Art55.HackDecitionary20120115_001
{
class Program
{
static void Main()
{
var dictionary = new Dictionary<int, string>();
{
class Program
{
static void Main()
{
var dictionary = new Dictionary<int, string>();
dictionary.Add(2, "A");
Console.WriteLine("Add Key 2");
ShowDictionaryState(dictionary);
Console.WriteLine("Add Key 2");
ShowDictionaryState(dictionary);
dictionary.Add(0, "B");
Console.WriteLine("Add Key 0");
ShowDictionaryState(dictionary);
Console.WriteLine("Add Key 0");
ShowDictionaryState(dictionary);
dictionary.Add(1, "C");
Console.WriteLine("Add Key 1");
ShowDictionaryState(dictionary);
}
Console.WriteLine("Add Key 1");
ShowDictionaryState(dictionary);
}
private static void ShowDictionaryState(Dictionary<int, string> dictionary)
{
var bucketsValue = GetFieldValue<int[]>(dictionary, "buckets");
for (int i = 0; i < bucketsValue.Length; i++)
{
Console.WriteLine("buckets[{0}]:{1}", i, bucketsValue[i]);
}
{
var bucketsValue = GetFieldValue<int[]>(dictionary, "buckets");
for (int i = 0; i < bucketsValue.Length; i++)
{
Console.WriteLine("buckets[{0}]:{1}", i, bucketsValue[i]);
}
Array entriesValue = GetFieldValue<Array>(dictionary, "entries");
for (int i = 0; i < entriesValue.Length; i++)
{
object entry = entriesValue.GetValue(i);
var hashCode = GetFieldValue<int>(entry, "hashCode");
var next = GetFieldValue<int>(entry, "next");
var key = GetFieldValue<int>(entry, "key");
var value = GetFieldValue<string>(entry, "value");
Console.WriteLine("Entry[{0}]:hashCode {1,5},next {2,2},key {3,2},value {4}", i, hashCode, next, key, value);
}
}
for (int i = 0; i < entriesValue.Length; i++)
{
object entry = entriesValue.GetValue(i);
var hashCode = GetFieldValue<int>(entry, "hashCode");
var next = GetFieldValue<int>(entry, "next");
var key = GetFieldValue<int>(entry, "key");
var value = GetFieldValue<string>(entry, "value");
Console.WriteLine("Entry[{0}]:hashCode {1,5},next {2,2},key {3,2},value {4}", i, hashCode, next, key, value);
}
}
private static T GetFieldValue<T>(object instance, string fieldName)
{
var field = instance.GetType().GetField(fieldName, BindingFlags.Instance | BindingFlags.NonPublic | BindingFlags.Public);
return (T)field.GetValue(instance);
}
}
}
{
var field = instance.GetType().GetField(fieldName, BindingFlags.Instance | BindingFlags.NonPublic | BindingFlags.Public);
return (T)field.GetValue(instance);
}
}
}
実行すると
Add Key 2
buckets[0]:-1
buckets[1]:-1
buckets[2]:0
Entry[0]:hashCode 2,next -1,key 2,value A
Entry[1]:hashCode 0,next 0,key 0,value
Entry[2]:hashCode 0,next 0,key 0,value
Add Key 0
buckets[0]:1
buckets[1]:-1
buckets[2]:0
Entry[0]:hashCode 2,next -1,key 2,value A
Entry[1]:hashCode 0,next -1,key 0,value B
Entry[2]:hashCode 0,next 0,key 0,value
Add Key 1
buckets[0]:1
buckets[1]:2
buckets[2]:0
Entry[0]:hashCode 2,next -1,key 2,value A
Entry[1]:hashCode 0,next -1,key 0,value B
Entry[2]:hashCode 1,next -1,key 1,value C
実行結果を観察すると、最初にDcitionaryにKeyが2、Valueが"A"を設定したタイミングでbucketsには3つの要素があり、2番目の要素に0で後は-1になっています。後の結果を見る限り-1がなし、-1以外の場合は、Entryのインデックスに対応しているように見えます。つまりKey 2は、bucketsの2番目の要素が示す値が0なので、Entryの0番目の要素の値に対応していると想像できます。
不思議な事に、Keyを一つ加えた状態で、bucketsやEntryが3つあります。おそらくはハッシュコードを配列の要素数で割った余りで配列のindexに対応付けているものだと思われますが、要素数の増減を観察すると面白い発見があるかもしれません。
ハッシュコードを要素数で割ったあまりという考えで結果を対応づけると、
2 mod 3 = 2
0 mod 3 = 0
1 mod 3 = 1
という結果になるため
2 mod 3 = 2 -> buckets[2]:0 -> Entry[0]:hashCode 2,next -1,key 2,value A
0 mod 3 = 0 -> buckets[0]:1 -> Entry[1]:hashCode 0,next -1,key 0,value B
1 mod 3 = 1 -> buckets[1]:2 -> Entry[2]:hashCode 1,next -1,key 1,value C
という具合に、ハッシュコードからbucketsのインデックスが対応付けられ、その値からどのEntryに対応付けいるかというところまでわかりました。
では、コードを変更して、ハッシュキーがぶつかった場合はどうなるのかを見てみたいと思います。
0 mod 3 = 0
3 mod 3 = 0
なので、この例で行くと
static void Main()
{
var dictionary = new Dictionary<int, string>();
dictionary.Add(2, "A");
Console.WriteLine("Add Key 2");
ShowDictionaryState(dictionary);
Console.WriteLine("Add Key 2");
ShowDictionaryState(dictionary);
dictionary.Add(0, "B");
Console.WriteLine("Add Key 0");
ShowDictionaryState(dictionary);
Console.WriteLine("Add Key 0");
ShowDictionaryState(dictionary);
dictionary.Add(3, "C");
Console.WriteLine("Add Key 1");
ShowDictionaryState(dictionary);
}
Console.WriteLine("Add Key 1");
ShowDictionaryState(dictionary);
}
実行結果は
Add Key 2
buckets[0]:-1
buckets[1]:-1
buckets[2]:0
Entry[0]:hashCode 2,next -1,key 2,value A
Entry[1]:hashCode 0,next 0,key 0,value
Entry[2]:hashCode 0,next 0,key 0,value
Add Key 0
buckets[0]:1
buckets[1]:-1
buckets[2]:0
Entry[0]:hashCode 2,next -1,key 2,value A
Entry[1]:hashCode 0,next -1,key 0,value B
Entry[2]:hashCode 0,next 0,key 0,value
Add Key 3
buckets[0]:2
buckets[1]:-1
buckets[2]:0
Entry[0]:hashCode 2,next -1,key 2,value A
Entry[1]:hashCode 0,next -1,key 0,value B
Entry[2]:hashCode 3,next 1,key 3,value C
0と3でハッシュコードの要素割りのあまりが同じ0になっています。これをたぐっていくと
0 mode 3 -> buckets[0]:2 -> Entry[2]:hashCode 3,next 1,key 3,value C
3 mode 3 -> buckets[0]:2 -> Entry[2]:hashCode 3,next 1,key 3,value C
0 mode 3の方のEntry.hashCodeは3ではないので、ここがおかしい訳ですが、nextという値をみると1となっています。ここも想像を膨らませてみると、nextとは、次に調べる要素のインデックスと解釈してみると
Entry[1]:hashCode 0,next -1,key 0,value B
というのが見つかり
0 mode 3
-> buckets[0]:2
-> Entry[2]:hashCode 3,next 1,key 3,value C
-> Entry[1]:hashCode 0,next -1,key 0,value B
という連想ができていることがわかります。keyは異なって、hachCodeは同じになる例も試してみたいのですが、見つけるのが大変そうなので今回はやめておきます。
更にハッシュコードを要素数で割ったあまりの値がぶつかるようなキーを選んでみます。
static void Main()
{
var dictionary = new Dictionary<int, string>();
dictionary.Add(6, "A");
dictionary.Add(0, "B");
dictionary.Add(3, "C");
ShowDictionaryState(dictionary);
}
dictionary.Add(0, "B");
dictionary.Add(3, "C");
ShowDictionaryState(dictionary);
}
実行すると
Add Key 3
buckets[0]:2
buckets[1]:-1
buckets[2]:-1
Entry[0]:hashCode 6,next -1,key 6,value A
Entry[1]:hashCode 0,next 0,key 0,value B
Entry[2]:hashCode 3,next 1,key 3,value C
bucketsが対応するインデックスが全てぶつかっているので、0以外は-1になっています。Keyからの連想を手動で調べると
6 mode 3
-> buckets[0]:2
-> Entry[2]:hashCode 3,next 1,key 3,value C
-> Entry[1]:hashCode 0,next 0,key 0,value B
-> Entry[0]:hashCode 6,next -1,key 6,value A
0 mode 3
-> buckets[0]:2
-> Entry[2]:hashCode 3,next 1,key 3,value C
-> Entry[1]:hashCode 0,next 0,key 0,value B
3 mode 3
-> buckets[0]:2
-> Entry[2]:hashCode 3,next 1,key 3,value C
Keyから連想するValueまでが、Dictinary内部にある状態から、たどりつけることがわかります。アルゴリズムの部分は完全に想像なので、不正確なのは否定できませんが、大体当ているのではないかと思います。
今度は、配列の要素数の変化をみてみることにします。
static void Main()
{
var dictionary = new Dictionary<int, int>();
int bucketsCount = 0;
foreach (var i in Enumerable.Range(0, 1000))
{
dictionary.Add(i, i);
int tmpBucketsCount = GetFieldValue<int[]>(dictionary, "buckets").Length;
if (bucketsCount < tmpBucketsCount)
{
bucketsCount = tmpBucketsCount;
Console.WriteLine("Add {0}, Length {1}", i, bucketsCount);
}
}
}
実行してみると
Add 0, Length 3
Add 3, Length 7
Add 7, Length 17
Add 17, Length 37
Add 37, Length 89
Add 89, Length 197
Add 197, Length 431
Add 431, Length 919
Add 919, Length 1931
List<T>のようににキャパシティーを超えたら、2倍になっているのかと思いきや、そうではないようです。見るかぎり今回の範囲では、素数になっているように見えます。ただし、連続した素数ではなく、素数を2倍して、最初に見つかる素数になっているように見えます。なぜ、そのような数字が採用されいるのかは、皆目検討がつきません。Dcitionaryにとってのキャパシティの増加傾向が、この数列が一番効果的なのかもしれませんし、キャパティが素数である必要があるのかもしれませんし、いろいろ想像が膨らみます。
static void Main()
{
var dictionary = new Dictionary<int, int>();
int entriesCount = 0;
foreach (var i in Enumerable.Range(0, 1000))
{
dictionary.Add(i, i);
int tmpEntriesCount = GetFieldValue<Array>(dictionary, "entries").Length;
if (entriesCount < tmpEntriesCount)
{
entriesCount = tmpEntriesCount;
Console.WriteLine("Add {0}, Length {1}", i, entriesCount);
}
}
}
実行すると
Add 0, Length 3
Add 3, Length 7
Add 7, Length 17
Add 17, Length 37
Add 37, Length 89
Add 89, Length 197
Add 197, Length 431
Add 431, Length 919
Add 919, Length 1931
bucketsとentriesの要素数は同じになるようです。
ということで、今回の調査をまとめてみます。
Dictionary<T, TKey>は、内部的にはハッシュコードを更に圧縮した値をインデックスとする配列(buckets)を保持する。bucketsの各要素の値は、エントリーのインデックスに対応している。エントリーは、ハッシュキー、重複かつ見つからなかった場合の次のエントリーのインデックス、Key、Valueを保持している。
と、予測してみた!
https://github.com/mono/mono/blob/master/mcs/class/corlib/System.Collections.Generic/Dictionary.cs