-3

Just curious more than anything else, but why isn't a dictionary such as the one below not ordered the same as it was created? But when I print out test it returns the same order from then on...

test = {'one':'1', 'two':'2', 'three':'3', 'four':'4'}

It's not that I need them ordered, but it's just been on my mind for awhile as to what is occurring here.

The only thing I've found on this is a quote from this article:

Python uses complex algorithms to determine where the key-value pairs are stored in a dictionary.

But what are these "complex algorithms" and why?

Ryan Haining
  • 35,360
  • 15
  • 114
  • 174
double_j
  • 1,636
  • 1
  • 18
  • 27
  • 1
    Because it makes the "complex algorithms" even more complicated. – Cong Ma Oct 03 '15 at 00:21
  • It should be noted that PHP uses similar "complex algorithms", but it also remembers the order that the elements were added (and allows you to reorder them). – Barmar Oct 03 '15 at 00:29

2 Answers2

4

Python needs to be able to access D[thing] quickly.

If it stores the values in the order that it receives them, then when you ask it for D[thing], it doesn't know in advance where it put that value. It has to go and find where the key thing appears and then find that value. Since it has no control over the order these are received, this would take about N/2 steps on average where N is the number of keys it's received.

But if instead it has a function (called a hash) that can turn thing in to a location in memory, it can quickly take thing and calculate that value, and check in that spot of memory. Of course, it's got to do a bit more overhead - checking that D[thing] has actually been defined, and checking for those rare cases where you may have defined D[thing1] and D[thing2] where the hash function of thing1 and thing2 happen to be the same (in which case a "collision" occurs and python has to figure out a new place to put one of them).

So for your example, you might expect that when you search for test['four'] it just goes to the last entry in a list it's stored and says "aha, that's '4'." But it can't just do that. How does it know that four corresponds to the last entry of the list. It could have come in any order, so it would have to create some other data structure which allows it to quickly tell that four was the last entry. This would take a lot of overhead.

It would be possible to make it output things in the order they were entered, but that would still require additional overhead tracking the order things were entered.

Joel
  • 22,598
  • 6
  • 69
  • 93
  • nitpick: it doesn't have to "**store** it in the order that it receives them". It only needs to _iterate_ in the order of insertion. But anyway it adds to complexity and hurts performance. See source code of `collections.OrderedDict`. – Cong Ma Oct 03 '15 at 00:26
  • @CongMa ? I'm not sure I understand. The question was asking why they aren't stored in the order of insertion. I don't understand what your point is. – Joel Oct 03 '15 at 00:29
  • @CongMa I think I see what you mean - you're looking more at the question: "why doesn't it output them in the order they were entered" – Joel Oct 03 '15 at 00:42
  • Yep, the OP's actually concerned with the order of printing the dict items, which is the iteration order but not necessarily storage layout order. – Cong Ma Oct 03 '15 at 00:45
0

For curiosity, if you want a ordered dictionary, use OrderedDict

Marcos Castro
  • 41
  • 6