オープンアドレス法

$n \le m$ とし、すべてのキーを表 $T[0..m-1]$ に直接格納します。探査関数 $h : U \times \{0, 1, \ldots, m-1\} \to \{0, \ldots, m-1\}$ を、各キー $k$ について探査列 $\langle h(k,0), h(k,1), \ldots, h(k,m-1)\rangle$ が $\{0, \ldots, m-1\}$ の並べ替えになるように定めます。

• 挿入：$i = 0, 1, 2, \ldots$ の順に $T[h(k,i)]$ を調べ、最初に見つかった空スロットに置く。
• 探索：同じ順に調べ、キーが一致すれば成功。空スロットに当たったら「無い」と答えて終了する。

代表的な探査法は次の 3 つです。

• 線形探査：$h(k,i) = (h'(k) + i) \bmod m$
• 二次探査：$h(k,i) = (h'(k) + c_1 i + c_2 i^2) \bmod m$（$c_1, c_2, m$ は探査列が表全体を覆うように選ぶ）
• 二重ハッシュ：$h(k,i) = (h_1(k) + i \cdot h_2(k)) \bmod m$（$h_2(k)$ は $m$ と互いに素でなければならない。$m$ を素数にして $1 \le h_2(k) \le m-1$ とすればよい）