#
# ハッシュ表 (激突の場合、チェイン法使用)
#
class ChainedHashDictionary
  def initialize (max_occupancy = 5)
    @max_occupancy = max_occupancy             # (最大) 占有率
    @count = 0                                 # 保存されている項目の数
    @size = 1                                  # ハッシュ表の大きさ
    init_table
  end
  
  def init_table
    @table = Array.new(@size) { [] }           # ハッシュ表そのもの
  end                                          # 簡単のため、連結リストの代わり配列を使用
   
  def hash_function(key)                       # ハッシュ関数
    key.hash % @size                           # Ruby のハッシュ関数を再利用
  end
  
  def find_bin(key)                            # ハッシュ表内の場所の特定
    @table[hash_function(key)]
  end
  
  def find(key)
    found = find_bin(key).find { |entry| entry.key==key }
    found.value or warn "Key #{key} not found"
  end

  def expand
    @size = @size * 2 + 1                      # 新しい大きさの計算
    @count = 0
    old_table = @table
    init_table                                 # 新しいハッシュ表の作成
    old_table.each do |bin|
      bin.each do |entry|
        insert entry
      end
    end
  end
  
  def insert(entry)
    @count += 1
    expand  if @count > @size*@max_occupancy
    find_bin(entry.key) << entry               # 項目の追加
  end
  
  def delete(key)
    find_bin(key).delete_if { |entry| entry.key==key and @count-=1 }
  end
    
  def print_stats
    puts
    puts "Number of entries: #{@count}"
    puts "Number of bins: #{@size}"
    puts "Average bin size: #{@count.to_f / @size}"
    @table.group_by { |bin| bin.size }.sort.each do |size, bins|
      puts "Number of bins of size #{size}: #{bins.size}"
    end
  end
end

#
# ハッシュ表 (激突の場合、解番地法使用)
#
class OpenHashDictionary
  def initialize (max_occupancy = 0.5)
    @max_occupancy = max_occupancy
    @count = 0
    @size = 1
    @deleted = 0
    init_table
  end
  
  def init_table
    @table = Array.new(@size) { nil } # nil は「空」の意味
  end
  
  def hash_function(key)
    key.hash % @size
  end
  
  def next_pos(pos) (pos+1) % @size end
  
  def find_pos(key)
    pos = hash_function(key)
    pos = next_pos(pos)  until @table[pos]==nil or @table[pos].key==key
    pos
  end
  
  def find(key)
    if found = @table[find_pos(key)]
      found.value
    else
      warn "Key #{key} not found"
      nil
    end
  end
  
  def expand
    @size = @size * 2 + 1
    @count = 0
    @deleted = 0
    old_table = @table
    init_table
    old_table.each do |entry|
      insert(entry)  unless entry==nil or entry==DELETED
    end
  end
  
  def insert(entry)
    @count += 1
    exand  if @count+@deleted > @size*@max_occupancy
    pos = hash_function(entry.key)
    pos = next_pos(pos)  until @table[pos]==nil
    @table[pos] = entry
  end
  
  def delete(key)
    if @table[find_pos(key)]
      @table[find_pos(key)] = DELETED
      @deleted += 1
    else
      warn "Key #{key} not found"
    end
  end
end

class Deleted; end
DELETED = Deleted.new               # 削除を表す特別な値

if __FILE__ == $0                   ## このファイルが直接呼び出された場合のみ実行
  class Fixnum                      # HashDictionary に整数を直接追加できる
    def key()  self  end            # ために整数を拡張
    def value()  self  end
  end

  hash_dict = ChainedHashDictionary.new(3)
  1001.times do |n|
    #puts
    #hash_dict.print_stats
    r = rand 10000000
    #puts "Inserting #{r}"
    hash_dict.insert r
  end

  puts hash_dict.inspect
  hash_dict.print_stats
end