Freeze can't work in constant time if it builds a hash when the dict is frozen so that the dict can be used as a key.

If all it does is set a flag that prevents modifications, that's different.