Data Structures and the Java Collections Framework, Third Edition

CHAPTER 14

Hashing

We start this chapter by reviewing some search algorithms from earlier chapters as a prelude to the introduction of a new search technique: hashing. The basic idea with hashing is that we perform some simple operation on an element's key to obtain an index in an array. The element is stored at that index. With an appropriate implementation, hashing allows searches (as well as insertions and removals) to be performed in constant average time. Our primary focus will be on understanding and using the HashMap class in the Java Collections Framework, but we will also consider other approaches to hashing. The application will use hashing to insert identifiers into a symbol table.

CHAPTER OBJECTIVES

1. Understand how hashing works, when it should be used, and when it should not be used.
2. Explain the significance of the Uniform Hashing Assumption.
3. Compare the various collision handlers: chaining, offset-of-1, quotient-offset.

14.1 A Framework to Analyze Searching

Before we begin looking at hashing, we need a systematic way to analyze search methods in general. Because the search may be successful or unsuccessful, the analysis of search methods should include both possibilities. For each search method we estimate averageTime_s (n), the average time—over all n elements in the collection—of a successful search. As always for average time, we make the simplifying assumption that each element in the collection is equally likely to be sought.

We will also be interested in worstTime ...