Java Reference
In-Depth Information
Chapter 10
Hashing
In this chapter, we will explain the following:
•
The fundamental ideas on which hashing is based
•
How to solve the search and insert problem using hashing
•
How to delete an item from a hash table
•
How to resolve collisions using linear probing
•
How to resolve collisions using quadratic probing
•
How to resolve collisions using chaining
•
How to resolve collisions using linear probing with double hashing
•
How to link items in order using arrays
10.1 Hashing Fundamentals
Searching for an item in a (large) table is a common operation in many applications. In this chapter, we discuss
hashing
, a fast method for performing this search. The main idea behind hashing is to use the key of an item
(for example, the vehicle registration number of a vehicle record) to determine
where
in the table (the
hash table
)
the item is stored. The key is first converted to a number (if it is not already one), and this number is mapped
(we say
hashed
) to a table location. The method used to convert a key to a table location is called the
hash function
.
It is entirely possible, of course, for two or more keys to hash to the same location. When this happens, we say we
have a
collision
, and we must find a way to resolve the collision. The efficiency (or otherwise) of hashing is determined to
a large extent by the method used to resolve collisions. Much of the chapter is devoted to a discussion of these methods.
10.1.1 The Search and Insert Problem
The classical statement of the search and insert problem is as follows:
Given a list of items (the list may be empty initially), search for a given item in the list. If the item is
not found, insert it in the list.
Items can be things such as numbers (student, account, employee, vehicle, and so on), names, words, or strings
in general. For example, suppose we have a set of integers, not necessarily distinct, and we want to find out how many
distinct integers there are.
Search WWH ::
Custom Search