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. 如果value是一个数组,那么rfetch在数组的元素中查找它的参数.
3. 双向哈希意味着这两个fetch和rfetch在固定时间内应该执行.

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

我考虑过使用两个单向Hashes同步修改它们中的一个(并将其打包到类中以避免同步问题),但也许我可以使用已有的解决方案？

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

在需要时构建工具没有任何问题.

Answer 2

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类,它可以有一个不同的API Hash,不是吗？您可以查看rgl或类似内容,但我不知道它们是如何实现的.

祝好运.