Java Reference
In-Depth Information
Hashing as a
Dictionary
Implementation
Chapter
22
Contents
The Efficiency of Hashing
The Load Factor
The Cost of Open Addressing
The Cost of Separate Chaining
Rehashing
Comparing Schemes for Collision Resolution
A Dictionary Implementation That Uses Hashing
Entries in the Hash Table
Data Fields and Constructors
The Methods
getValue
,
remove
, and
add
Iterators
Java Class Library: The Class
HashMap
Jave Class Library: The Class
HashSet
Prerequisites
Chapter
4
The Efficiency of Algorithms
Chapter 13
List Implementations That Use Arrays
Chapter 14
A List Implementation That Links Data
Chapter 15
Iterators
Chapter 19
Dictionaries
Chapter
20
Dictionary Implementations
Chapter
21
Introducing Hashing
Objectives
After studying this chapter, you should be able to
●
Describe the relative efficiencies of the various collision resolution techniques
Describe a hash table's load factor
●
Describe rehashing and why it is necessary
●
Use hashing to implement the ADT dictionary
●
