Python Hashing it Out

In this blog we are going to deep dive into Python dictionaries, When students learn data structures they

• learn how they work theoretically
• use off-the-shelf data structures to solve problems
• some implement these data structures from scratch.

However, I don’t often see classes exploring the off-the-shelf implementations.

Background

Recall that Python implements dictionaries using a hash table with open addressing. Long story short, dictionaries have an underlying array that stores key-value pairs. When inserting a key, Python uses hash values to “probe” through this array in a specific sequence until it finds an open slot for that key. This post assumes you have a basic understanding of open addressing. If you’d like a refresher on hash table concepts, this might help.

Also, the internals of a Python dictionary isn’t a mystery: you can check out the source code! If you don’t want to read through everything, there are a bunch of resources explaining Python dictionaries, like this and this.