Just curious - I thought dict keys would maintain sequence

[Steven D'Aprano]

On Mon, 18 Mar 2013 18:31:33 +1100, Chris Angelico wrote:

> On Mon, Mar 18, 2013 at 6:26 PM, Frank Millman <frank at chagford.com>
> wrote:
>> Hi all
>>
>> I know that you cannot rely on the order of keys in a dictionary, and I
>> am not attempting to do so.
>>
>> Nevertheless, the following surprised me. A program creates a
>> dictionary with a known set of keys. I would have thought that multiple
>> runs of the program would return the keys in the same sequence. As you
>> can see, the results appear to be totally random.
>>
>> Just out of interest, I would appreciate an explanation.
> 
> Mainly, it's just something you utterly cannot depend on, so it's
> allowed to vary based on the phase of the moon, the position of your
> hard drive platters, or anything else it likes. The hashing is actually
> randomized in recent versions of Python as a defense against a denial of
> service attack by generating hash collisions; that's most likely what
> you're seeing there. The dictionary object is not deterministic to that
> extent. :)

Correct. If you try the same in Python 3.2 instead of 3.3, you will get 
the same order each time.

You can read more about the dictionary hashing attack here:


http://mail.python.org/pipermail/python-dev/2011-December/115116.html
http://bugs.python.org/issue13703
http://bugs.python.org/issue14621

The current status is that Python's dict hashes are improved, but still 
leak enough information that attackers can cause a Denial Of Service 
attack with just a bit more effort than before, but work is ongoing to 
solve this issue.



-- 
Steven