⛳

【C#データ構造】ハッシュとは？チェイン法と開番地法について解説

2024/07/20に公開

 はじめにハッシュテーブルは、データを迅速に検索、挿入、削除するために使用されるデータ構造です。キーと値のペアを効率的に管理し、高速なアクセスを提供します。本記事では、ハッシュテーブルの基本概念と、チェイン法および開番地法の具体的な実装例をC#コードと共に解説します。また、一次ハッシュや二次ハッシュについても触れます。

 ハッシュテーブルとは？ハッシュテーブルは、キーをハッシュ関数によってハッシュ値に変換し、そのハッシュ値をインデックスとして配列にデータを格納します。これにより、データの操作が平均してO(1)の時間で行えます。

 ハッシュ関数ハッシュ関数は、キーを固定サイズのハッシュ値に変換します。理想的なハッシュ関数は、異なるキーに異なるハッシュ値を割り当て、衝突を最小限に抑えるものです。ハッシュ関数としては文字コードをそのまま数値に変換し、バケット数Bで割った余りとするという例があります。

 衝突異なるキーが同じハッシュ値を持つ場合、これを衝突と呼びます。衝突を処理するために、チェイン法と開番地法が使用されます。

 チェイン法チェイン法では、各バケットをリンクリストとして扱い、衝突が発生した場合はそのリストに新しい要素を追加します。

 開番地法開番地法では、衝突が発生した場合、次の空のバケットを探してデータを格納します。探索には一次探索、二次探索、二重ハッシュ法があります。

 一次探索（線形探索）衝突が発生した場合、次のバケットを順にチェックして空のバケットを見つけます。問題点は空ではないバケットが塊になってしまうことである。

 二次探索（二次ハッシュ）衝突が発生した場合、特定の間隔を空けたバケットをチェックして空のバケットを見つけます。

 二重ハッシュ法二つ目のハッシュ関数を使用して、衝突が発生した場合の次のバケットの位置を決定します。

 IsDeletedの必要性開番地法では、要素の削除時にその位置をマークする必要があります。単純に要素を削除すると、検索時に誤ってバケットが空であると判断されるため、削除されたことを示すフラグ（IsDeleted）が必要です。

 C#による実装
 チェイン法の実装using System;
using System.Collections.Generic;

/ < summary >
/ チェイン法を利用したハッシュテーブルの実装です。
/ ハッシュ関数はKeyの長さを用いる．
/ </ summary >
/ < typeparam name = "T" ></ typeparam >
public class HashTableChain<T>
{
  private const int BUCKET_SIZE = 5;
  private readonly List<T>[] buckets; // バケットごとのリスト

  public HashTableChain()
  {
    リストを初期化する．
    buckets = new List<T>[BUCKET_SIZE];
    for (int _i = 0; _i < buckets.Length; _i++)
    {
      buckets[_i] = new List<T>();
    }
  }

  / <summary>
  / ハッシュ関数を用いてバケット番号（インデックス）を返す．
  / ハッシュ関数はKeyの長さを用いる．
  / </summary>
  / <param name = "_data" ></ param >
  / < returns ></ returns >
  private int GetIndex(T _data)
  {
    return _data.ToString().Length % BUCKET_SIZE;
  }

  / <summary>
  / ハッシュに要素を追加する．
  / </summary>
  / <param name = "_data" ></ param >
  public void Insert(T _data)
  {
    int _index = GetIndex(_data);
    buckets[_index].Add(_data);
  }

  / <summary>
  / ハッシュから要素を削除する
  / </summary>
  / <param name = "_data" ></ param >
  public void Delete(T _data)
  {
    int _index = GetIndex(_data);
    List<T> _bucketList = buckets[_index];
    for (int _i = 0; _i < _bucketList.Count; _i++)
    {
      if (_bucketList[_i].Equals(_data))
      {
        _bucketList.RemoveAt(_i);
        break; // 要素を見つけて削除したらループを終了
      }
    }
  }
}

public class Example
{
  public static void Main()
  {
    HashTableChain<string> _hashTable = new HashTableChain<string>();
    _hashTable.Insert("dog");
    _hashTable.Insert("bird");
    _hashTable.Insert("cat");
    _hashTable.Delete("dog");
    _hashTable.Insert("rat");
  }
}

 開番地法の実装using System;

/// <summary>
/// 開番地法を利用したハッシュテーブルの実装です。
/// ハッシュ関数はKeyの長さを用いる．
/// 再ハッシュは一次ハッシュを用いる．
/// </summary>
/// <typeparam name="T"></typeparam>
public class HashTableOpenAddressing<T>
{
  private const int BUCKET_SIZE = 5;
  private readonly (T Data, bool IsDeleted)[] buckets; // バケットの配列

  public HashTableOpenAddressing()
  {
    // バケットを初期化する
    buckets = new (T Data, bool IsDeleted)[BUCKET_SIZE];
  }

  /// <summary>
  /// ハッシュ関数を用いてバケット番号（インデックス）を返す
  /// </summary>
  /// <param name="_data"></param>
  /// <param name="_count"></param>
  /// <returns></returns>
  private int GetIndex(T _data, int _count)
  {
    return (_data.ToString().Length + _count) % BUCKET_SIZE;
  }

  /// <summary>
  /// ハッシュに要素が存在するか確認する
  /// 再ハッシュは一次ハッシュを用いる．
  /// </summary>
  /// <param name="_data"></param>
  /// <returns></returns>
  public bool Member(T _data)
  {
    int _count = 0;//再ハッシュ回数カウンタ

    while (_count < BUCKET_SIZE)
    {
      //ハッシュ関数を適用する．
      int _index = GetIndex(_data, _count);

      //要素が重複している．
      if (buckets[_index].Data != null && buckets[_index].Data.Equals(_data))
      {
        return true;
      }

      //他のものが入っているか、deletedのときは再ハッシュ（一次ハッシュ）
      _count++;
    }

    //最後まで行った=要素の重複は存在しなかった．
    return false;
  }

  /// <summary>
  /// ハッシュに要素を追加する
  /// </summary>
  /// <param name="_data"></param>
  public void Insert(T _data)
  {
    //重複チェック(deletedの先も見る)
    if (Member(_data)) return;

    int _count = 0;//再ハッシュ回数カウンタ

    while (_count < BUCKET_SIZE)
    {
      //ハッシュ関数を適用する．
      int _index = GetIndex(_data, _count);

      //空番地を発見したならば要素を挿入する
      if (buckets[_index].Data == null || buckets[_index].IsDeleted)
      {
        buckets[_index] = (_data, false);
        return;
      }

      //他のものが入っているか、deletedのときは再ハッシュ（一次ハッシュ）
      _count++;
    }

    throw new InvalidOperationException("Hash table is full");
  }

  /// <summary>
  /// ハッシュから要素を削除する
  /// </summary>
  /// <param name="_data"></param>
  public void Delete(T _data)
  {
    int _count = 0;//再ハッシュ回数カウンタ

    while (_count < BUCKET_SIZE)
    {
      //ハッシュ関数を適用する．
      int _index = GetIndex(_data, _count);

      //削除したい要素が見つかったならば削除する．
      if (buckets[_index].Data != null && buckets[_index].Data.Equals(_data))
      {
        buckets[_index] = (default, true); //削除マーカーを設定
        return;
      }

      //他のものが入っているか、deletedのときは再ハッシュ（一次ハッシュ）
      _count++;
    }
  }
}

public class Example
{
  public static void Main()
  {
    HashTableOpenAddressing<string> _hashTable = new HashTableOpenAddressing<string>();
    _hashTable.Insert("dog");
    _hashTable.Insert("bird");
    _hashTable.Insert("cat");
    _hashTable.Delete("dog");
    _hashTable.Insert("rat");
    _hashTable.Delete("cat");
  }
}


 まとめハッシュテーブルは効率的なデータ構造で、検索、挿入、削除が高速に行える点が魅力です。チェイン法と開番地法は、衝突を処理するための代表的な手法であり、それぞれの特徴を理解し、用途に応じて使い分けることが重要です。

 参考書籍データ構造とアルゴリズム[第2版] (新・情報/通信システム工学)

https://amzn.to/3YtOnpz

はじめに

ハッシュテーブルとは？

ハッシュ関数

衝突

チェイン法

開番地法

一次探索（線形探索）

二次探索（二次ハッシュ）

二重ハッシュ法

IsDeletedの必要性

C#による実装

チェイン法の実装

開番地法の実装

まとめ

参考書籍

Discussion