実例！キャッシュの仕組み

ハッシング＋リンクトリスト

　「第3回：ソースでわかる！ハッシング」でハッシングとリンクトリストを組み合わせたものを紹介しました。今回はそのプログラムを紹介しますが、実はその本体はこれまでに紹介したものばかりです。1本のリンクトリストを扱うプログラムは第1回に紹介しました。これをハッシュ値が同じもの同士をひとつのリストにするようにして、複数のリストを作って管理するのがこの方法です。

　第3回の最後にハッシングとリンクトリストを使ったプログラムのinsert()関数を紹介しましたが、ハッシング機能のモジュールの全体を図1-1に示します。ハッシュ関数h()のほかに、このハッシュテーブル＋リンクトリストの構造を使った登録insert()、検索search()および削除delete()の機能を加えています。

　テストプログラムを含めたプログラム全体はこちら（http://www.thinkit.co.jp/images/article/159/4/15941.zip）からダウンロードできます（15941.zip/2 KB）。

　hash.phpについて少し説明します。はじめにllist.phpをインクルードしています。これはリンクトリスト機能を使うためです。ただ、insert()などの関数名がダブらないように、list_insert()のように名前を変えたことについては、上で述べた通りです。

　次に define() があります。

define( "ARRAY_SIZE", 13 );

　第3回のハッシュ関数ではハッシュ値を求めるために最後に35で割って、その余りを求めました。35は対象としたデータの総数です。実際には衝突が起こります。また、その衝突をリンクトリストで「吸収する」わけですから、この数はもっと少なくても構いません。ここでは13にしました。この数値については後でまた説明します。この値は何カ所かで使うのでdefine()を使って定義しています。

　次の関数insert()の中身は次のようになっています。

$hashval = h( $key );
list_insert( $array_of_anchor[$hashval], $key, $value );

　list_insert()はアンカーの位置（アンカーの配列のインデックス）を決めるためにハッシュ関数を呼び出しますが、あとはリスト操作関数を使うだけです。ほかの関数についての説明は不要でしょう。

　テストプログラムを図1-2に示します。対象のデータをinsert()で登録して、その結果を表示するだけです。これを実行した結果が図1-3です。ハッシュ値ごとにリストがどのように作られているかがわかるでしょう。

　図1-3を見ると、35 個の要素がほどよく分散していることがわかると思います。いかがでしょう。衝突が起こっていますが一番長いリストでも要素数は6になりました。

ハッシュ関数再考

　先の例ではハッシュ関数の最後の割り算のために13を使いました。中途半端な数値に思えると思いますが、この数値にはわけがあります。この値を使ったのはこの数が素数だからです。興味ある読者は、この値を変えて実験して見てください。分散の様子が変わることがわかると思います。例えば14を使うと、ハッシングのグループが増えるのでより分散するように思えますが、実際には偏りは大きくなることがわかります（図1-4）。

　素数で割った余りが分散することはよく知られています。ちなみに、素数のいくつかを紹介します。これらの値で試してみてください。

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73,
79, 83, 89, 97

　もちろん、結果がほどよく分散するかどうかは対象データの値（文字列）に依存しますので、素数で割り算した値をハッシュ値に使うのが最善であると言うことはできませんが、簡単で性能のよいハッシュ関数を設計するヒントにはなるでしょう。