【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。

  • 2013.01.15 Tuesday
  • 20:10
JUGEMテーマ:コンピュータ

Dictionary<T, TKey>の実装が、前々から気になっていたので、調べてみました。今回は、リフレクションを利用して、公開されていないフィールドの状態を観察することで、Dictionaryの内部で扱われているデータ構造やアルゴリズムを想像してみました。非公開な部分なので、バージョンによって差異がある可能性もあり、また、そもそも想像なので、不正確なことこの上ないことは、あらかじめご了承ください。
Dictionary<T, TKey>を観察するとpublicでないフィールドに
private int[] buckets;
private Entry<TKey, TValue>[] entries;
というのがあります。他にも沢山ありますが、アルゴリズムに関連しそうなネーミングなので、この二つを観察することにしてます。ちなみにEntry<T, TValue>構造体は以下の定義となっているようです。
private struct Entry
{
    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>();
            dictionary.Add(2, "A");
            Console.WriteLine("Add Key 2");
            ShowDictionaryState(dictionary);
            dictionary.Add(0, "B");
            Console.WriteLine("Add Key 0");
            ShowDictionaryState(dictionary);
            dictionary.Add(1, "C");
            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]);
            }
            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);
            }
        }
        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);
        }
    }
}

実行すると

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);
            dictionary.Add(0, "B");
            Console.WriteLine("Add Key 0");
            ShowDictionaryState(dictionary);
            dictionary.Add(3, "C");
            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);
        }

実行すると

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を保持している。

と、予測してみた!

コメント
monoのソースを見るって手が。まぁMicrosoftのDictionaryとは別物と考えたほうがいいですけれど。
https://github.com/mono/mono/blob/master/mcs/class/corlib/System.Collections.Generic/Dictionary.cs
  • karuakun
  • 2013/01/16 9:12 AM
ソースコードを紹介していただきありがとうございます。
  • art55
  • 2013/01/16 10:06 PM
コメントする








    
この記事のトラックバックURL
トラックバック

calendar

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  
<< August 2017 >>

あわせて読みたい

あわせて読みたいブログパーツ

selected entries

categories

archives

recent comment

  • 【キーボード】6年前のRealForceを復活させることはできる!?その3
    art55 (05/22)
  • 【キーボード】6年前のRealForceを復活させることはできる!?その3
    分解大好き (05/18)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    art55 (02/04)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    Gen (02/04)
  • 【キーボード】RealForce が壊れて帰ってきた。
    art55 (04/29)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    art55 (02/23)
  • 【.NET Framework 4.5】 IListがIReadOnlyListを継承してない理由。
    かるあ (02/22)
  • 【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。
    art55 (01/16)
  • 【C#】Dictionaryの実装・データ構造・アルゴリズムを観察する。
    karuakun (01/16)
  • 【NetOffice】【Excel】死なないExcelプロセスをKillする。
    art55 (12/05)

recent trackback

recommend

recommend

recommend

C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION)
C#プログラマのための.NETアプリケーション最適化技法 (Programmer's SELECTION) (JUGEMレビュー »)
Sasha Goldshtein,Dima Zurbalev,Ido Flatow,サシャ・ゴルドシュタイン,ディマ・ズルバレフ,イド・フラトー

recommend

ろんりと集合
ろんりと集合 (JUGEMレビュー »)
中内 伸光
とてもわかりやすいです。

recommend

recommend

シャノン・ノイマン・ディジタル世界
シャノン・ノイマン・ディジタル世界 (JUGEMレビュー »)
市川 忠男
4章がリレーショナルデータベースな内容になってます。ページ数があまりありませんが、ポイントがものすごく的確にまとまっていて、感動します。

recommend

recommend

東プレ Realforce91UBK-S 静音キーボード 静電容量無接点方式 変荷重 ブラック NG01BS
東プレ Realforce91UBK-S 静音キーボード 静電容量無接点方式 変荷重 ブラック NG01BS (JUGEMレビュー »)

テンキーレス、静音のRealForce91UBK-S。スコスコ感がたまらなく気持ちいいです。家と会社で2台持ってます。

recommend

recommend

プログラミング.NET Framework 第4版 (プログラミングシリーズ)
プログラミング.NET Framework 第4版 (プログラミングシリーズ) (JUGEMレビュー »)
Jeffrey Richter
発売予定美 2013年10月10日。.NET Frameworkとお付き合いする人のバイブルですね。

recommend

recommend

キャット・シッターの君に。
キャット・シッターの君に。 (JUGEMレビュー »)
喜多嶋 隆
私のイラストレータデビュー本です。

recommend

Essential .NET ― 共通言語ランタイムの本質
Essential .NET ― 共通言語ランタイムの本質 (JUGEMレビュー »)
ドン・ボックス,クリス・セルズ,Don Box,Chris Sells,吉松 史彰

links

profile

search this site.

others

mobile

qrcode

powered

無料ブログ作成サービス JUGEM