A Concise Introduction to Data Structures using Java

Chapter 11

Hash Tables

Hash tables focus on providing a fast search for any item. They achieve better search performance than even binary search trees by giving up one of the defining features of both binary search trees and heaps: that elements are stored according to their order.

11.1 Map Interface and Linked Implementation

The goal of a hash table is to provide close to O(1) search and insertion for any element. This emphasis on searching leads to a new interface, one based on looking up the value of a key.

Maps

A map is a set of key-value pairs in which each key is associated with one value. The same value may be paired with more than one key, but the point is that looking up a key returns the unique value that was stored for that key. Maps ...