CODEWITHSUNDEEP
python
mohsen
mohsen

Reputation: 1716

how is a dictionary sorted?

Ladies and Gents,

I have a question about dictionaries in python. While playing around I noticed something that to me seems strange.

I define a dict like this

stuff={'age':26,'name':'Freddie Mercury', 'ciy':'Vladivostok'}

I then add the word 'first' to stuff like this:

stuff[1]='first'

When I print it out, it's fine

stuff

{1: 'first', 'age': 26, 'name': 'Freddie Mercury', 'city': 'Vladivostok'}

Then I add the word second:

stuff[2]='second'

and that's fine, but when I display the content I get:

stuff

{1: 'first', 'age': 26, 2: 'second', 'name': 'Freddie Mercury', 'city': 'Vladivostok'}

** notice that 2 is now the third element, and not the second (in order) or the first (if elements are added to the beginning) element

And when I add in the third element 'wtf', now all of a sudden everything is back in order and I'm quite confused as to what's going on.

stuff[3]='wtf'

stuff

{1: 'first', 2: 'second', 3: 'wtf', 'name': 'Freddie Mercury', 'age': 26, 'city': 'Vladivostok'}

Could someone please explain to me what's going on here?

Upvotes: 2

Views: 414

Answers (6)

Anthon
Anthon

Reputation: 76607

The build in dict gives no guarantee of order of keys after an insertion or deletion.

If you want to keep insertion order (by time of key insertion/update or by key + value insertion/ update) or sorted by key, use the orderddict package http://anthon.home.xs4all.nl/Python/ordereddict/ that I wrote. It is implemented in C (and thus only works for CPython, but almost as fast as the build in dict).

Upvotes: 0

Reinstate Monica
Reinstate Monica

Reputation: 4723

There are some (important) guarantees about order. From the docs (Python 2.7.2) http://docs.python.org/library/stdtypes.html#dict.items:

If items(), keys(), values(), iteritems(), iterkeys(), and itervalues() are called with no intervening modifications to the dictionary, the lists will directly correspond. This allows the creation of (value, key) pairs using zip(): pairs = zip(d.values(), d.keys()). The same relationship holds for the iterkeys() and itervalues() methods: pairs = zip(d.itervalues(), d.iterkeys()) provides the same value for pairs. Another way to create the same list is pairs = [(v, k) for (k, v) in d.iteritems()].

Upvotes: 2

inspectorG4dget
inspectorG4dget

Reputation: 113945

In a list, elements are ordered by their index (position in the list).

A dictionary is, for a all intensive purposes, a bag. Things may move around, but you shouldn't be concerned about that. You access items by their keys. You could think of keys as labels, which uniquely identify their values. 

stuff = {} # hey python, please create a bag called stuff.
stuff[1]='first' # hey python, please put the string 'first' in my bag called stuff. 
                 # if I ever need to access 'first' from this bag, I will ask for 1
                 # so please attach the label (key) 1 to the item (value) 'first'
print stuff[1]   # hey python, please find the thing in my bag called stuff
                 # that has a label with 1 attached to it


print stuff[2]   # hey python, please find the thing in my bag called stuff
                 # that has a label called 1 attached to it
Traceback (most recent call last):
  File "<stdin>", line 3, in <module>
KeyError: 2      # python says "hey programmer, nothing in your bag called stuff has a label with 2 attached to it

Hope this helps

Upvotes: 1

Chris B.
Chris B.

Reputation: 90201

The order you get from a dictionary is undefined. You should not rely on it. In this case, it happens to depend on the hash values of the underlying keys, but you shouldn't assume that's always the case.

If order matters to you, use should use an OrderedDict (since Python 2.7):

>>> from collections import OrderedDict
>>> stuff=OrderedDict({'age':26,'name':'Freddie Mercury', 'city':'Vladivostok'})
>>> stuff[1]='first'
>>> print stuff
OrderedDict([('city', 'Vladivostok'), ('age', 26), ('name', 'Freddie Mercury'), (1, 'first')])
>>> stuff[2]='second'
>>> print stuff
OrderedDict([('city', 'Vladivostok'), ('age', 26), ('name', 'Freddie Mercury'), (1, 'first'), (2, 'second')])
>>> stuff[3]='wtf'
>>> print stuff
OrderedDict([('city', 'Vladivostok'), ('age', 26), ('name', 'Freddie Mercury'), (1, 'first'), (2, 'second'), (3, 'wtf')])

Upvotes: 22

Marcin
Marcin

Reputation: 49826

Learn what a hashtable is: http://en.wikipedia.org/wiki/Hash_table

In short, dict has an internal array, and inserts values at slots chosen through a hash function. The nature of this function is that it spreads the entries around evenly.

Upvotes: 7

TJD
TJD

Reputation: 11896

Dictionaries are unordered data structures, so you should have no expectations

Upvotes: 10

Related Questions