On Fri, Aug 10, 2012 at 8:39 AM, Tim Chase <python.l...@tim.thechases.com> wrote: > On 08/09/12 17:26, Dave Angel wrote: >> On 08/09/2012 06:03 PM, Andrew Cooper wrote: >> I'm glad you're wrong for CPython's dictionaries. The only time the >> lookup would degenerate to O[n] would be if the hash table had only one >> slot. CPython sensibly increases the hash table size when it becomes >> too small for efficiency. >> >> Where have you seen dictionaries so poorly implemented? > > PHP? > > http://www.phpclasses.org/blog/post/171-PHP-Vulnerability-May-Halt-Millions-of-Servers.html
That's the same hash collision attack that I alluded to above, and it strikes *many* language implementations. Most released a patch fairly quickly and quietly (Pike, Lua, V8 (JavaScript/ECMAScript), PHP), but CPython dared not, on account of various applications depending on hash order (at least for tests). It's not (for once) an indictment of PHP (maybe that should be an "inarrayment"?), it's a consequence of a hashing algorithm that favored simplicity over cryptographic qualities. (It feels weird to be defending PHP...) ChrisA -- http://mail.python.org/mailman/listinfo/python-list