High Performance Python

Chapter 4. Dictionaries and Sets

Questions You’ll Be Able to Answer After This Chapter

• What are dictionaries and sets good for?
• How are dictionaries and sets the same?
• What is the overhead when using a dictionary?
• How can I optimize the performance of a dictionary?
• How does Python use dictionaries to keep track of namespaces?

Sets and dictionaries are ideal data structures to be used when your data has no intrinsic order, but does have a unique object that can be used to reference it (the reference object is normally a string, but can be any hashable type). This reference object is called the “key,” while the data is the “value.” Dictionaries and sets are almost identical, except that sets do not actually contain values: a set is simply a collection of unique keys. As the name implies, sets are very useful for doing set operations.

Note

A hashable type is one that implements both the __hash__ magic function and either __eq__ or __cmp__. All native types in Python already implement these, and any user classes have default values. See Hash Functions and Entropy for more details.

While we saw in the previous chapter that we are restricted to, at best, O(log n) lookup time on lists/tuples with no intrinsic order (through a search operation), dictionaries and sets give us O(n) lookups based on the arbitrary index. In addition, like lists/tuples, dictionaries and sets have O(1) insertion time.^[4] As we will see in How Do Dictionaries and Sets Work?, this speed is accomplished through ...