Entry: main  << >>
.NETのDictionaryクラスに独自型をキーとして用いる場合気をつけること
0
    仕事でSystem.Collections.Generic.Dictionary型のキーに独自型を使った時にひどい目にあったのでメモ。


    MSDNライブラリ(System.Collections.Generic.Dictionary)には「IEquatableを実装してカスタマイズできます!!」と書いてあるけど、実際にはGetHashCodeをオーバーライドしておかなければならない。
    ---


    1.参照型をキーにしようとしたらインスタンス比較になった
    キーとなるClassを定義し、IEquatableを実装してこれでいけるだろうと思ったら、インスタンスが違ったときに同じ扱いしてくれない。

    Dictionaryクラスの説明では、
    ・IEquatableの実装がある場合それで比較します
    ・Equalsのオーバーライドがある場合それで比較します

    ということだったのだが、IEquatableでダメだったし、Equalsをオーバーライドしてもダメだった。

    DictionaryのコンストラクタオーバーロードでIEqualityComparerを指定しても、インスタンスが違っていたら同じ扱いにならない。

    クラスに静的なインスタンス取得メソッドを実装しようかと思ったけど、面倒になってここで参照型キーは諦めた。


    2.値型をキーにしたらうまく行った(ように見えた)
    Classの代わりにStructureでキー型を定義したらうまく行った。
    このとき、テスト用のメソッド内で幾つかのインスタンスを生成して比較し、IEquatable実装のEqualsメソッドを通っているかどうか、及びその結果を標準出力に表示して確認していた。

    3.実はうまく行ってなかった!!
    このディクショナリを含めたクラスをDLLにして、くっつけてテストしたら、同じ値を格納しているはずのキーが、同じ扱いにならない。
    ちょっと調べたところで、この記事を発見。ありがとうございます。
    IEquatableを実装するときは、GetHashCodeもオーバーライドしなければならないそう。

    GetHashCodeを、Structure各メンバのGetHashCodeをXorする形でオーバーライドして事なきを得ました。

    ---
    4.GetHashCodeをオーバーライドしなければならなかったのはなぜか?
    うまくいったのはいいけどなぜかわからないと気になってしょうがないので、msdnのObject.GetHashCodeメソッドに関するトピックを調べたら、
    「HashTableのキーとなるオブジェクトは、GetHashCodeとEqualsを正しくオーバーライドしないとキーとして働かない」とあった。
    Object.Equalsメソッドの解説も読んで、ハッシュテーブル関係のクラスがキーを比較する時の動作はこんなかんじなんだろうと思った。

    ・2つのキーをGetHashCodeの戻り値で比較し、違ったら違うキーとする。
    ・GetHashCodeが同じ時にだけ更にEqualsで比較する。

    このときに、DictionaryキーにIEquatableを実装していると、IEquatable.Equalsを実装したメソッドで比較してくれるといったところだろう。

    Dictionaryクラスの説明にはGetHashCodeに関する記述がなかったが、「ハッシュアルゴリズムの品質がパフォーマンスに影響します」といった一文があったので、GetHashCodeをオーバーライドすることに全く触れていないわけではないという事かもしれない。

    今考えるとGetHashCodeの戻り値はキャッシュしたほうがちょっとだけ早くなりそうだな。
    テスト工程だし体感的にストレスを感じないので、今度から工夫することにしよう。


    -追記-

    あとで知ったんだけど、ハッシュテーブルの実装というもの自体がこういう構造のものらしい。無知だった!
    | noppikinatta | 23:16 | comments(0) | trackbacks(0) | - | - |
    Comment








    Trackback