Fundamentals of Python: From First Programs Through Data StructuresObjectivesObjectives (continued)Using SetsUsing Sets (continued)The Python set ClassThe Python set Class (continued)A Sample Session with SetsA Sample Session with Sets (continued)Applications of SetsImplementations of SetsRelationship Between Sets and DictionariesList Implementations of Sets and DictionariesSetsDictionariesDictionaries (continued)Slide 17Slide 18Complexity Analysis of the List Implementations of Sets and DictionariesHashing StrategiesHashing Strategies (continued)Slide 22The Relationship of Collisions to DensityHashing with Non-Numeric KeysHashing with Non-Numeric Keys (continued)Slide 26Linear ProbingLinear Probing (continued)Slide 29Slide 30Quadratic ProbingQuadratic Probing (continued)ChainingSlide 34Complexity AnalysisComplexity Analysis (continued)Case Study: Profiling Hashing StrategiesSlide 38Slide 39Case Study: Profiling Hashing Strategies (continued)Slide 41Slide 42Hashing Implementation of DictionariesHashing Implementation of SetsSorted Sets and DictionariesSorted Sets and Dictionaries (continued)SummarySummary (continued)Fundamentals of Python:From First Programs Through Data Structures Chapter 19Unordered Collections: Sets and DictionariesFundamentals of Python: From First Programs Through Data Structures 2ObjectivesAfter completing this chapter, you will be able to:•Implement a set type and a dictionary type using lists•Explain how hashing can help a programmer achieve constant access time to unordered collections•Explain strategies for resolving collisions during hashing, such as linear probing, quadratic probing, and bucket/chainingFundamentals of Python: From First Programs Through Data Structures 3Objectives (continued)After completing this chapter, you will be able to: (continued)•Use a hashing strategy to implement a set type and a dictionary type•Use a binary search tree to implement a sorted set type and a sorted dictionary typeFundamentals of Python: From First Programs Through Data Structures 4•A set is a collection of items in no particular order•Most typical operations:–Return the number of items in the set–Test for the empty set (a set that contains no items)–Add an item to the set–Remove an item from the set–Test for set membership–Obtain the union of two sets–Obtain the intersection of two sets–Obtain the difference of two setsUsing SetsFundamentals of Python: From First Programs Through Data Structures 5Using Sets (continued)Fundamentals of Python: From First Programs Through Data Structures 6The Python set ClassFundamentals of Python: From First Programs Through Data Structures 7The Python set Class (continued)Fundamentals of Python: From First Programs Through Data Structures 8A Sample Session with SetsFundamentals of Python: From First Programs Through Data Structures 9A Sample Session with Sets (continued)Fundamentals of Python: From First Programs Through Data Structures 10Applications of Sets•Sets have many applications in the area of data processing–Example: In database management, answer to query that contains conjunction of two keys could be constructed from intersection of sets of items associated with those keysFundamentals of Python: From First Programs Through Data Structures 11Implementations of Sets•Arrays and lists may be used to contain the data items of a set–A linked list has the advantage of supporting constant-time removals of items•Once they are located in the structure•Hashing attempts to approximate random access into an array for insertions, removals, and searchesFundamentals of Python: From First Programs Through Data Structures 12Relationship Between Sets and Dictionaries•A dictionary is an unordered collection of elements called entries–Each entry consists of a key and an associated value–A dictionary’s keys must be unique, but its values may be duplicated•One can think of a dictionary as having a set of keysFundamentals of Python: From First Programs Through Data Structures 13List Implementations of Sets and Dictionaries•The simplest implementations of sets and dictionaries use lists•This section presents these implementations and assesses their run-time performanceSets•List implementation of a setFundamentals of Python: From First Programs Through Data Structures 14Fundamentals of Python: From First Programs Through Data Structures 15Dictionaries•Our list-based implementation of a dictionary is called ListDict–The entries in a dictionary consist of two parts, a key and a value•A list implementation of a dictionary behaves in many ways like a list implementation of a setFundamentals of Python: From First Programs Through Data Structures 16Dictionaries (continued)Fundamentals of Python: From First Programs Through Data Structures 17Dictionaries (continued)Fundamentals of Python: From First Programs Through Data Structures 18Dictionaries (continued)Fundamentals of Python: From First Programs Through Data Structures 19Complexity Analysis of the List Implementations of Sets and Dictionaries•The list implementations of sets and dictionaries require little programmer effort–Unfortunately, they do not perform well•Basic accessing methods must perform a linear search of the underlying list–Each basic accessing method is O(n)Fundamentals of Python: From First Programs Through Data Structures 20Hashing Strategies•Key-to-address transformation or a hashing function–Acts on a given key by returning its relative position in an array•Hash table–An array used with a hashing strategy•Collision–Placement of different keys at the same array indexFundamentals of Python: From First Programs Through Data Structures 21Hashing Strategies (continued)Fundamentals of Python: From First Programs Through Data Structures 22Hashing Strategies (continued)Fundamentals of Python: From First Programs Through Data Structures 23The Relationship of Collisions to Density•Density–The number of keys relative to the length of an array•As the density decreases, so does the probability of collisions•Keeping a low load factor even (say, below .2) seems like a good way to avoid collisions–Cost of memory incurred by load factors below .5 is probably prohibitive for data sets of millions of items–Even load factors below .5 cannot prevent many collisions from occurring for some data setsFundamentals of Python: From First Programs Through Data Structures 24Hashing with Non-Numeric