ハッシュテーブルってやつ

教科書とかでみるハッシュテーブルの実装はcollisionやrehashを考慮してないケースばかりなので、参考用に書いた。 といってもこのコードもpointer使ってないし削除やら同じキーがセットされた場合を考慮してないので、実用に使えるものではないので注意。

import std.container;


class Hashtable {

private:

  struct HashValue {
    byte[] key;
    byte[] value;
  }

  uint size;
  uint counter;
  DList!(HashValue)[] buckets;

  this(uint _size) {
    size = _size;
    buckets.length = _size;
    for (int i; i < size; ++i)
      buckets[i] = make!(DList!(HashValue));
  }

  @property
  uint getSize() {
    return size;
  }

  void set(byte[] key, byte[] value) {
    buckets[getIndex(key)].insertBack(HashValue(key, value));
    counter++;

    // ckeck rehash
    if (counter / buckets.length > 5)
      rehash();
  }

  byte[] get(byte[] key) {
    auto l = buckets[getIndex(key)];

    foreach(hvalue; l)
      if (hvalue.key == key)
        return hvalue.value;

    assert(0);
  }

private:

  // ported from Tokyo Cabinet
  uint getIndex(byte[] key) {
    uint hash = 19780211;
    foreach(octet; key)
      hash = hash * 37 + octet;
    return hash % size;
  }

  void rehash() {
    size *= 2;  // resize bucket size * 2
    DList!(HashValue)[] newBuckets;
    newBuckets.length = size;
    for (int i; i < size; ++i)
      newBuckets[i] = make!(DList!(HashValue));

    foreach(bucket; buckets) {
      foreach(hvalue; bucket) {
        uint newIndex = getIndex(hvalue.key);
        newBuckets[newIndex].insertBack(hvalue);
      }
    }
    buckets = newBuckets;
  }

}


unittest {
  import std.stdio;
  auto ht = new Hashtable(100);

  byte[] k = ['a', 'b', 'c'];
  byte[] v = ['1', '2', '3'];

  ht.set(k, v);
  auto tmp = ht.get(k);
  writeln(tmp);
  assert(tmp == v);
}


version(unittest) void main() {}

ここでrehashはsize*=2として2倍のbucketsを用意して、新たにハッシュ値を計算しなおしてから詰め直している。(sizeの値そのものを変更してるのでgetIndexの計算も変わることに注意)

これはわりかしnaiveながら一般的なやつだと思っているのだが、Redisなんかは遅延rehashというなかなかおもしろい仕組みを持っている。(興味がある人はsrc/dict.cあたりを読むとよい)

ハッシュテーブルは基本的なデータ構造ながらなかなかおもしろいので今後いろいろ遊んでみたい。

追記: このコードはD言語で書きました。まだまだ勉強中ですが、CやJavaよりも書きやすくRubyより実効速度がだいぶはやいので最近は重宝してます。