order independent hash?

[Hrvoje Niksic]

Steven D'Aprano <steve+comp.lang.python at pearwood.info> writes:

> Except for people who needed dicts with tens of millions of items.

Huge tree-based dicts would be somewhat slower than today's hash-based
dicts, but they would be far from unusable.  Trees are often used to
organize large datasets for quick access.

The case of dicts which require frequent access, such as those used to
implement namespaces, is different, and more interesting.  Those dicts
are typically quite small, and for them the difference between O(log n)
and O(1) is negligible in both theory (since n is "small", i.e. bounded)
and practice.  In fact, depending on the details of the implementation,
the lookup in a small tree could even be marginally faster.