March 2013
Intermediate to advanced
748 pages
21h 42m
English
book
Data Structures and Algorithms in Python
by Michael T. Goodrich, Roberto Tamassia, Michael H. Goldwasser
Content preview from Data Structures and Algorithms in Python
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
Start your free trial
Chapter 10
Maps, Hash Tables, and Skip Lists
Contents
10.1.2 Application: Counting Word Frequencies
10.1.3 Python's MutableMapping Abstract Base Class
10.1.5 Simple Unsorted Map Implementation
10.2.2 Collision-Handling Schemes
10.2.3 Load Factors, Rehashing, and Efficiency
10.2.4 Python Hash Table Implementation
10.3.2 Two Applications of Sorted Maps
10.4.1 Search and Update Operations in a Skip List
10.4.2 Probabilistic Analysis of Skip Lists 
10.5 Sets, Multisets, and Multimaps
10.5.2 Python's MutableSet Abstract Base Class
10.1 Maps and Dictionaries
Python's dict class is arguably the most significant data structure in the language. It represents an abstraction known as a dictionary in which unique keys are mapped to associated values. Because of the relationship they express between keys and values, dictionaries are commonly known as associative arrays or maps. In this book, we use the term dictionary when specifically discussing Python's dict class, and the term map when discussing the more general notion of the abstract ...