> ...when I pointed out that the values that the hash key relyed upon must not change, for the life of the hash map.

Now I'm wondering about something like:

  MutableHashMap<MutableKey<T1>, Value<T2>>

You could probably have they key be a container object and allow changing its internal value, which would then communicate to the hash map that it belongs to, that it should do some internal changes:

  Entry<MutableKey<String>, Value<SomeEntity>> entry = mutableHashMap.getEntryByKey("myKey");
  entry.setKey("myNewKey");

That logic could take an internal hash map, remove the element by the old key and add it with the new key. So, to an outside user it would seem like you can change the keys.

The only problem would be that depending on the language you're using, you wouldn't change the objects directly, but would use those containers and it would essentially just be some boilerplate around a regular hash map. For example, Java has MutableInt and similar classes, which here would be hooked up to the MutableHashMap that they belong to.

Then again, I can't come up with many cases where something like that would be nice to have, since if you want to "change" a key, you can just do the following manually:

  var ourValue = myHashMap.get("myKey");
  myHashMap.remove("myKey");
  myHashMap.put("myNewKey", ourValue);

the nitpicker in me wants to say that the hash key can change (and it works if you rehash items whose key changed), but lookup by key will fail because the item will landed in the bucket of its original hash... but yes keys can't change if you want your values to be retrievable by key.