= Memoization key
{title2=$K(x,c)$}
A <memoization key> identifies all information that determines a reusable answer. Write $x$ for explicit arguments and $c$ for relevant context. For a <function> $f$ and key <function> $K$, the necessary value condition is
$$
K(x,c)=K(y,d)\ \Longrightarrow\ f(x,c)=f(y,d).
$$
This implication need hold only for contexts in which the entry can be reused. The condition concerns <key equality>, not merely equality of <hash function> outputs: a <hash table> must resolve <hash collisions> by comparing complete keys. Include the identity or version of the procedure if one table stores results for several procedures or changing implementations.
For an original toy example, let $g(n,a)=an$. Caching only by $n$ after $g(3,2)=6$ incorrectly returns $6$ for $g(3,4)$, whose answer is $12$. The pair $(n,a)$ is complete for this <function>. If $a$ is hidden in mutable configuration, either freeze that configuration for the <memoization cache lifetime>, include a reliable version in the key, or invalidate affected entries before reuse. A version is sufficient only if every relevant change updates it. Object identity alone is likewise insufficient for a <mutable list> whose contents determine the answer.
Back to article page
