ハッシュ表の仕組みと衝突対策

2026年9月15日

前回、①に戻り、IPアドレス・サブネットマスクの計算方法を整理しました。今回は、②に戻り、データ構造の総まとめとして、「ハッシュ表」の仕組みを整理します。

ハッシュ表とは

ハッシュ表とは、データを特定の計算式(ハッシュ関数)にかけて、格納する場所を直接決めてしまうことで、非常に高速にデータを探し出せるようにしたデータ構造です。

これまで整理してきた線形探索や二分探索、二分探索木は、どれも「比較を繰り返しながら絞り込む」という考え方でした。ハッシュ表は発想が異なり、「比較せずに、計算だけで格納場所を決めてしまう」という点が大きな特徴です。

ハッシュ関数とは、データ(値)を受け取って、格納する場所を表す番号(ハッシュ値)を計算する関数のことです。

例えば、値を格納する場所が10個用意されているとき、「値を10で割った余り」をハッシュ値とする、といった単純な計算式が使われることがあります。値そのものではなく、この計算結果をもとに、格納場所が決まります。

ハッシュ関数を使うと、異なる値であっても、同じハッシュ値(同じ格納場所)が計算されてしまうことがあります。この状態を「衝突」と呼びます。

例えば、先ほどの「10で割った余り」という計算式の場合、13という値も23という値も、どちらも余りは３になるため、同じ格納場所を指してしまいます。データの種類が増えるほど、この衝突が起きる可能性は高くなります。

衝突が起きたときの対策として、代表的なものに次の２つがあります。

以前整理した連結リストの知識が、チェイン法の理解にそのまま生きてくる形になっており、ここまで学んできた単元どうしがつながっていく感覚がありました。

ハッシュ表のトレース問題では、まずハッシュ関数の計算式を正確に確認し、それぞれの値がどの場所に格納されるかを、１つずつ書き出すようにしています。そのうえで、衝突が起きた箇所については、問題文で指定されている対策方法(チェイン法かオープンアドレス法か)に沿って、格納場所を追い直す必要があります。

ハッシュ表は、「比較せずに計算だけで場所を決める」という発想が、これまでの探索アルゴリズムとは違っていて、最初は少し戸惑いました。ただ、衝突対策のチェイン法が、以前学んだ連結リストの応用だと気づいたことで、これまで学んできた単元が、少しずつつながってきているという実感が持てました。

次回は、③に戻り、学習の中間報告をまとめます。

よかったらシェアしてね！