Ruby哈希表的键是对象的函数？

Question

Ruby哈希表的键是对象的函数？

3

例如，

s1 = Student.new(1, "Bob", "Podunk High")
hash[1] = s1
puts hash[1].name    #produces "Bob"
s1.id = 15
puts hash[15].name   #produces "Bob"
puts hash[1].name    #fails

这不完全是哈希（Hash）行为，插入错误的键仍然需要定义。

虽然我肯定可以自己编写这种行为的容器，但很难使其快速，即在每次调用[]时不必搜索整个容器。只是想知道是否有更聪明的人已经制作了我可以借鉴的东西。

编辑：下面的一些好主意帮助我聚焦我的要求：

避免O(n)的查找时间
允许多个容器指向同一对象（关联而非组成）
具有不同的数据类型（例如可能使用name而不是id），而无需进行太多重新实现

- alexloh

4个回答

1

当您的键已更改时，必须通知容器，否则您必须在lg(n)中动态搜索键。

如果您很少更改键并且经常查找，请重新构建哈希：

def build_hash_on_attribute(objects, attribute)
  Hash[objects.collect { |e| [e.send(method), e] }]
end

s1 = OpenStruct.new id: 1, name: 's1'

h = build_hash_on_attribute([s1], :id)
h[1].name # => 's1'

h[1].id = 15
# rebuild the whole index after any key attribute has been changed
h = build_hash_on_attribute(h.values, :id)
h[1] # => nil
h[15].name # => 's1'

更新 02/12: 添加使用观察者模式的解决方案

如果您需要自动索引构建，可以使用以下观察者模式或装饰器模式。但是在装饰器模式中，您需要使用包装对象。

代码片段: https://gist.github.com/1807324

module AttrChangeEmitter
  def self.included(base)
    base.extend ClassMethods
    base.send :include, InstanceMethods
  end

  module ClassMethods
    def attr_change_emitter(*attrs)
      attrs.each do |attr|
        class_eval do
          alias_method "#{attr}_without_emitter=", "#{attr}="
          define_method "#{attr}_with_emitter=" do |v|
            previous_value = send("#{attr}")
            send "#{attr}_without_emitter=", v
            attr_change_listeners_on(attr).each do |listener|
              listener.call self, previous_value, v
            end
          end
          alias_method "#{attr}=", "#{attr}_with_emitter="
        end
      end
    end
  end

  module InstanceMethods
    def attr_change_listeners_on(attr)
      @attr_change_listeners_on ||= {}
      @attr_change_listeners_on[attr.to_sym] ||= []
    end

    def add_attr_change_listener_on(attr, block)
      listeners = attr_change_listeners_on(attr)
      listeners << block unless listeners.include?(block)
    end

    def remove_attr_change_listener_on(attr, block)
      attr_change_listeners_on(attr).delete block
    end
  end
end

class AttrChangeAwareHash
  include Enumerable

  def initialize(attr = :id)
    @attr = attr.to_sym
    @hash = {}
  end

  def each(&block)
    @hash.values.each(&block)
  end

  def on_entity_attr_change(e, previous_value, new_value)
    if @hash[previous_value].equal? e
      @hash.delete(previous_value)
      # remove the original one in slot new_value
      delete_by_key(new_value)
      @hash[new_value] = e
    end
  end

  def add(v)
    delete(v)
    v.add_attr_change_listener_on(@attr, self.method(:on_entity_attr_change))
    k = v.send(@attr)
    @hash[k] = v
  end

  alias_method :<<, :add

  def delete(v)
    k = v.send(@attr)
    delete_by_key(k) if @hash[k].equal?(v)
  end

  def delete_by_key(k)
    v = @hash.delete(k)
    v.remove_attr_change_listener_on(@attr, self.method(:on_entity_attr_change)) if v
    v
  end

  def [](k)
    @hash[k]
  end
end

class Student
  include AttrChangeEmitter
  attr_accessor :id, :name
  attr_change_emitter :id, :name

  def initialize(id, name)
    self.id = id
    self.name = name
  end
end

indexByIDA = AttrChangeAwareHash.new(:id)
indexByIDB = AttrChangeAwareHash.new(:id)
indexByName = AttrChangeAwareHash.new(:name)

s1 = Student.new(1, 'John')
s2 = Student.new(2, 'Bill')
s3 = Student.new(3, 'Kate')

indexByIDA << s1
indexByIDA << s3

indexByIDB << s1
indexByIDB << s2

indexByName << s1
indexByName << s2
indexByName << s3

puts indexByIDA[1].name # => John
puts indexByIDB[2].name # => Bill
puts indexByName['John'].id # => 1

s2.id = 15
s2.name = 'Batman'

p indexByIDB[2] # => nil
puts indexByIDB[15].name # => Batman

indexByName.each do |v|
  v.name = v.name.downcase
end

p indexByName['John'] # => nil
puts indexByName['john'].id # => 1

p indexByName.collect { |v| [v.id, v.name] }
# => [[1, "john"], [3, "kate"], [15, "batman"]]

indexByName.delete_by_key 'john'
indexByName.delete(s2)

s2.id = 1 # set batman id to 1 to overwrite john
p indexByIDB.collect { |v| [v.id, v.name] }
# => [[1, "batman"]]

p indexByName.collect { |v| [v.id, v.name] }
# => [[3, "kate"]]

- Ian Yang

1

虽然哈希对象可能不会按照您想要的方式运作，但您始终可以自定义要插入的对象以特定方式进行哈希。

您可以通过向现有类添加两个新方法来实现此操作：

class Student
  def hash
    self.id
  end

  def eql?(student)
    self.id == student.id
  end
end

通过定义hash以返回基于id的值，哈希将考虑这两个候选者在哈希中相同的位置。第二个定义声明了任何具有相同哈希值的两个对象之间的“哈希等价性”。

只要您的id值适合传统的32位Fixnum并且不是64位BIGINT数据库值，这将很好地工作。

正如fl00r指出的那样，只有当您的id是不可变的时，这才有效。对于大多数数据库来说，这往往是正确的。但是，在运行过程中更改id可能是一个非常糟糕的想法，因为它可能导致完全混乱和令人难以置信的错误。

- tadman

我责备自己选择不当的例子。哈希表并不是数据库表，也不需要以唯一标识为键。另一个可能会以“名称”或“座位号”为键，而这些值可能会经常变化。 - alexloh

1

有很多内存数据库可用。我曾在一个类似的项目中使用过Apache Derby。 - Confusion

1

这是一个难题。数据库供应商可以赚钱，因为这是一个难题。你基本上要实现传统的RDBMS索引：搜索派生数据，以提供对其派生自的数据的快速查找，同时允许该数据发生更改。如果你想从多个线程访问数据，你很快就会遇到所有使数据库符合ACID标准变得困难的问题。

我建议将数据放入数据库中，添加必要的索引，并让数据库 - 一款专为此目的优化的应用程序 - 完成工作。

- Confusion

既然你指出来了，看起来确实比我想象的要难解决。我可能会坚持使用不好的O(n)解决方案。在内存应用程序中使用数据库太慢了。 - alexloh

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- fl00r · Accepted Answer

你可以自己实现它。

看一下草案解决方案：

class Campus
  attr_reader :students
  def initialize
    @students = []
  end

  def [](ind)
    students.detect{|s| s.id == ind}
  end

  def <<(st)
    raise "Yarrr, not a student"   if st.class != Student
    raise "We already have got one with id #{st.id}" if self[st.id]
    students << st
  end
end

class Student
  attr_accessor :id, :name, :prop
  def initialize(id, name, prop)
    @id, @name, @prop = id, name, prop
  end
end

campus = Campus.new
st1 = Student.new(1, "Pedro", "Math")
st2 = Student.new(2, "Maria", "Opera")
campus << st1
campus << st2
campus[1]
#=> Student...id:1,name:pedro...
campus[2].name
#=> Maria
campus[2].id = 10
campus[2]
#=> error
campus[10].name
#=> Maria

或者您可以尝试使用数组类（如果您确实需要，也可以使用哈希表）：

class StrangeArray < Array
  def [](ind)
    self.detect{|v| v.id == ind} || raise "nothing found" # if you really need to raise an error
  end

  def <<(st)
    raise "Looks like a duplicate" if self[st.id]
    self.push(st)
  end
end

campus = StrangeArray.new
campus << Student.new(15, 'Michael', 'Music')
campus << Student.new(40, 'Lisa', 'Medicine')
campus[1]
#=> error 'not found'
campus[15].prop
#=> Music
campus[15].id = 20
campus[20].prop
#=> Music

在@tadman提出正确评论之后，您可以直接在学生类中引用您的hash：

class Student
  attr_accessor :name, :prop
  attr_reader :id, :campus
  def initialize(id, name, prop, camp=nil)
    @id, @name, @prop = id, name, prop
    self.campus = camp if camp
  end

  def id=(new_id)
    if campus
      rase "this id is already taken in campus" if campus[new_id]
      campus.delete id
      campus[new_id] = self
    end
    @id = new_id
  end

  def campus=(camp)
    rase "this id is already taken in campus" if camp[id]
    @campus = camp
    camp[@id] = self
  end
end

campus = {}
st1 = Student.new(1, "John", "Math")
st2 = Student.new(2, "Lisa", "Math", campus)
# so now in campus is only Lisa
st1.campus = campus
# we've just pushed John in campus
campus[1].name
#=> John
campus[1].id = 10
campus[10].name
#=> John