 <p>Is <code>MyKey</code> actually immutable?</p> <p>If a key is changed after it has been used in the <code>Multimap</code> (or a <code>HashMap</code>, for that matters), and the change effects <code>hashCode()</code> and <code>equals()</code>, you won't be able to find the associated values anymore: the modified hashcode means the lookup does not happen in the bucket where the values were stored.</p>