Because sets guarantee the uniqueness of the keys they contain, if you try to add an item that is already in the set, that item simply won’t be added. We then continue through the list, performing this step for every item in the phone book.įor the set method, instead of iterating over all unique names we have already seen, we can simply add the current name to our set of unique names. If it is a new unique name, we add it to our list of unique names. Here, we must check the current name against all the unique names we have already seen. We must go over all the items in our phone book, and thus this loop costs O(n). Through the entire list to find the phone number we required, as shown in With lists, we would store the phone numbers and names sequentially and scan Simple to answer the question, “What is John Doe’s phone number?” in the future. We would like to store this in a form that will make it Say we want to store contact information for everyone If the hash function is slow to evaluate, then any operations onĭictionaries or sets will be similarly slow. Insertions/lookups is O(1), the actual speed depends greatly on the hashing function that However, there is a cost to using dictionaries and sets. The use of an open address hash table as the underlying data structure. As we will see in How Do Dictionaries and Sets Work?, this speed is accomplished through Lists/tuples, dictionaries and sets have O(1) insertion time. Lists/tuples with no intrinsic order (through a search operation), dictionariesĪnd sets give us O(n) lookups based on the arbitrary index. While we saw in the previous chapter that we are restricted to, at best, O(log n) lookup time on Hash Functions and Entropy for more details. These, and any user classes have default values. All native types in Python already implement A hashable type is one that implements both the _hash_ magic function andĮither _eq_ or _cmp_.

Lists and dictionaries python