# Core Python Containers -- Under the Hood

3 0 2656

Uploaded on
10/26/2008

Mr. Raymond D Hettinger

Look under-the-hood at the implementation of Python's container classes. Understand their performance implications. And walk away with a sound basic understanding of how they work and when to use them.

Comments (2):

Submit Your Video

By anonymous 2017-09-20

The short answer is that lists use linear search and dicts use amortized O(1) search.

In addition, dict searches can skip an equality test either when 1) hash values don't match or 2) when there is an identity match. Lists only benefit from the identity-implies equality optimization.

Back in 2008, I gave a talk on this subject where you'll find all the details: https://www.youtube.com/watch?v=hYUsssClE94

Roughly the logic for searching lists is:

For dicts the logic is roughly:

Dictionary hash tables are typically between one-third and two-thirds full, so they tend to have few collisions (few trips around the loop shown above) regardless of size. Also, the hash value check prevents needless slow equality checks (the chance of a wasted equality check is about 1 in 2**64).

If your timing focuses on integers, there are some other effects at play as well. That hash of a int is the int itself, so hashing is very fast. Also, it means that if you're storing consecutive integers, there tend to be no collisions at all.

Original Thread