[issue13703] Hash collision security issue

[Charles-François Natali]

Charles-François Natali <neologix at free.fr> added the comment:

> 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.

----------

_______________________________________
Python tracker <report at bugs.python.org>
<http://bugs.python.org/issue13703>
_______________________________________