ruby - 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 在数组的元素中查找它的参数。
3. 双向哈希意味着 fetch 和 rfetch 都应该在恒定时间内执行。

Ruby 中是否存在这样的结构(包括外部库)？

我想过使用两个单向哈希来实现它，当其中一个被修改时同步(并将其打包到类中以避免同步问题)但也许我可以使用一个已经存在的解决方案？

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

查找将像普通散列查找一样运行(因为它们是普通散列查找)。添加一些运算符和可能合适的 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

在需要时构建工具并没有错。