[Tutor] PYTHONHASHSEED, -R

[Steven D'Aprano]

On 29/07/13 19:29, Albert-Jan Roskam wrote:

>> The dict isn't changing state,
>
> So that's the criterion! Thanks! So as long as you don't use __setitem__ and __delitem__ (maybe also __setattribute__, __delattribute__, ...) the state does not change.

Built-in dicts cannot take extra attributes:

py> d = {}
py> d.surprise = "what?"
Traceback (most recent call last):
   File "<stdin>", line 1, in <module>
AttributeError: 'dict' object has no attribute 'surprise'

and even if they did, it would be irrelevant for traversing the key/value pairs.


> and the table traversal in each case is
>> a single pass, looking for non-NULL values. I'm no language lawyer,
>> but it seems the wording in the docs under the description of views
>> guarantees that this is true across Python implementations:
>>
>> http://docs.python.org/2.7/library/stdtypes.html#dictionary-view-objects

Even before views, it has been a guarantee going as far back as I can remember that keys(), values() and items() will operate in the same order so long as they are called without modifying the dict between calls.


> >      Keys and values are iterated over in an arbitrary order which is
>>      non-random,
>
> That sounds like a contradictio in terminis to me. How can something be non-random and arbitrary at the same time?


That's easy. Two nights ago, I had to decide between having fish or chicken for dinner. For some reason, I decided on fish. I can't tell you why -- I like both equally well, they both needed eating, I could have picked one or the other. Although I had no problem deciding that I wanted the fish, I have no insight into my reasons for that decision. Presumably there is something deep inside my unconscious brain that led me to decide that "I feel like fish tonight" rather than chicken, but since I'm totally unaware of the reasons for that choice, it was an arbitrary choice.

Last night I had to choose between Italian or Chinese food. I really couldn't decide, so I tossed a coin[1]. That was a random choice, and I had no control over it. The result was entirely decided by the random process of tossing a coin.

In the case of dicts, the iteration order is *deterministic* and follows from the internal structure of the dictionary's hash table, but it is unpredictable and arbitrary:

- Python doesn't make any promises about that order, so it could change without warning from version to version.

- Even if it doesn't change, Python doesn't tell you what that order is (although you could work it out from reading the source code).

- Although that order depends on the history of the dict, the order that keys were added and deleted, and even on what keys it used to have but no longer does, not just the current keys.

- To be precise, a dict includes *hidden state* which cannot be seen from Python code (namely the internal hash table) but that affects the order of key iteration.

- Since the order is determined entirely by the (hidden) internal state of the dict, it will be the same each time you look, while a random order will likely change each time.

For example, in Python 2.7, here are two dicts which have the same value, but iterate in opposite order:

py> d1 = {-1: 'a'}
py> d1[-2] = 'b'
py>
py> d2 = {-2: 'b'}
py> d2[-1] = 'a'
py>
py> d1 == d2
True
py> print d1; print d2
{-2: 'b', -1: 'a'}
{-1: 'a', -2: 'b'}




[1] Well, no, actually I didn't. I asked my wife to decide.

-- 
Steven