Cuckoo HashingをRubyで作る

Radium SoftwareのCuckoo Hashingの記事、すごく面白かったです(http://d.hatena.ne.jp/KZR/20080531/p2)。
これって、どれくらい性能いいのかなと思い、Rubyで作ってみました。作って気づいたことです。

• ハッシュ関数の設計がとてもシビア。手を抜くと無駄な領域がものすごくたくさん出ます。それは、たくさん空き領域があってもリトライ回数がくれば強制的にリハッシュしてしまうからです。
• リトライ回数がなかなか面白そうなテーマの気がします。とりあえずハッシュバケットの平方根を使っていますが、それよりは小さくてもよさそうです。

この辺の議論はし尽くされているでしょう。やっぱり、元論文を読まないといけないのかなー？

使い方です。

• CuckooHash.newでオブジェクトを作ります。
• メソッドはと=だけです。イテレータもありません。

テストプログラム兼サンプルプログラムです
test_many_dataはrubyのライブラリディレクトリのrubyファイルのトークンの数を数えるものです。

require 'test/unit'
require 'cuckoo'
require 'find'
require 'ripper'

class TC_CukooHash<Test::Unit::TestCase
  def test_basic
    cht = CuckooHash.new
    cht[:a] = 1
    cht[:b] = 2
    cht[1234] = 32
    cht[3.1415] = 42
    cht[:k] = 5
    cht["k"] = "foo"
    cht["aaa"] = "bar"

    assert_equal(cht[:a], 1)
    assert_equal(cht[:b], 2)
    assert_equal(cht[:k], 5)
    assert_equal(cht[:a], 1)
    assert_equal(cht[:d], nil)
    assert_equal(cht[3.1415], 42)
    assert_equal(cht["k"], "foo")
    assert_equal(cht["foo"], nil)
  end

  def test_many_data
    cht = CuckooHash.new
    ht = Hash.new(0)
    Find.find('c:/cygwin/usr/local/lib/ruby/') do |f|
      if File.file?(f) and /\.rb$/ =~ f then
        Ripper.tokenize(File.read(f)).each do |token|
          if cht[token] == nil
            cht[token] = 0
          end

          cht[token] += 1
          ht[token] += 1
        end
      end
    end

    assert_equal(cht["def"], ht["def"])
    assert_equal(cht["class"], ht["class"])

  end
end

本体のプログラムです。

class CuckooHash
  # rubyのst.cよりもって来ました
  # 正確にはPeter Moore@UCBさんのハッシュテーブルパッケージからです
  PRIMES = [
	8 + 3,
	16 + 3,
	32 + 5,
	64 + 3,
	128 + 3,
	256 + 27,
	512 + 9,
	1024 + 9,
	2048 + 5,
	4096 + 3,
	8192 + 27,
	16384 + 43,
	32768 + 3,
	65536 + 45,
	131072 + 29,
	262144 + 3,
	524288 + 21,
	1048576 + 7,
	2097152 + 17,
	4194304 + 15,
	8388608 + 9,
	16777216 + 43,
	33554432 + 35,
	67108864 + 15,
	134217728 + 29,
	268435456 + 3,
	536870912 + 11,
	1073741824 + 85,
	0
  ]

  def initialize
    @primepos = 5
    @tabsize = PRIMES[@primepos]
    @table = [Array.new(@tabsize), Array.new(@tabsize)]
  end

  def [](key)
    if ent = lookup(key) then
      ent[1]
    else
      nil
    end
  end

  def []=(key, value)
    if ent = lookup(key) then
      ent[1] = value
      return value
    end

    cent = [key, value]
    while !insert(cent) do
      rehash
    end
    
    value
  end

  def hash0(obj)
    obj.hash
  end

  def hash1(obj)
    h = obj.hash
    (h % (65536 + 45)) * (h % (16384 + 43))
  end

  private

  def insert(cent)
    ent = nil
    (0..Math.sqrt(@tabsize)).each do |n|
      # テーブル0にトライ
      h = hash0(cent[0])
      h = h % @tabsize
      if ent = @table[0][h] then
        @table[0][h] = cent
        cent = ent
      else
        @table[0][h] =cent
        return true
      end

      # テーブル1にトライ
      h = hash1(cent[0])
      h = h % @tabsize
      if ent = @table[1][h] then
        @table[1][h] = cent
        cent = ent
      else
        @table[1][h] =cent
        return true
      end
    end

    return false
  end

  def rehash
    otable = @table
    @primepos += 1
    @tabsize = PRIMES[@primepos]
    @table = [Array.new(@tabsize), Array.new(@tabsize)]
    [0, 1].each do |n|
      otable[n].each do |ele|
        if ele then
          insert(ele)
        end
      end
    end
  end

  def lookup(key)
    h = hash0(key)
    h = h % @tabsize
    if ent = @table[0][h] and ent[0] == key then
      return ent
    end

    h = hash1(key)
    h = h % @tabsize
    if ent = @table[1][h] and ent[0] == key then
      return ent
    end

    nil
  end
end