辞書（連想配列）

キーの集合 $U$ と値の集合 $V$ を固定します。辞書とは、相異なるキーをもつ有限個の対の集合 $S \subseteq U \times V$ を保持し、次の 3 つの操作を提供する抽象データ型です。

• $\mathrm{search}(k)$：$(k, v) \in S$ となる $v$ を返す。そのような $v$ がなければ「無い」と答える。
• $\mathrm{insert}(k, v)$：$S$ に $(k, v)$ を加える（同じキーの対がすでにあれば値を置き換える）。
• $\mathrm{delete}(k)$：キーが $k$ である対を $S$ から取り除く。

以下、$n = |S|$ と書きます。