The abstract says

   "Hash tables have no intrinsic order for these associations, and
    allow key lookup and destructive updating in amortised constant time."

but as described in the section on hashing, it is a requirement is that
the hash function is good for the equivalence predicate associated with
the hash table.

How about adding "provided a good hash functions is used"?

--
Jens Axel Søgaard