Regarding Dictionaries in python

[Steven Taschuk]

Quoth Andy Jewell:
  [...]
> Dictionaries are not ordered entities - check the Tutorial.  [...]
> Numeric items are always added in ascending order (as far as my little 
> experiments showed anyway):  
> 
> >>> d={}
> >>> d[1]="one"
> >>> d
> {1: 'one'}
> >>> d[2]="two"
> >>> d
> {1: 'one', 2: 'two'}
  [etc.]

This happy sorting of int keys works in simple cases, but it is
very fragile and should not be relied on.

When it works, it's because (a) ints are their own hash values,
(b) entries are by preference placed at index hash(key) in the
underlying table, and (c) iteration over the dict occurs in the
order of the underlying table.

But even if the keys' hash function preserves order (as ints'
does, if we ignore negative values), the ordering can be broken if
hash(key) is larger than the table size (which is always a power
of 2, I think):

    >>> d = {6: 'foo'}
    >>> d[65536] = 'bar' # stored at index 65536 % tablesize == 0
    >>> d
    {65536: 'bar', 6: 'foo'}

Further, when a new key's hash is larger than the table size, it
might collide with an existing entry; in this case the new entry
has to be placed elsewhere.  The selection of the elsewhere is
complicated (see comments in Objects/dictobject.c), and can easily
break the sorting.  This kind of breakage depends not only on the
hash values, but on the order of insertion:

    >>> d = {}
    >>> d[23] ='foo'
    >>> d[7] = 'bar'  # collides with 23
    >>> d             # appears sorted anyway
    {7: 'bar', 23: 'foo'}

    >>> d = {}
    >>> d[7] = 'bar'
    >>> d[23] = 'foo' # collides with 7
    >>> d             # dis-sorted
    {23: 'foo', 7: 'bar'}

Moreover, this kind of breakage may go unnoticed until more
elements are added to the dict:

    >>> d = {}
    >>> d[2] = 'foo'
    >>> d[18] = 'bar' # collides with 2
    >>> d             # appears sorted anyway, until...
    {2: 'foo', 18: 'bar'}
    >>> d[5] = 'snee'
    >>> d
    {2: 'foo', 18: 'bar', 5: 'snee'}

In other words, do not be deceived by simple tests of this matter!

-- 
Steven Taschuk                                        staschuk at telusplanet.net
"Study this book; read a word then ponder on it.  If you interpret the meaning
 loosely you will mistake the Way."         -- Musashi, _A Book of Five Rings_