Java Reference
In-Depth Information
Chapter
21
Introducing
Hashing
Contents
What Is Hashing?
Hash Functions
Computing Hash Codes
Compressing a Hash Code into an Index for the Hash Table
Resolving Collisions
Open Addressing with Linear Probing
Open Addressing with Quadratic Probing
Open Addressing with Double Hashing
A Potential Problem with Open Addressing
Separate Chaining
Prerequisites
Chapter
19
Dictionaries
Chapter
20
Dictionary Implementations
Objectives
After studying this chapter, you should be able to
•
Describe the basic idea of hashing
•
Describe the purpose of a hash table, a hash function, and a perfect hash function
•
Explain why you should override the method
hashCode
for objects used as search keys
•
Describe how a hash function compresses a hash code into an index to the hash table
•
Describe collisions and explain why they occur
•
Describe open addressing as a method to resolve collisions
•
Describe linear probing, quadratic probing, and double hashing as particular open addressing schemes
•
Describe algorithms for the dictionary operations
getValue
,
add
, and
remove
when open addressing
resolves collisions
•
Describe separate chaining as a method to resolve collisions
•
Describe algorithms for the dictionary operations
getValue
,
add
, and
remove
when separate chaining
resolves collisions
•
Describe clustering and the problems it causes
