Consistent Hashingのごく単純な実装

ここを参考に。

require 'digest/md5'

class Node
  attr_reader :name

  def initialize(name)
    @name = name
    @values = []
  end

  def <<(value)
    @values << value
  end

  def values
    @values.sort
  end

  def hash
    Digest::MD5.hexdigest(@name.to_s)
  end
end

class Nodes
  def initialize
    @nodes = {}
  end

  def <<(node)
    @nodes[node.hash] = node
  end

  def put(value)
    node = search(value)
    node << value
  end

  def nodes
    @nodes.values.sort_by {|i| i.hash }
  end

  private
  def search(value)
    value_key = Digest::MD5.hexdigest(value.to_s)
    sorted_keys = @nodes.keys.sort
    max = sorted_keys.length - 1

    (0...max).each do |i|
      a = sorted_keys[i]
      b = sorted_keys[i + 1]

      if a <= value_key and value_key < b
        return @nodes[b]
      end
    end

    return @nodes[sorted_keys.first]
  end
end

def test(names)
  ns = Nodes.new

  names.each do |name|
    node = Node.new(name)
    ns << node
  end

  ('A'..'Z').each do |c|
    ns.put(c)
  end

  puts ns.nodes.map {|node| node.name }.join(' -> ')

  ns.nodes.each do |node|
    puts "#{node.name}:\t#{node.values.join ' '}"
  end
end

test %w(foo bar zoo baz); puts

test %w(foo bar zoo); puts

test %w(foo bar)

~$ ruby ch.rb

bar -> baz -> foo -> zoo

bar:    C D G I J O Q R X Z

baz:    E M P S U V W Y

foo:    A B F K N

zoo:    H L T
bar -> foo -> zoo

bar:    C D G I J O Q R X Z

foo:    A B E F K M N P S U V W Y

zoo:    H L T
bar -> foo

bar:    C D G H I J L O Q R T X Z

foo:    A B E F K M N P S U V W Y

仮想ノードを作ってみる。

require 'digest/md5'

class Node
  attr_reader :name

  def initialize(name)
    @name = name
    @values = []
  end

  def <<(value)
    @values << value
  end

  def values
    @values.sort
  end

  def name_hash(i)
    Digest::MD5.hexdigest(@name + i.to_s)
  end
end

class Nodes
  def initialize(repls = 1)
    @repls = repls
    @nodes = {}
  end

  def <<(node)
    @repls.times do |i|
      @nodes[node.name_hash(i)] = node
    end
  end

  def put(value)
    node = search(value)
    node << value
  end

  def each
    @nodes.values.uniq.each do |node|
      yield(node)
    end
  end

  private
  def search(value)
    value_key = Digest::MD5.hexdigest(value.to_s)
    sorted_keys = @nodes.keys.sort
    max = sorted_keys.length - 1

    (0...max).each do |i|
      a = sorted_keys[i]
      b = sorted_keys[i + 1]

      if a <= value_key and value_key < b
        return @nodes[b]
      end
    end

    return @nodes[sorted_keys.first]
  end
end

def test(names)
  ns = Nodes.new(1024)

  names.each do |name|
    node = Node.new(name)
    ns << node
  end

  ('A'..'Z').each do |c|
    ns.put(c)
  end

  ns.each do |node|
    puts "#{node.name}:\t#{node.values.join ' '}"
  end
end

test %w(foo bar zoo baz); puts

test %w(foo bar zoo); puts

test %w(foo bar)

~$ ruby ch2.rb

foo:    A B E K X Z

bar:    C D I M R S W Y

zoo:    H J P T U V

baz:    F G L N O Q
bar:    C D I M O R S W Y

foo:    A B E F G K L Q X Z

zoo:    H J N P T U V
bar:    C D H I M N O P R S W Y

foo:    A B E F G J K L Q T U V X Z

…仮想ノードを作るときのハッシュ値の算出方法は正しいんだろうか？
ハッシュ値が衝突したときはどうするんだろう？