Java Reference
In-Depth Information
sorted set: black green grey orange red tan white yellow
headSet ("orange"): black green grey
tailSet ("orange"): orange red tan white yellow
first: black
last : yellow
Fig. 16.17
|
Using
SortedSet
s and
TreeSet
s. (Part 2 of 2.)
Map
s
associate
keys
to
values
. The keys in a
Map
must be
unique
, but the associated values
need not be. If a
Map
contains both unique keys and unique values, it's said to implement
a
one-to-one mapping
. If only the keys are unique, the
Map
is said to implement a
many-
to-one mapping
—many keys can map to one value.
Map
s differ from
Set
s in that
Map
s contain keys and values, whereas
Set
s contain only
values. Three of the several classes that implement interface
Map
are
Hashtable
,
HashMap
and
TreeMap
.
Hashtable
s and
HashMap
s store elements in hash tables, and
TreeMap
s store
elements in trees. This section discusses hash tables and provides an example that uses a
HashMap
to store key-value pairs.
Interface
SortedMap
extends
Map
and maintains its keys
in
sorted
order—either the elements'
natural
order or an order specified by a
Comparator
.
Class
TreeMap
implements
SortedMap
.
Map
Implementation with Hash Tables
When a program creates objects, it may need to store and retrieve them efficiently. Storing
and retrieving information with arrays is efficient if some aspect of your data directly
matches a numerical key value and if the
keys are unique
and tightly packed. If you have
100 employees with nine-digit social security numbers and you want to store and retrieve
employee data by using the social security number as a key, the task will require an array
with over 800 million elements, because nine-digit Social Security numbers must begin
with 001-899 (excluding 666) as per the Social Security Administration's website
This is impractical for virtually all applications that use social security numbers as keys. A
program having an array that large could achieve high performance for both storing and
retrieving employee records by simply using the social security number as the array index.
Numerous applications have this problem—namely, that either the keys are of the
wrong type (e.g., not positive integers that correspond to array subscripts) or they're of the
right type, but
sparsely
spread over a
huge range
. What is needed is a high-speed scheme for
converting keys such as social security numbers, inventory part numbers and the like into
unique array indices. Then, when an application needs to store something, the scheme
could convert the application's key rapidly into an index, and the record could be stored
at that slot in the array. Retrieval is accomplished the same way: Once the application has
a key for which it wants to retrieve a data record, the application simply applies the con-
version to the key—this produces the array index where the data is stored and retrieved.
The scheme we describe here is the basis of a technique called
hashing
. Why the
name? When we convert a key into an array index, we literally scramble the bits, forming
