次に、アルゴリズムZによって得られたハッシュインデックスを使ってキーワード列をメモリーに格納する様子を図に示します。
メモリーの「ハッシュ表エリア」には、ハッシュインデックスの種類数、つまり「ハッシュの箱」と同じ数(英語のアルファベットならば26個)の領域が用意してあって、先ほど例に出した対応表と同じ番号が振られています。
それぞれの領域にはメモリーの番地(アドレス)が書かれていて、その番地は「ハッシュレコード」と呼ばれる別の場所を指しています。それぞれのハッシュレコードには、「キーワードが保存されている番地」「キーワード番号」「次のハッシュレコードの番地」が保存されています。
「次のハッシュレコードの番地」は1つの「ハッシュの箱」に2つ以上のキーワードを格納するために必要です。2つめ以降のキーワードに対応するハッシュレコードは、「ハッシュ表エリア」からぶら下がっていく形で保存されていきます。それぞれの「箱」の末尾にあたるハッシュレコードでは、「次のハッシュレコードの番地」に特別な数値が入っていて、これ以上先には進まなくてよいことが分かるようになっています。
それでは、上の図のハッシュ表を使って「ascii」のキーワード番号を求めてみましょう。「ascii」のアルゴリズムZによるハッシュインデックスは、先の図で示した通り「u」です。図左の対応表で「u」は20番であることが分かるので、ハッシュ表エリアの20番を参照し、最初のキーワードにあたる2001番地のハッシュレコードを参照します。3001番地のハッシュレコードに入っているキーワード「abandon」と探している「ascii」は異なっているので、このハッシュレコードはパスして、「次のハッシュレコードの番地」つまり2007番地のハッシュレコードを次に参照します。
こうして2013番地にたどり着くと、3013番地のハッシュレコードに入っているキーワード「ascii」は、探しているキーワードと一致します。「ascii」のキーワード番号は203であることが分かりました。おめでとうございます! ずっと短い処理で、キーワードから番号を取り出せました! ちなみに、もしハッシュ表エリア、または「次のハッシュレコード番地」に特別な数値が入っていれば、探しているキーワードは存在しないことが分かります。
ハッシュ表の仕組みをここまで読み進めてきていかがでしたか? 摩訶不思議な仕組みですが、人間には難しい「偏ったデータを均等に区分けして素早く探す」という仕事を、パソコンは易々とこなしてしまうのです。名刺を区分けしたり探したりするのにいちいち名前からハッシュインデックスを計算するなんてこと、人間にはちょっと真似できないですよね。「なぜ偏ったデータを均等に区分けできるのか」をきちんと理解するのは難しいのですが、ここでは「賢いアルゴリズムの凄さ」をまずは感じとってみてください。