アルゴリズムZを工夫する
アルゴリズムZにはまだまだ工夫の余地があります。
「1つの箱に入っているデータの数が多すぎるので、箱の数を増やしたい」
たとえば英単語70000語をハッシュ表に格納してしまうと、1箱あたり平均2700個程度のキーワードが入ってしまいます。これでは検索時間がかかりすぎてしまうので、箱の数（つまりハッシュインデックスの数）を増やしてみましょう。下の図のように、アルゴリズムZを1歩手前で止めて、ハッシュインデックスを2文字で得るようにします。
たとえば、「ascii」のハッシュインデックスは「wc」で、対応するハッシュエリア番号は「26×22＋2＝574」となります。この方法だと、箱の数は26×26＝676個、1箱あたりのキーワード数は100個程度になり、ずいぶん高速化されます。さらにハッシュインデックスを3文字、4文字と増やしていけばさらに高速化できますが、その代わり多くのメモリーを使ってしまいます。
アルゴリズムの多くがあてはまる原則として、計算時間とメモリーの使用量はあちらを立てればこちらが立たずの関係にある、というのがあります。計算時間を減らそうとするとメモリーの使用量が増えてしまうし、逆にメモリーの使用量を減らそうとすると計算時間が増えてしまうという関係です。パソコンを新しく買うときは、この原則をちょっと思い出してみてください。メモリーの量をケチってしまうと、長い処理時間を我慢するはめになることもありますから……。もちろんこの原則があてはまらない例外もあることをお忘れなく。
「長いキーワードだと、ハッシュインデックスを計算するのにけっこう時間がかかってしまいそうだけど」
実は、ハッシュインデックスの計算にかかる時間についてアルゴリズムZはあまり優れていません。下の図のグラフの黒線に、キーワードの文字列長とアルゴリズムZで引き算が行なわれる回数の関係を示しています。
キーワードが長くなればなるほど、引き算の回数は加速度的に増えてしまうことが分かります（高校数学の言葉を借りれば、引き算の回数は文字列長Lの2乗、つまりL2に比例します）。そこで、アルゴリズムZに改良を加えて、アルゴリズムZ'を作ってみました。
アルゴリズムZは「長さNの文字列から長さN-1の文字列を作り出す操作を繰り返す」のに対し、アルゴリズムZ'は「長さNの文字列から長さN/2(端数切り上げ)の文字列を作り出す操作を繰り返す」という違いがあります。図のグラフの色線に、キーワードの文字列長とアルゴリズムZ'で引き算が行われる回数の関係を示しています。アルゴリズムZと比べると、ずいぶん増え方が緩やかですよね（高校数学の言葉を借りれば、引き算の回数はL×log(L)に比例します）。
このように、アルゴリズムを考える上で、「データの大きさと計算時間の関係を考える」ことはとても重要です。全く同じ処理をするにも、上手いアルゴリズムと下手なアルゴリズムでは処理時間に雲泥の差が出ます。Googleを作っている優秀なエンジニアたちは、いかに上手いアルゴリズムを使うかで日々頭をひねっているのです。
「意地悪をすれば、ハッシュインデックスの分布が偏ってしまうようなキーワード集合も作れるんじゃない？」
意図的に、ハッシュインデックスが「a」になるキーワードだけを集めてハッシュ表を作れば、（何のためにそんなことをするのかはさておき）せっかくのハッシュ表が何の役にも立ちません。第1回で説明した線形探索よりも、仕組みが複雑な分よけいに時間が掛かってしまいます。ただし、「文書の転置インデックスを作る」という現実の目的を満たす上では、そのような意図が入る余地はほぼないので、無視してもよい問題です。
どんな種類のデータに対しても「偏りがない」ハッシュインデックスの計算アルゴリズムは、厳密には「意図的に特定のハッシュインデックスが出てくるようなデータを作るのがとても難しい」という性質を満たさなければなりません。この性質を満たすアルゴリズムを理解するには高度な数学の知識が必要になります（きちんと説明しようとすれば1冊の本が書けてしまうほどです）。
また、この性質を満たすアルゴリズムは、データが改ざんされていないかどうかを検証する手段としても使えます。現在、そのような性質をもつと考えられている関数（一方向性関数）がいくつか知られていて、広く使われています（SHA-1などが有名です）。
ハッシュ表の仕組みは、GoogleなどのWeb検索エンジンはもちろんのこと、大企業や官庁の大規模データベースシステム、電子辞書ソフトなどいろいろな場所で大活躍しています。また、ハッシュインデックスを求めるアルゴリズムは、暗号アルゴリズムと組みあわせて、電子証明やデータの改ざん防止にも活用されています。まさに縁の下の力持ちである「ハッシュ表」の存在を、頭の片隅に入れておきましょう。
