I'm implementing Hopcroft's algorithm for DFA minimization, and a new hash table operation occurred to me:

  (choose-and-remove! hash-table) => key, value

The idea is that it picks a key-value pair at random, removes it, and returns it.  To implement that with the current proposals, one must get the list of keys, pick one element from it, look up the associated value, remove the key and value, and return them.  Constructing the list of keys when one is only going to use a single element is wasteful.

I'm using a simple implementation of sets built on top of hash tables, so I'm actually implementing remove-an-element for sets, not for hash tables, but picking an element at random from a set is a common operation and worth optimizing, and supporting it at the hash table level seems likely to be fruitful, too.