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

  • 2013.01.16 Wednesday
  • 22:03
JUGEMテーマ:コンピュータ

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

上記の投稿で、System.Collections.Generic.Dictionary<T, TKey>の内部の状態を観察すしてみました。あるタイミングの内部状態のスナップショットのいくつかを観察し、変化を見ていくことで、法則性をみいだし、アルゴリズムを考察したかったというのが目的でした。

今回は逆に、アルゴリズムからせめて行きたいと思います。どういうアルゴリズムを組めば、ディクショナリとして成立するかという事を考えたいと思います。

ディクショナリの要件としていくつかあると思いますが、

1.キーと値を登録できる。
2.存在するキーを渡すと値を得ることができる。
3.キーによる検索は、高速であること。
4.登録されたキーの量によって検索速度が落ちないこと。

といった感じでしょうか。これを満たすロジックを考察していきたいと思います。まず、System.Object.GetHashCodeメソッドに着目してみます。GetHashCodeメソッドで得られるハッシュ コードは、等価テスト中にオブジェクトを識別するために使用される数値です。GetHashCodeメソッドの戻り値はint型の為、ハッシュ コードはint型で表せる範囲の値を返します。KeyのGetHashCodeメソッドを利用することでハッシュ コードを取得し、その値を配列のインデックスと対応させ、その要素の値にValueを設定することによってKeyとValueが配列で管理するというアルゴリズムが成立します。

絵で描くと

残念ながら、このアルゴリズムは、いくつかの問題があります。ひとつは、異なるキーでハッシュコードが重複するという問題です。文字列など無限の組み合わせが存在する場合は、GetHashCodeメソッドの戻り値のint型で表せる範囲を超えることは自明です。



では、問題を解決してみることにします。





用意した配列に直接値を入れず、Keyと値を保持したオブジェクトの参照を配列に格納してみることにします。Keyと値を保持したオブジェクトに更に参照をつなげて線形リストにします。これでキーがぶつかった場合は、リストが連結されていき、検索する際は、ハッシュコードとまず一致する事で線形リストのヘッダーにたどり着き、Keyの等価性を見ることで、重複するハッシュコードでも検索が可能になります。

しかし、まだ、問題があります。図中では「ハッシュテーブル」と名付けている配列の要素数が問題となります。仮にGetHashCodeメソッドが返す範囲をカバーする配列を作ろうとしても作れません。まずはsz配列を利用したいため、負の値は問題となります。System.Int32.MinValueが0に対応するように計算させると、今度は最大値はintの範囲を超える値にもなります。なので負の数字は扱えません。さらに、System.Int32.MaxValueの要素数を持つ配列のインスタンスは生成できません。

var arrary = new int[System.Int32.MaxValue];

上記のコードはコンパイルは通りますが、実行すると例外が発生します。メモリが確保できないからです。リソース上の問題なので回避できません。

そこで、この問題を解決するために、GetHashCodeメソッドをから得たハッシュコードを更に圧縮する必要があります。そして、圧縮した範囲をカバーできる配列を用意するというアルゴリズムにします。前回の考察で「要素数は素数で、要素数を超える場合は、リサイズされる。要素数(素数)を2倍した値から順方向に存在する素数のメンバーのうち、最初の見つかる素数を次の要素数にする」という動きをいたと思いますが、とりあえず、要素数が7の場合で考えてみたいと思います。



上記の図は、ハッシュテーブルの要素が7の場合です。本来ならキーは4つ以上登録ずみですが、ごちゃごちゃするので省略しています。まず、AddしたタイミングでKeyからGetHashCodeメソッドを呼び出し、ハッシュコードを得ます。その値を要素数で割り余りを得ることでハッシュコードを0から6の範囲で圧縮することができます。その値がハッシュテーブルのindexに対応していることがわかります。参照をたぐる事で、検索時にキーから値を連想することが可能です。今回は、Keyで比較するよりも圧縮前のハッシュコードで比較した方が高速であるため、ハッシュテーブルの参照先のオブジェクトにハッシュコードをキャッシュさせました。

これで、ディクショナリの概念的なアルゴリズムは説明できていると思います。ただ、System.Collections.Generic.Dictionary<T, TKey>の内部状態の観察から、上記の説明で「参照」と書いた部分は、実際には「参照」ではなく、配列のインデックスを利用しているという事が分かっているため、そこを少しだけ書き換えてみることにします。



絵は大幅に変わりましたが、線形リストの実装方法を配列に切り替えただけです。


キー1から値を検索する際は、キー1のハッシュコードを圧縮し、ハッシュテーブルのインデックスに対応させ、その値からエントリーの配列のインデックスを見つけ、エントリー内の配列からキー1と一致する要素を見つけ、最終的に「メロン」という値を見つけ出すことができる。という事がわかります。

と、まあこんな感じでアルゴリズムを考える上での「トンチ絵」が書けました。・・・いつの間にか絵を描くことが目的になってしまいましたが、私の頭はすっかりすっきりになったので、今回はこれで終了。

コメント
コメントする








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

calendar

S M T W T F S
  12345
6789101112
13141516171819
20212223242526
2728293031  
<< January 2019 >>

あわせて読みたい

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

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