Why are Python dictionaries NOT stored in the orde

Question

This question already has an answer here:

• Why is the order in dictionaries and sets arbitrary? 6 answers

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?

Answer 1

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

Answer 2

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.