C#のGetHashCodeメソッドとDictionaryでのハッシュコード衝突

はじめに

C#でプログラミングをしていると、Dictionary<TKey, TValue>を使う場面は非常に多いです。キーに基づく高速なデータアクセスができるこのコレクション型は、内部的に「ハッシュテーブル」という仕組みを使って実装されています。

このとき重要になるのが、TKeyとして使われる型がGetHashCodeメソッドを適切に実装しているかどうかです。本記事では、GetHashCodeの効果的な実装方法と、ハッシュコードが衝突した場合にDictionaryがどう対処するのかについて、具体例を交えながら詳しく解説します。

GetHashCodeとは？

GetHashCodeは、.NETのobjectクラスに定義されているメソッドで、オブジェクトの「ハッシュ値（整数値）」を返します。これは、オブジェクトの等価性を判断するための手がかりとして、DictionaryやHashSetなどのコレクションで使われます。

C#では、クラスにこのメソッドをオーバーライドして、開発者が任意のロジックでハッシュコードを生成できます。

GetHashCodeの実装例（Personクラス）

以下に、典型的なGetHashCodeの実装例を示します。

public class Person
{
    public string Name { get; set; }
    public int Age { get; set; }

    public override int GetHashCode()
    {
        unchecked
        {
            int hash = 17;
            hash = hash * 23 + (Name != null ? Name.GetHashCode() : 0);
            hash = hash * 23 + Age.GetHashCode();
            return hash;
        }
    }

    public override bool Equals(object obj)
    {
        if (obj is Person other)
            return Name == other.Name && Age == other.Age;
        return false;
    }
}

解説：

  • uncheckedブロックにより、オーバーフローを無視します（安全かつ高速）。
  • 17と23は任意の素数です。一般的に、異なる値をうまく混ぜるために素数が使われます。
  • Nameがnullのときは0を使い、NullReferenceExceptionを避けています。

Dictionaryにおけるハッシュコードの利用

Dictionaryは、キーをGetHashCode()で変換し、その値に基づいて「バケット（内部的な配列のインデックス）」を決定します。しかし、異なるキーでも同じハッシュコードを返すことがあります。これをハッシュ衝突と呼びます。

.NETのDictionaryは、この衝突を次のように処理しています：

  1. ハッシュコードが一致するキーは同じバケットに格納。
  2. 各バケットは「連結リスト」や「探索木」などのデータ構造で保持。
  3. Equals()メソッドを使って本当に等しいキーかどうかを確認。

つまり、ハッシュコードが衝突しても、Equals()で識別できる限り、異なるキーとして扱えます。

実際の衝突シナリオ

以下のコードでは、意図的にGetHashCodeを衝突させています。

public class Person
{
    public string Name { get; set; }
    public int Age { get; set; }

    public override int GetHashCode()
    {
        // 故意に衝突を起こす
        return Age % 2;
    }

    public override bool Equals(object obj)
    {
        if (obj is Person other)
            return Name == other.Name && Age == other.Age;
        return false;
    }
}

上記クラスを使って以下のようにDictionaryを操作してみましょう

var dic = new Dictionary<Person, string>();

var person1 = new Person() { Name = "Taro", Age = 25 };   // Hash: 1
var person2 = new Person() { Name = "Jiro", Age = 26 };   // Hash: 0
var person3 = new Person() { Name = "Saburo", Age = 27 }; // Hash: 1

dic.Add(person1, "役職1");
dic.Add(person2, "役職2");
dic.Add(person3, "役職3");

Console.WriteLine(dic[person1]);  // 出力: 役職1
Console.WriteLine(dic[person2]);  // 出力: 役職2
Console.WriteLine(dic[person3]);  // 出力: 役職3

重要なポイント：

  • person1とperson3は同じハッシュコード（1）を持ちます。
  • しかし、Equalsが異なるため、Dictionaryは2つの異なるキーとして認識。
  • 値の取得は問題なく動作します。

なぜGetHashCodeが重要なのか？

  • パフォーマンスへの影響：良質なハッシュ関数は、衝突を最小限に抑えます。衝突が多いと、Dictionaryの内部的な探索時間が増加し、O(1)のはずがO(n)に近づくこともあります。
  • 信頼性：Equalsが正しく機能していても、ハッシュコードが偏っていると、意図しない上書きやデータ喪失の可能性があります。

ハッシュ関数を設計するコツ

  • 複数のプロパティを使う。
  • nullの考慮を忘れない。
  • 可能であれば、HashCode.Combine()（.NET Core 2.1以降）を使うとより安全。

例：

public override int GetHashCode()
{
    return HashCode.Combine(Name, Age);
}

のAPIは、内部的に最適化された方法で複数のフィールドを組み合わせ、より分散性の高いハッシュコードを生成します。

Equalsの実装も忘れずに

DictionaryやHashSetなどで正しく動作させるためには、EqualsとGetHashCodeはペアで実装する必要があります。片方だけをオーバーライドすると、想定しない動作になることがあります。

まとめ

  • Dictionaryは高速アクセスを提供する強力なコレクションだが、GetHashCodeの実装が鍵を握っている。
  • ハッシュコードが衝突しても、Equalsが適切に定義されていれば問題なく動作する。
  • とはいえ、衝突が多くなると内部の処理が重くなり、パフォーマンスが低下する恐れがある。
  • ハッシュ関数はできるだけランダム性が高く、プロパティを組み合わせて作るように心がけよう。
  • .NETのHashCode.Combineを活用するのもおすすめ。

C#で堅牢なクラスを作成し、ハッシュベースのコレクションを最大限活用するためには、GetHashCodeとEqualsの正しい実装が不可欠です。この基本をマスターすることで、より信頼性の高いアプリケーションを設計できるようになるでしょう。

タグ

関連投稿