4

Ruby のハッシュは、そのハッシュ値 (文字列と数値) を使用するだけです。内部的には、Murmur ハッシュ関数を使用します。2 つの異なるキーに対して同じハッシュ値を持つ確率がゼロではないことを考えると、どうすればそれができるのだろうか。

4

2 に答える 2

2

「ハッシュ テーブル」またはディクショナリは衝突してもまったく問題ないことを覚えておいてください。実際、それは期待され、合理的な実装に対応しています。

理想的には、衝突ができるだけ少ないハッシュを作成するように努めます。優れたハッシュ関数を作成するものについては、博士レベルの議論が行われていますが、それらは避けられません。衝突が発生すると、コンテナ内で 2 つの値が同じインデックスを共有します。

値のハッシュ方法に関係なく、ハッシュに基づく潜在的な一致を評価する必要があります。アクセスしている値が要求されたものであることを確認するために、直接比較が実行されます。偶然に同じ場所にマッピングされるものではありません。

通常のハッシュ テーブルは、一般的な用途では完全に隠されていますが、配列の配列と考えることができます。

これがどのように動作するかを調べたい場合は、Ruby で独自のハッシュ テーブルを実装できます。

class ExampleHash
  include Enumerable

  def initialize
    @size = 9
    @slots = Array.new(@size) { [ ] }
  end

  def [](key)
    @slots[key.hash % @size].each do |entry|
      if (entry[0] == key)
        return entry[1]
      end
    end

    nil
  end

  def []=(key, value)
    entries = @slots[key.hash % @size]

    entries.each do |entry|
      if (entry[0] == key)
        entry[1] = value

        return
      end
    end

    entries << [ key, value ]
  end
end

hashRuby のすべてのオブジェクトには、オブジェクトのコンテンツに基づいて大きな数値を生成する組み込みメソッドがあるため、これは簡単です。

于 2016-04-30T07:40:12.830 に答える