Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.python > #41401 > unrolled thread

Re: Just curious - I thought dict keys would maintain sequence

Back to article view | Back to comp.lang.python

This discussion starts older than the indexed window; earlier articles aren't shown. The article labeled Started by below is the oldest one visible, not the original post.

Contents

  Re: Just curious - I thought dict keys would maintain sequence Chris Angelico <rosuav@gmail.com> - 2013-03-18 18:31 +1100
    Re: Just curious - I thought dict keys would maintain sequence Steven D'Aprano <steve+comp.lang.python@pearwood.info> - 2013-03-18 07:59 +0000

#41401 — Re: Just curious - I thought dict keys would maintain sequence

On Mon, Mar 18, 2013 at 6:26 PM, Frank Millman <frank@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. :)

ChrisA

[toc] | [next] | [standalone]

#41405

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

> On Mon, Mar 18, 2013 at 6:26 PM, Frank Millman <frank@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

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.python

csiph-web