At their core, Python dictionaries are powered by a clever data structure called a hash table. Think of a hash table like a well-organized library with a finite number of shelves, or "buckets."

When you want to add a new key-value pair, Python doesn't just place it anywhere. It first runs the key through a special function called a hash function. This function takes your key (which can be a string, number, or tuple) and instantly calculates a unique numerical value called a hash. This hash value determines which bucket the key-value pair belongs in. It's like a librarian instantly knowing the exact shelf for a book just by looking at its title.

This hashing process is incredibly fast. When you need to retrieve, update, or delete a value, Python hashes the key again, instantly finds the correct bucket, and performs the operation. This is why dictionaries are so efficient for lookups.

The speed of an operation is measured by its time complexity. For dictionaries, the ideal scenario is that every key hashes to a unique bucket. When this happens, the time it takes to find an item is constant, regardless of the dictionary's size. Whether the dictionary has 10 items or 10 million, the time to perform an operation remains the same.

This is described as $O(1)$ time complexity, or "constant time."

• Insertion: $O(1)$ on average
• Deletion: $O(1)$ on average
• Lookup/Access: $O(1)$ on average

This average-case performance is what makes dictionaries a go-to choice for many programming tasks, especially when you need to quickly access data without searching through a list.

What happens if the hash function produces the same bucket number for two different keys? This is called a hash collision. It's like two different books being assigned to the exact same spot on a shelf.

Python anticipates this and handles it gracefully. Instead of overwriting the old value, it stores both key-value pairs in the same bucket, typically using a list-like structure. When you look up a key that resulted in a collision, Python first finds the right bucket and then has to search through the items in that bucket to find the specific key you asked for.

While Python's hash function is very good at avoiding collisions, they can still happen. In a poorly constructed, worst-case scenario where every single key hashes to the same bucket, the hash table essentially becomes a single long list. Searching for an item would require checking every single entry. This degrades the performance of lookups, insertions, and deletions to $O(n)$, or "linear time," where $n$ is the number of items in the dictionary. Luckily, this is extremely rare in practice.

A dictionary's memory usage, or space complexity, is directly related to the number of key-value pairs it stores. If you have $n$ items in your dictionary, the space complexity is $O(n)$.

However, there's a small catch. To keep collisions rare and operations fast, a Python dictionary doesn't just create enough buckets for the items it currently holds. It maintains a certain number of empty buckets as well. When the dictionary gets too full (about two-thirds capacity), Python automatically resizes the underlying hash table to create more buckets. This resizing operation can temporarily use more memory, but it ensures that the dictionary remains efficient as it grows.

Let's see this in action.

As you can see, the time to access an element near the beginning of the dictionary's creation is virtually identical to the time for an element created much later. This demonstrates the $O(1)$ lookup time in practice. The size of the dictionary has no significant impact on the speed of accessing any given element.

Understanding how dictionaries work under the hood helps you write more efficient code, especially when dealing with large amounts of data. Their average-case $O(1)$ performance for key operations makes them a powerful tool in any Python programmer's toolkit.