データ構造におけるオープンアドレス法によるハッシュの仕組みを解説
オープンアドレス法とは
オープンアドレス法(開番地法)は、ハッシュテーブルにおける衝突(コリジョン)を解決するためのもう一つの代表的な手法です。チェイン法(連鎖法)とは異なり、要素を別のデータ構造に格納するのではなく、ハッシュテーブル自体に直接データを挿入する点が大きな特徴です。そのため、すべてのキーを格納できるよう、ハッシュテーブルのサイズはキーの総数よりも大きく設定する必要があります。
オープンアドレス法の3つの主要な手法
オープンアドレス法には、広く知られている手法として以下の3つがあります。
- 線形探査法(Linear Probing)
- 二次探査法(Quadratic Probing)
- ダブルハッシング(Double Hashing)
基本的な動作の流れ
他のハッシュ手法と同様に、まずハッシュ関数を使ってデータの格納位置を計算します。計算された位置が空いていれば、そのまま要素を挿入します。しかし、すでに別のデータが占めている場合(衝突が発生した場合)は、特定の数式に従って次の空きスロットを探索します。
線形探査法では線形の式を用いて空き場所を順番に探し、二次探査法では二次関数を用いて間隔を広げながら探索を行います。これにより、データが特定の場所に偏る「クラスタリング」の問題をある程度緩和できます。
ダブルハッシングの特徴
ダブルハッシングでは、衝突が発生した際に別のハッシュ関数を使用して新しい格納位置を求めます。このとき使われる関数は「副ハッシュ関数(セカンダリハッシュ関数)」と呼ばれます。なお、副ハッシュ関数は衝突が発生しない限り使用されません。この手法により、規則的なパターンによる衝突の集中を効果的に回避できます。
-
データ構造の基礎：チェイン法（連鎖法）によるハッシュの仕組み
チェイン法（連鎖法）によるハッシュとはこのセクションでは、チェイン法（Chaining、連鎖法）と呼ばれるハッシュ手法について解説します。チェイン法は、ハッシュテーブルにおける衝突（コリジョン）を解決するための代表的な手法の一つです。ハッシュテーブルでは、異なるキーが同じハッシュ値にマッピングされる「衝突」を完全に避けることはできません。しかし、衝突の発生をできるだけ抑えたり、同じハッシュ値を持つ複数の要素を適切に格納したりすることは可能です。チェイン法はまさにこの課題に対処するためのアプローチです。基本的な仕組みここでは、0から6までの値を返すハッシュ関数 h(x) を想定してみましょう。こ
-
ハーフエッジデータ構造（HalfedgeDS）とは？基本概念とCGAL実装例をわかりやすく解説
はじめにテンプレートパラメータとして用いられるハーフエッジデータ構造（Halfedge Data Structure、略称 HalfedgeDS）は、頂点・辺・面の接続情報（インシデンス情報）を管理できる、辺を中心としたデータ構造として定義されています。平面地図（planar map）や多面体など、任意の次元空間に埋め込まれた向き付け可能な2次元曲面の表現に適した構造です。このデータ構造では、各辺が逆向きの向きを持つ2つのハーフエッジ（半辺）に分割されます。各ハーフエッジは、隣接する1つの面と1つの頂点への参照を保持し、逆に各面および各頂点にも、それぞれ1つの接続ハーフエッジが格納されます。さ