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?

Abshire

For a quick-and-dirty, you can use the built-in hash.invert() to make a separate inverse hash (https://mcmap.net/q/116453/-how-to-find-a-hash-key-containing-a-matching-value). As @ken-bloom points out, a more robust implementation of this is at raa.ruby-lang.org/project/inverthash – Jacobjacoba

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.

Horvitz

It's probably a good idea to return v.dup instead of v in fetch_from, otherwise you will could get nasty side effects, e.g. b.rfetch(:a).pop – Roid

Answer 2

There is no such structure built-in in Ruby.

Note that Hash#rassoc does something similar, but it returns only the first match and is linear-time:

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

Also, it isn't possible to fullfill your requirements in Ruby in a perfectly safe manner, as you won't be able to detect changes in values that are arrays. E.g.:

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??

Computing a hash everytime to detect a change will make your lookup linear-time. You could duplicate the array-values and freeze them, though (like Ruby does for Hash keys that are strings!)

What you seem to need is a Graph class, which could have a different API than a Hash, no? You can check out rgl or similar, but I don't know how they're implemented.

Good luck.

Bony

Answer 3

There is a Hash#invert method (http://www.ruby-doc.org/core-2.1.0/Hash.html#method-i-invert) to achieve this. It won't map multiple values to an array though.

Cocktail

Answer 4

Try this:

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

Gang

Yes, it's the simplest solution, however, it requires linear time so it breaks the third point mentioned in the question. – Outtalk

Answer 5

If you're not doing lots of updates to this hash, you might be able to use inverthash.

Meyerhof