📄 _chapter 2.htm
字号:
<td class="docTableCell" vAlign="top">the new element</td>
</tr>
</table>
<p> </li>
<li>
<p class="docList"><tt>int indexOf(Object element)</tt></p>
<p class="docList">returns the position of the first occurrence of an element
equal to the specified element, or -1 if no matching element is found.</p>
<table cellSpacing="0" cellPadding="1" width="93%" border="1">
<colgroup span="3" align="left">
</colgroup>
<tr>
<td class="docTableCell" vAlign="top"><span class="docEmphasis">
Parameters:</span></td>
<td class="docTableCell" vAlign="top"><tt>element</tt></td>
<td class="docTableCell" vAlign="top">the element to match</td>
</tr>
</table>
<p> </li>
<li>
<p class="docList"><tt>int lastIndexOf(Object element)</tt></p>
<p class="docList">returns the position of the last occurrence of an element
equal to the specified element, or -1 if no matching element is found.</p>
<table cellSpacing="0" cellPadding="1" width="93%" border="1">
<colgroup span="3" align="left">
</colgroup>
<tr>
<td class="docTableCell" vAlign="top"><span class="docEmphasis">
Parameters:</span></td>
<td class="docTableCell" vAlign="top"><tt>element</tt></td>
<td class="docTableCell" vAlign="top">the element to match</td>
</tr>
</table>
<p> </li>
</ul>
<h5 class="docSection3Title" id="ch02lev3sec4"><span class="docEmphasis"><tt>
java.util.ListIterator</tt></span></h5>
<p><img alt="graphics/api.gif" src="api.gif" border="0" width="46" height="45"><br>
</p>
<ul>
<li>
<p class="docList"><tt>void add(Object element)</tt></p>
<p class="docList">adds an element before the current position.</p>
<table cellSpacing="0" cellPadding="1" width="93%" border="1">
<colgroup span="3" align="left">
</colgroup>
<tr>
<td class="docTableCell" vAlign="top"><span class="docEmphasis">
Parameters:</span></td>
<td class="docTableCell" vAlign="top">element</td>
<td class="docTableCell" vAlign="top">the element to add</td>
</tr>
</table>
<p> </li>
<li>
<p class="docList"><tt>void set(Object element)</tt></p>
<p class="docList">replaces the last element visited by <tt>next</tt> or <tt>
previous</tt> with a new element. Throws an <tt>IllegalStateException</tt> if
the list structure was modified since the last call to <tt>next</tt> or <tt>
previous</tt>.</p>
<table cellSpacing="0" cellPadding="1" width="93%" border="1">
<colgroup span="3" align="left">
</colgroup>
<tr>
<td class="docTableCell" vAlign="top"><span class="docEmphasis">
Parameters:</span></td>
<td class="docTableCell" vAlign="top">element</td>
<td class="docTableCell" vAlign="top">the new element</td>
</tr>
</table>
<p> </li>
<li>
<p class="docList"><tt>boolean hasPrevious()</tt></p>
<p class="docList">returns <tt>true</tt> if there is another element to visit
when iterating backwards through the list.</li>
<li>
<p class="docList"><tt>Object previous()</tt></p>
<p class="docList">returns the previous object. Throws a <tt>
NoSuchElementException</tt> if the beginning of the list has been reached.</li>
<li>
<p class="docList"><tt>int nextIndex()</tt></p>
<p class="docList">returns the index of the element that would be returned by
the next call to <tt>next</tt>.</li>
<li>
<p class="docList"><tt>int previousIndex()</tt></p>
<p class="docList">returns the index of the element that would be returned by
the next call to <tt>previous</tt>.</li>
</ul>
<h5 class="docSection3Title" id="ch02lev3sec5"><tt>java.util.LinkedList</tt></h5>
<p><img alt="graphics/api.gif" src="api.gif" border="0" width="46" height="45"><br>
</p>
<ul>
<li>
<p class="docList"><tt>LinkedList()</tt></p>
<p class="docList">constructs an empty linked list.</li>
<li>
<p class="docList"><tt>LinkedList(Collection elements)</tt></p>
<p class="docList">constructs a linked list and adds all elements from a
collection.</p>
<table cellSpacing="0" cellPadding="1" width="93%" border="1">
<colgroup span="3" align="left">
</colgroup>
<tr>
<td class="docTableCell" vAlign="top"><span class="docEmphasis">
Parameters:</span></td>
<td class="docTableCell" vAlign="top">elements</td>
<td class="docTableCell" vAlign="top">the elements to add</td>
</tr>
</table>
<p> </li>
<li>
<p class="docList"><tt>void addFirst(Object element)</tt></li>
<li>
<p class="docList"><tt>void addLast(Object element)</tt></p>
<p class="docList">add an element to the beginning or the end of the list.</p>
<table cellSpacing="0" cellPadding="1" width="93%" border="1">
<colgroup span="3" align="left">
</colgroup>
<tr>
<td class="docTableCell" vAlign="top"><span class="docEmphasis">
Parameters:</span></td>
<td class="docTableCell" vAlign="top">element</td>
<td class="docTableCell" vAlign="top">the element to add</td>
</tr>
</table>
<p> </li>
<li>
<p class="docList"><tt>Object getFirst()</tt></li>
<li>
<p class="docList"><tt>Object getLast()</tt></p>
<p class="docList">return the element at the beginning or the end of the list.</li>
<li>
<p class="docList"><tt>Object removeFirst()</tt></li>
<li>
<p class="docList"><tt>Object removeLast()</tt></p>
<p class="docList">remove and return the element at the beginning or the end
of the list.</li>
</ul>
<h4 class="docSection2Title" id="ch02lev2sec4">Array Lists</h4>
<p class="docText">In the preceding section, you saw the <tt>List</tt> interface
and the <tt>LinkedList</tt> class that implements it. The <tt>List</tt>
interface describes an ordered collection in which the position of elements
matters. There are two protocols for visiting the elements: through an iterator
and by random access with methods <tt>get</tt> and <tt>set</tt>. The latter are
not appropriate for linked lists, but of course they make a lot of sense for
arrays. The collections library supplies the familiar <tt>ArrayList</tt> class
that implements the <tt>List</tt> interface. An <tt>ArrayList</tt> encapsulates
a dynamically reallocated <tt>Object[]</tt> array.</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 are a veteran Java programmer, you will have
used the <tt>Vector</tt> class whenever you needed a dynamic array. Why
use an <tt>ArrayList</tt> instead of a <tt>Vector</tt>? There is one
simple reason. All methods of the <tt>Vector</tt> class are
<span class="docEmphasis">synchronized.</span> It is safe to access a <tt>
Vector</tt> object from two threads. But if you only access a vector from
a single thread梑y far the more common case梱our code wastes quite a bit
of time with synchronization. In contrast, the <tt>ArrayList</tt> methods
are not synchronized. We recommend that you use an <tt>ArrayList</tt>
instead of a <tt>Vector</tt> whenever you don't need synchronization.</td>
</tr>
</table>
</div>
<h4 class="docSection2Title" id="ch02lev2sec5">Hash Sets</h4>
<p class="docText">Linked lists and arrays let you specify in which order you
want to arrange the elements. However, if you are looking for a particular
element and you don't remember its position, then you need to visit all elements
until you find a match. That can be time-consuming if the collection contains
many elements. If you don't care about the ordering of the elements, then there
are data structures that let you find elements much faster. The drawback is that
those data structures give you no control over the order in which the elements
appear. The data structures organize the elements in an order that is convenient
for their own purposes.</p>
<p class="docText">A well-known data structure for finding objects quickly is
the <span class="docEmphasis">hash table.</span> A hash table computes an
integer, called the <span class="docEmphasis">hash code,</span> for each object.
You will see in the next section how these hash codes are computed. What's
important for now is that hash codes can be computed quickly and that the
computation only depends on the state of the object that needs to be hashed, and
not on the other objects in the hash table.</p>
<p class="docText">A hash table is an array of linked lists. Each list is called
a <span class="docEmphasis">bucket</span> (see
<a class="docLink" href="#ch02fig08">Figure 2-8</a>). To find the place of an
object in the table, compute its hash code and reduce it modulo the total number
of buckets. The resulting number is the index of the bucket that holds the
element. For example, if an object has hash code 345 and there are 101 buckets,
then the object is placed in bucket 42 (because the remainder of the integer
division 345/101 is 42). Perhaps you are lucky and there is no other element in
that bucket. Then, you simply insert the element into that bucket. Of course, it
is inevitable that you sometimes hit a bucket that is already filled. This is
called a <span class="docEmphasis">hash collision.</span> Then, you need to
compare the new object with all objects in that bucket to see if it is already
present. Provided that the hash codes are reasonably randomly distributed and
the number of buckets is large enough, only a few comparisons should be
necessary.</p>
<center>
<h5 id="ch02fig08" class="docFigureTitle">Figure 2-8. A hash table</h5>
<p>
<img alt="graphics/02fig08.gif" src="02fig08.gif" border="0" width="300" height="235"></p>
</center>
<p class="docText">If you want more control over the performance of the hash
table, you can specify the initial bucket count. The bucket count gives the
number of buckets that are used to collect objects with identical hash values.
If too many elements are inserted into a hash table, the number of collisions
increases and retrieval performance suffers.</p>
<p class="docText">If you know approximately how many elements will eventually
be in the table, then you should set the initial bucket count to about 150
percent of the expected element count. Some researchers believe that it is a
good idea to make the size of the hash table a prime number to prevent a
clustering of keys. The evidence for this isn't conclusive, but it certainly
can't hurt. For example, if you need to store about 100 entries, set the initial
bucket size to 151.</p>
<p class="docText">Of course, you do not always know how many elements you need
to store, or your initial guess may be too low. If the hash table gets too full,
it needs to be <span class="docEmphasis">rehashed.</span> To rehash the table, a
table with more buckets is created, all elements are inserted into the new
table, and the original table is discarded. In the Java programming language,
the <span class="docEmphasis">load factor</span> determines when a hash table is
rehashed. For example, if the load factor is 0.75 (which is the default) and the
hash table becomes more than 75 percent full, then the table is automatically
rehashed, using twice as many buckets. For most applications, it is reasonable
to leave the load factor at 0.75.</p>
<p class="docText">Hash tables can be used to implement several important data
structures. The simplest among them is the <span class="docEmphasis">set</span>
type. A set is a collection of elements without duplicates. The <tt>add</tt>
method of a set first tries to find the object to be added, and only adds it if
it is not yet present.</p>
<p class="docText">The Java collections library supplies a <tt>HashSet</tt>
class that implements a set based on a hash table. At the time of this writing,
the default constructor <tt>HashSet</tt> constructs a hash table with 101
buckets and a load factor of 0.75. These values may change in future releases.
If you care at all about these values, you should specify your own, with the
constructors</p>
<pre>HashSet(int initialCapacity)
HashSet(int initialCapacity, float loadFactor)
</pre>
<p class="docText">You add elements with the <tt>add</tt> method. The <tt>
contains</tt> method is redefined to make a fast lookup to find if an element is
already present in the set. It only checks the elements in one bucket and not
all elements in the collection.</p>
<p class="docText">The hash set iterator visits all buckets in turn. Since the
hashing scatters the elements around in the table, they are visited in seemingly
random order. You would only use a hash set if you don't care about the ordering
of the elements in the collection.</p>
<p class="docText">The sample program at the end of this section (<a class="docLink" href="#ch02list02">Example
2-2</a>) reads words from <tt>System.in</tt>, adds them to a set, and finally
prints out all words in the set. For example, you can feed the program the text
from <span class="docEmphasis">Alice in Wonderland</span> (which you can obtain
from <a class="docLink" href="http://www.gutenberg.net" target="_blank">
www.gutenberg.net</a>) by launching it from a command shell as</p>
<pre>java SetTest < alice30.txt
</pre>
<p class="docText">The program reads all words from the input and adds them to
the hash set. It then iterates through the unique words in the set and finally⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -