キーつきの保存による冪等性

$K$ をキーの集合、$f : K \to V$ を写像とする。保存域は $K$ から $V$ への部分写像 $\sigma$（有限個のキーに値が対応している表）を保持し、1 件の書き込みは原子的（表に入るか、まったく入らないか）とする。キー $\kappa \in K$ に対する操作 $\mathrm{step}(\kappa)$ を、「$\kappa$ が $\sigma$ の定義域にあれば $\sigma(\kappa)$ を返す。なければ $v = f(\kappa)$ を計算し、$(\kappa, v)$ を表に書き込んで $v$ を返す」と定める。最初の表 $\sigma_0$ が、定義域の上で $f$ と一致するとする。このとき、$\mathrm{step}(\kappa_1), \ldots, \mathrm{step}(\kappa_n)$ をどんな順序で、同じキーを何回繰り返して、またどの操作が途中で中断されても、次が成り立つ。

1. 表はつねに定義域の上で $f$ と一致し、最後まで行われた $\mathrm{step}(\kappa)$ は $f(\kappa)$ を返す。
2. すべての操作が少なくとも 1 回ずつ最後まで行われた後の表は、定義域が $\mathrm{dom}\,\sigma_0 \cup \{\kappa_1, \ldots, \kappa_n\}$ で、その上で $f$ と一致する表であり、順序と繰り返しの回数によらない。とくに $\mathrm{step}(\kappa)$ を 2 回続けて行った後の表は、1 回行った後の表と同じである（冪等性）。