[Solved] Why are Python dictionaries NOT stored in the order they were created? [duplicate]

Question

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.

Accepted Answer

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.