[Effective C#] 項目10 GetHashCode() の罠に注意すること

本日の Effective C# は「項目10 GetHashCode() の罠に注意すること」です。

これですねぇ、私は大いなる間違いを犯しています。ここで懺悔しますから、許してください。

Object.GetHashCode メソッドはハッシュテーブルなどでの検索に使われます。線形サーチに比べると圧倒的に高速なのです。

もし独自に作成する型がコンテナのキーとして使用されることがないのであれば、この項目の話題は特に気にしなくてもかまいません。

うーん、一応、HashSet) クラスとかもあるので、キーのみってわけじゃないと思いますが、無理して実装する必要はないってことですね。

  1. 2 つのオブジェクトが等しい (== 演算子の定義によって等しい) 場合、それらのオブジェクトからは同じハッシュ値が生成されなければならない。同じハッシュ値が生成されない場合、コンテナからオブジェクトを探しだすためのキーとしてハッシュコードを使用することができない。
  2. 任意のオブジェクト A に対して、A.GetHashCode() は各インスタンス毎に異なる値でなければならない。A のどんなメソッドが呼ばれたとしても、A.GetHashCode() は常に同じ値を返さなければならない。これによって、オブジェクトが格納されている正しいバケツを常に見つけだすことができる。
  3. ハッシュ関数は任意に入力された複数の整数値に対し、ランダム分布となる返り値を返す必要がある。この性質により、ハッシュベースのコンテナへ効率的にオブジェクトを格納できる。

私はこのうち、2 を無視してたかもしれない。まあ、キーとして使うために、構造体を不変型として書いてた気がするので、結果オーライなんだけど、知らなかったので、やばいコードを書くところだったかもしれない。

ちなみに、このうち 1 の制約は面白い。等価なオブジェクトは同じハッシュコードを返す必要があるのですが、等価でないオブジェクトは違うハッシュコードを返す必要はないわけです。まずはハッシュコードで比較し、Equals メソッドを呼び出して確実に等価なことを導き出しています。ですので、

public override int GetHashCode()
{
    return 1;
}

このコードは動きます。ただし、線形サーチになるので、むっちゃ遅いですけど。

話を戻して。キーとして使うようなものは、不変型の構造体を使用した方が良さそうな感じです。不変型ならば、2 の問題はないですし。(構造体の場合は、コピーになるので、キーの値が書き換わることがないっぽい)

参照型を用いる場合は少々厄介です。この辺は Equals() メソッドも関連してきます。(Equals() メソッドとの統一性が必要)

ハッシュコードの実装は、メンバの GetHashCode() を利用するのがよいようです。その方が分布がまんべんなくなるからです。また、複数のメンバからハッシュコードを生成する場合は、xor を使うのがよいと書かれています。

注意しなければいけないことは。

ハッシュ値の生成に使用されるすべてのメンバは不変にするべきです。

2 のルールを守ることですね。3 が守れなくても、パフォーマンス上の問題しかないですけど、2 はやばいです。

2010/03/29 追記:

ReSharper の Code Generation で Equals()/GetHashCode() メソッドの実装を行う」でも書きましたが、ReSharperCode Generation を使うと、簡単に実装できます。

コメントを追加

Filtered HTML

  • ウェブページアドレスとメールアドレスは、自動的にハイパーリンクに変換されます。
  • 使用できるHTMLタグ: <a> <em> <strong> <cite> <code> <ul> <ol> <li> <dl> <dt> <dd> <blockquote> <img>
  • 次のタグを使用してソースコード構文をハイライトすることができます。: <code>, <blockcode>, <c>, <cpp>, <drupal5>, <drupal6>, <java>, <javascript>, <php>, <python>, <ruby> The supported tag styles are: <foo>, [foo].
  • 行と段落は自動的に折り返されます。

Plain text

  • HTMLタグは利用できません。
  • ウェブページアドレスとメールアドレスは、自動的にハイパーリンクに変換されます。
  • 行と段落は自動的に折り返されます。
CAPTCHA
This question is for testing whether you are a human visitor and to prevent automated spam submissions.
イメージ CAPTCHA
Enter the characters shown in the image.
エラー | まさくらのブログ

エラー

サイトに予期せぬエラーが起こりました。しばらくたってから再度お試しください。