二次探索法とは
二次探索法（Quadratic Probing）とは、ハッシュテーブルにおいて、キーのハッシュ値が既に他のキーによって占有されている場合（衝突が発生した場合）に、次の探査位置を決定するために、探査回数の二次関数を用いてインデックスを算出する衝突回避策の一つです。
線形探索法におけるクラスタリング（衝突が連鎖的に発生する現象）を緩和する効果が期待されます。
二次探索法 の基本概念
ハッシュテーブルでは、キーをハッシュ関数に通して得られたハッシュ値をインデックスとして、データを格納します。衝突が発生した場合、何らかの方法で空いているスロットを探す必要があります。
二次探索法では、最初のハッシュ値 h(key) が衝突した場合、次の探査位置は (h(key)+c1i+c2i2)modsize という形式で計算されます。ここで、i は衝突が発生した回数（探査の試行回数）、c1 と c2 は定数（通常 c1=0,c2=1 または c1=c2=1/2 などが用いられます）、size はハッシュテーブルのサイズです。
最も単純な形式では、次の探査位置は h(key)+12,h(key)+22,h(key)+32,… のように、探査回数の二乗を加算した位置を順に調べます。
二次探索法 の仕組み
- 最初のハッシュ値の計算: キー k に対して、ハッシュ関数 h(k) を用いて初期のハッシュ値 v=h(k)modsize を計算します。
- 衝突の検出: インデックス v のスロットが既に占有されている場合、衝突が発生します。
- 二次関数的な探査: 衝突が発生した場合、次の探査位置を以下の式で計算します。 probe(i)=(v+c1i+c2i2)modsize ここで、i=1,2,3,… は衝突が発生した回数（または探査の試行回数）であり、c1 と c2 はあらかじめ定められた定数です。一般的には、c1=0 かつ c2=1 とすることが多く、この場合、探査シーケンスは h(k),(h(k)+12)modsize,(h(k)+22)modsize,(h(k)+32)modsize,… となります。
- 空きスロットの発見: 生成されたインデックスのスロットが空いている場合、その位置にデータを格納します。探索時にも同様のシーケンスを辿り、キーと一致するデータが見つかれば探索成功、空のスロットに到達すればキーが存在しないと判断します。
二次探索法 の利点
- 一次クラスタリングの緩和: 線形探索法では、衝突が発生したスロットの近傍に連続してデータが格納される一次クラスタリングが発生しやすいですが、二次探索法では探査ステップ幅が二次関数的に増加するため、この現象を緩和する効果があります。
- 線形探索よりも広範囲の探査: 線形探索が隣接するスロットを順に探査するのに対し、二次探索はより広い範囲のスロットを飛び飛びに探査するため、衝突が解消されやすくなります。
二次探索法 の欠点
- 二次クラスタリングの可能性: 異なるキーが最初のハッシュ値で衝突した場合、その後の探査シーケンスが同じになるため、二次クラスタリングと呼ばれる、同じハッシュ値を持つキーが同じ探査パスを辿る現象が発生する可能性があります。これは、線形探索ほど深刻ではありませんが、性能劣化の原因となり得ます。
- テーブルサイズの制約: ハッシュテーブルのサイズが素数であり、かつ負荷率（格納されている要素数 / テーブルサイズ）が 0.5 以下であれば、新しい要素を必ず挿入できることが保証されています。しかし、負荷率が高くなると、探査がテーブル全体を網羅できなくなる可能性があります。
- 削除処理の複雑性: 線形探索と同様に、削除されたスロットを単純に空きとマークすると、その後の探索が途中で終了してしまう可能性があるため、特別なマーキングや再ハッシュなどの処理が必要になる場合があります。
二次探索法 の応用
二次探索法は、線形探索法よりも衝突による性能劣化を抑えたい場合に、ハッシュテーブルの衝突解決戦略の一つとして利用されます。しかし、より均等な分布と高い性能を求める場合には、ダブルハッシュ法などの他の手法が選択されることもあります。
二次探索法は、ハッシュテーブルにおける衝突問題を、探査回数の二乗を用いて次の探査位置を決定することで解決する手法です。線形探索法と比較して一次クラスタリングを緩和する利点がありますが、二次クラスタリングの可能性やテーブルサイズの制約といった欠点も存在します。ハッシュテーブルの設計においては、これらの特性を考慮し、適切な衝突解決戦略を選択することが重要です。
関連用語
お問い合わせ
システム開発・アプリ開発に関するご相談がございましたら、APPSWINGBYまでお気軽にご連絡ください。
APPSWINGBYの
ソリューション
APPSWINGBYのセキュリティサービスについて、詳しくは以下のメニューからお進みください。
システム開発
既存事業のDXによる新規開発、既存業務システムの引継ぎ・機能追加、表計算ソフトによる管理からの卒業等々、様々なWebシステムの開発を行っています。
iOS/Androidアプリ開発
既存事業のDXによるアプリの新規開発から既存アプリの改修・機能追加まで様々なアプリ開発における様々な課題・問題を解決しています。
リファクタリング
他のベンダーが開発したウェブサービスやアプリの不具合改修やソースコードの最適化、また、クラウド移行によってランニングコストが大幅にあがってしまったシステムのリアーキテクチャなどの行っています。
ご相談・お問い合わせはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、
お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、
より良い社会創りに貢献していきます。
T関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答致します。
ご相談・お問合せはこちら
APPSWINGBYのミッションは、アプリでビジネスを加速し、お客様とともにビジネスの成功と未来を形作ること。
私達は、ITテクノロジーを活用し、様々なサービスを提供することで、より良い社会創りに貢献していきます。
IT関する疑問等、小さなことでも遠慮なくお問合せください。３営業日以内にご返答させて頂きます。
