ハッシュテーブルってやつ
教科書とかでみるハッシュテーブルの実装は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より実効速度がだいぶはやいので最近は重宝してます。