PR

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

2008年11月28日(金)
須藤 克彦

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

 「第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

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

  • 1
神戸情報大学院大学
1980年立命館大学理工学部卒、独立系ソフトハウスに入社。CやFORTRANコンパイラなどの言語処理系の設計・開発に約10年間従事。その後ユーザ系企業でUNIXによるクライアントサーバシステムの設計・開発を主導。同時に企業の内外で人材育成に注力する。現在は神戸情報大学院大学で講師として教鞭(きょうべん)をとる。「ソフトウエア工学の基礎を勉強してオールラウンドプレーヤーを目指せ」が技術者育成についての口癖。http://www.kic.ac.jp/professors/sudo/index.html

Think IT会員サービス無料登録受付中

Think ITでは、より付加価値の高いコンテンツを会員サービスとして提供しています。会員登録を済ませてThink ITのWebサイトにログインすることでさまざまな限定特典を入手できるようになります。

Think IT会員サービスの概要とメリットをチェック

他にもこの記事が読まれています