[issue13703] Hash collision security issue
Martin v. Löwis
report at bugs.python.org
Thu Jan 26 22:00:16 CET 2012
Martin v. Löwis <martin at v.loewis.de> 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 http://hg.python.org/sandbox/loewis/branches#avl
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)
Python tracker <report at bugs.python.org>
More information about the Python-bugs-list