Двунаправленный хэш-стол в рубине

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

Нет ничего плохого в том, чтобы создавать ваши инструменты, когдаони вам нужны.

Answer 2

Такой структуры нет в Ruby.

Обратите внимание, что Hash#rassoc делает что-то похожее, но возвращает только первое совпадение и имеет линейное время:

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

Кроме того, невозможно полностью удовлетворить ваши требования в Ruby, поскольку вы не сможете обнаружить изменения значений, которые являются массивами. 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??

Вычисление хеша каждый раз, чтобы обнаружить изменение, сделает ваш поиск линейным по времени. Вы можете дублировать значения массива и заморозить их, хотя (как это делает Ruby для ключей Hash, которые являются строками!)

Вам нужен класс Graph, API которого может отличаться от Hash, нет? Вы можете проверить rgl или аналогичный, но я не знаю, как они реализованы.

Удачи.

Answer 3

Существует метод Hash#invert (http://www.ruby -doc.org / core-2.1.0 / Hash.html # method-i-invert ) для достижения этого.Однако он не будет отображать несколько значений в массив.

Answer 4

Если вы не делаете много обновлений для этого хэша, вы можете использовать inverthash .

Answer 5

Попробуйте это:

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