Why Is a Dictionary "Not Ordered"

Why is a Dictionary not ordered ?

Well, for one thing it's not clear whether you expect this to be insertion-order or key-order. For example, what would you expect the result to be if you wrote:

var test = new Dictionary<int, string>();
test.Add(3, "three");
test.Add(2, "two");
test.Add(1, "one");
test.Add(0, "zero");

Console.WriteLine(test.ElementAt(0).Value);

Would you expect "three" or "zero"?

As it happens, I think the current implementation preserves insertion ordering so long as you never delete anything - but you must not rely on this. It's an implementation detail, and that could change in the future.

Deletions also affect this. For example, what would you expect the result of this program to be?

using System;
using System.Collections.Generic;

class Test
{ 
    static void Main() 
    {
        var test = new Dictionary<int, string>();
        test.Add(3, "three");
        test.Add(2, "two");
        test.Add(1, "one");
        test.Add(0, "zero");

        test.Remove(2);
        test.Add(5, "five");

        foreach (var pair in test)
        {
            Console.WriteLine(pair.Key);
        }
    }     
}

It's actually (on my box) 3, 5, 1, 0. The new entry for 5 has used the vacated entry previously used by 2. That's not going to be guaranteed either though.

Rehashing (when the dictionary's underlying storage needs to be expanded) could affect things... all kinds of things do.

Just don't treat it as an ordered collection. It's not designed for that. Even if it happens to work now, you're relying on undocumented behaviour which goes against the purpose of the class.

Dictionary values are not ordered python

If you need a dict that maintains insertion order, Python versions >= 2.7 include the OrderedDict class in the collections module.

A regular dict:

>>> ud = {}
>>> ud['first'] = 1
>>> ud['second'] = 2
>>> ud['third'] = 3
>>> ud.values()
[2, 3, 1]

An ordered dict:

>> from collections import OrderedDict
>>> od = OrderedDict()
>>> od['first'] = 1
>>> od['second'] = 2
>>> od['third'] = 3
>>> od.values()
[1, 2, 3]

Why dictionary values aren't in the inserted order?

Dictionaries in Python are unordered by definition. Use OrderedDict if you need the order in which values were inserted (it's available in Python 2.7 and 3.x).

Why updating Dictionary is not sorted by the same order

Before Python 3.7 dict was not ordered and if you wanted to preserve the order of items in a dictionary you had to use OrderedDict

This happened because the dictionary type previously implemented its hash table algorithm with a combination of the hash built-in function and a random seed that was assigned when the Python interpreter started. Together, these behaviors caused dictionary orderings to not match insertion order and to randomly shuffle between program executions.

In Python 3.7 and above order of items in the dictionary are preserved, and you don't have to use OrderedDict anymore.

the insertion-order preservation nature of dict objects has been
declared to be an official part of the Python language spec.

The way that dictionaries preserve insertion ordering is now part of the Python language specification. You can rely on this behavior and even make it part of the APIs you design for your classes and functions.

I also measured the performance of creation regular dict and OrderedDict and regular dict is about 2.5-3 times faster than OrderedDict

from collections import OrderedDict

data = [(i, chr(i)) for i in range(65, 91)]


%%timeit

d = dict(data)

2.27 µs ± 235 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)


%%timeit

d = OrderedDict(data)

6.59 µs ± 1.32 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)


%%timeit

d = {}

for k, v in data:
    d[k] = v

4.84 µs ± 1.31 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)


%%timeit

d = OrderedDict()

for k, v in data:
    d[k] = v

7.48 µs ± 1.6 µs per loop (mean ± std. dev. of 7 runs, 100000 loops each)

Why are Python dictionaries NOT stored in the order they were created?

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.

---

Related Topics