📄 _chapter 2.htm
字号:
<html>
<head>
<meta http-equiv="Content-Type" content="text/html; charset=windows-1252">
<title>Chapter 2</title>
<link rel="stylesheet" type="text/css" href="docsafari.css">
<link rel="stylesheet" type="text/css" href="style.css">
</head>
<body>
<ul></ul>
<table width="100%" border="1" bgcolor="#EBEBFF">
<tr>
<td width="5%" align="left" valign="middle"><a href="_chapter%201.htm"><img src="Larrow.gif" width="17" height="19" border="0"></a></td>
<td align="center" valign="middle"><a class="docLink" href="Front%20matter.htm">CONTENTS</a></td>
<td width="5%" align="right" valign="middle"><a href="_chapter%203.htm"><img src="Rarrow.gif" width="17" height="19" border="0"></a></td>
</tr>
</table>
<h2 class="docChapterTitle">Chapter 2. Collections</h2>
<ul>
<li>
<p class="docList"><a class="docLink" href="#c2s1">Collection Interfaces</a></li>
<li>
<p class="docList"><a class="docLink" href="#c2s2">Concrete Collections</a></li>
<li>
<p class="docList"><a class="docLink" href="#c2s3">The Collections Framework</a></li>
<li>
<p class="docList"><a class="docLink" href="#c2s4">Algorithms</a></li>
<li>
<p class="docList"><a class="docLink" href="#c2s5">Legacy Collections</a></li>
</ul>
<p class="docText">Object-oriented programming (OOP) encapsulates data inside
classes, but this doesn't make how you organize the data inside the classes any
less important than in traditional programming languages. Of course, how you
choose to structure the data depends on the problem you are trying to solve.
Does your class need a way to easily search through thousands (or even millions)
of items quickly? Does it need an ordered sequence of elements
<span class="docEmphasis">and</span> the ability to rapidly insert and remove
elements in the middle of the sequence? Does it need an arraylike structure with
random-access ability that can grow at run time? The way you structure your data
inside your classes can make a big difference when it comes to implementing
methods in a natural style, as well as for performance.</p>
<p class="docText">This chapter shows how Java technology can help you
accomplish the traditional data structuring needed for serious programming. In
college computer science programs, there is a course called
<span class="docEmphasis">Data Structures</span> that usually takes a semester
to complete, so there are many, many books devoted to this important topic.
Exhaustively covering all the data structures that may be useful is not our goal
in this chapter; instead, we cover the fundamental ones that the standard Java
library supplies. We hope that, after you finish this chapter, you will find it
easy to translate any of your data structures to the Java programming language.</p>
<h3 class="docSection1Title" id="c2s1">Collection Interfaces</h3>
<p class="docText">Before the release of the Java 2 platform, the standard
library supplied only a small set of classes for the most useful data
structures: <tt>Vector</tt>, <tt>Stack</tt>, <tt>Hashtable</tt>, <tt>BitSet</tt>,
and the <tt>Enumeration</tt> interface that provides an abstract mechanism for
visiting elements in an arbitrary container. That was certainly a wise choice梚t
takes time and skill to come up with a comprehensive collection class library.</p>
<p class="docText">With the advent of the Java 2 platform, the designers felt
that the time had come to roll out a full-fledged set of data structures. They
faced a number of conflicting design decisions. They wanted the library to be
small and easy to learn. They did not want the complexity of the "Standard
Template Library" (or STL) of C++, but they wanted the benefit of "generic
algorithms" that STL pioneered. They wanted the legacy classes to fit into the
new framework. As all designers of collection libraries do, they had to make
some hard choices, and they came up with a number of idiosyncratic design
decisions along the way. In this section, we will explore the basic design of
the Java collections framework, show you how to put it to work, and explain the
reasoning behind some of the more controversial features.</p>
<h4 class="docSection2Title" id="ch02lev2sec1">Separating Collection Interfaces and Implementation</h4>
<p class="docText">As is common for modern data structure libraries, the Java
collection library separates <span class="docEmphasis">interfaces</span> and
<span class="docEmphasis">implementations.</span> Let us look at that separation
with a familiar data structure, the <span class="docEmphasis">queue.</span> The
Java library does not supply a queue, but it is nevertheless a good example to
introduce the basic concepts.</p>
<div class="docNote">
<p class="docNoteTitle">NOTE</p>
<table cellSpacing="0" cellPadding="1" width="90%" border="0">
<tr>
<td vAlign="top" width="60">
<img alt="graphics/note.gif" src="note.gif" align="left" border="0" width="54" height="53"><br>
</td>
<td vAlign="top">
<p class="docText">If you need a queue, you can simply use the <tt>
LinkedList</tt> class that we discuss later in this chapter.</td>
</tr>
</table>
</div>
<p class="docText">A <span class="docEmphasis">queue interface</span> specifies
that you can add elements at the tail end of the queue, remove them at the head,
and find out how many elements are in the queue. You use a queue when you need
to collect objects and retrieve them in a "first in, first out" fashion (see
<a class="docLink" href="#ch02fig01">Figure 2-1</a>).</p>
<center>
<h5 id="ch02fig01" class="docFigureTitle">Figure 2-1. A queue</h5>
<p>
<img alt="graphics/02fig01.gif" src="02fig01.gif" border="0" width="500" height="152"></p>
</center>
<p class="docText">If there was a queue interface in the collections library, it
might look like this:</p>
<pre>interface Queue
{
void add(Object obj);
Object remove();
int size();
}
</pre>
<p class="docText">The interface tells you nothing about how the queue is
implemented. There are two common implementations of a queue, one that uses a
"circular array" and one that uses a linked list (see
<a class="docLink" href="#ch02fig02">Figure 2-2</a>).</p>
<center>
<h5 id="ch02fig02" class="docFigureTitle">Figure 2-2. Queue implementations</h5>
<p>
<img alt="graphics/02fig02.gif" src="02fig02.gif" border="0" width="500" height="298"></p>
</center>
<p class="docText">Each implementation can be expressed by a class that realizes
the <tt>Queue</tt> interface:</p>
<pre>class CircularArrayQueue <span class="docEmphStrong">implements Queue</span>
{
CircularArrayQueue(int capacity) { . . . }
public void add(Object obj) { . . . }
public Object remove() { . . . }
public int size() { . . . }
private Object[] elements;
private int head;
private int tail;
}
class LinkedListQueue <span class="docEmphStrong">implements Queue</span>
{
LinkedListQueue() { . . . }
public void add(Object obj) { . . . }
public Object remove() { . . . }
public int size() { . . . }
private Link head;
private Link tail;
}
</pre>
<p class="docText">When you use a queue in your program, you don't need to know
which implementation is actually used once the collection has been constructed.
Therefore, it makes sense to use the concrete class (such as <tt>
CircularArrayQueue</tt>) <span class="docEmphasis">only</span> when you
construct the collection object. Use the <span class="docEmphasis">interface
type</span> to hold the collection reference.</p>
<pre><span class="docEmphStrong">Queue</span> expressLane = new <span class="docEmphStrong">CircularArrayQueue</span>(100);
expressLane.add(new Customer("Harry"));
</pre>
<p class="docText">This approach makes it easy to change your mind and use a
different implementation. You only need to change your program in one place梩he
constructor. If you decide that a <tt>LinkedListQueue</tt> is a better choice
after all, your code becomes:</p>
<pre>Queue expressLane = new <span class="docEmphStrong">LinkedListQueue();</span>
expressLane.add(new Customer("Harry"));
</pre>
<p class="docText">Why would you choose one implementation over another? The
interface says nothing about the efficiency of the implementation. A circular
array is somewhat more efficient than a linked list, so it is generally
preferable. However, as usual, there is a price to pay. The circular array is a
<span class="docEmphasis">bounded</span> collection梚t has a finite capacity. If
you don't have an upper limit on the number of objects that your program will
collect, you may be better off with a linked list implementation after all.</p>
<p class="docText">This example illustrates another issue for the designer of a
collection class library. Strictly speaking, in a bounded collection, the
interface of the <tt>add</tt> method should indicate that the method can fail:</p>
<pre>class CircularArrayQueue
{
public void add(Object obj)
<span class="docEmphStrong">throws CollectionFullException</span>
. . .
}
</pre>
<p class="docText">That's a problem梟ow the <tt>CircularArrayQueue</tt> class
can't implement the <tt>Queue</tt> interface since you can't add exception
specifiers when overriding a method. Should one have two interfaces, <tt>
BoundedQueue</tt> and <tt>Queue</tt>? Or should the <tt>add</tt> method throw an
unchecked exception? There are advantages and disadvantages to both approaches.
It is these kinds of issues that make it genuinely hard to design a logically
coherent collection class library.</p>
<p class="docText">As we already mentioned, the Java library has no separate
class for queues. We just used this example to illustrate the difference between
interface and implementation since a queue has a simple interface and two
well-known distinct implementations. In the next section, you will see how the
Java library classifies the collections that it supports.</p>
<h4 class="docSection2Title" id="ch02lev2sec2">Collection and Iterator Interfaces in the Java
Library</h4>
<p class="docText">The fundamental interface for collection classes in the Java
library is the <tt>Collection</tt> interface. The interface has two fundamental
methods:</p>
<pre>boolean add(Object obj)
Iterator iterator()
</pre>
<p class="docText">There are several methods in addition to these two; we will
discuss them later.</p>
<p class="docText">The <tt>add</tt> method adds an object to the collection. The
<tt>add</tt> method returns <tt>true</tt> if adding the object actually changed
the collection, and <tt>false</tt> if the collection is unchanged. For example,
if you try to add an object to a set and the object is already present, then the
<tt>add</tt> request is rejected since sets reject duplicates.</p>
<p class="docText">The <tt>iterator</tt> method returns an object that
implements the <tt>Iterator</tt> interface梬e will describe that interface in a
moment. You can use the iterator object to visit the elements in the container
one by one.</p>
<p class="docText">The <tt>Iterator</tt> interface has three fundamental
methods:</p>
<pre>Object next()
boolean hasNext()
void remove()
</pre>
<p class="docText">By repeatedly calling the <tt>next</tt> method, you can visit
the elements from the collection one by one. However, if you reach the end of
the collection, the <tt>next</tt> method throws a <tt>NoSuchElementException</tt>.
Therefore, you need to call the <tt>hasNext</tt> method before calling <tt>next</tt>.
That method returns <tt>true</tt> if the iterator object still has more elements
to visit. If you want to inspect all elements in a collection, you request an
iterator and then keep calling the <tt>next</tt> method while <tt>hasNext</tt>
returns true.</p>
<pre>Iterator iter = c.iterator();
while (iter.hasNext())
{
Object obj = iter.next();
<span class="docEmphasis">do something with</span> obj
}
</pre>
<div class="docNote">
<p class="docNoteTitle">NOTE</p>
<table cellSpacing="0" cellPadding="1" width="90%" border="0">
<tr>
<td vAlign="top" width="60">
<img alt="graphics/note.gif" src="note.gif" align="left" border="0" width="54" height="53"><br>
</td>
<td vAlign="top">
<p class="docText">Old-timers will notice that the <tt>next</tt> and <tt>
hasNext</tt> methods of the <tt>Iterator</tt> interface serve the same
purpose as the <tt>nextElement</tt> and <tt>hasMoreElements</tt> methods
of an <tt>Enumeration</tt>. The designers of the Java collection library
could have chosen to extend the <tt>Enumeration</tt> interface. But they
disliked the cumbersome method names and chose to introduce a new
interface with shorter method names instead.</td>
</tr>
</table>
</div>
<p class="docText">Finally, the <tt>remove</tt> method removes the element that
was returned by the last call to <tt>next</tt>.</p>
<p class="docText">You may well wonder why the <tt>remove</tt> method is a part
of the <tt>Iterator</tt> interface. It is more efficient to remove an element if
you know <span class="docEmphasis">where</span> it is. The iterator knows about
<span class="docEmphasis">positions</span> in the collection. Therefore, the <tt>
remove</tt> method is a part of the <tt>Iterator</tt> interface. If you visited
an element that you didn't like, you can efficiently remove it.</p>
<p class="docText">There is an important conceptual difference between iterators
in the Java collection library and iterators in other libraries. In traditional
collection libraries such as the Standard Template Library of C++, iterators are
modeled after array indexes. Given such an iterator, you can look up the element
that is stored at that position, much like you can look up an array element <tt>
a[i</tt>] if you have an array index <tt>i</tt>. Independently of the lookup,
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -