order independent hash?

[Hrvoje Niksic]

Chris Angelico <rosuav at gmail.com> writes:

> 2011/12/5 Hrvoje Niksic <hniksic at xemacs.org>:
>> If a Python implementation tried to implement dict as a tree,
>> instances of classes that define only __eq__ and __hash__ would not
>> be correctly inserted in such a dict.
>
> Couldn't you just make a tree of hash values? Okay, that's probably
> not the most useful way to do things, but technically it'd comply with
> the spec.

That's a neat idea.  The leaves of the tree would contain a list of
items with the same hash, but that's what you effectively get with a
linear-probe hash table anyway.

As you said, not immediately useful, but one could imagine the technique
being of practical use when implementing Python or a Python-compatible
language in a foreign environment that supports only tree-based
collections.