Python Dictionaries are Ordered now, but how?…and why?

GIF from giphy

Yup, starting from python version 3.7 dictionary order is guaranteed to be insertion order. Does that mean OrderedDict is useless now? Not really, there are a few differences which i’ll explain at the end, First let’s talk about the new python 3.7+ dicts.

contestants = { 'Randy Orton': 'Red', 'Dwayne Johnson' : 'Blue' }
contestants['Jhon Cena'] = 'Red'
contestants['Dave Bautista'] = 'Blue'
del contestants['Dwayne Johnson']
print(contestants) 
# for python 3.7+ the output is {'Randy Orton': 'Red', 'Jhon Cena': 'Red', 'Dave Bautista': 'Blue'}

How’s this even possible?

A simple Hash Table consists of key-value pair arranged in pseudo random order based on the calculations from Hash Function. The traditional implementation of python dict used a sparse array which had lots of unused spaces in between. The new implementation uses a combination of dense array and sparse array, the dense array stores the key-value pair while the sparse array stores the indices to this dense array.

This can be represented using DS like so, ( more details here )

d = {'timmy': 'red', 'barry': 'green', 'guido': 'blue'}
# the dict d is traditionally stored as (notice the unused spaces)
   entries = [['--', '--', '--'],
              [-8522787127447073495, 'barry', 'green'],
              ['--', '--', '--'],
              ['--', '--', '--'],
              ['--', '--', '--'],
              [-9092791511155847987, 'timmy', 'red'],
              ['--', '--', '--'],
              [-6480567542315338377, 'guido', 'blue']]
# with the new way it is organised like so (memory is saved here)
   indices =  [None, 1, None, None, None, 0, None, 2]
   entries =  [[-9092791511155847987, 'timmy', 'red'],
               [-8522787127447073495, 'barry', 'green'],
               [-6480567542315338377, 'guido', 'blue']]

Visual representation

Fancy, but Why though?

You might be wondering how this new change helps you, correct? let’s look at the advantages,

• Less memory required for both usage and creation of Dictionaries.
• Faster Iteration ( It’s considered to be 2x faster based on information from this site )
• Order is maintained while iterating through the dictionary and while converting a dictionary to some other data type, example: list(contestants.keys()) or list(contestants.values())

OrderedDict vs Dict 3.7+

OrderedDict has two extra features (methods) that a regular Dictionary doesn’t have — reversed and move_to_end

1. reversed reversed the order of the dictionary(OrderedDict), reversed(ordered_dict) Note: this feature might be added to regular dictionary in python 3.8+
2. move_to_end moves a key to the end of the OrderedDict, ordered_dict.move_to_end('Jhon Cena')

It’s safer to use OrderedDict for now as some systems might still be using python version 3.6 and below. But keep this information in mind because if an interviewer asks you if a dict maintains order, it might be a trick question.

also , if you tell something wrong in an interview just say that it’s a new feature and will be added on the next release 😀. Just kidding, don’t actually do this in an interview…