0

I was under the impression that dictionaries are not indexed. But when using zip() on two dictionaries it returns result that points otherwise. For example:

d1={'a'=1,'b'=2}
d2={'c'=1,'d'=2}

zip(d1,d2) in Python 2 will always return 

[('a', 'c'),('b', 'd')]

Can anyone explain the indexing and storage of lists?

jonrsharpe
  • 115,751
  • 26
  • 228
  • 437
Mayank
  • 11
  • 3
  • 1
    Dictionaries are not *ordered*. Just try to add the same items in the two dictionaries using a different order, maybe deleting and re-inserting some items and you will see that the order changes. – Bakuriu Jun 25 '16 at 16:47
  • Dictionaries aren't *ordered*, and can't necessarily be *indexed* (unless the keys are integers `0`-`n`), but they are *iterable* (you iterate over the keys, as your example shows). It's not clear which part of this you find surprising. By indexing do you actually mean ordering? – jonrsharpe Jun 25 '16 at 16:53
  • If you are asking "how are hashtables implemented" that's a too broad question which you extremely easy search on google. – Bakuriu Jun 25 '16 at 16:57
  • [This](https://www.youtube.com/watch?v=C4Kc8xzcA68) PyCon talk explores the internals of Python dicts. – dawg Jun 25 '16 at 16:57
  • Pretty sure this is a dupe of http://stackoverflow.com/questions/15479928/why-is-the-order-in-python-dictionaries-and-sets-arbitrary – Padraic Cunningham Jun 25 '16 at 17:15

1 Answers1

3

Dictionaries are implemented using hashtables. All such data structures do not provide any guarantee on the order of the keys. For example:

>>> import string
>>> d1 = {}
>>> for letter in string.ascii_lowercase:
...     d1[letter] = 1
... 
>>> d2 = {}
>>> for letter in reversed(string.ascii_lowercase):
...     d2[letter] = 1
... 
>>> d1 == d2
True
>>> print(list(d1), list(d2), list(zip(d1, d2)), sep='\n')
['u', 'f', 'm', 'x', 'n', 'k', 'q', 't', 'e', 'r', 'j', 'd', 'o', 'b', 'g', 'c', 'z', 'v', 'y', 'a', 'i', 'l', 's', 'p', 'w', 'h']
['u', 'f', 'm', 'x', 'n', 'k', 't', 's', 'q', 'j', 'd', 'e', 'o', 'b', 'g', 'c', 'z', 'v', 'y', 'a', 'i', 'l', 'p', 'h', 'w', 'r']
[('u', 'u'), ('f', 'f'), ('m', 'm'), ('x', 'x'), ('n', 'n'), ('k', 'k'), ('q', 't'), ('t', 's'), ('e', 'q'), ('r', 'j'), ('j', 'd'), ('d', 'e'), ('o', 'o'), ('b', 'b'), ('g', 'g'), ('c', 'c'), ('z', 'z'), ('v', 'v'), ('y', 'y'), ('a', 'a'), ('i', 'i'), ('l', 'l'), ('s', 'p'), ('p', 'h'), ('w', 'w'), ('h', 'r')]

Note how not all keys are matched.

The order depends on the history of the dictionary. I believe by default python creates objects that can store something like 8 items, after that the size of the table must grow and the elements have to be moved, changing the order. So if you use very small dictionaries with keys that do not cause collision you end up with consistent order, but it's all an implementation detail.

Whenever you add/delete a few items you will see the order diverge.

To give an example of order changing see this:

>>> d3 = {}
>>> for letter in string.ascii_lowercase:
...     d3[letter] = 1
...     print(list(d3))
... 
['a']
['a', 'b']
['a', 'b', 'c']
['a', 'b', 'c', 'd']
['a', 'b', 'e', 'c', 'd']
['a', 'b', 'e', 'd', 'c', 'f']
['a', 'b', 'g', 'e', 'd', 'c', 'f']
['a', 'b', 'g', 'e', 'd', 'c', 'f', 'h']
['a', 'b', 'g', 'e', 'i', 'd', 'c', 'f', 'h']
['a', 'b', 'g', 'e', 'i', 'd', 'c', 'j', 'f', 'h']
['a', 'b', 'g', 'e', 'i', 'd', 'c', 'j', 'f', 'k', 'h']
['b', 'g', 'c', 'f', 'k', 'a', 'i', 'e', 'j', 'l', 'd', 'h']
['b', 'g', 'c', 'f', 'm', 'k', 'a', 'i', 'e', 'j', 'l', 'd', 'h']
['b', 'g', 'c', 'f', 'm', 'n', 'k', 'a', 'i', 'e', 'j', 'l', 'd', 'h']
['b', 'g', 'c', 'f', 'm', 'n', 'k', 'a', 'i', 'e', 'j', 'l', 'd', 'o', 'h']
['b', 'g', 'c', 'f', 'm', 'n', 'k', 'a', 'i', 'e', 'j', 'l', 'd', 'p', 'o', 'h']
['b', 'g', 'c', 'f', 'm', 'n', 'k', 'a', 'i', 'e', 'q', 'j', 'l', 'd', 'p', 'o', 'h']
['b', 'g', 'c', 'f', 'm', 'n', 'k', 'a', 'i', 'e', 'r', 'q', 'j', 'l', 'd', 'p', 'o', 'h']
['b', 'g', 'c', 'f', 'm', 'n', 'k', 'a', 'i', 'e', 'r', 'q', 'j', 'l', 'd', 'p', 's', 'o', 'h']
['b', 'g', 'c', 'f', 'm', 'n', 'k', 'a', 'i', 't', 'e', 'r', 'q', 'j', 'l', 'd', 'p', 's', 'o', 'h']
['b', 'g', 'c', 'f', 'm', 'u', 'n', 'k', 'a', 'i', 't', 'e', 'r', 'q', 'j', 'l', 'd', 'p', 's', 'o', 'h']
['u', 'f', 'm', 'n', 'k', 'q', 't', 'e', 'r', 'j', 'd', 'o', 'b', 'g', 'c', 'v', 'a', 'i', 'l', 's', 'p', 'h']
['u', 'f', 'm', 'n', 'k', 'q', 't', 'e', 'r', 'j', 'd', 'o', 'b', 'g', 'c', 'v', 'a', 'i', 'l', 's', 'p', 'w', 'h']
['u', 'f', 'm', 'x', 'n', 'k', 'q', 't', 'e', 'r', 'j', 'd', 'o', 'b', 'g', 'c', 'v', 'a', 'i', 'l', 's', 'p', 'w', 'h']
['u', 'f', 'm', 'x', 'n', 'k', 'q', 't', 'e', 'r', 'j', 'd', 'o', 'b', 'g', 'c', 'v', 'y', 'a', 'i', 'l', 's', 'p', 'w', 'h']
['u', 'f', 'm', 'x', 'n', 'k', 'q', 't', 'e', 'r', 'j', 'd', 'o', 'b', 'g', 'c', 'z', 'v', 'y', 'a', 'i', 'l', 's', 'p', 'w', 'h']

As you can see from ['a', 'b', 'e', 'c', 'd'] by adding f the order changed to ['a', 'b', 'e', 'd', 'c', 'f'], see how c and d were swapped? Etc. etc. for all other letters, until you end up with u at the beginning.

Bakuriu
  • 98,325
  • 22
  • 197
  • 231