現代のプログラミング言語では、ハッシュテーブルはライブラリーに完備されているためだ。
C言語でも、オープンソースを探せば、良いライブラリーが見つかる。
C言語をよく使う自分は、趣味でハッシュテーブルを自作して来た。
最近またハッシュテーブルを自作して、本質を深く理解できたので、メモしておく。
C言語を学び、ハッシュテーブル、リストなどのデータ格納アルゴリズムを一度は実装して確認することで、コンピューターで大量のデータを取り扱う基本を学ぶことができる。
ハッシュテーブルは、データをキーと値の組で保管するものだ。
キーは、数字ではなく、名前のような文字列や、複数の数値の組み合わせである。
値も複雑なデータの組み合わせとなる。
キーはデータを一意に区別できるものである。
複雑なキー情報に一致する値を素早く探し出すために、ハッシュという方法を用いる。
登録されるデータの最大の個数 M をあらかじめ想定しておき、
複雑なキー情報から単純で高速な方法で、0から(M-1)までの数値 Si をハッシュ計算し、
それを、ハッシュテーブルのインデックス番号として利用するのだ。
ハッシュ計算は、データを一意に区別することができる複雑なキーのすべての情報を用いて、
これを log2(M)ビット長に圧縮するためにある。
ハッシュ値は、0から(M-1)までに一様に散らばるように工夫する。
コンピューターの整数計算は、Mをはるかに超える桁数(32bitや64bitで)で行うため、
いったん大きな整数に圧縮してから、 M で割り算した余りを求めて、
0から(M-1)までに収めるのだ。
キーである長い文字列をいったん一つの整数に圧縮する方法で最も楽な方法は、全文字を数値として扱いそれらを合計することである。キーが複数の整数を含む配列でも同様である。
合計法の結果をMで割り算して余りを求めることなるが、Mが2のべき乗(2, 4, 8, 16, 32, ...)の場合は好ましくない。その理由は、コンピューター内部で文字も整数も2進数で表現されているため、合計法の結果の2進数の下位桁は、もともとのキーのそれぞれの2進数の下位桁でのみを合計された物であり、上位桁の情報を一切含まないからである。
従って合計法を用いてハッシュ計算をする場合、Mは、約数に2を含まないほうがよいのだ。ならば、いっそのことMは素数(prime number)がより好ましいとなる。
合計法は簡単で高速であるが、文字列"ABC"と文字列"CBA"が同じ結果になるという欠点を持つ。合計法は、文字の出現順序を圧縮情報に取り込んでいないことが原因だ。文字の出現順序をとりこむためには、合計値を加算する前に、古い合計値のビット列を1ビットだけ回転させるとよいだろう。C言語的には、以下である。
#define BIT_LEN (sizeof(unsigned int) * 8)
unsigned int hash_sum = 0;
for(i = 0; keyText[i] != 0; ++i){
hash_sum = ((hash_sum << 1) | (hash_sum >>(BIT_LEN - 1))) + (unsigned int)keyText[i];
}
slotIndex = hash_sum % primeM;
この hash_sum 値は、キーの付加情報として保存しておいたほうが、テーブルを拡張するときにこれを再計算することが不要になる。
(C言語で高度に汎用化したハッシュテーブルライブラリーを用意するとき、キーの比較関数だけでなく、hash_sumの計算関数をもポインタで渡すようなライブラリーを設計することになる。さらに、キーと値の複写関数や消去解放関数も用意することになるだろう。)
ハッシュテーブルのハッシュ計算はどのような実装をしても、結果値の衝突が必ず発生しうる。
衝突が起きた時に、どうやって格納するかを考えておかなければならない。
M個までしか登録しないという前提があれば、slotIndexを加算して次のスロットに格納するという方法がある。次のスロットが使用中ならさらに加算してそのまた次に格納する、未使用スロットが見つからずどんどん加算してslotIndexがMになったら、0に戻して探すのである。何とか法というらしいが、あまり良い方法とは言えない。理由は、M個までしか登録できないこと。ハッシュ値を計算してslotIndexを求めてもそこにデータがいない可能性があるからである。つまり、衝突の恐れがあるのでデータ読み出しに最大でM回の比較時間がかかるのだ。
M個以上のデータを登録できるようにしたいし、さらに、ハッシュ値を計算してslotIndexを求めたらそこにデータがいることを保証もしたい。そこで、slotIndexの位置に、一方向リストを格納する。リストの要素で、キーと値の組(さらにhash_sum 値も)格納しておくのだ。
実装を間違えないようにしたいことは、一方向リストにデータを追加するときは、リストの最後ではなくリストの先頭につなぐことが、処理時間を少なくできる方法である。
誕生日のパラドックスとは、学校の30人クラスには、誕生日が同じ人がけっこうな確率でいるという事実である。以下の計算を見てほしい。
n人のクラスで誕生日がすべて異なる確率 probability p1 は、
p1(n) = 365! / ( (365 ^ n) * (365 - n)! )
n人のクラスで誕生日が同じ人が2人以上いる確率 p2 は
p2(n) = 1 - p1(n)
n = 23人のとき、確率 p2(23) = 0.507 となる。
もし、 n 人の会社にあなたが入社したら、あなたと同じ誕生日の人がいる確率 p3 は、
p3(n) = 1 - ((365 - 1)/365) ^ n
である。n = 23 ならば、 p3(23) = 0.0611 , p3(253) = 0.5... である。
ハッシュテーブルのサイズをM(素数)とし、すでに n 個のデータが登録されているときに、データを追加登録するとして、すでに同じキーのデータがある確率 p4 は、
p4(M, n) = 1 - ((M - 1)/M) ^ n
この式をnについて解くため、これから、式を変形する。
P = 1 - ((M - 1)/M) ^ n
((M - 1)/M) ^ n = P - 1
n * log((M - 1)/M) = log(P - 1)
n = log(P - 1) / log((M - 1)/M)
P = 0.5として、2のべき乗より少しだけ小さい素数Mについてnを計算してみると
| index | べき乗 | 素数M | n | (n/素数M) |
| 1 | 2 | 2 | 1.00 | 0.50 |
| 2 | 4 | 3 | 1.71 | 0.57 |
| 3 | 8 | 7 | 4.50 | 0.64 |
| 4 | 16 | 13 | 8.66 | 0.67 |
| 5 | 32 | 31 | 21.14 | 0.68 |
| 6 | 64 | 61 | 41.93 | 0.69 |
| 7 | 128 | 127 | 87.68 | 0.69 |
| 8 | 256 | 251 | 173.63 | 0.69 |
| 9 | 512 | 509 | 352.47 | 0.69 |
| 10 | 1,024 | 1,021 | 707.36 | 0.69 |
| 11 | 2,048 | 2,039 | 1,412.98 | 0.69 |
| 12 | 4,096 | 4,093 | 2,836.70 | 0.69 |
| 13 | 8,192 | 8,191 | 5,677.22 | 0.69 |
| 14 | 16,384 | 16,381 | 11,354.10 | 0.69 |
| 15 | 32,768 | 32,749 | 22,699.53 | 0.69 |
| 16 | 65,536 | 65,521 | 45,415.35 | 0.69 |
ハッシュテーブルのサイズをM(素数)とすると、おおよそ70%の使用度になったら、平均的な衝突確率が50%を超えると言えるだろう。
(2のべき乗より少しだけ小さい素数Mとした理由は、ハッシュテーブル領域を動的に確保するとき、確保したいサイズが1024バイト(2^10)の整数倍を超えない範囲でできるだけ大きいほうが、のメモリ利用効率が良いから。2のべき乗より少しだけ大きい素数とすれば、動的に確保したときメモリーで未使用の断片が生まれやすいと言える。)
したがって、ハッシュテーブルのサイズをM(素数)として、テーブルへの登録キーの数が70%を超えたら、テーブルサイズを次の2倍のサイズに拡大する(Mをもっと大きな素数にする)ことが好ましい。
テーブルサイズを拡大するときに、キー、値の組とともに保存しておいた hash_sum 値 を新しい大きなMで割った余りを求めて、新しいスロット番号とすることになる。
高校程度の数学(素数、2進数、確率、べき乗、階乗、対数)、プログラミング言語Cなどの知識が、こういうところで役立っていると言える。
No comments:
Post a Comment