memcachedの実装を読んでみる

週末をあまりに無為に過してしまうのはあれなので、memcachedの実装を読んでみる。
連想配列の実装というものを一度、実際のコードで追いかけてみたかったというのもある。そういう意味ではmemcachedは連想配列そのものなので、実装例としては適任かなと。
連想配列といえば、キーをハッシュ関数にかけて戻り値をインデックスとした(ポインタのポインタ)配列の先に繋いでいるのだろうとはなんとなく想像していたが、ほぼ想像通りの実装だった。連想配列の実装として一般的なのかはわからないが、インデックスとして使うサイズが20bit決め打ちだったり、ハッシュ値の偏りを是正するような仕掛は入っていなかった。意外と単純なんだな。
ちなみに、使っているハッシュ関数は、http://burtleburtle.net/bob/hash/evahash.htmlで解説されているものを使用している。動作原理の数学的裏付けとかまでは追いかけていないが、3つの変数でビットをコネコネしているようだ。なんだかこれでそれなりに混ざりそうな感じ。ちなみにハッシュ値は32bit、ただし前述の通り下位20bitしか使っていない。
あと、以前ruby bindingを使ったときには気付かなかったが、エントリの有効期限を設定できるのか。これだとワーストケースが制限出来るので、使い易くなるかも。