uyota 匠の一手

ハシュテーブルは、一般的に使われるデータ構造だ。ハッシュ関数と言われる算術を用い、特定の要素に高速にアクセスする為に用いる。大きさにも制限があるので、この算術式によっては、異なった値も同じ場所に割り当てられる事がある。この衝突を回避する方法に、リストなどを使う連鎖法 (chaining) と開番地法（open addressing）がある。

よくあちこちの説明では、この二つが上げられ各々の利点などが比較されている事が多い。そしてその一つに、開番地法の方が実装が簡単と出ている事が多い。しかし、開番地法の重大な欠点に触れているものは見たことがない。

開番地法では、実質的に削除は不可能だ。こちらは良く指摘される欠点だが、テーブルが埋まってくると急に性能が劣化する。特に 80% を越えた当たりからだ。それゆえ使うとしたら、挿入と検索だけしか行なわず、要素数もあらかじめ見当がつくの場合ぐらいしか無い。たくさんの挿入と削除を行なうような処理には向かない。そのため、開番地法は、理論上の賜で実装する意味はほとんど無いと思っている。

削除が難しい理由は、削除した後の後処理の為だ。消した後に出来る開きをどうにか始末しなくてはならない。

簡単な試みとしては、削除されたと印を付けることだ。検索の場合は、削除印のある場所の値は無視して処理をする。ここであたかも空のレコードのように処理を止めると、見つからない値が出来てしまう。挿入時には上書きすることができる。削除しても、レコード自体は有効なので、ハッシュテーブルの効率は下がることはあっても上がることはない。既にテーブルの初期値大きさからくる制限があるので、この副作用は辛い。

もし、実際にレコードを削除しようとするともっと難しい問題にあたる。衝突回避に2重ハッシュ (double hashing) を使っていたら、全ての値を調べる以外は不可能だ。削除された所に移動できる、レコードが二つ目のハッシュに何処に飛ばされたのかは皆目見当がつかない。線形走査法 (linear probing) だと、次の位置が分かるので、移動を試みることは出来る。もし、移動が出来たとしても、新しい空きが出来るので、その作業を繰り返す羽目になる。ハッシュ関数は元々演算処理的に高くつく事も多いので、比較的埋まっているハッシュテーブルだと、削除の代償は大きくなる。

削除の難しさ、性能劣化の特性、汎用性の無さから使ったことがない。