Author alex
Recipients Arach, Arfrever, Huzaifa.Sidhpurwala, Jim.Jewett, Mark.Shannon, PaulMcMillan, Zhiping.Deng, alex, barry, benjamin.peterson, christian.heimes, dmalcolm, eric.araujo, eric.snow, fx5, georg.brandl, grahamd, gregory.p.smith, gvanrossum, gz, jcea, lemburg, loewis, mark.dickinson, neologix, pitrou, skrah, terry.reedy, tim.peters, v+python, vstinner, zbysz
Date 2012-01-26.21:04:27
SpamBayes Score 4.28784e-10
Marked as misclassified No
Message-id <>
In-reply-to <>
On Thu, Jan 26, 2012 at 4:00 PM, Martin v. Löwis <>wrote:

> Martin v. Löwis <> added the comment:
> I'd like to propose an entirely different approach: use AVL trees for
> colliding strings, for dictionaries containing only unicode or byte strings.
> A prototype for this is in
> It is not fully working yet, but I'm now confident that this is a feasible
> approach.
> It has the following advantages over the alternatives:
> - performance in case of collisions is O(log(N)), where N is the number of
> colliding keys
> - no new exceptions are raised, except for MemoryError if it runs out of
> memory for allocating nodes in the tree
> - the hash values do not change
> - the dictionary order does not change as long as no keys collide on hash
> values (which for all practical purposes should mean that the dictionary
> order does not change in all places where it matters)
> ----------
> nosy: +loewis
> _______________________________________
> Python tracker <>
> <>
> _______________________________________


What happens if, instead of putting strings in a dictionary directly, I
have them wrapped in something.  For example, the classes Antoine and I
pasted early.  These define hash and equal as being strings, but don't have
an ordering.

Date User Action Args
2012-01-26 21:04:28alexsetrecipients: + alex, lemburg, gvanrossum, tim.peters, loewis, barry, georg.brandl, terry.reedy, gregory.p.smith, jcea, mark.dickinson, pitrou, vstinner, christian.heimes, benjamin.peterson, eric.araujo, grahamd, Arfrever, v+python, zbysz, skrah, dmalcolm, gz, neologix, Arach, Mark.Shannon, eric.snow, Zhiping.Deng, Huzaifa.Sidhpurwala, Jim.Jewett, PaulMcMillan, fx5
2012-01-26 21:04:28alexlinkissue13703 messages
2012-01-26 21:04:27alexcreate