tij0090.html

学习java的经典书籍

produces the value given the corresponding key, and 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>remove(Object
key)
</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
removes the key-value pair from the list. There are enumerations: 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>keys(&#160;)</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
produces an 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Enumeration</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
of the keys, and 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>elements(&#160;)</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
produces an 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Enumeration</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
of all the values. That&#8217;s all there is to a 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Dictionary</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">A
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Dictionary</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
isn&#8217;t terribly difficult to implement. Here&#8217;s a simple approach,
which uses two 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Vector</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">s,
one for keys and one for values:
</FONT><P></DIV>

<font color="#990000"><PRE><font color="#009900">//: AssocArray.java</font>
<font color="#009900">// Simple version of a Dictionary</font>
<font color="#0000ff">import</font> java.util.*;

<font color="#0000ff">public</font> <font color="#0000ff">class</font> AssocArray <font color="#0000ff">extends</font> Dictionary {
  <font color="#0000ff">private</font> Vector keys = <font color="#0000ff">new</font> Vector();
  <font color="#0000ff">private</font> Vector values = <font color="#0000ff">new</font> Vector();
  <font color="#0000ff">public</font> <font color="#0000ff">int</font> size() { <font color="#0000ff">return</font> keys.size(); }
  <font color="#0000ff">public</font> <font color="#0000ff">boolean</font> isEmpty() {
    <font color="#0000ff">return</font> keys.isEmpty();
  }
  <font color="#0000ff">public</font> Object put(Object key, Object value) {
    keys.addElement(key);
    values.addElement(value);
    <font color="#0000ff">return</font> key;
  }
  <font color="#0000ff">public</font> Object get(Object key) {
    <font color="#0000ff">int</font> index = keys.indexOf(key);
    <font color="#009900">// indexOf() Returns -1 if key not found:</font>
    <font color="#0000ff">if</font>(index == -1) <font color="#0000ff">return</font> <font color="#0000ff">null</font>;
    <font color="#0000ff">return</font> values.elementAt(index);
  }
  <font color="#0000ff">public</font> Object remove(Object key) {
    <font color="#0000ff">int</font> index = keys.indexOf(key);
    <font color="#0000ff">if</font>(index == -1) <font color="#0000ff">return</font> <font color="#0000ff">null</font>;
    keys.removeElementAt(index);
    Object returnval = values.elementAt(index);
    values.removeElementAt(index);
    <font color="#0000ff">return</font> returnval;
  }
  <font color="#0000ff">public</font> Enumeration keys() {
    <font color="#0000ff">return</font> keys.elements();
  }
  <font color="#0000ff">public</font> Enumeration elements() {
    <font color="#0000ff">return</font> values.elements();
  }
  <font color="#009900">// Test it:</font>
  <font color="#0000ff">public</font> <font color="#0000ff">static</font> <font color="#0000ff">void</font> main(String[] args) {
    AssocArray aa = <font color="#0000ff">new</font> AssocArray();
    <font color="#0000ff">for</font>(<font color="#0000ff">char</font> c = 'a'; c &lt;= 'z'; c++)
      aa.put(String.valueOf(c),
             String.valueOf(c)
             .toUpperCase());
    <font color="#0000ff">char</font>[] ca = { 'a', 'e', 'i', 'o', 'u' };
    <font color="#0000ff">for</font>(<font color="#0000ff">int</font> i = 0; i &lt; ca.length; i++)
      System.out.println("Uppercase: " +
             aa.get(String.valueOf(ca[i])));
  }
} <font color="#009900">///:~ </PRE></font></font><DIV ALIGN=LEFT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">The
first thing you see in the definition of 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>AssocArray</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
is that it 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>extends
Dictionary
</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.
This means that 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>AssocArray</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><I>is
a type of 
</I></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Dictionary</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">,
so you can make the same requests of it that you can a 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Dictionary</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.
If you make your own 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Dictionary</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">,
as is done here, all you need to do is fill in all the methods that are in 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Dictionary</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.
(And you 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><I>must</I></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
override all the methods because all of them &#8211; with the exception of the
constructor &#8211; are abstract.)
</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">The
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Vector</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">s
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>keys</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
and 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>values</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
are linked by a common index number. That is, if you call 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>put(&#160;)</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
with a key of &#8220;roof&#8221; and a value of &#8220;blue&#8221; (assuming
you&#8217;re associating the various parts of a house with the colors they are
to be painted) and there are already 100 elements in the 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>AssocArray</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">,
then &#8220;roof&#8221; will be the 101 element of 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>keys</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
and &#8220;blue&#8221; will be the 101 element of 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>values</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.
And if you look at 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>get(&#160;)</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">,
when you pass &#8220;roof&#8221; in as the key, it produces the index number
with 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>keys</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>indexOf(&#160;)</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">,
and then uses that index number to produce the value in the associated 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>values</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
vector.
</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">The
test in 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>main(&#160;)</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
is simple; it&#8217;s just a map of lowercase characters to uppercase
characters, which could obviously be done in a number of more efficient ways.
But it shows that 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>AssocArray</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
is functional.
</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">The
standard Java library contains only one embodiment of a 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Dictionary</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">,
called 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Hashtable</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.</FONT><A NAME="fnB34" HREF="#fn34">[34]</A><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
Java&#8217;s 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Hashtable</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
has the same basic interface as 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>AssocArray
</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">(since
they both inherit 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Dictionary</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">),
but it
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>
</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">differs
in one distinct way: efficiency. If you look at what must be done for a 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>get(&#160;)</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">,
it seems pretty slow to search through a 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Vector</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
for the key. This is where 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Hashtable</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
speeds things up. Instead of the tedious linear search for the key, it uses a
special value called a 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><I>hash
code
</I></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><I>
</I></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">The
hash code is a way to take some information in the object in question and turn
it into a &#8220;relatively unique&#8221; 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>int</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
for that object. All objects have a hash code, and <A NAME="Index797"></A></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>hashCode(&#160;)</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
is a method in the root class <A NAME="Index798"></A></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Object</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">.
A 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Hashtable
</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">takes
the 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>hashCode(&#160;)</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
of the object and uses it to quickly hunt for the key. This results in a
dramatic performance improvement.
</FONT><A NAME="fnB35" HREF="#fn35">[35]</A><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
The 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><I>way</I></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
that a 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Hashtable</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
works is beyond the scope of this book
</FONT><A NAME="fnB36" HREF="#fn36">[36]</A><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
&#8211; all you need to know is that 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Hashtable</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
is a fast 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Dictionary</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">,
and that a 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Dictionary</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
is a useful tool.
</FONT><P></DIV><DIV ALIGN=LEFT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">As
an example of the use of a 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Hashtable</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">,
consider a program to check the randomness of Java&#8217;s <A NAME="Index799"></A><A NAME="Index800"></A></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Math.random(&#160;)</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
method. Ideally, it would produce a perfect distribution of random numbers, but
to test this you need to generate a bunch of random numbers and count the ones
that fall in the various ranges. A 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Hashtable</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
is perfect for this, since it associates objects with objects (in this case,
the values produced by 
</FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black"><B>Math.random(&#160;)</B></FONT><FONT FACE="Carmina Md BT" SIZE=3 COLOR="Black">
with the number of times those values appear):
</FONT><P></DIV>