11

Ruby で双方向ハッシュ テーブルが必要です。例えば：

h = {:abc => 123, :xyz => 789, :qaz => 789, :wsx => [888, 999]}
h.fetch(:xyz) # => 789
h.rfetch(123) # => abc
h.rfetch(789) # => [:xyz, :qaz]
h.rfetch(888) # => :wsx

メソッドrfetchは逆フェッチを意味し、私の提案にすぎません。

次の 3 つの点に注意してください。

  1. 複数のキーが同じ値にマップされている場合はrfetch、それらすべてを配列にパックして返します。
  2. 値が配列の場合、配列rfetchの要素の中からそのパラメーターを探します。
  3. 双方向ハッシュとは、 と の両方が一定時間内に実行されることを意味しfetchますrfetch。

そのような構造は Ruby (外部ライブラリを含む) に存在しますか?

そのうちの1つが変更されたときに同期される2つの一方向ハッシュを使用して実装することを考えました（そして、同期の問題を回避するためにクラスにパックします）が、既存のソリューションを使用できるでしょうか？

4

5 に答える 5

7

You could build something yourself pretty easily, just use a simple object that wraps two hashes (one for the forward direction, one for the reverse). For example:

class BiHash
    def initialize
        @forward = Hash.new { |h, k| h[k] = [ ] }
        @reverse = Hash.new { |h, k| h[k] = [ ] }
    end

    def insert(k, v)
        @forward[k].push(v)
        @reverse[v].push(k)
        v
    end

    def fetch(k)
        fetch_from(@forward, k)
    end

    def rfetch(v)
        fetch_from(@reverse, v)
    end

    protected

    def fetch_from(h, k)
        return nil if(!h.has_key?(k))
        v = h[k]
        v.length == 1 ? v.first : v.dup
    end
end

Look ups will behave just like normal hash lookups (because they are normal hash lookups). Add some operators and maybe decent to_s and inspect implementations and you're good.

Such a thing works like this:

b = BiHash.new
b.insert(:a, 'a')
b.insert(:a, 'b')
b.insert(:a, 'c')
b.insert(:b, 'a')
b.insert(:c, 'x')

puts b.fetch(:a).inspect            # ["a", "b", "c"]
puts b.fetch(:b).inspect            # "a"
puts b.rfetch('a').inspect          # [:a, :b]
puts b.rfetch('x').inspect          # :c
puts b.fetch(:not_there).inspect    # nil
puts b.rfetch('not there').inspect  # nil

There's nothing wrong with building your tools when you need them.

于 2011-08-03T18:32:10.763 に答える
5

Rubyにはそのような構造が組み込まれていません。

Hash#rassocは同様のことを行いますが、最初の一致のみを返し、線形時間であることに注意してください。

h = {:abc => 123, :xyz => 789, :qaz => 789, :wsx => [888, 999]}
h.rassoc(123) # => [:abc, 123]

また、配列である値の変更を検出できないため、完全に安全な方法で Ruby の要件を満たすことはできません。例えば：

h = MyBidirectionalArray.new(:foo => 42, :bar => [:hello, :world])
h.rfetch(:world) # => :bar
h[:bar].shift
h[:bar] # => [:world]
h.rfetch(:world) # => should be nil, but how to detect this??

変更を検出するために毎回ハッシュを計算すると、ルックアップが線形時間になります。ただし、配列値を複製してフリーズすることもできます (Ruby が文字列であるハッシュ キーに対して行うように!)

あなたが必要としているのは Graph クラスHashです。rglなどをチェックアウトできますが、それらがどのように実装されているかはわかりません。

幸運を。

于 2011-08-03T14:44:05.263 に答える
3

Hash#invertこれを実現する方法 ( http://www.ruby-doc.org/core-2.1.0/Hash.html#method-i-invert )があります。ただし、複数の値を配列にマップすることはありません。

于 2014-03-15T15:15:29.617 に答える
0

このハッシュに対して多くの更新を行っていない場合は、 inverthashを使用できる可能性があります。

于 2011-08-03T14:59:18.647 に答える
0

これを試して：

class Hash
  def rfetch val
    select { |k,v| v.is_a?(Array) ? v.include?(val) : v == val }.map { |x| x[0] }
  end
end
于 2011-08-03T12:41:12.257 に答える