動的ハッシュ表: W. Litwin の線形ハッシュ法

現代のデータベース・マネジメント・システムがハッシュ索引に利用している線形ハッシュ法 (Linear Hashing) のさわりを、 Ruby で遊んでみます。 線形ハッシュ法は、 外部記憶装置上へ動的にハッシュ表を作製する方法の一つで、 1980 年に W. Litwin が発見しました。 なお、 線形ハッシュの実例のソースコードを読むなら、 PostgreSQL のハッシュ索引がこの手法を広めた P. Larson の論文通りでわかりやすいかもしれません。

動的ハッシュ表には、 他に gdbm が採用している拡張ハッシュ法もあります。 どちらもビット・パターンの一部が同じハッシュ値のレコードをバケットにまとめて格納していきます。 違いはバケットがあふれたときの扱いで、 拡張ハッシュ法ではあふれた時点で即座にバケットを分割します。 線形ハッシュ法では、 バケットの分割はラウンド・ロビンで先頭から順番におこなっていき、 分割の順が回ってくるまでは、 あふれたままにします。 大雑把には、 挿入時にバケット分割の負荷をかけるのが拡張ハッシュ法で、 読み出し時にあふれた分の探索で負荷をかけるのが線形ハッシュ法と言えるのでしょう。 初期の K. Thompson の dbm から線形ハッシュまでを眺めるには次のレビューがわかりやすいです。

http://www.eecs.harvard.edu/margo/papers/usenix91/paper.pdf

線形ハッシュ法の仕組みがわかりやすいのは、 初期時のバケットの個数が 2 のべき乗の場合なので、 今回は 4 つのバケットから始めることにします。 さらに、 バケットのあふれの扱いを考えるが面倒なので、 あふれを気にせずに配列に突っ込んでいくことにします。 バケットが 4 つのときはハッシュ値の下位 2 ビットを使って、 レコードをバケットへ push します。 使っているビット数は level 変数で表します。 例えば、 原子番号 10 までの元素名をキーとして、 4 つのバケットに突っ込んでいった結果は次のようになりました。 なお、 レコードは安直にキーと値のペアの配列にしています。

    assert @bucket[0] == [["Hydrogen", 1], ["Carbon", 6], ["Nitrogen", 7], ["Neon", 10]]
    assert @bucket[1] == [["Beryllium", 4]]
    assert @bucket[2] == [["Helium", 2]]
    assert @bucket[3] == [["Lithium", 3], ["Boron", 5], ["Oxygen", 8], ["Fluorine", 9]]
    assert @level == 2 && @step_ptr == 0

この次のレコードを追加した時点で最初のバケット分割がおこるものとします。 レコードは 2 番目のバケットへ追加するのですが、 追加場所に関係なく分割がおこなわれ、 バケットの数が 5 つに増えます。 分割対象のバケットはステップ・ポインタ step_ptr が示しており、 ゼロに初期化するので、 まず先頭のバケットが分割されます。 分割が終わると step_ptr は 1 に変化します。

    assert @level == 2 && @step_ptr == 0
    # split_bucket で分割実行
    assert @bucket[0] == [["Carbon", 6], ["Nitrogen", 7], ["Neon", 10]]
    assert @bucket[1] == [["Beryllium", 4], ["Sodium", 11]]
    assert @bucket[2] == [["Helium", 2]]
    assert @bucket[3] == [["Lithium", 3], ["Boron", 5], ["Oxygen", 8], ["Fluorine", 9]]
    assert @bucket[4] == [["Hydrogen", 1]]
    assert @level == 2 && @step_ptr == 1

さらにバケットの分割が進んで、 step_ptr が 2 になりました。 ここまでで、 バケット 0 は 0 と 4 に分割され、 1 は 1 と5 に分割されています。 2 と 3 は分割前のままです。

    assert @bucket[0] == [["Carbon", 6], ["Nitrogen", 7], ["Neon", 10]]
    assert @bucket[1] == [["Beryllium", 4]]
    assert @bucket[2] == [["Helium", 2], ["Aluminum", 13], ["Phosphorus", 15]]
    assert @bucket[3] == [["Lithium", 3], ["Boron", 5], ["Oxygen", 8], ["Fluorine", 9]]
    assert @bucket[4] == [["Hydrogen", 1]]
    assert @bucket[5] == [["Sodium", 11], ["Magnesium", 12], ["Silicon", 14]]
    assert @level == 2 && @step_ptr == 2

さて、 step_ptr がゼロでないときは、 分割されたバケットと、 分割前のバケットが混在しています。 分割前のバケットに使うハッシュ値のビット数は level で、 分割済みのバケットに使うのは level + 1 ビットです。 この事情を考慮して、 キーからバケット番号を求めるメソッドは次のようになります。

#@<キーからバケット番号を求めます@>=
  def bucket_address(key)
    x = key.hash & ((1 << (@level + 1)) - 1)
    if x < (1 << @level) + @step_ptr
      x                   # バケットの個数より少ないとき
    else
      x ^ (1 << @level)   # @level + 1 ビット目をゼロに潰す
    end
  end

バケットにキーを持つレコードが含まれているかどうかは、 Array の assoc メソッドで調べることができるので、 ハッシュ表にキーが含まれているかどうかを調べるのは簡単です。

#@<キーがハッシュ表に含まれているかどうか調べます@>=
  def key?(key)
    x = bucket_address(key)
    not @bucket[x].assoc(key).nil?
  end

さらにバケットの分割を進めていくと、 level が 2 のときは 3 のバケットの分割で、 すべてのバケットを分割してしまったことになります。 この場合、 level を増やして 3 にし、 step_ptr をゼロに戻します。

    assert @bucket[0] == [["Carbon", 6], ["Nitrogen", 7], ["Neon", 10], ["Chlorine", 17]]
    assert @bucket[1] == [["Beryllium", 4]]
    assert @bucket[2] == [["Helium", 2], ["Phosphorus", 15], ["Sulfur", 16]]
    assert @bucket[3] == [["Lithium", 3], ["Boron", 5], ["Fluorine", 9], ["Argon", 18]]
    assert @bucket[4] == [["Hydrogen", 1]]
    assert @bucket[5] == [["Sodium", 11], ["Magnesium", 12], ["Silicon", 14]]
    assert @bucket[6] == [["Aluminum", 13]]
    assert @bucket[7] == [["Oxygen", 8], ["Potassium", 19]]
    assert @level == 3 && @step_ptr == 0

バケットの分割をおこなうタイミングは、 あふれ分を勘定にいれない収録可能なレコード数に対する、 収録されている全レコード数の割合がしきい値を越えたところとするのが良く使われているやりかたのようです。 ここでは、 75% をしきい値に選ぶことにします。 バケットの収録可能レコード数が少ないときは、 このしきい値だと激しくあふれることがあるのですが、 多くなると、 おとなしくなっていく傾向があります。

# Linear Hashing by W. Litwin (1980)
class LinearHashing
  BUCKET_SIZE = 4
  UTILIZATION = BUCKET_SIZE * 256 * 75 / 100

  attr_reader :size, :level, :step_ptr, :bucket

  def initialize
    @level = 2      # ハッシュ値の利用ビット数
    @step_ptr = 0   # 次に分割するバケット番号
    @size = 0       # レコード数
    @bucket = Array.new(1 << @level) { Array.new }
  end

#@<キーからバケット番号を求めます@>
#@<キーがハッシュ表に含まれているかどうか調べます@>

  def store(key, value)
    x = bucket_address(key)
    r = @bucket[x].assoc(key)
    if not r.nil?
      r[1] = value
    else
      @bucket[x].push [key, value]
      @size += 1
      n = (1 << @level) + @step_ptr
      if (@size << 8) > n * UTILIZATION
        split_bucket    # 全収容可能レコード数の 75% を越えたら分割をします
      end
    end
  end

#@<step_ptr のバケットを分割します@>

end

バケットの分割は、 分割対象のバケット中に登録済みのレコードのハッシュ値から level + 1 ビット分を取り出して、 それの最上位がゼロなら元の場所のバケットへ、 1 なら新しいバケットへ push していきます。

#@<step_ptr のバケットを分割します@>=
  def split_bucket
    bucket_lower = []  # 元の場所のバケット用
    bucket_upper = []  # 新しく追加するバケット用
    hash_mask = (1 << (@level + 1)) - 1
    n = 1 << @level
    @bucket[@step_ptr].each do |r|
      x = r[0].hash & hash_mask
      if x < n
        bucket_lower.push r    # 最上位ビットがゼロ
      else
        bucket_upper.push r    # 最上位ビットが 1
      end
    end
    @bucket[@step_ptr] = bucket_lower
    @bucket.push bucket_upper

    @step_ptr += 1
    if @step_ptr >= n
      @step_ptr = 0
      @level += 1
    end
  end