Ruby中的雙向哈希表

Question

我需要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意味着逆轉取和只是我的建議。

注意三件事情：

1. 如果有多個按鍵的同時值映射然後rfetch回報所有的人，裝在陣列。
2. 如果值是一個數組然後rfetch查找其PARAM的數組的元素之一。
3. 雙向散列意味着兩個fetch和rfetch應在一定時間執行。

是否在紅寶石（包括外部庫）存在這樣的結構？

我想過使用同步的兩個單向散列實現它時，其中一個被修改（和它包裝成類，以避免同步問題），但也許我可以用一個已經存在的解決方案嗎？

Answer 1

你可以建立自己的東西很容易地，只需使用一個簡單的對象，它包裝兩個散列（一個前進方向，一爲反向）。例如：

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 

看UPS的行爲就像正常的哈希查找（因爲他們是正常哈希查詢）。添加一些運營商，也許體面的to_s和inspect實現，你很好。

這樣的事情是這樣的：

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 

沒有什麼錯當你需要他們構建工具。

Answer 2

試試這個：

class Hash 
    def rfetch val 
    select { |k,v| v.is_a?(Array) ? v.include?(val) : v == val }.map { |x| x[0] } 
    end 
end 

Answer 3

有內置在Ruby中沒有這樣的結構。

注意Hash#rassoc有類似的功能，但只返回第一場比賽，是線性時間：

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

而且，不可能fullfill在一個完全安全的方式在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不同的API，不是嗎？您可以查看rgl或類似的內容，但我不知道它們是如何實現的。

祝你好運。

Answer 4

如果你沒有做大量的更新這個哈希，您可能能夠使用inverthash。

Answer 5

有一個Hash#invert方法（http://www.ruby-doc.org/core-2.1.0/Hash.html#method-i-invert）來實現這一點。它不會將多個值映射到數組。