mar...@v.loewis.de writes: > >> It doesn't change anything, you will still get collisions. > > > > > > That depends right? If the collision is because they all have the same > > hash(), yes. It might be different if it is because the secondary hashing > > (or whatever it's called :-) causes collisions. > > But Python deals with the latter case just fine already. The open hashing > approach relies on the dict resizing "enough" to prevent collisions after > the dictionary has grown. Unless somebody can demonstrate a counter example, > I believe this discussion is a red herring. > > Plus: if an attacker could craft keys that deliberately cause collisions > because of the dictionary size, they could likely also craft keys in the same > number that collide on actual hash values, bringing us back to the original > problem.
I thought that the original problem was that with N insertions in the dictionary, by repeatedly inserting different keys generating the same hash value an attacker could arrange that the cost of finding an open slot is O(N), and thus the cost of N insertions is O(N^2). If so, frequent resizing could make the attacker's problem much more difficult, as the distribution of secondary probes should change with each resize. _______________________________________________ Python-Dev mailing list Python-Dev@python.org http://mail.python.org/mailman/listinfo/python-dev Unsubscribe: http://mail.python.org/mailman/options/python-dev/archive%40mail-archive.com