On 12/04/11 08:08, Chris Angelico wrote:
2011/12/5 Hrvoje Niksic<hnik...@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.
From an interface perspective, I suppose it would work. However
one of the main computer-science reasons for addressing by a hash
is to get O(1) access to items (modulo pessimal hash
structures/algorithms which can approach O(N) if everything
hashes to the same value/bucket), rather than the O(logN) time
you'd get from a tree. So folks reaching for a hash/map might be
surprised if performance degraded with the size of the contents.
-tkc
--
http://mail.python.org/mailman/listinfo/python-list
