hashの実装について

アルゴリズム

Beautiful Codeという本にhashの実装についての章があったので、少し調べてみた。

参考にしたソース、資料

本ではPythonのhash実装を説明していたが、そこでポイントされていたのが下記の資料。

  • 資料

http://svn.python.org/view/python/trunk/Objects/dictnotes.txt?view=markup

  • ソース

http://svn.python.org/view/python/trunk/Objects/dictobject.c?view=markup

小技

hashのindexを取得する時、配列のサイズで剰余演算を行うが、配列のサイズを2の階乗にしておくと、ビット演算で高速に剰余を取得できる。
上記のdictobject.cの lookdict_string メソッド内で、

i = hash & mask

のような感じの箇所。maskはあらかじめ 配列のサイズ - 1 に設定されている。

open addressでのアドレス取得

ソースの先頭付近のコメントで解説されている。
上と同じlookdict_string メソッド内で、変動値を入れながら、

nextIndex = (currentIndex * 定数値 + ループごとの変動値 + 1) mod entrySize

のようなロジックで次のインデックスを取得している。
ループごとの変動値の初期化にもhash値を使っている所も工夫されている。
コメント部分にも書いてあるが、

 j = ((5*j) + 1) mod 2**i

を繰り返すと、jが重複せずindexを一巡する。