[Tutor] Python dictionary element order

[denis]

----- Original Message -----
From: Lloyd Kvam <pythonTutor at venix.com>
To: <tpc at csua.berkeley.edu>
Cc: <tutor at python.org>
Sent: Tuesday, April 20, 2004 1:06 AM
Subject: Re: [Tutor] Python dictionary element order


> The ordering of keys and values retrieved from a dictionary is
> undefined.  There is no requirement that keys or values support an
> ordering.  For instance, they could be complex numbers.

Python's dicts use hash fuctions to boost the search of values. Below
wikipedia's definition at http://en.wikipedia.org/wiki/Hash_table :

***********
Hash table
>From Wikipedia, the free encyclopedia.

In computer science, a hash table is a data structure that implements an
associative array. Like any associative array a hash table is used to store
many key => value associations (this is a many to one relationship as the
hash table is almost universally smaller than the number of keys).

A hash table maintains two arrays, one for keys, one for values (or possibly
one array of (key, value) pairs - it doesn't really matter). The elements of
these arrays are referred to as buckets. When required to find the
associated value for a given key, the key is fed through a hash function to
yield an integer (called the hash value). This integer is then the index to
the associated value. Commonly the hash value is calculated using modulo
arithmetic, modulo a prime p (with a hash table of size p).
***********

The hash function yields (small) integers because they're the easiest and
fastest processed data type. These integers are then used as pointers to the
searched data. When in a dictionary you precisely use (small ?) integer
keys, I imagine that the hash values produced out of them will have the same
sort order as the original integers. (morever, as the hash functions are
based on modulo operations, if the integers are smaller than the table size,
they may be simply let unchanged, or what ?). Well, this is just guessing.
I got this from unsorted integer keys :

>>> l=[3,4,1,5,2]
>>> r={}
>>> for i in l :
 r[i]=i
>>> for k in r.keys() : print k,
1 2 3 4 5

salutation,
denis

PS : I find this list great. Thank you all. (Having these days a bit more
time than usually, I try to answer -- for myself -- many of the questions :
I learn much thanks to that and, above all, I discover more and more how
much I didn't know !)


> On Mon, 2004-04-19 at 18:41, tpc at csua.berkeley.edu wrote:
> > hi everybody, I am confused about the default element order for keys of
> > type string in Python dictionary.
> >
> > <code>
> > fruitlist = ['apple', 'grape', 'orange', 'pear', 'watermelon', 'mango']
> > eaten = {}
> > while fruitlist:
> >         fruit = fruitlist.pop()
> >         if fruit not in eaten:
> > eaten[fruit] = 1
> > </code>
> > eaten outputs
> > {'grape': 1, 'apple': 1, 'pear': 1, 'mango': 1, 'watermelon': 1,
'orange':
> > 1}
> >
> > When I input a list of numbers:
> >
> > <code>
> > numlist = [1, 2, 3, 4, 5, 6]
> > numdict = {}
> > while numlist:
> > num = numlist.pop()
> > if num not in numdict:
> > numdict[num] = 'NULL'
> > </code>
> > numdict outputs
> > {1: 'NULL', 2: 'NULL', 3: 'NULL', 4: 'NULL', 5: 'NULL', 6: 'NULL'}
> >
> > I understand list.pop() outputs the last element in the list, so
> > the dictionary element order indicated to me there was some kind of
> > default sorting.  The first element in eaten should be 'mango', or at
the
> > very least 'apple' if Python dictionaries by default sort keys of type
string
> > alphabetically.
> >
> > What is going on here ?
> >
> >
> >
> >
> > _______________________________________________
> > Tutor maillist  -  Tutor at python.org
> > http://mail.python.org/mailman/listinfo/tutor
> --
>
> Lloyd Kvam
> Venix Corp.
> 1 Court Street, Suite 378
> Lebanon, NH 03766-1358
>
> voice: 603-653-8139
> fax: 801-459-9582
>
>
> _______________________________________________
> Tutor maillist  -  Tutor at python.org
> http://mail.python.org/mailman/listinfo/tutor
>