ハッシュテーブルの説明

私のお気に入りのデータ構造の1つは、シンプルで強力なハッシュテーブルです。

キーと値のペアを格納する効率的な方法であるため、おそらく以前に使用したことがあります。

ハッシュテーブルの実装の背後には、研究する価値のある興味深いコンピュータサイエンスの概念がいくつかあります。これは、まさにこの記事で行うことです！

バケットとハッシュ関数

ハッシュテーブルの基本的な考え方は、効率的に（O(1)で）できるようにすることです。 ）キーでインデックス付けされたデータを取得します。

簡単に復習すると、Rubyでハッシュテーブルを使用すると次のようになります。

prices = {
  apple: 0.50,
  ice_cream: 3,
  steak: 10
}

ハッシュテーブルを実装するには、2つのコンポーネントが必要です。

• テーブルエントリを保存する場所
• このデータストア内の特定の位置（インデックス）にキーと値のペアを割り当てる方法

つまり、配列とハッシュ関数が必要です。

単純なハッシュ関数の実装

ハッシュ関数 はハッシュテーブルの重要なコンポーネントです。

この関数は、キーを、関連する値を検索または更新するために使用できるインデックスに変換します。

これがプレーン配列とハッシュテーブルの大きな違いです。

配列では、インデックスを介してのみ値にアクセスでき、インデックスは数値のみになります。ハッシュテーブルでは、キーを介して値にアクセスします。キーは何でもかまいません （文字列、記号、整数…）、ハッシュ関数を記述できる限り。

すべての文字をASCII値に変換してから合計することにより、文字列の単純なハッシュ関数を記述できます。

ここに例があります ：

BUCKETS = 32

def hash(input)
  input.to_s.chars.inject(0) { |sum, ch| sum + ch.ord } % BUCKETS
end

このメソッドでは、to_sを使用します 文字列を操作していることを確認します。

これは、「未定義のメソッド」エラーを回避するのに役立ちます。次に、charsの組み合わせ （文字列をArrayに変換します その文字の）＆inject 値を合計するため。

ブロック内でordを使用しました 文字を順序値に変換するメソッド。

最後に、モジュロ演算子%を使用しました 結果の値が配列に適合することを確認します。この配列の各エントリを「バケット」と呼びます。

バケット配布

理想的には、すべてのバケットを均等に満たす必要があります。これにより、値を取得する必要があるときに最高のパフォーマンスが得られます。

このコードを使用してハッシュ関数をテストするとどうなるか見てみましょう：

# Create an array of size BUCKETS with all elements set to 0
table   = Array.new(BUCKETS) { 0 }
letters = Array('a'..'z')

10_000.times do
  # Create a random string
  input = Array.new(5) { letters.sample }.join

  # Count hash distribution
  table[hash(input)] += 1
end

これにより、次の結果が生成されます。

[302, 290, 299, 309, 321, 293, 316, 301, 296, 306, 340, 321, 313, 304, 318, 296, 331, 306, 348, 330, 310, 313, 298, 292, 304, 315, 337, 325, 325, 331, 319, 291]

キーが均等に分散されているようです…

…しかし、バケットの数を増やすとどうなりますか？

この例では、128のバケットサイズを使用しました（以前は32でした）：

[22, 24, 33, 36, 41, 58, 61, 66, 97, 77, 88, 110, 89, 82, 123, 121, 119, 111, 147, 178, 136, 176, 144, 180, 190, 193, 185, 192, 223, 209, 208, 196, 215, 251, 233, 226, 231, 236, 219, 218, 227, 221, 206, 220, 208, 213, 201, 191, 182, 165, 188, 141, 160, 135, 130, 117, 139, 106, 121, 85, 70, 93, 74, 61, 57, 54, 40, 46, 32, 36, 30, 21, 25, 17, 14, 16, 16, 14, 8, 11, 5, 5, 1, 1, 2, 1, 3, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 2, 0, 4, 3, 6, 0, 2, 9, 13, 11, 12, 14, 12, 23, 12, 22]

それはもはや素晴らしいディストリビューションのようには見えません！

何が起こっているのですか？

問題は、同じサイズのすべての文字列が特定の範囲内にあるため、ハッシュ関数が十分ではないことです。そのため、中央に空のバケットがたくさんあります。

より優れたハッシュ関数

文字列をインデックスに変換するためのより良い方法が必要です。考えられる実装の1つを見てみましょう。

BUCKETS = 256

def hash(input)
  input.to_s.each_char.inject(0) do |sum, ch|
    (sum << 8) ^ (ch.ord) ^ (sum >> 4)
  end % BUCKETS
end

ここで起こっているのはビットシフトです（>> ＆<< 演算子）。値は「排他的論理和演算子」（^）を使用して結合されます 。

このビットシフトは物事を混乱させ、より良い鍵配分をもたらします。 。完璧ではありませんが、単純なASCIIベースの関数よりも優れています🙂

適切なハッシュ関数が必要な場合は、MurmurHashのようなものを検討します。これは、Rubyが使用しているものだと思います。

衝突の処理

有用なハッシュテーブルはまだありません。

なぜですか？

2つのキーが同じインデックスにハッシュされると、古い値が上書きされることに気付いたかもしれませんが、それは良くありません！

これはハッシュ衝突と呼ばれ、これらに対処するためのいくつかの戦略があります。

例 ：

• ダブルハッシュ
• 線形プロービング
• 個別の連鎖

リンクリストを使用して特定の「バケット」のエントリを格納する、個別のチェーンを見てみましょう。

したがって、:abcと仮定すると、 ＆:ccc 同じインデックスにハッシュすると、ハッシュテーブルは次のようになります。

3: [:abc, 100] -> [:ccc, 200]
4: nil
5: [:yx, 50]

次に、正しいキーを見つけるために線形検索が必要になります。

ルックアップ時間はO(n)に向かってゆっくりと低下する可能性があるため、これはパフォーマンスに影響を与えます。 、予想されるO(1)の代わりに 。

このO(something)に慣れていない場合 「Big-O表記」と呼ばれる表記。

リンクリストが深くなりすぎてハッシュテーブルのパフォーマンスが低下するのを防ぐには、より多くのバケットを使用してハッシュテーブルを再作成する必要があります。

Rubyはこれを自動的に行いますが、それでも知っておくとよいでしょう。

結論

この記事の目的は、ハッシュテーブルの実装を作成することではなく、実際にどのように機能するかを理解するのに役立つことです。そのため、おもしろいと思います。

ブログを続けるために、この投稿を共有することを忘れないでください🙂