Author neologix
Recipients Arach, Arfrever, Huzaifa.Sidhpurwala, Jim.Jewett, Mark.Shannon, PaulMcMillan, Zhiping.Deng, alex, barry, benjamin.peterson, christian.heimes, dmalcolm, eric.snow, fx5, georg.brandl, grahamd, gregory.p.smith, gvanrossum, gz, haypo, jcea, lemburg, mark.dickinson, merwok, neologix, pitrou, skrah, terry.reedy, tim.peters, v+python, zbysz
Date 2012-01-20.10:39:45
SpamBayes Score 6.66789e-07
Marked as misclassified No
Message-id <CAH_1eM0cdFYPJgbMgbR60o-9B_t_4prfxfMcayCO7ZUjqg1yHQ@mail.gmail.com>
In-reply-to <1327051841.74.0.786264271225.issue13703@psf.upfronthosting.co.za>
Content
> Since we are are trying to fix a problem where hash(X) == hash(Y), you
> can't make them orderable by using the hash-values and build a binary
> out of the (equal) hash-values.

That's not what I suggested.
Keys would be considered equal if they are indeed equal (__eq__). The
hash value is just used to know if the key belongs to the left or the
right child tree. With a self-balanced binary search tree, you'd still
get O(log(N)) complexity.

Anyway, I still think that the hash randomization is the right way to
go, simply because it does solve the problem, whereas the collision
counting doesn't: Martin made a very good point on python-dev with his
database example.
History
Date User Action Args
2012-01-20 10:39:47neologixsetrecipients: + neologix, lemburg, gvanrossum, tim.peters, barry, georg.brandl, terry.reedy, gregory.p.smith, jcea, mark.dickinson, pitrou, haypo, christian.heimes, benjamin.peterson, merwok, grahamd, Arfrever, v+python, alex, zbysz, skrah, dmalcolm, gz, Arach, Mark.Shannon, eric.snow, Zhiping.Deng, Huzaifa.Sidhpurwala, Jim.Jewett, PaulMcMillan, fx5
2012-01-20 10:39:46neologixlinkissue13703 messages
2012-01-20 10:39:45neologixcreate