order independent hash?

[Terry Reedy]

On 12/2/2011 4:53 AM, Hrvoje Niksic wrote:
> Chris Angelico<rosuav at gmail.com>  writes:
>
>>> The hash can grow with (k,v) pairs accumulated in the run time.
>>> An auto memory management mechanism is required for a hash of a non-fixed size of (k,v) pairs.
>>
>> That's a hash table
>
> In many contexts "hash table" is shortened to "hash" when there is no
> ambiguity.  This is especially popular among Perl programmers where the
> equivalent of dict is called a hash.
>
>> Although strictly speaking, isn't that "Python dicts are implemented
>> as hash tables in CPython"? Or is the hashtable implementation
>> mandated?
>
> It's pretty much mandated because of the __hash__ protocol.

Lib Ref 4.8. Mapping Types — dict
"A mapping object maps hashable values to arbitrary objects."

This does not say that the mapping has to *use* the hash value ;-).
Even if it does, it could use a tree structure instead of a hash table. 
But hash tables seem to work well for general purposes,

"Mappings are mutable objects."
(This would change if a frozendict were added.)

especially when additions and deletions are needed.

-- 
Terry Jan Reedy