Bidirectional Hash table in Ruby

Question

I need a bidirectional Hash table in Ruby. For example:

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

Method rfetch means reversed fetch and is only my proposal.

Note three things:

1. If multiple keys map at the same value then rfetch returns all of them, packed in array.
2. If value is an array then rfetch looks for its param among elements of the array.
3. Bidirectional Hash means that both fetch and rfetch should execute in constant time.

Does such structure exists in Ruby (including external libraries)?

I thought about implementing it using two one-directional Hashes synchronized when one of them is modified (and packing it into class to avoid synchronization problems) but maybe I could use an already existing solution?

Answer 1

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.