Chapter 10
Maps, Hash Tables, and Skip Lists
Contents
10.1.2 Application: Counting Word Frequencies
10.1.3 An AbstractMap Base Class
10.1.4 A Simple Unsorted Map Implementation
10.2.2 Collision-Handling Schemes
10.2.3 Load Factors, Rehashing, and Efficiency
10.2.4 Java 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.1 Maps
A map is an abstract data type designed to efficiently store and retrieve values based upon a uniquely identifying search key for each. Specifically, a map stores key-value pairs (k, v), which we call entries, where k is the key and v is its corresponding value. Keys are required to be unique, so that the association of keys to values defines a mapping. Figure 10.1 provides a conceptual illustration of a map using the file-cabinet metaphor. For a more modern metaphor, think about the web as being a map whose entries are the web pages. The key of a page is its URL (e.g., http://datastructures.net/) and its ...
Get Data Structures and Algorithms in Java, 6th Edition now with the O’Reilly learning platform.
O’Reilly members experience books, live events, courses curated by job role, and more from O’Reilly and nearly 200 top publishers.
