Zenn
📕

[C#] Dictionary(HashTable)を自作して理解する

2023/01/14に公開・約11,200字
C#
初心者
#
設計
入門
tech

まえがき

Dictionaryを使っていて、ハッシュの重複とか、ハッシュをindexに変換するのはどうしてるのか気になりました。

そして今回の意図は、「ハッシュテーブルの仕組みを理解する」です。

C# を使って、なるだけ簡単に作ります。
意外と簡単で、各関数はだいたい十数行程度です。
一応、C++にも対応するものがあるので、同じように実装可能です。

実装

必要なクラスとフィールドは以下の通りです。

using System.Collections.Generic;

class HashTable<TKey, TValue> {
   readonly private LinkedList<KeyValuePair<TKey, TValue>>[] _bucket;
   readonly private IEqualityComparer<TKey> _equalityComparer;
   
   public HashTable(IEqualityComparer<TKey>? equalityComparer = null)
   {
      _bucket = new LinkedList<KeyValuePair<TKey, TValue>>[16];
      _equalityComparer = equalityComparer ?? EqualityComparer<TKey>.Default;
   }
}

  • _bucketは、要素を格納するリンクリストの配列です。
    16は配列の要素数です。今回は試しなので、少なめにしています。
    各自適当な数にしてください。長いほど効率が良くなります。

  • _equalityComparerは、キーの比較とハッシュ化を行います。

今回は、変更することもないのでreadonlyにします。

Countを実装する場合は、_countにAdd,Remove,Clearなどで要素数をカウントする必要がありますが、今回はしません。「IDictionaryバージョン」の項ではCountも実装しています。

キー ➡ ハッシュ ➡ インデックスのしくみ

  1. 「キー ➡ ハッシュ」は、C#なのでGetHashCodeを使用します。
    今回はIEqualityComparerがあるので、IEqualityComparer.GetHashCode(T)を使用します。
  2. インデックスなので、マイナスのハッシュを対処します。今回はAbsを使いました。
  3. _bucket.Lengthで割った余りをインデックスとします。

これで、[0 .. _bucket.Length - 1]のインデックスに変換することが出来ます。

private int KeyToIdx(TKey key) {
   var hash = _equalityComparer.GetHashCode(key!); // 1
   return System.Math.Abs(hash) % _bucket.Length; // 2,3
}

KeyToIdxは、今後使用していきます。

Add

ひとまず、Addを作ってみましょう。

連鎖法を使って、要素追加してみます。

連鎖法を使うと、簡単にindexの被りの対処が出来ます。

  1. keyをハッシュ化し、格納先の_bucketの長さで割ったあまりがindex(マイナスはAbsで対処)
  2. idx番目にkeyが既に含まれていたら例外を投げます。
  3. 問題なければAddLastで要素を追加します。
public void Add(TKey key, TValue value)
{
   var idx = KeyToIdx(key); // 1

   _bucket[idx] ??= new();
   var list = _bucket[idx];

   foreach (var elem in list) // 2
   {
      if (_equalityComparer.Equals(key, elem.Key))
      {
         throw new ArgumentException(
	    $"キーが既に存在します。 (key: {key})", paramName: nameof(key));
      }
   }

   list.AddLast(new KeyValuePair<TKey, TValue>(key, value)); // 3
}

idxが被っていても、LinkedListに追加されますが、キーは重複できません。

AddのTest
HashTable<int, string> hashTable = new();

hashTable.Add(10, "abc");
hashTable.Add(20, "def");
hashTable.Add(26, "ghi");
hashTable.Add(36, "jkl");

hashTable.Add(10, "mno");// 重複

GetEnumerator

Addしたものを可視化できるように、Enumeratorを実装します。
バケツにKeyValuePairを使用したため、そのまま返すだけでいいです。

public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
{
   foreach (var list in _bucket)
   {
      if (list == null)
         continue;

      foreach (var elem in list)
      {
         yield return elem;
      }
   }
}

HashTable<int, string> hashTable = new();

hashTable.Add(10, "abc");
hashTable.Add(20, "def");
hashTable.Add(26, "ghi");
hashTable.Add(36, "jkl");
hashTable.Add(-100, "mno");

foreach (var (key, val) in hashTable)
{
   Console.WriteLine($"{key}: {val}");
}
出力
20: def
36: jkl
-100: mno
10: abc
26: ghi

ハッシュを_bucket.Lengthで割った余りがindexになっているため、
余りが一番小さい20(20%16=4)が一番上に来ました。

順番は、最初に設定した_bucketの要素数で変化します。
その最大値を_bucketの要素数にすれば完全にオーダーされますが、
今回はAbsを使用したため、結局マイナスはオーダー出来ません。

TryGetValue

GetValueはDictionaryにないので、ひとまずTryGetValueを実装します。

public bool TryGetValue(TKey key, out TValue value) {
   var idx = KeyToIdx(key);

   var list = _bucket[idx];

   if (list != null)
      foreach (var elem in list)
      {
         if (_equalityComparer.Equals(key, elem.Key))
         {
            value = elem.Value;
            return true;
         }
      }

   value = default!;
   return false;
}

HashTable<int, string> hashTable = new();

hashTable.Add(10, "abc");
hashTable.Add(20, "def");

string? val;

if (hashTable.TryGetValue(10, out val))
   Console.WriteLine(val);

if (hashTable.TryGetValue(10000, out val))
   Console.WriteLine(val);
出力
abc

this[]

GetとAddを実装したので、インデックスアクセス[]が実装できます。
ただ、DictionaryはSetがないため、まずはprivateでSetValueを実装します。

private void SetValue(TKey key, TValue value)
{
   var idx = KeyToIdx(key);

   var appendElem = new KeyValuePair<TKey, TValue>(key, value);

   if (_bucket[idx] == null)
   {
      _bucket[idx] = new();
      _bucket[idx].AddLast(appendElem);
      return;
   }

   var list = _bucket[idx];

   if (list != null)
   {
      var node = list.First;

      while (node != null)
      {
         ref var elem = ref node.ValueRef;

         if (_equalityComparer.Equals(key, elem.Key))
         {
            elem = appendElem;
            return;
         }

         node = node.Next;
      }
   }

   list!.AddLast(appendElem);

   return;
}

this[]を実装します。

public TValue this[TKey key] {
      get => TryGetValue(key, out var val)
         ? val
         : throw new KeyNotFoundException($"'{key}' は見つかりませんでした。");
      set => SetValue(key, value);
}

テスト。this[]を使用して、要素追加と上書きをします。

HashTable<int, string> hashTable = new();

hashTable[10] = "abc";
hashTable[20] = "def";
hashTable[1000] = "ghi";

hashTable[10] = "xxx";

foreach (var (key, val) in hashTable)
{
   Console.WriteLine($"{key}: {val}");
}
出力
20: def
1000: ghi
10: xxx

IDictionaryバージョン

以下はIDictionaryの実装もしたバージョンです。

(あまり動作確認はしてません。実用ならDictionaryを使ってください。)

IDictionaryバージョン
using System.Collections;
using System.Collections.Generic;

public class HashTable<TKey, TValue> : IDictionary<TKey, TValue>
{

   readonly private LinkedList<KeyValuePair<TKey, TValue>>[] _bucket;
   readonly private IEqualityComparer<TKey> _equalityComparer;

   private int _count;

   public ICollection<TKey> Keys {
      get
      {
         TKey[] keys = new TKey[_count];
         int idx = 0;
         foreach (var elem in this)
         {
            keys[idx++] = elem.Key;
         }
         return keys;
      }
   }

   public ICollection<TValue> Values {
      get
      {
         TValue[] values = new TValue[_count];
         int idx = 0;
         foreach (var elem in this)
         {
            values[idx++] = elem.Value;
         }
         return values;
      }
   }

   public int Count => _count;

   public bool IsReadOnly => false;

   public HashTable(IEqualityComparer<TKey>? equalityComparer = null) {
      _bucket = new LinkedList<KeyValuePair<TKey, TValue>>[16];
      _equalityComparer = equalityComparer ?? EqualityComparer<TKey>.Default;
   }

   private int KeyToIdx(TKey key) {
      var hash = _equalityComparer.GetHashCode(key!);

      return System.Math.Abs(hash) % _bucket.Length;
   }

   private void SetValue(TKey key, TValue value) {
      var idx = KeyToIdx(key);

      var appendElem = new KeyValuePair<TKey, TValue>(key, value);

      if (_bucket[idx] == null)
      {
         _bucket[idx] = new();
         _bucket[idx].AddLast(appendElem);
         ++_count;
         return;
      }

      var list = _bucket[idx];

      if (list != null)
      {
         var node = list.First;

         while (node != null)
         {
            ref var elem = ref node.ValueRef;

            if (_equalityComparer.Equals(key, elem.Key))
            {
               elem = appendElem;
               return;
            }

            node = node.Next;
         }
      }

      list!.AddLast(appendElem);
      ++_count;

      return;
   }

   public IEnumerator<KeyValuePair<TKey, TValue>> GetEnumerator()
   {
      foreach (var list in _bucket)
      {
         if (list == null)
            continue;

         foreach (var elem in list)
         {
            yield return elem;
         }
      }

   }

   public TValue this[TKey key] {
      get => TryGetValue(key, out var val)
         ? val
         : throw new KeyNotFoundException($"'{key}' は見つかりませんでした。");
      set => SetValue(key, value);
   }

   public bool TryGetValue(TKey key, out TValue value)
   {
      var idx = KeyToIdx(key);

      var list = _bucket[idx];

      if (list != null)
         foreach (var elem in list)
         {
            if (_equalityComparer.Equals(key, elem.Key))
            {
               value = elem.Value;
               return true;
            }
         }

      value = default!;
      return false;

   }

   public void Add(TKey key, TValue value)
   {
      var idx = KeyToIdx(key);

      _bucket[idx] ??= new();
      var list = _bucket[idx];

      foreach (var elem in list)
      {
         if (_equalityComparer.Equals(key, elem.Key))
         {
            throw new ArgumentException($"キーが既に存在します。 (key: {key})", paramName: nameof(key));
         }
      }

      list.AddLast(new KeyValuePair<TKey, TValue>(key, value));
      ++_count;
   }

   public bool ContainsKey(TKey key)
   {
      var idx = KeyToIdx(key);
      var list = _bucket[idx];
      foreach (var elem in list)
      {
         if (_equalityComparer.Equals(key, elem.Key))
         {
            return true;
         }
      }

      return false;
   }

   public bool Remove(TKey key)
   {
      var idx = KeyToIdx(key);
      var list = _bucket[idx];

      var node = list.First;

      while (node != null)
      {
         ref var elem = ref node.ValueRef;

         if (_equalityComparer.Equals(key, elem.Key))
         {
            list.Remove(node);
            --_count;
            return true;
         }

         node = node.Next;
      }

      return false;
   }

   public void Add(KeyValuePair<TKey, TValue> item)
   {
      Add(item.Key, item.Value);
   }

   public void Clear()
   {
      foreach (var list in _bucket)
      {
         list?.Clear();
      }
      _count = 0;
   }

   public bool Contains(KeyValuePair<TKey, TValue> item)
   {
      var idx = KeyToIdx(item.Key);
      var list = _bucket[idx];
      foreach (var elem in list)
      {
         if (_equalityComparer.Equals(item.Key, elem.Key)
            && EqualityComparer<TValue>.Default.Equals(item.Value, elem.Value))
         {
            return true;
         }
      }

      return false;
   }

   public void CopyTo(KeyValuePair<TKey, TValue>[] array, int arrayIndex)
   {
      if (array.Length < arrayIndex + _count)
         throw new ArgumentException("配列の長さが足りません。", paramName: nameof(array));

      int i = 0;
      foreach (var elem in this)
      {
         array[i] = elem;
         ++i;
      }
   }

   public bool Remove(KeyValuePair<TKey, TValue> item)
   {
      var idx = KeyToIdx(item.Key);
      var list = _bucket[idx];

      var node = list.First;

      while (node != null)
      {
         ref var elem = ref node.ValueRef;

         if (_equalityComparer.Equals(item.Key, elem.Key)
            && EqualityComparer<TValue>.Default.Equals(item.Value, elem.Value))
         {
            list.Remove(node);
            --_count;
            return true;
         }

         node = node.Next;
      }

      return false;
   }

   IEnumerator IEnumerable.GetEnumerator() {
      IEnumerator<KeyValuePair<TKey, TValue>> e = this.GetEnumerator();
      return e;
   }
}

おわり

今回は、連鎖法を使って、ハッシュテーブルの(Set,Get,Add)を実装しました。

筆者はハッシュ被りの処理など、ハッシュテーブルの仕組みが分かって安心しました。

さようなら。

参考

https://ja.wikipedia.org/wiki/ハッシュテーブル
https://ufcpp.net/study/dotnet/bcl_collection_algorithm.html

Discussion

ログインするとコメントできます