中文Thinking in Java：chap11

Thinking in Java 3rd Edition
g12544 1 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
11:对象的集合
如果程序的对象数量有限，且寿命可知，那么这个程序是相当简单的。
一般来说，程序都是根据具体情况在不断地创建新的对象，而这些情况又只有在程序运行的时候才能确定。不到运行时你是不会知道你到底需要多少对象，甚至是什么类型的对象。为了解决这种常见的编程问题，你得有办法能在任何时间，任何地点，创建任何数量的对象。所以你不能指望用命名的reference来持有每个对象,
MyObject myReference;
原因就在于，你不可能知道究竟需要多少这样的对象。
针对这个相当关键的问题，绝大多数语言都提供了某种解决办法。Java
也提供了好几种持有对象(或者更准确的说，是对象的reference) 的方法。我们前面讨论的数组是语言内置的数据类型。此外，Java 的工具类库g17836g2265g6336一g3883g8616g17751g4448g6984的g4493g3132类(container classes也g15999g12228为
collection classes，g1306是g11013于Collectiong15999Java 2用来命名类库的某个g4388g19610，所以我g17836是用g8022g6336g5627更g5390的g7427语"container")。g4439提供了g3809g7446
而g12946g14280的方法来持有甚至是g6817g6523你的对象。
数组
我们g5062g13475在g125444g12468的g7380g2530g18108g2010，对数组的绝大多数内g4493g1328了g5529要的g1183g13473，
此外我们g17836g9448g12046了g3926何定g1053g2656g2033g3999g2282一个数组。g7424g12468的所关g8892的问题是
g256持有对象g257，而数组只是g1866g1025的一个方法。g18039么数组又是g1985什么要我们
g3926此g18337g16282的g2614?
数组g994g1866g4439g4493g3132的g2318g2047体g10628在g989个方面：g6940g10587，类型g16794g2047以g2462可以持有
primitives。数组是Java提供的，能g19555g7438g4396g1660g2656g16787问reference序g2027的
g16844多方法g1025的，g7380g20652g6940的一种。数组是一个g12628g2345的g13459g5627序g2027，所以g4439可以
g5567g17907的g16787问g1866g1025的g1815g13044。g1306是g17907g5242是有g1207g1227的g727当你创建了一个数组g1055
g2530，g4439的g4493量就g3278定了，而g1000在g1866g10995命g2620g7411g18336不能g6925g2476。也g16780你会提g16770g1820
创建一个数组，g12573到g5567不g3827用的时候，g1889创建一个新的，g9994g2530g4570g7099数组g18336
的referenceg1852g18108g4560到新的g18336面。g1866g4466(我们以g2530会g16774的)ArrayList就是这么g1582的。g1306是这种g9801g8975g5627所g5114来的g5332g19156，g1363得ArrayList的g6940g10587g8616
g17227数组有了g7138g7186g991g19489。
C++的vector g4493g3132类确g4466能知道g4439到底持有了什么类型的对象，g1306是
g994Java的数组相g8616，g4439又有g2490一个g13582点：C++ vector的[]运g12651g12538不
Chapter 11,Collections of Objects
g12544 2 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g1328g17805g11040g7828查，所以你可能会不知不觉就过了g110401。而Java对数组g2656g4493g3132都
g1582g17805g11040g7828查g727g3926果过了g11040，g4439就会给一个RuntimeException。这种异常表g7138这个错误是g11013程序员造成的，这样你就用不着g1889在程序g18336面g7828查了(译者g8892：这g18336的原文有些模棱两可，我想他要表达的意思可能是以g991
两种g1025的一个。一是指，你不用g1889g1328g17805g11040g7828查了g727二是指，通过异常信息，你就可以知道错误是g11013过g11040造成的，因而不用查源g1207码了)。顺便说一g991，C++的vector不g1328g17805g11040g7828查是为了g17907g5242g727而在Java，不论是数组或是用g4493g3132，你都得面对g17805g11040g7828查所g5114来的g3278定的g5627能g991g19489。
g7424g12468所探讨的g1866g4439泛型g4493g3132类g17836g2265g6336List，Set g2656Map。g4439们处理对象的时候就好像这些对象都没有自己的具体类型一样。也就是说，g4493g3132g4570g4439
所含的g1815g13044都看成是(Javag1025所有类的根类)Object的。这样你只需创建一种g4493g3132，就能把所有类型的对象g1852都放进去。从这个角g5242来看，这种
g1582法很不错(只是苦了primitive。g3926果是常量，你g17836可以用Java的
primitive的wrapper类g727g3926果是g2476量，g18039就只能放到你自己的类g18336
了)。g994g1866他泛型g4493g3132相g8616，这g18336体g10628出数组的g12544二个优势：创建数组的时候，你也同时指g7138了g4439所持有的对象的类型(这又引出了g12544g989点 —— 数组可以持有primitives，而g4493g3132却不行)。也就是说，g4439会在编译的时候
g1328类型g7828查，从而防止你插入错误类型的对象，或者是在提取对象的时候把对象的类型给搞错了。Java在编译g2656运行时都能阻止你g4570一个不恰当的消息传给对象。所以这并不是说g1363用g4493g3132就有什么危险，只是g3926果编译
g3132能g3827帮你指定，g18039么程序运行会更g5567，g7380终用户也会g17751少受到程序运行异常的骚扰。
从g6940g10587g2656类型g7828查的角g5242来看，g1363用数组总是没错的。g1306是，g3926果你在解决一个更为一般的问题，g18039数组就会g7186得功能太弱了点。g7424g12468g1820g16774数组，
g9994g2530g19610g1025g12946力讨论Java的g4493g3132类。
数组是第一流的对象
不管你用的是g18039种类型的数组，数组的标g16794g12538g4466际上都是一个g256创建在堆
(heap)g18336的g4466g4466在在的对象的g257reference。g4466际上是g18039个对象持有g1866他对象的reference。你既可以用数组的g2033g3999g2282语句，隐含地创建这个对象，也可以用new表达式，g7138确地创建这个对象。只读的length属g5627
能告诉你数组能g4396g1660多少g1815g13044。g4439是数组对象的一g18108g2010(g4466际上也是你唯一能g16787问的属g5627或方法)。‘[]’语法是g2490一条g16787问数组对象的途径。
g991面这段程序g9448g12046了几种g2033g3999g2282数组的办法，以g2462g3926何g4570数组的
reference赋给不同的数组对象。此外，g4439g17836g7186g12046了，对象数组g2656
primitives数组在g1363用方法上几乎是g4448g1852相同。唯一的不同是，对象数组持有reference，而primitive数组则直接持有值。
//,c11:ArraySize.java
1g993g17819g11507g11352g5831g11705g17959vectorg11352g4493g18339g7389g3822g3835g712g17836g7171g7389g2162g8873g11352g712g7368g1321g1929at( )g7053g8873g11842g4466g1582g17805g11040g7828g7609g452
Thinking in Java 3rd Edition
g12544 3 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
// Initialization & re-assignment of arrays,
import com.bruceeckel.simpletest.*;
class Weeble {} // A small mythical creature
public class ArraySize {
private static Test monitor = new Test( );
public static void main(String[] args) {
// Arrays of objects,
Weeble[] a; // Local uninitialized variable
Weeble[] b = new Weeble[5]; // Null references
Weeble[] c = new Weeble[4];
for(int i = 0; i < c.length; i++)
if(c[i] == null) // Can test for null
reference
c[i] = new Weeble( );
// Aggregate initialization,
Weeble[] d = {
new Weeble( ),new Weeble( ),new Weeble( )
};
// Dynamic aggregate initialization,
a = new Weeble[] {
new Weeble( ),new Weeble( )
};
System.out.println("a.length=" + a.length);
System.out.println("b.length = " + b.length);
// The references inside the array are
// automatically initialized to null,
for(int i = 0; i < b.length; i++)
System.out.println("b[" + i + "]=" + b[i]);
System.out.println("c.length = " + c.length);
System.out.println("d.length = " + d.length);
a = d;
System.out.println("a.length = " + a.length);
// Arrays of primitives,
int[] e; // Null reference
int[] f = new int[5];
int[] g = new int[4];
for(int i = 0; i < g.length; i++)
g[i] = i*i;
int[] h = { 11,47,93 };
// Compile error,variable e not initialized,
//!System.out.println("e.length=" + e.length);
System.out.println("f.length = " + f.length);
// The primitives inside the array are
// automatically initialized to zero,
for(int i = 0; i < f.length; i++)
System.out.println("f[" + i + "]=" + f[i]);
System.out.println("g.length = " + g.length);
System.out.println("h.length = " + h.length);
e = h;
System.out.println("e.length = " + e.length);
e = new int[] { 1,2 };
System.out.println("e.length = " + e.length);
monitor.expect(new String[] {
"a.length=2",
"b.length = 5",
"b[0]=null",
"b[1]=null",
Chapter 11,Collections of Objects
g12544 4 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
"b[2]=null",
"b[3]=null",
"b[4]=null",
"c.length = 4",
"d.length = 3",
"a.length = 3",
"f.length = 5",
"f[0]=0",
"f[1]=0",
"f[2]=0",
"f[3]=0",
"f[4]=0",
"g.length = 4",
"h.length = 3",
"e.length = 3",
"e.length = 2"
});
}
} ///:~
数组a是一个尚未g2033g3999g2282的局g18108g2476量，在你g4570g1866正确地g2033g3999g2282g1055前，编译
g3132禁止你对这个referenceg1328任何事情。数组b是一个g5062g13475进行了g2033g3999
g2282的数组，g4439g15999连到了一个g256Weeble对象的 referenceg257的数组，只是这个数组g18336面g17836没有真正放上Weeble对象。g1306是g11013于b指向的是一个合法的对象，所以你g5062g13475可以查询g1866g4493量大小了。这就g5114来一个小问题：你没法知道数组g18336面究竟放了多少g1815g13044，因为length只是告诉你数组能放多少g1815g13044，也就是说是数组对象的g4493量，而不是g4439真正g5062g13475持有的
g1815g13044的数量。g1306是，创建数组对象的时候，g4439所持有的reference都会
g15999自动地g2033g3999g2282为null，所以你可以通过g7828查数组的某个g256槽位g257是否为null，来判断g4439是否持有对象。以此类推，primitive的数组，会自动
g4570数字g2033g3999g2282为零，字g12538g2033g3999g2282为(char)0，booleang2033g3999g2282为
false。
数组cg9448g12046了数组对象的创建，g19555g2530g4439直接用Weeble对象对数组各个
g256槽位g257进行赋值。数组d就是所g16871g256总体g2033g3999g2282(aggregate
initialization)g257的语法，g4439只用一条语句，就创建了数组对象(隐含地g1363
用了new，就像对数组c)，并g1000用Weeble对象进行了g2033g3999g2282。
g991一个数组的g2033g3999g2282可以g15999理解为g256动g5589的总体g2033g3999g2282(dynamic
aggregate initialization)g257。d所g1363用的g256总体g2033g3999g2282g257语句，只能在定g1053d的时候用。g1306是用这种语法，你就可以在任何地方创建g2656g2033g3999g2282数组对象。g8616方说，g1563g16786hide( )是一个g1363用Weeble对象的数组g1582g2454数的方法。g18039么，你可以这样g16855用,
hide(d);
Thinking in Java 3rd Edition
g12544 5 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g1306是你也可以动g5589地创建一个数组，把g4439当g1328g2454数传给hide( ),
hide(new Weeble[] { new Weeble( ),new Weeble( ) });
在很多情况g991，这能给你的编程g5114来便g2045。
表达式,
a = d;
g9448g12046了g3926何g4570一个reference指向g2490一个数组对象。这么g1582g17331g1363用g1866他对象的refernce没什么两样。g10628在ag2656d都指向堆g1025的同一个数组对象。
ArraySize.java的g12544二g18108g2010g5224g5461了primitive数组的工g1328方式g2656对象数组的几乎一g6732一样。只是g4439能直接持有primitive的值。
primitive的容器
g4493g3132类只能持有Object对象的reference。而数组g19512了能持有
Objects的referenceg1055外，g17836可以直接持有primitive。当g9994可以g1363
用g16844g3926Integer，Doubleg1055类的wrapper类，把primitive的值放到
g4493g3132g1025，g1306这样总有点g5630g5630的。此外，primitive数组的g6940g10587要g8616
wrapper类g4493g3132的g20652出g16780多。
当g9994，g3926果你g1363用primitive的时候，g17836需要g18039种g256能g19555需要自动g6205g4649
的g257g4493g3132类的g9801g8975g5627，g18039就不能用数组了。你只能用g4493g3132来g4396g1660
primitive的wrapper类。也g16780你会想，g5224g16825为每种primitive都提供一个ArrayList，g1306是g17963g6034的是Java没为你准g3803。2
返回一个数组
g1563g16786你g1901了一个方法，g4439g17832g3250的不是一个而是一组g1008g16211。在Cg2656C++g1055
类的语言g18336，这g1226事就有些g19602办了。因为你不能g17832g3250一个数组，你只能g17832
g3250一个指向数组的指针。g11013于要处理g256g6523g2058数组g10995命g2620g7411g257g1055类的g21647g9914
事，这么g1582很g4493g7143会出错，g7380g2530g4560g14280内g4396g8856g9443。
Javag18331取了类g1296的解决方g7708，g1306是不同g1055处在于，g4439g17832g3250的g256就是一个数组g257。g994C++不同，你g8716g17840也不g5529为Java的数组g6817g5527——只要你g17836
需要g4439，g4439就g17836在g727一g7098你用g4448了，g3415g3346g3250g6922g3132会帮你把g4439g6183g6207g5190g1940。
2g17837g4613g7171C++g7138g7186g8616Javag5390g11352g3332g7053g1114g712g3252g1038g4439g11352templateg1863g19202g16801g6915g6357g2454g6980g2282g12879g3423(parameterized type)g452
Chapter 11,Collections of Objects
g12544 6 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g991面的g1375g4388g9448g12046了g3926何g17832g3250一个String数组,
//,c11:IceCream.java
// Returning arrays from methods,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class IceCream {
private static Test monitor = new Test( );
private static Random rand = new Random( );
public static final String[] flavors = {
"Chocolate","Strawberry","Vanilla Fudge Swirl",
"Mint Chip","Mocha Almond Fudge","Rum Raisin",
"Praline Cream","Mud Pie"
};
public static String[] flavorSet(int n) {
String[] results = new String[n];
boolean[] picked = new boolean[flavors.length];
for(int i = 0; i < n; i++) {
int t;
do
t = rand.nextInt(flavors.length);
while(picked[t]);
results[i] = flavors[t];
picked[t] = true;
}
return results;
}
public static void main(String[] args) {
for(int i = 0; i < 20; i++) {
System.out.println(
"flavorSet(" + i + ") = ");
String[] fl = flavorSet(flavors.length);
for(int j = 0; j < fl.length; j++)
System.out.println("\t" + fl[j]);
monitor.expect(new Object[] {
"%% flavorSet\\(\\d+\\) = ",
new TestExpression("%%
\\t(Chocolate|Strawberry|"
+ "Vanilla Fudge Swirl|Mint Chip|Mocha
Almond "
+ "Fudge|Rum Raisin|Praline Cream|Mud
Pie)",8)
});
}
}
} ///:~
flavorSet( ) 创建了一个名为results 的String数组。这个数组的
g4493量是g11013传给g4439的g2454数n所决定的。接g991来g4439从flavors数组g18336面g19555g7438
g17885g6333flavors(译者g8892：表g12046g1924g9620g1952的g2487g2631)，放到resultsg1025，g7380g2530g17832g3250
results。g17832g3250数组g17331g17832g3250对象没什么两样——都是一个reference。因此数组是不是在flavorSet( )或是g1866他什么地方创建的并不g18337要。只要
Thinking in Java 3rd Edition
g12544 7 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
你g17836需要，g4439就不会消g3845g727一g7098你用g4448了，g3415g3346g3250g6922g3132g17139g17143帮你g6922g6354g5190
g1940。
g1889g19480g5114说一g991，flavorSet( )g19555g7438g17885g6333flavors的时候，会g7828查g18039个
flavor以前是不是没g15999g17885g1025过。这是g11013dog5502g10627g1582的。g4439不断的g1328g19555g7438g17885
g6333，直到g6226到一个在picked数组g1025g17836没有的。(当g9994，也可以用g256g8616g17751
Stringg257的方式来g7828查g19555g7438g17885出的flavor是不是g5062g13475在results数组g1025
了。)g3926果成功，g4439会g9167g2164这条g16772g5417，g9994g2530g4559g6226g991一个(g17894g3698i)。
main( )会g6183g2372出20g3883flavors，这样你就能看到，每g8437flavorSet( )
都是g19555g7438g17885g6333flavors的。g3926果把g17767出g4560到文g1226你就能看得更g9177g7982。只是
g16772着看文g1226的时候，你只是想g6373一个而不是真的想g2519g1924g9620g1952。
Arrays 类
java.utilg18336面有一个Arrays类，g4439g2265g6336了一组可用于数组的static
方法，这些方法都是一些g4466用工具。g1866g1025有g3247个g3534g7424方法：用来g8616g17751两个数组是否相g12573的equals( )g727用来g3647g1817数组的fill( )g727用来对数组进行
g6502序的sort( )g727以g2462用于在一个g5062g6502序的数组g1025查g6226g1815g13044的
binarySearch( )。所有这些方法都对primitiveg2656Object进行了g18337
g17745。此外g17836有一个asList( )方法，g4439接受一个数组，g9994g2530把g4439g17728成一个
Listg4493g3132。g2530面你会g4410到。
g15441g9994Arraysg17836是有用的，g1306g4439的功能并不g4448g6984。g1042g1375来说，g3926果g4439能g16765
我们不用g1901forg5502g10627就能直接g6183g2372数组，g18039就好了。此外，正g3926你所看到的，fill( )只能用一个值g3647数组。所以，g3926果g3926果你想把g19555g7438g10995成的数字
g3647进数组的g16817，fill( )是g7092能为力的。
因此为Arrays类提供一些g20081外的功能g17836是有意g1053的。为方便g17227g18504，我把
g4439放到package com.bruceeckel.utilg18336。g4439可以g6183g2372任何类型的数组g727并g1000用g256你定g1053的generator对象g10995成的g257值或对象g3647g1817一个数组。
g11013于要为各种primitive以g2462Objectg7393g2165，程序g18336有大量的几乎是g18337g3809
的g1207码。3g8616g3926，next( )g5529g20047根据不同的情况g17832g3250不同的类型，所以每种类型都需要一个g256generatorg257 接g2487。
//,com:bruceeckel:util:Generator.java
package com.bruceeckel.util;
public interface Generator { Object next( ); } ///:~
3 C++g11352g12255g5219g2604g1262g16285g5483g712g3926g7536g14033g11004g21676g16760g2454g6980g2656g8181g7507g11352g16817g712g2499g1209g4581g1901g5468g3822g1207g11733g452g13792Pythong11352g12255g5219g2604g2029g1262g16760
g1038g712g17837g1022g12879g5223g7424g17535g4613g7171g3822g1325g11352g452
Chapter 11,Collections of Objects
g12544 8 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
//,com:bruceeckel:util:BooleanGenerator.java
package com.bruceeckel.util;
public interface BooleanGenerator { boolean
next( ); } ///:~
//,com:bruceeckel:util:ByteGenerator.java
package com.bruceeckel.util;
public interface ByteGenerator { byte next( ); }
///:~
//,com:bruceeckel:util:CharGenerator.java
package com.bruceeckel.util;
public interface CharGenerator { char next( ); }
///:~
//,com:bruceeckel:util:ShortGenerator.java
package com.bruceeckel.util;
public interface ShortGenerator { short next( ); }
///:~
//,com:bruceeckel:util:IntGenerator.java
package com.bruceeckel.util;
public interface IntGenerator { int next( ); } ///:~
//,com:bruceeckel:util:LongGenerator.java
package com.bruceeckel.util;
public interface LongGenerator { long next( ); }
///:~
//,com:bruceeckel:util:FloatGenerator.java
package com.bruceeckel.util;
public interface FloatGenerator { float next( ); }
///:~
//,com:bruceeckel:util:DoubleGenerator.java
package com.bruceeckel.util;
public interface DoubleGenerator { double next( ); }
///:~
Thinking in Java 3rd Edition
g12544 9 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
Arrays2g2265含了很多toString( )方法以g18337g17745各种类型。这些方法能g16765
你很方便地g6183g2372出一个数组。toString( )方法用了StringBuffer而不是String对象。这是出于运行g6940g10587的g13783g15397g727当你需要g18337g3809g16855用一个方法以组g16025字g12538g1030的时候，g17751为g7138g7246的g17885g6333g17836是g1363用g6940g10587更g20652的
StringBuffer，而不是更方便的String。这g18336，创建StringBuffer
的时候用了一个g2033g3999值，g9994g2530g1889g4439g2530面接String。g7380g2530，把resultg17728
g6454成Stringg1889g17832g3250,
//,com:bruceeckel:util:Arrays2.java
// A supplement to java.util.Arrays,to provide
additional
// useful functionality when working with arrays,
Allows
// any array to be converted to a String,and to be
filled
// via a user-defined "generator" object,
package com.bruceeckel.util;
import java.util.*;
public class Arrays2 {
public static String toString(boolean[] a) {
StringBuffer result = new StringBuffer("[");
for(int i = 0; i < a.length; i++) {
result.append(a[i]);
if(i < a.length - 1)
result.append(",");
}
result.append("]");
return result.toString( );
}
public static String toString(byte[] a) {
StringBuffer result = new StringBuffer("[");
for(int i = 0; i < a.length; i++) {
result.append(a[i]);
if(i < a.length - 1)
result.append(",");
}
result.append("]");
return result.toString( );
}
public static String toString(char[] a) {
StringBuffer result = new StringBuffer("[");
for(int i = 0; i < a.length; i++) {
result.append(a[i]);
if(i < a.length - 1)
result.append(",");
}
result.append("]");
return result.toString( );
}
public static String toString(short[] a) {
StringBuffer result = new StringBuffer("[");
for(int i = 0; i < a.length; i++) {
result.append(a[i]);
if(i < a.length - 1)
result.append(",");
}
Chapter 11,Collections of Objects
g12544 10 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
result.append("]");
return result.toString( );
}
public static String toString(int[] a) {
StringBuffer result = new StringBuffer("[");
for(int i = 0; i < a.length; i++) {
result.append(a[i]);
if(i < a.length - 1)
result.append(",");
}
result.append("]");
return result.toString( );
}
public static String toString(long[] a) {
StringBuffer result = new StringBuffer("[");
for(int i = 0; i < a.length; i++) {
result.append(a[i]);
if(i < a.length - 1)
result.append(",");
}
result.append("]");
return result.toString( );
}
public static String toString(float[] a) {
StringBuffer result = new StringBuffer("[");
for(int i = 0; i < a.length; i++) {
result.append(a[i]);
if(i < a.length - 1)
result.append(",");
}
result.append("]");
return result.toString( );
}
public static String toString(double[] a) {
StringBuffer result = new StringBuffer("[");
for(int i = 0; i < a.length; i++) {
result.append(a[i]);
if(i < a.length - 1)
result.append(",");
}
result.append("]");
return result.toString( );
}
// Fill an array using a generator,
public static void fill(Object[] a,Generator gen)
{
fill(a,0,a.length,gen);
}
public static void
fill(Object[] a,int from,int to,Generator gen)
{
for(int i = from; i < to; i++)
a[i] = gen.next( );
}
public static void
fill(boolean[] a,BooleanGenerator gen) {
fill(a,0,a.length,gen);
}
public static void
Thinking in Java 3rd Edition
g12544 11 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
fill(boolean[] a,int from,int
to,BooleanGenerator gen){
for(int i = from; i < to; i++)
a[i] = gen.next( );
}
public static void fill(byte[] a,ByteGenerator
gen) {
fill(a,0,a.length,gen);
}
public static void
fill(byte[] a,int from,int to,ByteGenerator gen)
{
for(int i = from; i < to; i++)
a[i] = gen.next( );
}
public static void fill(char[] a,CharGenerator
gen) {
fill(a,0,a.length,gen);
}
public static void
fill(char[] a,int from,int to,CharGenerator gen)
{
for(int i = from; i < to; i++)
a[i] = gen.next( );
}
public static void fill(short[] a,ShortGenerator
gen) {
fill(a,0,a.length,gen);
}
public static void
fill(short[] a,int from,int to,ShortGenerator
gen) {
for(int i = from; i < to; i++)
a[i] = gen.next( );
}
public static void fill(int[] a,IntGenerator gen)
{
fill(a,0,a.length,gen);
}
public static void
fill(int[] a,int from,int to,IntGenerator gen)
{
for(int i = from; i < to; i++)
a[i] = gen.next( );
}
public static void fill(long[] a,LongGenerator
gen) {
fill(a,0,a.length,gen);
}
public static void
fill(long[] a,int from,int to,LongGenerator gen)
{
for(int i = from; i < to; i++)
a[i] = gen.next( );
}
public static void fill(float[] a,FloatGenerator
gen) {
fill(a,0,a.length,gen);
}
public static void
Chapter 11,Collections of Objects
g12544 12 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
fill(float[] a,int from,int to,FloatGenerator
gen) {
for(int i = from; i < to; i++)
a[i] = gen.next( );
}
public static void fill(double[] a,
DoubleGenerator gen){
fill(a,0,a.length,gen);
}
public static void
fill(double[] a,int from,int to,DoubleGenerator
gen) {
for(int i = from; i < to; i++)
a[i] = gen.next( );
}
private static Random r = new Random( );
public static class
RandBooleanGenerator implements BooleanGenerator {
public boolean next( ) { return
r.nextBoolean( ); }
}
public static class
RandByteGenerator implements ByteGenerator {
public byte next( ) { return
(byte)r.nextInt( ); }
}
private static String ssource =
"ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxy
z";
private static char[] src = ssource.toCharArray( );
public static class
RandCharGenerator implements CharGenerator {
public char next( ) {
return src[r.nextInt(src.length)];
}
}
public static class
RandStringGenerator implements Generator {
private int len;
private RandCharGenerator cg = new
RandCharGenerator( );
public RandStringGenerator(int length) {
len = length;
}
public Object next( ) {
char[] buf = new char[len];
for(int i = 0; i < len; i++)
buf[i] = cg.next( );
return new String(buf);
}
}
public static class
RandShortGenerator implements ShortGenerator {
public short next( ) { return
(short)r.nextInt( ); }
}
public static class
RandIntGenerator implements IntGenerator {
private int mod = 10000;
Thinking in Java 3rd Edition
g12544 13 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
public RandIntGenerator( ) {}
public RandIntGenerator(int modulo) { mod =
modulo; }
public int next( ) { return r.nextInt(mod); }
}
public static class
RandLongGenerator implements LongGenerator {
public long next( ) { return r.nextLong( ); }
}
public static class
RandFloatGenerator implements FloatGenerator {
public float next( ) { return r.nextFloat( ); }
}
public static class
RandDoubleGenerator implements DoubleGenerator {
public double next( ) {return r.nextDouble( );}
}
} ///:~
要想用g10995成g3132(generator)来g3647g9397数组，就要传一个合g17878的interface
的reference给fill( )方法。这个接g2487g5224g16825有一个能g10995成正确类型的对象的next( )方法(g11013接g2487g3926何g4466g10628来决定)。fill( )方法只是g12628g2345地g16855用
next( )，直到g3647g9397所需的g14551g3272。g10628在你可以通过g4466g10628合g17878的interface
来创建generator，g9994g2530用fill( )来g1363用这个generator。
g8991g16809的时候g19555g7438数g10995成g3132就会很有用了，所以g19512了用Stringg10995成g3132来g1207
表Objectg1055外，我们g17836创建了一g6984g3883内g18108类来g4466g10628所有primitiveg10995成
g3132的接g2487。你会看到RandStringGenerator用
RandCharGenerator来g3647g1817一个char的数组，g9994g2530g1889把这个数组g17728
g6454成String。这个数组的大小是g11013g7512造g2001数的g2454数所决定的。
g21676g16760情况g991，为了不g16765g10995成的数字太大，RandIntGenerator会对
10，000取模。g1306是g18337g17745的g7512造g2001数g1813g16780你g17885g6333一个更小的数值。
g991面的程序在g8991g16809类库的同时g17836g12046g14551了g16825g3926何g1363用类库。
//,c11:TestArrays2.java
// Test and demonstrate Arrays2 utilities,
import com.bruceeckel.util.*;
public class TestArrays2 {
public static void main(String[] args) {
int size = 6;
// Or get the size from the command line,
if(args.length != 0) {
size = Integer.parseInt(args[0]);
if(size < 3) {
System.out.println("arg must be >= 3");
System.exit(1);
}
}
boolean[] a1 = new boolean[size];
Chapter 11,Collections of Objects
g12544 14 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
byte[] a2 = new byte[size];
char[] a3 = new char[size];
short[] a4 = new short[size];
int[] a5 = new int[size];
long[] a6 = new long[size];
float[] a7 = new float[size];
double[] a8 = new double[size];
Arrays2.fill(a1,new
Arrays2.RandBooleanGenerator( ));
System.out.println("a1 = " +
Arrays2.toString(a1));
Arrays2.fill(a2,new
Arrays2.RandByteGenerator( ));
System.out.println("a2 = " +
Arrays2.toString(a2));
Arrays2.fill(a3,new
Arrays2.RandCharGenerator( ));
System.out.println("a3 = " +
Arrays2.toString(a3));
Arrays2.fill(a4,new
Arrays2.RandShortGenerator( ));
System.out.println("a4 = " +
Arrays2.toString(a4));
Arrays2.fill(a5,new
Arrays2.RandIntGenerator( ));
System.out.println("a5 = " +
Arrays2.toString(a5));
Arrays2.fill(a6,new
Arrays2.RandLongGenerator( ));
System.out.println("a6 = " +
Arrays2.toString(a6));
Arrays2.fill(a7,new
Arrays2.RandFloatGenerator( ));
System.out.println("a7 = " +
Arrays2.toString(a7));
Arrays2.fill(a8,new
Arrays2.RandDoubleGenerator( ));
System.out.println("a8 = " +
Arrays2.toString(a8));
}
} ///:~
sizeg2454数有一个g21676g16760的值，不过你也可以通过命g1208行来g16786定。
填满一个数组
Java标准类库Arrays也g2265g6336了一个fill( )方法，g1306是g4439太g12628g2345了g727g4439
只是g12628g2345的把一个的值g3809g2058到数组各个位置，g3926果是对象，则g4570相同的
referenceg6347g17137到每个位置。可以用Arrays2.toString( )把
Arrays.fill( )的工g1328方式g9177g9177g7982g7982地g7186g12046出来,
//,c11:FillingArrays.java
// Using Arrays.fill( )
import com.bruceeckel.simpletest.*;
Thinking in Java 3rd Edition
g12544 15 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
import com.bruceeckel.util.*;
import java.util.*;
public class FillingArrays {
private static Test monitor = new Test( );
public static void main(String[] args) {
int size = 6;
// Or get the size from the command line,
if(args.length != 0)
size = Integer.parseInt(args[0]);
boolean[] a1 = new boolean[size];
byte[] a2 = new byte[size];
char[] a3 = new char[size];
short[] a4 = new short[size];
int[] a5 = new int[size];
long[] a6 = new long[size];
float[] a7 = new float[size];
double[] a8 = new double[size];
String[] a9 = new String[size];
Arrays.fill(a1,true);
System.out.println("a1 = " +
Arrays2.toString(a1));
Arrays.fill(a2,(byte)11);
System.out.println("a2 = " +
Arrays2.toString(a2));
Arrays.fill(a3,'x');
System.out.println("a3 = " +
Arrays2.toString(a3));
Arrays.fill(a4,(short)17);
System.out.println("a4 = " +
Arrays2.toString(a4));
Arrays.fill(a5,19);
System.out.println("a5 = " +
Arrays2.toString(a5));
Arrays.fill(a6,23);
System.out.println("a6 = " +
Arrays2.toString(a6));
Arrays.fill(a7,29);
System.out.println("a7 = " +
Arrays2.toString(a7));
Arrays.fill(a8,47);
System.out.println("a8 = " +
Arrays2.toString(a8));
Arrays.fill(a9,"Hello");
System.out.println("a9 = " + Arrays.asList(a9));
// Manipulating ranges,
Arrays.fill(a9,3,5,"World");
System.out.println("a9 = " + Arrays.asList(a9));
monitor.expect(new String[] {
"a1 = [true,true,true,true,true,true]",
"a2 = [11,11,11,11,11,11]",
"a3 = [x,x,x,x,x,x]",
"a4 = [17,17,17,17,17,17]",
"a5 = [19,19,19,19,19,19]",
"a6 = [23,23,23,23,23,23]",
"a7 = [29.0,29.0,29.0,29.0,29.0,29.0]",
"a8 = [47.0,47.0,47.0,47.0,47.0,47.0]",
"a9 = [Hello,Hello,Hello,Hello,Hello,
Hello]",
Chapter 11,Collections of Objects
g12544 16 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
"a9 = [Hello,Hello,Hello,World,World,
Hello]"
});
}
} ///:~
你可以g3647g9397g6984个数组，或者像g7380g2530两句g18039样，只g3647g1866g1025的某个g14551g3272。相g8616
只能用一个值的Arrays.fill( )，Arrays2.fill( )的运行g13479果就更有g17271
一些了。
复制一个数组
Java标准类库提供了一个System.arraycopy( )的static方法。相
g8616forg5502g10627，g4439能以更g5567的g17907g5242g6347g17137数组。System.arraycopy( )对所有类型都g1328了g18337g17745。g991面就是一个用g4439来处理int数组的g1375g4388。
//,c11:CopyingArrays.java
// Using System.arraycopy( )
import com.bruceeckel.simpletest.*;
import com.bruceeckel.util.*;
import java.util.*;
public class CopyingArrays {
private static Test monitor = new Test( );
public static void main(String[] args) {
int[] i = new int[7];
int[] j = new int[10];
Arrays.fill(i,47);
Arrays.fill(j,99);
System.out.println("i = " + Arrays2.toString(i));
System.out.println("j = " + Arrays2.toString(j));
System.arraycopy(i,0,j,0,i.length);
System.out.println("j = " + Arrays2.toString(j));
int[] k = new int[5];
Arrays.fill(k,103);
System.arraycopy(i,0,k,0,k.length);
System.out.println("k = " + Arrays2.toString(k));
Arrays.fill(k,103);
System.arraycopy(k,0,i,0,k.length);
System.out.println("i = " + Arrays2.toString(i));
// Objects,
Integer[] u = new Integer[10];
Integer[] v = new Integer[5];
Arrays.fill(u,new Integer(47));
Arrays.fill(v,new Integer(99));
System.out.println("u = " + Arrays.asList(u));
System.out.println("v = " + Arrays.asList(v));
System.arraycopy(v,0,u,u.length/2,v.length);
System.out.println("u = " + Arrays.asList(u));
monitor.expect(new String[] {
"i = [47,47,47,47,47,47,47]",
"j = [99,99,99,99,99,99,99,99,99,99]",
"j = [47,47,47,47,47,47,47,99,99,99]",
"k = [47,47,47,47,47]",
Thinking in Java 3rd Edition
g12544 17 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
"i = [103,103,103,103,103,47,47]",
"u = [47,47,47,47,47,47,47,47,47,47]",
"v = [99,99,99,99,99]",
"u = [47,47,47,47,47,99,99,99,99,99]"
});
}
} ///:~
传给arraycopy( )的g2454数g2265g6336源数组，标g16794从源数组的g2750个位置g5332g3999
g6347g17137的g1571g12239量，g11458标数组，标g16794从g11458标数组的g2750个位置g5332g3999g6347g17137的g1571g12239
量，以g2462要g6347g17137的g1815g13044的数量。当g9994g17241出数组g17805g11040会引g2469异常。
这个g1375g4388告诉我们对象数组g2656primitive数组都能g6347g17137。g1306是g3926果你g6347g17137
的是对象数组，g18039么你只g6347g17137了g4439们的reference —— 对象g7424g17535不会g15999
g6347g17137。这g15999g12228为g8985g6347g17137(shallow copy) (见g19480g5417A)。
数组的比较
为了能g8616g17751数组是否g4448g1852相g12573，Arrays提供了g13475g18337g17745的equals( )方法。当g9994，也是针对各种primitive以g2462Object的。两个数组要想g4448g1852
相g12573，g4439们g5529g20047有相同数量的g1815g13044，而g1000数组的每个g1815g13044g5529g20047g994g2490一个数组的相对g5224的位置上的g1815g13044相g12573。g1815g13044的相g12573g5627，用eqauls( )判断。
(对于primitive，g4439会g1363用g1866wrapper类的equals( )g727g8616g3926intg1363用
Integer.equals( )。)g1375g3926,
//,c11:ComparingArrays.java
// Using Arrays.equals( )
import com.bruceeckel.simpletest.*;
import java.util.*;
public class ComparingArrays {
private static Test monitor = new Test( );
public static void main(String[] args) {
int[] a1 = new int[10];
int[] a2 = new int[10];
Arrays.fill(a1,47);
Arrays.fill(a2,47);
System.out.println(Arrays.equals(a1,a2));
a2[3] = 11;
System.out.println(Arrays.equals(a1,a2));
String[] s1 = new String[5];
Arrays.fill(s1,"Hi");
String[] s2 = {"Hi","Hi","Hi","Hi","Hi"};
System.out.println(Arrays.equals(s1,s2));
monitor.expect(new String[] {
"true",
"false",
"true"
});
}
} ///:~
Chapter 11,Collections of Objects
g12544 18 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g17227g1820a1g2656a2是g4448g1852相g12573的，所以g17767出g13479果是g256trueg257，g1306是我们g1474g6925
了一个g1815g13044，于是g13479果就g2476成g256falseg257了。在g2530一个g1375g4388g18336，s1的所有
g1815g13044指向相同的对象，g1306是s2却有g1128个各自g10432立的对象。g1306是数组是否相g12573是g3534于g1866内g4493，(通过Object.equals( ))，因此g13479果仍是
"true"。
数组元素的比较
Java 1.0 g9941.1的类库g13582少一些g18337要特g5627，g1866g1025g1055一就有没有提供g12651
法，甚至连个g12628g2345的g6502序都没有。对g18039些g7411望能有一个像样的标准类库的人来说，这g12628直是太g1208人不解了。g17836好Java2g1328了补救，至少是解决了
g6502序问题。
编g1901泛型g6502序程序的时候会遇到一个问题，就是g4439只能根据对象的g4466际类型进行g8616g17751。当g9994为每种类型都g1901一个的g6502序程序也不啻是一个办法，g1306
是这样一来你就会g2469g10628，碰到新的类型的时候，要想g3809用g1207码就不g18039么g4493
g7143了。
g16786计的一项g18337要g11458标就是g256要g4570会g2476g2656不会g2476的g1008g16211g2010g5332来g257。这g18336，不会g2476的g1008g16211就是通用的g6502序g12651法，而会g2476的g1008g16211就是对象是怎样g8616g17751大小的。所以g994g1866在各种g6502序程序g18336面都插进g8616g17751g12651法，g17836不g3926g1363用g3250g16855
(callback)技g7427。有了g3250g16855，你就能把g256会根据情况的不同而g6925g2476g257的g1207
码g2010离出来，而用相同的g1207码来g16855用g18039些会g2476的g1207码。
Javag18336面有两种能g16765你g4466g10628g8616g17751功能的方法。一是g4466g10628
java.lang.Comparable接g2487，并以此g4466g10628类g256自有的g257g8616g17751方法。
这是一个很g12628g2345的接g2487，g4439只有一个方法compareTo( )。这个方法能接受g2490一个对象g1328为g2454数，g3926果g10628有对象g8616g2454数小，g4439会g17832g3250一个g17139数，
g3926果相同则g17832g3250零，g3926果g10628有的对象g8616g2454数大，g4439就g17832g3250一个正数。
g991面就是一个g4466g10628Comparable接g2487的类，此外g4439g17836用Java标准类库的Arrays.sort( )方法g9448g12046了g8616g17751的g13479果,
//,c11:CompType.java
// Implementing Comparable in a class,
import com.bruceeckel.util.*;
import java.util.*;
public class CompType implements Comparable {
int i;
int j;
public CompType(int n1,int n2) {
i = n1;
j = n2;
}
public String toString( ) {
Thinking in Java 3rd Edition
g12544 19 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
return "[i = " + i + ",j = " + j + "]";
}
public int compareTo(Object rv) {
int rvi = ((CompType)rv).i;
return (i < rvi? -1,(i == rvi? 0,1));
}
private static Random r = new Random( );
public static Generator generator( ) {
return new Generator( ) {
public Object next( ) {
return new
CompType(r.nextInt(100),r.nextInt(100));
}
};
}
public static void main(String[] args) {
CompType[] a = new CompType[10];
Arrays2.fill(a,generator( ));
System.out.println(
"before sorting,a = " + Arrays.asList(a));
Arrays.sort(a);
System.out.println(
"after sorting,a = " + Arrays.asList(a));
}
} ///:~
一g7098你定g1053了g8616g17751的方法，你就得g17139g17143确定这个对象g5224g16825依据什么同g1866g4439
对象进行g8616g17751。这g18336我们只用到了i的值，而j的值则g15999忽略了。
static randInt( )方法会g10995成一个g1183于0到100g1055间的正数，而
generator( )方法则用g256创建匿名内g18108类g257的方法(g2454见g12544八g12468)，创建了一个g4466g10628Generator接g2487的对象。而这个对象又会用randInt( )g10995
成的g19555g7438数创建了多个CompType对象。main( )用这个generator
把CompType型的数组g3647g9397。接g991来，g5332g3999对数组g6502序。g3926果
CompType没有g4466g10628Comparable接g2487，g18039么程序运行g16855用到
sort( )的时候，就会引g2469一个ClassCastException错误。这是因为
sort( )会把传给g4439的g2454数g17728g6454成Comparable。
g10628在g1563g16786，有人给你一个没有g4466g10628Comparable接g2487的类，或者这个类g4466g10628了Comparable接g2487，g1306是你g2469g10628g4439的工g1328方式不是你所希望的，于是要g18337新定g1053一个新的g8616g17751方法。Java没有g5390求你一定要把g8616g17751
g1207码塞进类g18336，g4439的解决方g7708是g1363用g256策略模式(strategy design
pattern)4g257。有了策略g1055g2530，你就能把会g2476的g1207码封g16025到g4439自己的类g18336
(即所g16871的策略对象strategy object)。你把策略对象交给不会g2476的g1207
码，g9994g2530g11013g4439运用策略g4448成g6984个g12651法。这样，你就可以用不同的策略对象来表g12046不同的g8616g17751方式，g9994g2530把g4439们都交给同一个g6502序程序了。接g991来就要g256通过g4466g10628Comparator接g2487g257来定g1053策略对象了。这个接g2487有两个
4 Design Patterns,Erich Gammag12573g14891,Addison-Wesley 1995g5192g1998g10268g452
Chapter 11,Collections of Objects
g12544 20 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
方法compare( )g2656equals( )。g1306是g19512非是有特殊的g5627能要求，否则你用不着去g4466g10628equals( )。因为只要是类，g4439就都隐含地继承自
Object，而Objectg18336面g5062g13475有了一个equals( )了。所以你尽可以g1363
用g13582省的Object的equals( )，这样就g5062g13475g9397足接g2487的要求了。
(我们要g12573一会儿才会g16774到的)Collections类g18336专门有一个会g17832g3250g994对象自有的g8616g17751法相反的Comparator的方法。g4439能很轻g7143地g15999用到
CompType上面。
//,c11:Reverse.java
// The Collecions.reverseOrder( ) Comparator
import com.bruceeckel.util.*;
import java.util.*;
public class Reverse {
public static void main(String[] args) {
CompType[] a = new CompType[10];
Arrays2.fill(a,CompType.generator( ));
System.out.println(
"before sorting,a = " + Arrays.asList(a));
Arrays.sort(a,Collections.reverseOrder( ));
System.out.println(
"after sorting,a = " + Arrays.asList(a));
}
} ///:~
Collections.reverseOrder( )g17832g3250了一个Comparator的
reference。
g1889g1042个g1375g4388，我们g16765Comparator根据j，而不是i的值来g8616g17751
CompType对象。
//,c11:ComparatorTest.java
// Implementing a Comparator for a class,
import com.bruceeckel.util.*;
import java.util.*;
class CompTypeComparator implements Comparator {
public int compare(Object o1,Object o2) {
int j1 = ((CompType)o1).j;
int j2 = ((CompType)o2).j;
return (j1 < j2? -1,(j1 == j2? 0,1));
}
}
public class ComparatorTest {
public static void main(String[] args) {
CompType[] a = new CompType[10];
Arrays2.fill(a,CompType.generator( ));
System.out.println(
"before sorting,a = " + Arrays.asList(a));
Arrays.sort(a,new CompTypeComparator( ));
System.out.println(
Thinking in Java 3rd Edition
g12544 21 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
"after sorting,a = " + Arrays.asList(a));
}
} ///:~
compare( )方法会根据g12544一个g2454数是小于，g12573于g17836是大于g12544二个g2454
数，g2010g2047g17832g3250g17139g6984数，零或是正g6984数。
数组的排序
有了内置的g6502序方法g1055g2530，你就能对任何数组g6502序了，不论是primitive
的g17836是对象数组，只要g4439g4466g10628了Comparable接g2487或有一个g994g1055相关的Comparator对象就行了。这个功能g3647补了Java类库的一个大g9443
洞。信不信g11013你，Java1.0g26561.1连字g12538g1030的g6502序都没有。g991面是一个
g19555g7438g10995成String并对g1866g6502序的程序,
//,c11:StringSorting.java
// Sorting an array of Strings,
import com.bruceeckel.util.*;
import java.util.*;
public class StringSorting {
public static void main(String[] args) {
String[] sa = new String[30];
Arrays2.fill(sa,new
Arrays2.RandStringGenerator(5));
System.out.println(
"Before sorting," + Arrays.asList(sa));
Arrays.sort(sa);
System.out.println(
"After sorting," + Arrays.asList(sa));
}
} ///:~
你可以从程序的g17767出看到，这个g12651法是按字典顺序进行g6502序的。就是把首字母大g1901的g2345词放在前面，小g1901字母g5332头的放在g2530面。(电g16817簿就是这么
g6502的。)或g16780你想忽略大小g1901进行g6502序，g18039就自己定g1053一个
Comparator类吧，只要覆g1901g21676g16760的String Comparable的行为就可以了。g13783g15397到g4570来的g3809用，我们把这个类放进了g256utilg257package,
//,com:bruceeckel:util:AlphabeticComparator.java
// Keeping upper and lowercase letters together,
package com.bruceeckel.util;
import java.util.*;
public class AlphabeticComparator implements
Comparator {
public int compare(Object o1,Object o2) {
String s1 = (String)o1;
String s2 = (String)o2;
Chapter 11,Collections of Objects
g12544 22 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
return
s1.toLowerCase( ).compareTo(s2.toLowerCase( ));
}
} ///:~
程序g5332头g1582了个类型g17728g6454，这样g3926果你传了个错误的类型，g4439就会抛出异常。字g12538g1030会g1820g15999g17728g6454成小g1901，g1889进行g8616g17751。接g991来用String内置的
compareTo( )方法进行g8616g17751。
g991面就是AlphabeticComparator的g8991g16809g1207码,
//,c11:AlphabeticSorting.java
// Keeping upper and lowercase letters together,
import com.bruceeckel.util.*;
import java.util.*;
public class AlphabeticSorting {
public static void main(String[] args) {
String[] sa = new String[30];
Arrays2.fill(sa,new
Arrays2.RandStringGenerator(5));
System.out.println(
"Before sorting," + Arrays.asList(sa));
Arrays.sort(sa,new AlphabeticComparator( ));
System.out.println(
"After sorting," + Arrays.asList(sa));
}
} ///:~
Java标准类库所用的g6502序g12651法g5062g13475g1328了优g2282——对primitive，g4439用的是
g256g5567g17907g6502序(Quicksort)g257，对对象，g4439用的是g256稳定合并g6502序(stable
merge sort)g257。所以g19512非是prolier表g7138g6502序g12651法是瓶颈，否则你不用为g5627能担g5527。
查询有序数组
一g7098数组g6502g4448序，你就能用Arrays.binarySearch( )进行g5567g17907查询了。g1306是切忌对一个尚未g6502序的数组g1363用binarySearch( )g727因为这么
g1582的g13479果是没意g1053的。接g991来，我们用RandIntGenerator来g3647数组，g9994g2530用同一个generatorg10995成一个g19555g7438数，g1889在数组g18336面g6226这个数字,
//,c11:ArraySearching.java
// Using Arrays.binarySearch( ),
import com.bruceeckel.util.*;
import java.util.*;
public class ArraySearching {
Thinking in Java 3rd Edition
g12544 23 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
public static void main(String[] args) {
int[] a = new int[100];
Arrays2.RandIntGenerator gen =
new Arrays2.RandIntGenerator(1000);
Arrays2.fill(a,gen);
Arrays.sort(a);
System.out.println(
"Sorted array," + Arrays2.toString(a));
while(true) {
int r = gen.next( );
int location = Arrays.binarySearch(a,r);
if(location >= 0) {
System.out.println("Location of " + r +
" is " + location + ",a[" +
location + "] = " + a[location]);
break; // Out of while loop
}
}
}
} ///:~
whileg5502g10627会不断地g10995成g19555g7438数，直到g4439g6226到为止。
g3926果Arrays.binarySearch( )g6226到了，g4439就g17832g3250一个大于或g12573于0
的值。否则g4439就g17832g3250一个g17139值，而这个g17139值要表达的意思是，g3926果你手动维护这个数组的g16817，这个值g5224g16825插在g2750个位置。这个值就是,
-(g6566g1849g9869)-1
g256插入点g257就是，在所有g256g8616要g6226的g18039个值g257更大值g1025，g7380小的g18039个值的g991标，或者，g3926果数组g1025所有的值都g8616要g6226的值小，g4439就是
a.size( )。
g3926果数组g18336面有g18337g3809g1815g13044，g18039g4439不能保证会g17832g3250g2750一个。这个g12651法不支持
g18337g3809g1815g13044，不过g4439也不报错。所以，g3926果你需要的是一个g7092g18337g3809g1815g13044的有序序g2027的g16817，g18039么可以g13783g15397g1363用g7424g12468g2530面所g1183g13473的TreeSet(支持『g6502序顺序g256sorted orderg257』)g2656LinkedHashSet(支持『插入顺序
g256sorted orderg257』)。这两个类会帮你照看所有细节。只有在遇到g5627能瓶颈的时候，你才g5224g16825用手动维护的数组来g1207替这两个类。
g3926果g6502序的时候用到了Comparator (针对对象数组，primitive数组不g1813g16780g1363用Comparator)，g18039么binarySearch( )的时候，也g5529g20047
g1363用同一个Comparator (用这个方法的g18337g17745版)。g8616方说，我们g1474g6925了
AlphabeticSorting.java,
//,c11:AlphabeticSearch.java
// Searching with a Comparator,
Chapter 11,Collections of Objects
g12544 24 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
import com.bruceeckel.simpletest.*;
import com.bruceeckel.util.*;
import java.util.*;
public class AlphabeticSearch {
private static Test monitor = new Test( );
public static void main(String[] args) {
String[] sa = new String[30];
Arrays2.fill(sa,new
Arrays2.RandStringGenerator(5));
AlphabeticComparator comp = new
AlphabeticComparator( );
Arrays.sort(sa,comp);
int index = Arrays.binarySearch(sa,sa[10],
comp);
System.out.println("Index = " + index);
monitor.expect(new String[] {
"Index = 10"
});
}
} ///:~
g5529g20047把Comparator当g1328binaraySearch( )的g12544g989个g2454数传给g4439。
在这个g1375g4388g18336，g11013于要g6226的g1008g16211是从数组g18336面g6373的，因此肯定能g6226到。
数组部分的总结
总而言g1055，g3926果你要持有一组对象，首g17885，同时也是g6940g10587g7380g20652的g17885g6333，g5224
g16825是数组。而g1000，g3926果这是一组primitive的g16817，你也只能用数组。接g991
来，我们要g16774一些更为一般的情况，也就是g1901程序的时候g17836不知道要用多少对象，或者要用一种更g3809g7446方式来g4396g1660对象情况。为此，Java提供了
g256g4493g3132类(container class)g257。g1866g3534g7424类型有List,Setg2656Map。有了这些工具，你就能解决很多问题了。
g4439们g17836有一些g2047的特g5627。g8616方说Set所持有的对象，个个都不同，Map
则是一个g256关联g5627数组(associative array)g257，g4439能在两个对象g1055间建立联系。此外，g994数组不同，g4439们g17836能自动g16855g6984大小，所以你可以往g18336面放任意数量的对象。这样g1901程序的时候，就不用g6817g5527要g5332多大的空间了。
容器简介
就我个人的感受，g4493g3132类能极大地g3698g5390我的编程能力，是软g1226g5332g2469领域g7380
得力的工具g1055一。Java2的g18337新g16786计5了1.0g26561.1g18336面g18039个表g10628差劲的
g4493g3132类。新的g16786计更紧凑也更合理。同时g4439也补齐了g4493g3132类库的功能，提供了链表(linked list)、队g2027(queue)g2656双向队g2027(deques，读成
g256decksg257)这几种数据g13479g7512的功能。
5g11013Sung11352Joshua Blochg17139g17143g16786g16757g452
Thinking in Java 3rd Edition
g12544 25 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
要g16786计g4493g3132类库是很g19602的(对绝大多数类库，g16786计总是很g19602的)。C++的
g4493g3132类库g18336g2265g6336了很多各色各样的类。相g8616原g1820什么都没有，这种g16786计当
g9994好出不少，g1306是g4439并不g17878合Java。也有走g2490一个极端的。我就曾看到过一个只g2265g6336g256containerg257类的g4493g3132类库。g4439的工g1328方式既象g13459g5627序
g2027，又象关联g5627数组。Java 2的g4493g3132类库则取了个折g1025：g4439g4466g10628了g256成熟的g4493g3132类库所g5224g4466g10628g257的一切功能，同时g4439又g8616C++或g1866g4439类g1296的g4493
g3132类库更g7143g4410g7143用。所以这个类库可能会有些g5630。不像早g7411的Java类库，这些g5630异g1055处并不是什么g16786计g13582陷，相反g4439是在仔细斟酌了各种g3809g7446
因g13044g1055g2530才g1328的决定。或g16780你得花一点时间来熟悉这个类库，g1306是我相信，你很g5567就会g4410会g4493g3132类，g9994g2530把g4439们派上用场。
Java2的g4493g3132类要解决g256怎样持有对象g257，而g4439把这个问题g2010成两类,
1,Collection,通常是一组有一定规律的g10432立g1815g13044。Listg5529g20047按照特定的顺序持有这些g1815g13044，而Set则不能保g4396g18337g3809的g1815g13044。(bag没有这个限
g2058，g1306是Java的g4493g3132类库没有g4466g10628g4439，因为Listg5062g13475提供这种功能了。)
2,Map,一组以g256键——值g257(key-value)形式出g10628的pair。g2033看上去，g4439
g5224g16825是一个pair的Collection，g1306是真这么去g1582的g16817，g4439就会g2476得很滑稽，所以g17836是把这个g8022念g10432立g2027出来为好。退一步说，真的要用到
Map的某个g4388g19610的时候，创建一个Collection也是很方便的。Map
可以g17832g3250g256键(key)的g257Set，值的Collection，或者pair的Set。g2656数组一样，Map不需要什么g1474g6925，就能很g4493g7143地g6205g4649成多维。你只要直接把Map的值g16786成Map就可以了(g9994g2530g4439的值g1889是Map，以此类推)。
我们g1820来看看g4493g3132的一般特g5627，g9994g2530深入细节，g7380g2530g1889看为什么会有这么多版g7424，以g2462g3926何进行g17885g6333。
打印容器
不像数组，g4493g3132不需要借助g2047的类就能g9177g9177g7982g7982地把自己给g6183g2372出来。g991
面这个g1375g4388g17836g1183g13473了几种g3534g7424的g4493g3132,
//,c11:PrintingContainers.java
// Containers print themselves automatically,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class PrintingContainers {
private static Test monitor = new Test( );
static Collection fill(Collection c) {
c.add("dog");
c.add("dog");
c.add("cat");
return c;
}
static Map fill(Map m) {
m.put("dog","Bosco");
m.put("dog","Spot");
Chapter 11,Collections of Objects
g12544 26 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
m.put("cat","Rags");
return m;
}
public static void main(String[] args) {
System.out.println(fill(new ArrayList( )));
System.out.println(fill(new HashSet( )));
System.out.println(fill(new HashMap( )));
monitor.expect(new String[] {
"[dog,dog,cat]",
"[dog,cat]",
"{dog=Spot,cat=Rags}"
});
}
} ///:~
正g3926前面所g16774的，Java的g4493g3132类g2010成两种g3534g7424类型。g4439们的g2318g2047就在，
每个位置能放多少对象。Collection只g1813g16780每个位置上放一个对象(这个名字有点误g4560，因为g4493g3132类库也常g15999统g12228为collections)。g4439g2265g6336g256以一定顺序持有一组对象g257的List，以g2462g256只能g1813g16780g9167g2164不g18337g3809的对象g257
的Set。ArrayList是一种List，而HashSet则是一种Set。你可以用add( )方法往Collectiong18336面g2164对象。
Map保g4396的是g256键(key)—值g257形式的pair，很像是一个微型数据库。
上面这段程序用了一种叫HashMap的Map。g3926果你建了一个g256州g2656首府g257的Map，g9994g2530想查一g991Ohio的首府在g2750g18336，你就可以用g4439来g6226
了。用法g2656用g991标查数组是一样的。(Map又g15999g12228为关联g5627数组
associative array。)你可以用put( )方法往Mapg18336面g2164g1815g13044。g4439接受键—值形式pairg1328g2454数。g1375程只g9448g12046了怎样把g1815g13044g2164进去，g4439没g1582查询。这g18108g2010的内g4493我们以g2530g1889g16774。
fill( )方法g17836为Collectiong2656Mapg1328了g18337g17745。g3926果你看过g17767出，就会
g2469g10628g21676g16760情况g991(g1363用g4493g3132类的toString( )方法)的g6183g2372g6940果g5062g13475很不错了，所以我们就不g1889提供g20081外的g6183g2372支持了。g6183g2372出来的Collection会用方g6336号g6336g17227来，g1815g13044g994g1815g13044g1055间用逗号g2010g5332。Map会用花g6336号g6336g17227
来，键g2656值g1055间用g12573号联g17227来(键在左g17805，值在右g17805)。
你能一眼就看出各种g4493g3132的g3534g7424行为。List会老老g4466g4466地持有你所g17767入的所有对象，既不g1582g6502序也不g1582编g17765。Set则每个对象只接受一g8437，而g1000
g17836要用g4439自己的规则对g1815g13044进行g18337新g6502序(一般情况g991，你关g5527的只是
Setg2265没g2265g6336某个对象，而不是g4439到底g6502在g2750g18336——g3926果是g18039样，你g7380好
g17836是用List)。而Map也不接g6922g18337g3809的pair，至于是不是g18337g3809，要g11013
key来决定。此外，g4439也有g4439自己的内g18108g6502序规则，不会受g17767入顺序g5445
g2721。g3926果插入顺序是很g18337要的，g18039你就只能g1363用LinkedHashSet或
LinkedHashMap了。
填充容器
Thinking in Java 3rd Edition
g12544 27 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g15441g9994g4493g3132的g6183g2372问题是解决了，g1306g4439的g3647g1817却g17836g17331java.util.Arrays一样，有着相同的不足。g2656Arrays一样，Collection也有一个叫
Collections的g17753助类，g4439g2265含了一些g19757g5589的g4466用工具方法，g1866g1025就有一个fill( )。这个fill( )也只是把同一个对象的referenceg3809g2058到g6984个
g4493g3132，而g1000g4439g17836只能为List，不能为Setg2656Map工g1328。
//,c11:FillingLists.java
// The Collections.fill( ) method,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class FillingLists {
private static Test monitor = new Test( );
public static void main(String[] args) {
List list = new ArrayList( );
for(int i = 0; i < 10; i++)
list.add("");
Collections.fill(list,"Hello");
System.out.println(list);
monitor.expect(new String[] {
"[Hello,Hello,Hello,Hello,Hello," +
"Hello,Hello,Hello,Hello,Hello]"
});
}
} ///:~
g4466际上这个方法g17836不g3926Arrays，因为g4439只能在替g6454，而不是在往List
g18336面g2164新的g1815g13044。
为了能创建一些有g4466际意g1053的g1375g4388，我补g1817了一个g5114fill( )方法的
Collections2类库(为方便g17227见，我把g4439放进了
com.bruceeckel.util)。g4439能用generatorg2164g1815g13044，而g1000g17836能g16765你指定要add( )多少g1815g13044。前面定g1053的Generator能同Collections一同工g1328，g1306是Map需要一个g4439自己的generator interface，因为每
g8437g16855用g4439的next( )的时候要g10995成两个对象。g991面就是这个Pair类,
//,com:bruceeckel:util:Pair.java
package com.bruceeckel.util;
public class Pair {
public Object key,value;
public Pair(Object k,Object v) {
key = k;
value = v;
}
} ///:~
接g991来是g10995成这个Pair的generator的interface,
Chapter 11,Collections of Objects
g12544 28 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
//,com:bruceeckel:util:MapGenerator.java
package com.bruceeckel.util;
public interface MapGenerator { Pair next( ); }
///:~
g1582g4448准g3803g1055g2530，我们就能g5332g3999编g1901g4493g3132类的g4466用工具了,
//,com:bruceeckel:util:Collections2.java
// To fill any type of container using a generator
object,
package com.bruceeckel.util;
import java.util.*;
public class Collections2 {
// Fill an array using a generator,
public static void
fill(Collection c,Generator gen,int count) {
for(int i = 0; i < count; i++)
c.add(gen.next( ));
}
public static void
fill(Map m,MapGenerator gen,int count) {
for(int i = 0; i < count; i++) {
Pair p = gen.next( );
m.put(p.key,p.value);
}
}
public static class
RandStringPairGenerator implements MapGenerator {
private Arrays2.RandStringGenerator gen;
public RandStringPairGenerator(int len) {
gen = new Arrays2.RandStringGenerator(len);
}
public Pair next( ) {
return new Pair(gen.next( ),gen.next( ));
}
}
// Default object so you don't have to create your
own,
public static RandStringPairGenerator rsp =
new RandStringPairGenerator(10);
public static class
StringPairGenerator implements MapGenerator {
private int index = -1;
private String[][] d;
public StringPairGenerator(String[][] data) {
d = data;
}
public Pair next( ) {
// Force the index to wrap,
index = (index + 1) % d.length;
return new Pair(d[index][0],d[index][1]);
}
public StringPairGenerator reset( ) {
index = -1;
return this;
}
Thinking in Java 3rd Edition
g12544 29 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
}
// Use a predefined dataset,
public static StringPairGenerator geography =
new StringPairGenerator(CountryCapitals.pairs);
// Produce a sequence from a 2D array,
public static class StringGenerator implements
Generator{
private String[][] d;
private int position;
private int index = -1;
public StringGenerator(String[][] data,int pos)
{
d = data;
position = pos;
}
public Object next( ) {
// Force the index to wrap,
index = (index + 1) % d.length;
return d[index][position];
}
public StringGenerator reset( ) {
index = -1;
return this;
}
}
// Use a predefined dataset,
public static StringGenerator countries =
new StringGenerator(CountryCapitals.pairs,0);
public static StringGenerator capitals =
new StringGenerator(CountryCapitals.pairs,1);
} ///:~
这两个fill( )都要根据g2454数来决定要往g4493g3132g18336面g2164多少g1815g13044。此外，
Map有两个generator：RandStringPairGeneratorg2656
StringPairGenerator。前者会g10995成g19555g7438的字g12538g1030pair，g1866g19283g5242要g11013
g7512造g2001数的g2454数决定g727而g2530者会根据一个两维的字g12538g1030数组，g10995成字g12538g1030
pair。StringGenerator也接受一个两维的字g12538g1030数组，g1306是g4439g10995成的是g2345个的，而不是成对的g1815g13044。static的rsp，geography，
countries以g2462capitals对象提供了g20056g16786的generator，g1866g1025g2530面g989
个会用到g3281g4490g2462g1866首都。g8892意，g3926果你要创建更多的对象pair，
generator就会g5502g10627到数组的g5332头，g1306是g3926果你把这些对象pair放进
Map，g18039么这些g18337g3809的g1008g16211就会g15999忽略g6493。
g991面就是g20056定g1053的数据g19610。g4439g2265g6336了g3281g4490的名字g2462g1866首都,
//,com:bruceeckel:util:CountryCapitals.java
package com.bruceeckel.util;
public class CountryCapitals {
public static final String[][] pairs = {
// Africa
{"ALGERIA","Algiers"},{"ANGOLA","Luanda"},
{"BENIN","Porto-Novo"},{"BOTSWANA","Gaberone"},
Chapter 11,Collections of Objects
g12544 30 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
{"BURKINA FASO","Ouagadougou"},
{"BURUNDI","Bujumbura"},
{"CAMEROON","Yaounde"},{"CAPE VERDE","Praia"},
{"CENTRAL AFRICAN REPUBLIC","Bangui"},
{"CHAD","N'djamena"},{"COMOROS","Moroni"},
{"CONGO","Brazzaville"},
{"DJIBOUTI","Dijibouti"},
{"EGYPT","Cairo"},{"EQUATORIAL
GUINEA","Malabo"},
{"ERITREA","Asmara"},{"ETHIOPIA","Addis Ababa"},
{"GABON","Libreville"},{"THE GAMBIA","Banjul"},
{"GHANA","Accra"},{"GUINEA","Conakry"},
{"GUINEA","-"},{"BISSAU","Bissau"},
{"COTE D'IVOIR (IVORY COAST)","Yamoussoukro"},
{"KENYA","Nairobi"},{"LESOTHO","Maseru"},
{"LIBERIA","Monrovia"},{"LIBYA","Tripoli"},
{"MADAGASCAR","Antananarivo"},
{"MALAWI","Lilongwe"},
{"MALI","Bamako"},{"MAURITANIA","Nouakchott"},
{"MAURITIUS","Port Louis"},{"MOROCCO","Rabat"},
{"MOZAMBIQUE","Maputo"},{"NAMIBIA","Windhoek"},
{"NIGER","Niamey"},{"NIGERIA","Abuja"},
{"RWANDA","Kigali"},
{"SAO TOME E PRINCIPE","Sao Tome"},
{"SENEGAL","Dakar"},{"SEYCHELLES","Victoria"},
{"SIERRA LEONE","Freetown"},
{"SOMALIA","Mogadishu"},
{"SOUTH AFRICA","Pretoria/Cape Town"},
{"SUDAN","Khartoum"},
{"SWAZILAND","Mbabane"},{"TANZANIA","Dodoma"},
{"TOGO","Lome"},{"TUNISIA","Tunis"},
{"UGANDA","Kampala"},
{"DEMOCRATIC REPUBLIC OF THE CONGO (ZAIRE)",
"Kinshasa"},
{"ZAMBIA","Lusaka"},{"ZIMBABWE","Harare"},
// Asia
{"AFGHANISTAN","Kabul"},{"BAHRAIN","Manama"},
{"BANGLADESH","Dhaka"},{"BHUTAN","Thimphu"},
{"BRUNEI","Bandar Seri Begawan"},
{"CAMBODIA","Phnom Penh"},
{"CHINA","Beijing"},{"CYPRUS","Nicosia"},
{"INDIA","New Delhi"},{"INDONESIA","Jakarta"},
{"IRAN","Tehran"},{"IRAQ","Baghdad"},
{"ISRAEL","Tel Aviv"},{"JAPAN","Tokyo"},
{"JORDAN","Amman"},{"KUWAIT","Kuwait City"},
{"LAOS","Vientiane"},{"LEBANON","Beirut"},
{"MALAYSIA","Kuala Lumpur"},{"THE
MALDIVES","Male"},
{"MONGOLIA","Ulan Bator"},
{"MYANMAR (BURMA)","Rangoon"},
{"NEPAL","Katmandu"},{"NORTH
KOREA","P'yongyang"},
{"OMAN","Muscat"},{"PAKISTAN","Islamabad"},
{"PHILIPPINES","Manila"},{"QATAR","Doha"},
{"SAUDI ARABIA","Riyadh"},
{"SINGAPORE","Singapore"},
{"SOUTH KOREA","Seoul"},{"SRI LANKA","Colombo"},
{"SYRIA","Damascus"},
{"TAIWAN (REPUBLIC OF CHINA)","Taipei"},
{"THAILAND","Bangkok"},{"TURKEY","Ankara"},
Thinking in Java 3rd Edition
g12544 31 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
{"UNITED ARAB EMIRATES","Abu Dhabi"},
{"VIETNAM","Hanoi"},{"YEMEN","Sana'a"},
// Australia and Oceania
{"AUSTRALIA","Canberra"},{"FIJI","Suva"},
{"KIRIBATI","Bairiki"},
{"MARSHALL ISLANDS","Dalap-Uliga-Darrit"},
{"MICRONESIA","Palikir"},{"NAURU","Yaren"},
{"NEW ZEALAND","Wellington"},{"PALAU","Koror"},
{"PAPUA NEW GUINEA","Port Moresby"},
{"SOLOMON ISLANDS","Honaira"},
{"TONGA","Nuku'alofa"},
{"TUVALU","Fongafale"},{"VANUATU","< Port-
Vila"},
{"WESTERN SAMOA","Apia"},
// Eastern Europe and former USSR
{"ARMENIA","Yerevan"},{"AZERBAIJAN","Baku"},
{"BELARUS (BYELORUSSIA)","Minsk"},
{"GEORGIA","Tbilisi"},
{"KAZAKSTAN","Almaty"},{"KYRGYZSTAN","Alma-
Ata"},
{"MOLDOVA","Chisinau"},{"RUSSIA","Moscow"},
{"TAJIKISTAN","Dushanbe"},
{"TURKMENISTAN","Ashkabad"},
{"UKRAINE","Kyiv"},{"UZBEKISTAN","Tashkent"},
// Europe
{"ALBANIA","Tirana"},{"ANDORRA","Andorra la
Vella"},
{"AUSTRIA","Vienna"},{"BELGIUM","Brussels"},
{"BOSNIA","-"},{"HERZEGOVINA","Sarajevo"},
{"CROATIA","Zagreb"},{"CZECH
REPUBLIC","Prague"},
{"DENMARK","Copenhagen"},{"ESTONIA","Tallinn"},
{"FINLAND","Helsinki"},{"FRANCE","Paris"},
{"GERMANY","Berlin"},{"GREECE","Athens"},
{"HUNGARY","Budapest"},{"ICELAND","Reykjavik"},
{"IRELAND","Dublin"},{"ITALY","Rome"},
{"LATVIA","Riga"},{"LIECHTENSTEIN","Vaduz"},
{"LITHUANIA","Vilnius"},
{"LUXEMBOURG","Luxembourg"},
{"MACEDONIA","Skopje"},{"MALTA","Valletta"},
{"MONACO","Monaco"},{"MONTENEGRO","Podgorica"},
{"THE NETHERLANDS","Amsterdam"},
{"NORWAY","Oslo"},
{"POLAND","Warsaw"},{"PORTUGAL","Lisbon"},
{"ROMANIA","Bucharest"},{"SAN MARINO","San
Marino"},
{"SERBIA","Belgrade"},{"SLOVAKIA","Bratislava"},
{"SLOVENIA","Ljujiana"},{"SPAIN","Madrid"},
{"SWEDEN","Stockholm"},{"SWITZERLAND","Berne"},
{"UNITED KINGDOM","London"},{"VATICAN CITY","--
-"},
// North and Central America
{"ANTIGUA AND BARBUDA","Saint John's"},
{"BAHAMAS","Nassau"},
{"BARBADOS","Bridgetown"},{"BELIZE","Belmopan"},
{"CANADA","Ottawa"},{"COSTA RICA","San Jose"},
{"CUBA","Havana"},{"DOMINICA","Roseau"},
{"DOMINICAN REPUBLIC","Santo Domingo"},
{"EL SALVADOR","San Salvador"},
{"GRENADA","Saint George's"},
Chapter 11,Collections of Objects
g12544 32 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
{"GUATEMALA","Guatemala City"},
{"HAITI","Port-au-Prince"},
{"HONDURAS","Tegucigalpa"},
{"JAMAICA","Kingston"},
{"MEXICO","Mexico City"},
{"NICARAGUA","Managua"},
{"PANAMA","Panama City"},{"ST,KITTS","-"},
{"NEVIS","Basseterre"},{"ST,LUCIA","Castries"},
{"ST,VINCENT AND THE GRENADINES","Kingstown"},
{"UNITED STATES OF AMERICA","Washington,D.C."},
// South America
{"ARGENTINA","Buenos Aires"},
{"BOLIVIA","Sucre (legal)/La
Paz(administrative)"},
{"BRAZIL","Brasilia"},{"CHILE","Santiago"},
{"COLOMBIA","Bogota"},{"ECUADOR","Quito"},
{"GUYANA","Georgetown"},{"PARAGUAY","Asuncion"},
{"PERU","Lima"},{"SURINAME","Paramaribo"},
{"TRINIDAD AND TOBAGO","Port of Spain"},
{"URUGUAY","Montevideo"},
{"VENEZUELA","Caracas"},
};
} ///:~
这只是一个两维的字g12538g1030数组。6g991面是fill( )方法g2656generator的g8991
g16809,
//,c11:FillTest.java
import com.bruceeckel.util.*;
import java.util.*;
public class FillTest {
private static Generator sg =
new Arrays2.RandStringGenerator(7);
public static void main(String[] args) {
List list = new ArrayList( );
Collections2.fill(list,sg,25);
System.out.println(list + "\n");
List list2 = new ArrayList( );
Collections2.fill(list2,Collections2.capitals,
25);
System.out.println(list2 + "\n");
Set set = new HashSet( );
Collections2.fill(set,sg,25);
System.out.println(set + "\n");
Map m = new HashMap( );
Collections2.fill(m,Collections2.rsp,25);
System.out.println(m + "\n");
Map m2 = new HashMap( );
Collections2.fill(m2,Collections2.geography,
25);
System.out.println(m2);
}
} ///:~
6g17837g1135g6980g6466g7171g3324Internetg990g6226g11352g712g6117g11004Pythong12255g5219g1328g1114g980g991g3800g10714 (g16277www.Python.org)g452
Thinking in Java 3rd Edition
g12544 33 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
有了这些工具，你就能用有g4466际意g1053的数据来g8991g16809g4493g3132了。
容器的缺点：不知道对象的类型
Java的g4493g3132有个g13582点，就是往g4493g3132g18336面放对象的时候，会把对象的类型信息给g5336g1014了。这是因为g5332g2469g4493g3132类的程序员不会知道你要用g4439来保g4396什么类型的对象，而g16765g4493g3132g1177只保g4396特定类型的对象又会g5445g2721g4439的通用g5627。
所以g4493g3132g15999g1582成只持有Object，也就是所有对象的根类的reference，
这样g4439就能持有任何类型的对象了。(当g9994不g2265g6336primitive，因为g4439们不是对象，也没有继承g2047的对象。)这是一个很了不g17227的方g7708，只是,
1,g11013于在g4570对象放入g4493g3132的时候，g4439的类型信息g15999g6184g6493了，所以g4493g3132对
g256能往g18336面g2164什么类型的对象g257没有限g2058。g8616方说，即g1363你想g16765g4439只持有cat，g2047人也能很轻g7143地把dog放进去。
2,g11013于对象的类型信息没了，g4493g3132只知道g4439持有的Object的reference，
所以对象在g1363用g1055前g17836g5529g20047进行类型g17728g6454。
好的一面是,Java不会g16765你误用放进g4493g3132g18336的对象。g1563g16786你往cat的g4493
g3132g18336面g6184了个dog，g9994g2530要把这个g4493g3132g18336的所有对象都当cat来用，当你把dog的reference从cat的g4493g3132g18336面g6301出来，并g1000g16809g3282g4570g4439g17728g6454成
cat的时候，就会引g2469一个RuntimeException。
接g991来我们就用大g4490g7380常用ArrayListg4493g3132类来g1042一个g1375g4388。对g2033g4410者来说，你可以把ArrayList想成g256一个能g3827自动g6205g4649的数组g257。
ArrayList的用法也是很g12628g2345：g1820创建一个，用add( )把对象放进去，
要用的时候g1889给get( )传一个g991标——就g17331用数组差不多，只是不需要用方g6336号了。7ArrayList也有一个size( )方法，g4439会告诉你g4493g3132g18336面有多少对象，这样你就不会g12907g5527大意地过了g11040g9994g2530引g2469异常了。
g1820创建Catg2656Dog,
//,c11:Cat.java
package c11;
public class Cat {
private int catNumber;
public Cat(int i) { catNumber = i; }
public void id( ) {
System.out.println("Cat #" + catNumber);
}
} ///:~
7g17837g12193g3332g7053g14033g18337g17745g17828g12651g12538g4613g3921g1114g452
Chapter 11,Collections of Objects
g12544 34 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
//,c11:Dog.java
package c11;
public class Dog {
private int dogNumber;
public Dog(int i) { dogNumber = i; }
public void id( ) {
System.out.println("Dog #" + dogNumber);
}
} ///:~
g1820把Catg2656Dog放进g4493g3132，g9994g2530g1889把g4439们g6450出来,
//,c11:CatsAndDogs.java
// Simple container example,
// {ThrowsException}
package c11;
import java.util.*;
public class CatsAndDogs {
public static void main(String[] args) {
List cats = new ArrayList( );
for(int i = 0; i < 7; i++)
cats.add(new Cat(i));
// Not a problem to add a dog to cats,
cats.add(new Dog(7));
for(int i = 0; i < cats.size( ); i++)
((Cat)cats.get(i)).id( );
// Dog is detected only at run time
}
} ///:~
Catg2656Dog是两个不同的类g727g19512了都是对象g1055外，g4439们没有什么相同g1055
处。(g3926果你不g7138确地说g7138这个类是继承g16853的，g18039么g4439就自动继承
Object。)g11013于ArrayList持有的是Object，所以你不g1306能用
ArrayList的add( )来g2164Cat，也可以用g4439来g2164Dog。这么g1582在编译
g2656运行的时候都不会报错。g1306是，当你用get( )方法把你g16760为是Cat的对象取出来的时候，你得到的是一个要g17728g6454成Cat的Object的
reference。于是，在你能g16855用Cat的id( )方法g1055前，你g17836要用g6336号来g1582g5390g2058的类型g17728g6454g727不g9994的g16817就是一个语法错误。这样，到程序运行的时候，当你把Dogg17728g6454成Cat的时候，就会得到一个异常了。
这g17836不只是g21647g9914。g4439g17836会g2058造一些很g19602g2469g10628的bug。g1563g3926程序在什么地方
(或好几个地方)往g4493g3132g18336面插了对象，g9994g2530你g2469g10628，只要程序g6203行到了这个地方，就会有一个异常g17317出来，告诉你g4493g3132g18336面有一个错误的对象，于是你就得把这个g3363的插入点g6226出来。在绝大多数情况g991，这不是什么问题，g1306是你g17836是g5224g16825对这种可能g5627保持g16698g5801。
Thinking in Java 3rd Edition
g12544 35 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
有时即使不正确它也能运行
有时，即便不把对象g17728g6454成原g1820的类型，g4439好像也能正常工g1328。有一种情况g8616g17751特殊：String 能从编译g3132g18039g18336得到一些能g1363g1055g5191稳工g1328的特殊帮助。只要编译g3132没能得到g4439所g7411望的String对象，g4439就会g16855用
toString( )。这个方法g11013Object定g1053，能g15999任何Java类覆g1901。g4439
所g17832g3250的String对象，会g15999用到任何要用g4439的地方。
于是只要覆g1901了类的toString( )方法，你就能g6183g2372对象了，就像g991面这样,
//,c11:Mouse.java
// Overriding toString( ),
public class Mouse {
private int mouseNumber;
public Mouse(int i) { mouseNumber = i; }
// Override Object.toString( ),
public String toString( ) {
return "This is Mouse #" + mouseNumber;
}
public int getNumber( ) { return mouseNumber; }
} ///:~
//,c11:MouseTrap.java
public class MouseTrap {
static void caughtYa(Object m) {
Mouse mouse = (Mouse)m; // Cast from Object
System.out.println("Mouse," +
mouse.getNumber( ));
}
} ///:~
//,c11:WorksAnyway.java
// In special cases,things just seem to work
correctly,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class WorksAnyway {
private static Test monitor = new Test( );
public static void main(String[] args) {
List mice = new ArrayList( );
for(int i = 0; i < 3; i++)
mice.add(new Mouse(i));
for(int i = 0; i < mice.size( ); i++) {
// No cast necessary,automatic
// call to Object.toString( ),
System.out.println("Free mouse," +
mice.get(i));
Chapter 11,Collections of Objects
g12544 36 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
MouseTrap.caughtYa(mice.get(i));
}
monitor.expect(new String[] {
"Free mouse,This is Mouse #0",
"Mouse,0",
"Free mouse,This is Mouse #1",
"Mouse,1",
"Free mouse,This is Mouse #2",
"Mouse,2"
});
}
} ///:~
你会g2469g10628Mouse的toString( )g15999覆g1901了。main( )的g12544二个forg5502
g10627g18336有g991面这句,
System.out.println("Free mouse," + mice.get(i));
编译g3132g20056计‘+’g2530面g17331着的是一个String对象。而get( )g17832g3250了一个Object，所以为了得到g4439所g7411望的String，编译g3132会g1611g1611地g16855用
toString( )。g17963g6034的是，你只能对Stringg10621这g3883把g6115g727g1866g4439类不行。
g12544二种解决方g7708是把类型g17728g6454g15267g17227来，把g4439放到MouseTrapg18336面去。
caughtYa( )方法接受的不是Mouse，而是一个要g17728g6454成Mouse的
Object。当g9994，这种g1582法是相当专g8190的，g11013于g4439g6355的是Object，因此什么g1008g16211都能传给g4439了。g1306是g3926果类型g17728g6454g3845g17145了，g1563g16786你传了一个错误的类型，程序运行的时候就会抛出异常。这当g9994不g2462编译时的g7828查，g1306也
g17836g12651g1593g3778。g8892意，g3926果你用这种方法,
MouseTrap.caughtYa(mice.get(i));
类型g17728g6454就不g1889需要了。
做一个类型敏感的ArrayList
可能你不会就这样放g5335这个问题。g17836有一个更g7092g3374不g6715的解决方g7708，就是用ArrayList来建一个新的类，g16765g4439只能处理你规定的类型,
//,c11:MouseList.java
// A type-conscious List,
import java.util.*;
public class MouseList {
private List list = new ArrayList( );
public void add(Mouse m) { list.add(m); }
Thinking in Java 3rd Edition
g12544 37 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
public Mouse get(int index) {
return (Mouse)list.get(index);
}
public int size( ) { return list.size( ); }
} ///:~
g991面就是对这个新g4493g3132g1582的g8991g16809,
//,c11:MouseListTest.java
import com.bruceeckel.simpletest.*;
public class MouseListTest {
private static Test monitor = new Test( );
public static void main(String[] args) {
MouseList mice = new MouseList( );
for(int i = 0; i < 3; i++)
mice.add(new Mouse(i));
for(int i = 0; i < mice.size( ); i++)
MouseTrap.caughtYa(mice.get(i));
monitor.expect(new String[] {
"Mouse,0",
"Mouse,1",
"Mouse,2"
});
}
} ///:~
g19512了有一个private的ArrayList，以g2462两个很像ArrayList的方法
g1055外，新的MouseList同前面g18039个g1375g4388非常像。g1306是g4439不g1889接g6922g2656g17832g3250
泛型的Object对象了，g4439只处理Mouse对象。
g8892意，g3926果MouseList是继承ArrayList的，g18039么add(Mouse)就
g2476成了对add(Object)的g18337g17745了，于是g256g4493g3132能放什么对象g257g17836是没有限g2058，而你也不会得到你所希望的g6940果。而用了合成g1055g2530，MouseList
只是g2345g13443地g2045用了ArrayList。g4439会g1820g1582一些工g1328，g9994g2530g1889把g991一步的任g2165交给ArrayList。
因为MouseList只接受Mouse，所以g3926果你说,
mice.add(new Pigeon( ));
编译的时候就会报错。g15441g9994g1177从g1207码的角g5242来g16774，这种方g7708g8616g17751g1899g19283，g1306
是g3926果你用错了类型，g4439会立g2063告诉你。
g16772g1315，get( )的时候不需要g1582类型g17728g6454g727g4439g8716g17840都是Mouse。
Chapter 11,Collections of Objects
g12544 38 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
参数化类型 (Parameterized types)
这并不是一个g4408立的问题。很多时候，你都会碰到要g2045用g1866g4439类型创建新的类型，而编译的时候这种类型的信息又是极为有用的情况。这就是所g16871
的g256g2454数g2282类型(parameterized types)g257的g8022念了。在C++g1025，g4439是用
templates直接g11013语言提供支持的。Java很可能会在JDK 1.5g18336面提供
g4439自己的g2454数g2282类型，generics。
迭代器
g7092论是g2750种g4493g3132，你都得有办法既能放g1008g16211进去，也能g6355g1008g16211出来。g8617
竟，g4493g3132的g1039要任g2165就是g4396放对象。ArrayList的add( )就是用来放g1008
g16211的，而get( )则是把对象g6355出来的办法。ArrayList很g9801g8975g727你可以
g19555时提取任何g1008g16211，并g1000g6454一个g991标，g20544上就能g17885g6333g2490一个g1815g13044。
g1306是，g3926果你深入g991去，就会g2469g10628这么g1582会有一个g13582点：要这样用的g16817，
你g5529g20047g20056g1820知道g4493g3132的确切类型。可能g2030g5332g3999的时候，你会觉得这并不是什么问题，g1306是g1563g16786，你用ArrayListg1582了个g16786计，g9994g2530g2469觉，在这种情况g991，g17885Set才对，g18039你g16825怎么办g2614g731或者，你想g1901一段泛型程序，
为了g16765g4439能g256不g13475g18337g1901就能同各种g4493g3132一同工g1328g257，g4439g5224g16825既不知道也不关g5527g4439要处理的是g2750种g4493g3132，g18039么你又g16825怎么办g2614g731
g256g17857g1207g3132(iterator)g257的g8022念(又是一个g16786计模式)就是用来达成这种g6289象的。g17857g1207g3132是一个对象，g4439的任g2165是，能在g16765g256g4470户程序员在不知道，或者不关g5527他所处理的是什么样的底g4630序g2027g13479g7512g257的情况g991，就能在一个对象序g2027g1025前g2530g12239动，并g17885取g1866g1025的对象。此外g17857g1207g3132g17836是一种通常所说的
g256轻量g13435g257的对象，即创建g1207g1227很小的对象。所以，你常会g2469g10628g17857g1207g3132有一些看上去很g3867g5630的限g2058：g8616g3926有些g17857g1207g3132只能按一个方向g12239动。
Java的Iterator就属于有这种限g2058的g17857g1207g3132。g4439g1582不了很多事情，g19512
了,
1,用iterator( )方法叫g4493g3132传给你一个Iterator对象。g12544一g8437g16855用
Iterator的next( )方法的时候，g4439就会传给你序g2027g1025的g12544一个g1815g13044。
2,用next( )方法g14731取序g2027g1025的g991一个对象。
3,用hasNext( )方法查询序g2027g1025是否g17836有g1866他对象。
4,用remove( )方法g2036g19512g17857g1207g3132所g17832g3250的g7380g2530一个g1815g13044。
就这么多了。这只是g17857g1207g3132的一个很g12628g2345的g4466g10628，不过g17836是很g5390大(对
List来说，g17836有一个更g12946g5051的ListIterator)。为了能看到g4439是怎样工
g1328的，我们要g18337g1901一g17953g7424g12468前面所g16774的CatsAndDogs.java。原来我们是用get( )来g17885取g1815g13044的，g10628在我们要用Iterator,
//,c11:CatsAndDogs2.java
// Simple container with Iterator,
Thinking in Java 3rd Edition
g12544 39 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
package c11;
import com.bruceeckel.simpletest.*;
import java.util.*;
public class CatsAndDogs2 {
private static Test monitor = new Test( );
public static void main(String[] args) {
List cats = new ArrayList( );
for(int i = 0; i < 7; i++)
cats.add(new Cat(i));
Iterator e = cats.iterator( );
while(e.hasNext( ))
((Cat)e.next( )).id( );
}
} ///:~
可以看到，g7380g2530这几行是用Iterator，而不是forg5502g10627来g17953g2394g6984个序g2027
的。有了Iterator，你就不用g6817g5527g4493g3132g18336g17836有几个g1815g13044。hasNext( )
g2656next( )g5062g13475帮你g6183理好了。
g1889g1042一个g1375程，想想怎样g1901一个通用的g6183g2372程序,
//,c11:Printer.java
// Using an Iterator,
import java.util.*;
public class Printer {
static void printAll(Iterator e) {
while(e.hasNext( ))
System.out.println(e.next( ));
}
} ///:~
仔细看printAll( )。g8892意一g991，g4439g18336面没有要g6183g2372g2750种序g2027的信息。g4439
要的只是一个Iterator的对象，对一个序g2027来说这g5062g13475g3827了：你可以用
g4439来g14731取g4493g3132g1025的g991一个对象，g4439也会告诉你是不是到g11040了。这种g256一g991
g4388就g6355走g4493g3132g18336的所有对象，g9994g2530g1889一个一个地进行处理g257的思g17347是非常
g5390大的，也是g17155g12371g7424g1082的。
g4466际上这段程序g17836要泛g2282，因为g4439g17836隐含地g16855用了Object.toString( )
方法。println( )对所有的primitveg2656Object都g1582了g18337g17745g727在各种情况g991，g4439都会自动g16855用合g17878的toString( )方法来g10995成g4439所需的String
对象。
尽管不是g5529g20047的，g1306你g17836是可以g7138确地g1363用类型传g17894。g13479果就是g16855用
toString( ),
System.out.println((String)e.next( ));
Chapter 11,Collections of Objects
g12544 40 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
总g1055，g19512了是g16855用Object的方法，一般情况g991，你总g17836要g1582一些g1866他事情，否则又会g6770上类型传g17894的问题了。你要把g4439当g1328你感g1864g17271的g18039种对象的序g2027的Iterator，g9994g2530把g4439g17728g6454成g11458标类型(g3926果出了错，又会得到一个运行时异常)。
我们可以用g4439来g6183g2372Hamsters，并以此g1328一个g8991g16809,
//,c11:Hamster.java
public class Hamster {
private int hamsterNumber;
public Hamster(int hamsterNumber) {
this.hamsterNumber = hamsterNumber;
}
public String toString( ) {
return "This is Hamster #" + hamsterNumber;
}
} ///:~
//,c11:HamsterMaze.java
// Using an Iterator,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class HamsterMaze {
private static Test monitor = new Test( );
public static void main(String[] args) {
List list = new ArrayList( );
for(int i = 0; i < 3; i++)
list.add(new Hamster(i));
Printer.printAll(list.iterator( ));
monitor.expect(new String[] {
"This is Hamster #0",
"This is Hamster #1",
"This is Hamster #2"
});
}
} ///:~
你可以g1901一个g6355Collection对象当g2454数的printAll( )，g1306是
Iterator能提供更好的g256g14085g19069g7438g2058(decoupling)g257。
不经意的递归 (Unintended recursion)
g11013于Java的标准g4493g3132类(同g1866g4439类一样)也是继承Object的，因此g4439们也有一个toString( )方法。这个方法g5062g13475g15999覆g1901了，所以g4439能g10995成一个表g12046g4439自己以g2462所有g4439所保g4396的对象的String。g8616g3926ArrayList的
Thinking in Java 3rd Edition
g12544 41 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
toString( )方法就会g17953g2394ArrayList的每个g1815g13044，g9994g2530g16855用g4439们的
toString( )方法。g1563g16786你要g6183g2372类的地g3348。好像g7380直接的办法就是g1363用
this(C++的程序员g4600g1866g2928g8438用这种办法),
//,c11:InfiniteRecursion.java
// Accidental recursion,
// {RunByHand}
import java.util.*;
public class InfiniteRecursion {
public String toString( ) {
return " InfiniteRecursion address," + this +
"\n";
}
public static void main(String[] args) {
List v = new ArrayList( );
for(int i = 0; i < 10; i++)
v.add(new InfiniteRecursion( ));
System.out.println(v);
}
} ///:~
g3926果你直接创建一个InfiniteRecursion，g9994g2530把g4439g6183g2372出来，你就会得到一g1030g7092g12363g7092尽的异常。把g4439放到ArrayList也一样。这是
toString( )在g1328g5630。当你g1901,
"InfiniteRecursion address," + this
的时候，编译g3132看到Stringg2656‘+’g2530面g17331着的不是String。于是g4439
g16809着g4570thisg17728g6454成String。g17728g6454要用到toString( )，于是就g2476成g17894
g5414g16855用了。
g3926果你真的想g6183g2372对象的地g3348，解决办法就是去g16855用Object的
toString( )方法，g4439就是g5190这g8975的。所以不要用this，g5224g16825g1901
super.toString( )。
容器分类学
根据编程的需要，Collectiong2656Mapg2010g2047有好几个g4466g10628。所以看g6038
Javag4493g3132类(JDK 1.4)的关系g3282是很有用的。
Chapter 11,Collections of Objects
g12544 42 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g12544一眼看到这g5364g3282的时候，你会觉得很g19675g6800。不过你g20544上就会知道，g4466际上只有g989种g4493g3132组g1226——Map，Listg2656Set，而每种又有两到g989个g4466
g10628。g7380常用的几个g4493g3132g5062g13475用g12907g21669g13459g7706了g17227来。看到这g18336，这g5364g3282就不g1889
g18039么g1208人望而g10995g11043了。
用点号g7706g17227来的是interface，用g15406g13459g7706g17227来的是abstract类，g4466g13459
则表g12046g7234通的(g256g4466体concreteg257)类。点g13459的g12673头表g12046类g4466g10628了这个
interface(或者，abstract类表g12046g18108g2010g4466g10628了这个interface)。g4466g13459
g12673头表g12046这个类可以g2058造g12673头所指的g18039个类的对象。g8616g3926，Collection
能g2058造Iterator，而Listg17836能g2058造ListIterator(也能g2058造
Iterator，因为List是继承自Collection的)。
g994g4396放对象有关的接g2487g2265g6336Collection，List，Setg2656Map。在理想情况g991，绝大多数g1207码g5224g16825只同这些接g2487g6183交道，只是在创建g4493g3132的时候才要g12946确地指g7138g4439的确切类型。所以你可以这样创建一个List。
List x = new LinkedList( );
Thinking in Java 3rd Edition
g12544 43 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
当g9994，你也可以g17885g6333g16765x成为LinkedList(而不是泛型的List)，这样
x就g5114上了准确的类型信息。interface的优g19609 (同时也是g4439的g7424意)就在于，你想g1474g6925具体的g4466g10628的时候，只要g6925一g991创建的g3780g7138就可以了，就像这样,
List x = new ArrayList( );
g7092需g5790动g1866g4439g1207码(用g17857g1207g3132也能g14731得一些这种泛型g5627)。
这个类系g18336面有很多以“Abstract”g5332头的类，g2033看g17227来这可能会g16765人有点不g7138g11345。g4466际上g4439们只是一些g18108g2010g4466g10628某个接g2487的办成g2709。g1563g3926你要编一个你自己的Set，不要从Set接g2487g5332g3999g6396个g4466g10628g4439的方法g727相反你
g7380好继承AbstractSet，这样就能把编程的工g1328量g2399g13565到g7380g1314了。g1306
是，g4466际上g4493g3132类库的功能g5062g13475g3827g5390的了，我们要求的事情g4439几乎都能g1582
到。所以对我们来说，你g4448g1852可以忽略以“Abstract”g5332头的类。
因此看这g5364g3282的时候，真正需要关g5527只是g20042g4630的interfaceg2656g18039些g4466体类(用g4466g13459g7706g17227来的g18039些)。通常你会创建g4466体类的对象，g9994g2530把g4439上传到相g5224的interface，g1889在程序g18336面g1363用这个interface。此外，g1901新g1207
码的时候不用g13783g15397用g5062g13475g9132g8772的g1008g16211。所以这g5364g3282能g15999g12628g2282为g3926g991所g12046,
g10628在g4439只g2265g6336g18039些你g5191常会用到的接g2487g2656类了。这些g1008g16211也是g7424g12468要着g18337
探讨的。g8892意，这g5364g3282g18336没有g2265g6336WeakHashMapg2656JDK 1.4的
IdentityHashMap。这是因为g4439们是有特殊用途的，你不太可能会用到g4439们。
Chapter 11,Collections of Objects
g12544 44 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g991面就是一个用String对象来g3647g1817 (用ArrayList表g12046的)
Collection，并g1000g6183g2372g1866所有g1815g13044的g1375g4388,
//,c11:SimpleCollection.java
// A simple example using Java 2 Collections,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class SimpleCollection {
private static Test monitor = new Test( );
public static void main(String[] args) {
// Upcast because we just want to
// work with Collection features
Collection c = new ArrayList( );
for(int i = 0; i < 10; i++)
c.add(Integer.toString(i));
Iterator it = c.iterator( );
while(it.hasNext( ))
System.out.println(it.next( ));
monitor.expect(new String[] {
"0",
"1",
"2",
"3",
"4",
"5",
"6",
"7",
"8",
"9"
});
}
} ///:~
main( )的g12544一行创建了一个ArrayList对象，g9994g2530把g4439上传给了
Collection。g11013于程序只用到了Collection的方法，因此只要是继承
Collection的都能正常工g1328，不过ArrayList是我们g7380常用的
Collection。
add( )，就像g4439的名字告诉我们的，会把新的g1815g13044放进Collection。
g1306是文g7735g18336面特g2047仔细地g3780g7138，g256add( )会确保g4493g3132g2265含指定的g1815
g13044g257。这句g16817是说给Set的，因为g4439只g9167g2164原g1820没有的g1815g13044。对
ArrayList或g1866g4439List，add( )总是g256把g4439放进去g257，因为List并不关g5527g4439是不是保g4396了相同的g1815g13044。
Collection都能用iterator( )方法g1147g10995一个Iterator。这g18336，我们用Iterator来g17953g2394g6984个Collection，g9994g2530把g4439们g6183g2372出来。
Collection的功能
Thinking in Java 3rd Edition
g12544 45 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g991面这g5364表给出了Collection的所有功能，也就是你能用Setg2656List
g1582什么事(不g2265g6336从Object自动继承过来的方法)。(Listg17836有一些g20081外的功能。)Map不是继承Collection的，所以我们会g2318g2047对g5465。
boolean add(Object) 确保g4493g3132能持有你传给g4439的g18039个g2454数。
g3926果没能把g4439g2164进去，就g17832g3250false。
(这是个g256可g17885g257的方法，g7424g12468g12257g2530会
g1889g1328解g18334。)
boolean
addAll(Collection)
g2164入g2454数Collection所含的所有g1815
g13044。只要g2164了g1815g13044，就g17832g3250true。
(g256可g17885g257)
void clear( ) g9177g19512g4493g3132所保g4396的所有g1815g13044。(g256可
g17885g257)
boolean
contains(Object)
g3926果g4493g3132持有g2454数Object，就g17832g3250
true。
boolean
containsAll(Collection)
g3926果g4493g3132持有g2454数Collection所含的
g1852g18108g1815g13044，就g17832g3250true。
boolean isEmpty( ) g3926果g4493g3132g18336面没有保g4396任何g1815g13044，就g17832
g3250true。
Iterator iterator( ) g17832g3250一个可以在g4493g3132的各g1815g13044g1055间g12239动的Iterator。
boolean
remove(Object)
g3926果g4493g3132g18336面有这个g2454数Object，g18039
么就把g1866g1025的某一个给g2036了。只要g2036g19512
过g1008g16211，就g17832g3250true。(g256可g17885g257)
boolean
removeAll(Collection)
g2036g19512g4493g3132g18336面所有g2454数Collection所
g2265含的g1815g13044。只要g2036过g1008g16211，就g17832g3250
true。(g256可g17885g257)
boolean
retainAll(Collection)
只保g4396g2454数Collection所g2265g6336的g1815g13044
(g19610合论g1025g256交g19610g257的g8022念)。g3926果g2469g10995
过g2476g2282，则g17832g3250true。(“可g17885”)
int size( ) g17832g3250g4493g3132所含g1815g13044的数量。
Object[] toArray( ) g17832g3250一个g2265含g4493g3132g1025所有g1815g13044的数组。
Object[]
toArray(Object[] a)
g17832g3250一个g2265含g4493g3132g1025所有g1815g13044的数组，
g1000这个数组不是g7234通的Object数组，
g4439的类型g5224g16825同g2454数数组a的类型相同
(要g1582类型g17728g6454)。
g8892意，这g18336没有能进行g19555g7438g16787问的get( )方法。这是因为Collection
g17836g2265g6336Set。而Set有g4439自己的内g18108顺序(因此g19555g7438g16787问是g8639g7092意g1053
的)。所以g3926果你要g7828查Collection的g1815g13044，你就g5529g20047g1363用g17857g1207g3132。
Chapter 11,Collections of Objects
g12544 46 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g991面这段程序把这些方法都g9448g12046了一g17953。g1889g16774一g991，g4466g10628了Collection
接g2487的g4493g3132都有这些功能，只是ArrayList是用着g7380顺手的,
//,c11:Collection1.java
// Things you can do with all Collections,
import com.bruceeckel.simpletest.*;
import java.util.*;
import com.bruceeckel.util.*;
public class Collection1 {
private static Test monitor = new Test( );
public static void main(String[] args) {
Collection c = new ArrayList( );
Collections2.fill(c,Collections2.countries,5);
c.add("ten");
c.add("eleven");
System.out.println(c);
// Make an array from the List,
Object[] array = c.toArray( );
// Make a String array from the List,
String[] str = (String[])c.toArray(new
String[1]);
// Find max and min elements; this means
// different things depending on the way
// the Comparable interface is implemented,
System.out.println("Collections.max(c) = " +
Collections.max(c));
System.out.println("Collections.min(c) = " +
Collections.min(c));
// Add a Collection to another Collection
Collection c2 = new ArrayList( );
Collections2.fill(c2,Collections2.countries,5);
c.addAll(c2);
System.out.println(c);
c.remove(CountryCapitals.pairs[0][0]);
System.out.println(c);
c.remove(CountryCapitals.pairs[1][0]);
System.out.println(c);
// Remove all components that are
// in the argument collection,
c.removeAll(c2);
System.out.println(c);
c.addAll(c2);
System.out.println(c);
// Is an element in this Collection?
String val = CountryCapitals.pairs[3][0];
System.out.println("c.contains(" + val + ") = "
+ c.contains(val));
// Is a Collection in this Collection?
System.out.println(
"c.containsAll(c2) = " + c.containsAll(c2));
Collection c3 = ((List)c).subList(3,5);
// Keep all the elements that are in both
// c2 and c3 (an intersection of sets),
c2.retainAll(c3);
System.out.println(c);
// Throw away all the elements
// in c2 that also appear in c3,
c2.removeAll(c3);
Thinking in Java 3rd Edition
g12544 47 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
System.out.println("c.isEmpty( ) = " +
c.isEmpty( ));
c = new ArrayList( );
Collections2.fill(c,Collections2.countries,5);
System.out.println(c);
c.clear( ); // Remove all elements
System.out.println("after c.clear( ):");
System.out.println(c);
monitor.expect(new String[] {
"[ALGERIA,ANGOLA,BENIN,BOTSWANA,BURKINA
FASO," +
"ten,eleven]",
"Collections.max(c) = ten",
"Collections.min(c) = ALGERIA",
"[ALGERIA,ANGOLA,BENIN,BOTSWANA,BURKINA
FASO," +
"ten,eleven,BURUNDI,CAMEROON,CAPE VERDE,"
+
"CENTRAL AFRICAN REPUBLIC,CHAD]",
"[ANGOLA,BENIN,BOTSWANA,BURKINA FASO,ten,
" +
"eleven,BURUNDI,CAMEROON,CAPE VERDE," +
"CENTRAL AFRICAN REPUBLIC,CHAD]",
"[BENIN,BOTSWANA,BURKINA FASO,ten,eleven,
" +
"BURUNDI,CAMEROON,CAPE VERDE," +
"CENTRAL AFRICAN REPUBLIC,CHAD]",
"[BENIN,BOTSWANA,BURKINA FASO,ten,eleven]",
"[BENIN,BOTSWANA,BURKINA FASO,ten,eleven,
" +
"BURUNDI,CAMEROON,CAPE VERDE," +
"CENTRAL AFRICAN REPUBLIC,CHAD]",
"c.contains(BOTSWANA) = true",
"c.containsAll(c2) = true",
"[BENIN,BOTSWANA,BURKINA FASO,ten,eleven,
" +
"BURUNDI,CAMEROON,CAPE VERDE," +
"CENTRAL AFRICAN REPUBLIC,CHAD]",
"c.isEmpty( ) = false",
"[COMOROS,CONGO,DJIBOUTI,EGYPT," +
"EQUATORIAL GUINEA]",
"after c.clear( ):",
"[]"
});
}
} ///:~
我们把数据放在ArrayListg18336面，g9994g2530把g4439传给Collection，所以很
g9177g7982，g19512了Collection接g2487，我们什么都没用。main( )只是g12628g2345地
g9448g12046了一g17953Collection的方法。
接g991来我们要g16774List，Setg2656Map的各种g4466g10628了，每g16774一种g4493g3132，我都会(用g7155号)告诉你g21676g16760情况g991g5224g16825g17885用g2750种g4466g10628。你会g2469g10628，我们没把老式的Vector，Stackg2656Hashtableg2265g6336进来。这是因为，g7092论是
g2750种g4493g3132，Java 2 的类库g18336都有更好的g17885g6333。
Chapter 11,Collections of Objects
g12544 48 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
List的功能
正g3926你从ArrayListg18039g18336所看到的，List的g3534g7424用法是相当g12628g2345的。g15441
g9994绝大多数时候，你只是用add( )g2164对象，用get( )取对象，用
iterator( )g14731取这个序g2027的Iterator，g1306Listg17836有一些g2047的很有用的方法。
g4466际上有两种List：g6809g19283对g1815g13044进行g19555g7438g16787问的，g17751常用的
ArrayList，g2656更g5390大的LinkedList。LinkedList不是为g5567g17907的g19555g7438
g16787问而g16786计的，g1306是g4439却有一组更g2164通用的方法。
List (接g2487) List的g7380g18337要的特g5461就是有序g727g4439会确保以一定的顺序保g4396g1815g13044。List在Collection的g3534g11796上g9167g2164
了大量方法，g1363g1055能在序g2027g1025间插入g2656g2036g19512g1815g13044。
(只对LinkedList推g14628g1363用。)List可以g2058造
ListIterator对象，你g19512了能用g4439在List的g1025间插入g2656g2036g19512g1815g13044g1055外，g17836能用g4439g8851两个方向g17953g2394
List。
ArrayList* 一个用数组g4466g10628的List。能进行g5567g17907的g19555g7438g16787问，
g1306是往g2027表g1025间插入g2656g2036g19512g1815g13044的时候g8616g17751g5942。
ListIterator只能用在反向g17953g2394ArrayList的场合，不要用g4439来插入g2656g2036g19512g1815g13044，因为相g8616
LinkedList，在ArrayListg18336面用
ListIterator的系统g5332g19156g8616g17751g20652。
LinkedList 对顺序g16787问进行了优g2282。在Listg1025间插入g2656g2036g19512g1815
g13044的g1207g1227也不g20652。g19555g7438g16787问的g17907g5242相对g17751g5942。(用
ArrayList吧。)此外g4439g17836有addFirst( )，
addLast( )，getFirst( )，getLast( )，
removeFirst( )g2656removeLast( )g12573方法(这些方法，接g2487g2656g3534类g3355未定g1053)，你能把g4439当成g7644
(stack)，队g2027(queue)或双向队g2027(deque)来用。
g991面这段程序把各种g6817g1328都g19610g1025到方法g18336面：List都能g1328的事
(basicTest( ))，用Iterator在g2027表g1025g12239动(iterMotion( ))，g1474g6925
g2027表的g1815g13044(iterManipulation( ))，查看List的g6817g1328g13479果
(testVisual( ))，以g2462LinkedList所g10432有的方法。
//,c11:List1.java
// Things you can do with Lists,
import java.util.*;
import com.bruceeckel.util.*;
public class List1 {
public static List fill(List a) {
Collections2.countries.reset( );
Thinking in Java 3rd Edition
g12544 49 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
Collections2.fill(a,Collections2.countries,10);
return a;
}
private static boolean b;
private static Object o;
private static int i;
private static Iterator it;
private static ListIterator lit;
public static void basicTest(List a) {
a.add(1,"x"); // Add at location 1
a.add("x"); // Add at end
// Add a collection,
a.addAll(fill(new ArrayList( )));
// Add a collection starting at location 3,
a.addAll(3,fill(new ArrayList( )));
b = a.contains("1"); // Is it in there?
// Is the entire collection in there?
b = a.containsAll(fill(new ArrayList( )));
// Lists allow random access,which is cheap
// for ArrayList,expensive for LinkedList,
o = a.get(1); // Get object at location 1
i = a.indexOf("1"); // Tell index of object
b = a.isEmpty( ); // Any elements inside?
it = a.iterator( ); // Ordinary Iterator
lit = a.listIterator( ); // ListIterator
lit = a.listIterator(3); // Start at loc 3
i = a.lastIndexOf("1"); // Last match
a.remove(1); // Remove location 1
a.remove("3"); // Remove this object
a.set(1,"y"); // Set location 1 to "y"
// Keep everything that's in the argument
// (the intersection of the two sets),
a.retainAll(fill(new ArrayList( )));
// Remove everything that's in the argument,
a.removeAll(fill(new ArrayList( )));
i = a.size( ); // How big is it?
a.clear( ); // Remove all elements
}
public static void iterMotion(List a) {
ListIterator it = a.listIterator( );
b = it.hasNext( );
b = it.hasPrevious( );
o = it.next( );
i = it.nextIndex( );
o = it.previous( );
i = it.previousIndex( );
}
public static void iterManipulation(List a) {
ListIterator it = a.listIterator( );
it.add("47");
// Must move to an element after add( ),
it.next( );
// Remove the element that was just produced,
it.remove( );
// Must move to an element after remove( ),
it.next( );
// Change the element that was just produced,
it.set("47");
}
public static void testVisual(List a) {
Chapter 11,Collections of Objects
g12544 50 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
System.out.println(a);
List b = new ArrayList( );
fill(b);
System.out.print("b = ");
System.out.println(b);
a.addAll(b);
a.addAll(fill(new ArrayList( )));
System.out.println(a);
// Insert,remove,and replace elements
// using a ListIterator,
ListIterator x = a.listIterator(a.size( )/2);
x.add("one");
System.out.println(a);
System.out.println(x.next( ));
x.remove( );
System.out.println(x.next( ));
x.set("47");
System.out.println(a);
// Traverse the list backwards,
x = a.listIterator(a.size( ));
while(x.hasPrevious( ))
System.out.print(x.previous( ) + " ");
System.out.println( );
System.out.println("testVisual finished");
}
// There are some things that only LinkedLists can
do,
public static void testLinkedList( ) {
LinkedList ll = new LinkedList( );
fill(ll);
System.out.println(ll);
// Treat it like a stack,pushing,
ll.addFirst("one");
ll.addFirst("two");
System.out.println(ll);
// Like "peeking" at the top of a stack,
System.out.println(ll.getFirst( ));
// Like popping a stack,
System.out.println(ll.removeFirst( ));
System.out.println(ll.removeFirst( ));
// Treat it like a queue,pulling elements
// off the tail end,
System.out.println(ll.removeLast( ));
// With the above operations,it's a dequeue!
System.out.println(ll);
}
public static void main(String[] args) {
// Make and fill a new list each time,
basicTest(fill(new LinkedList( )));
basicTest(fill(new ArrayList( )));
iterMotion(fill(new LinkedList( )));
iterMotion(fill(new ArrayList( )));
iterManipulation(fill(new LinkedList( )));
iterManipulation(fill(new ArrayList( )));
testVisual(fill(new LinkedList( )));
testLinkedList( );
}
} ///:~
Thinking in Java 3rd Edition
g12544 51 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
为了g12046g14551正确的语法，我们g16765basicTest( )g2656iterMotion( )g16855用了一些方法。g15441g9994我们g6355了g17832g3250的值，g1306是却没有用g4439。有时，程序根g7424就不去g6355g17832g3250值。g1901程序g1055前，你g5224g16825到java.sun.com去看看JDK的文
g7735，查一查这些方法的g4448g6984用法。
g16772g1315，g4493g3132只是一个g4396g1660对象的g11430g4388。g3926果这个小g11430g4388能帮你解决所有的问题，g18039你就用不着去管g4439是怎么g4466g10628的(在绝大多数情况g991，这是g1363用对象的g3534g7424g8022念)。g3926果g5332g2469g10627g3671g18336面g17836有一些g2047的，会造成g3278定的g5627能
g5332g19156的因g13044g4396在，g18039么ArrayListg2656LinkedListg1055间的g5627能差g2047就会
g2476得不g18039么g18337要了。你只需要g4439们g1025的一个。你甚至可以想像有这样一种
g256g4448g13666g257的g6289象g4493g3132：g4439能根据用途，自动地切g6454g1866底g4630的g4466g10628。
用LinkedList做一个栈
g256g7644(stack)g257有时也g15999g12228为g256g2530进g1820出g257(LIFO)的g4493g3132。就是说，g7380g2530
一个g15999g256g2399g257进g7644g1025的g1008g16211，会g12544一个g256g5389g257出来。同g1866他Javag4493g3132一样，g2399进去g2656g5389出来的g1008g16211都是Object，所以g19512非你只用Object的功能，否则就g5529g20047对g5389出来的g1008g16211进行类型g17728g6454。
LinkedList的方法能直接g4466g10628g7644的功能，所以你g4448g1852可以不g1901Stack
而直接g1363用LinkedList。g1306是有一个叫g256g7644g257的类能g16765我们把g6937事g16774的更好,
//,c11:StackL.java
// Making a stack from a LinkedList,
import com.bruceeckel.simpletest.*;
import java.util.*;
import com.bruceeckel.util.*;
public class StackL {
private static Test monitor = new Test( );
private LinkedList list = new LinkedList( );
public void push(Object v) { list.addFirst(v); }
public Object top( ) { return list.getFirst( ); }
public Object pop( ) { return
list.removeFirst( ); }
public static void main(String[] args) {
StackL stack = new StackL( );
for(int i = 0; i < 10; i++)
stack.push(Collections2.countries.next( ));
System.out.println(stack.top( ));
System.out.println(stack.top( ));
System.out.println(stack.pop( ));
System.out.println(stack.pop( ));
System.out.println(stack.pop( ));
monitor.expect(new String[] {
"CHAD",
"CHAD",
"CHAD",
"CENTRAL AFRICAN REPUBLIC",
"CAPE VERDE"
});
Chapter 11,Collections of Objects
g12544 52 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
}
} ///:~
g3926果你只想要g7644的功能，g18039么继承就不太合g17878了。因为继承出来的是一个
g6329有LinkedList的所有方法的类(g2530面你就会看到Java 1.0类库的g16786
计者们是怎样g7697在Stack上的)。
用LinkedList做一个队列
队g2027(queue)是一个g256g1820进g1820出g257(FIFO)g4493g3132。也就是，你从一端把g1008
g16211放进去，从g2490一端把g1008g16211取出来。所以你放g1008g16211的顺序也就是取g1008g16211的顺序。LinkedList有支持队g2027的功能的方法，所以g4439也能g15999当g1328
Queue来用。
//,c11:Queue.java
// Making a queue from a LinkedList,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class Queue {
private static Test monitor = new Test( );
private LinkedList list = new LinkedList( );
public void put(Object v) { list.addFirst(v); }
public Object get( ) { return list.removeLast( ); }
public boolean isEmpty( ) { return
list.isEmpty( ); }
public static void main(String[] args) {
Queue queue = new Queue( );
for(int i = 0; i < 10; i++)
queue.put(Integer.toString(i));
while(!queue.isEmpty( ))
System.out.println(queue.get( ));
monitor.expect(new String[] {
"0",
"1",
"2",
"3",
"4",
"5",
"6",
"7",
"8",
"9"
});
}
} ///:~
g17836能很轻g7143地用LinkedListg1582一个deque(双向队g2027)。g4439很像队g2027，
只是你可以从任意一端g9167g2164g2656g2036g19512g1815g13044。
Thinking in Java 3rd Edition
g12544 53 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
Set的功能
Set的接g2487就是Collection的，所以不像g18039两个List，g4439没有g20081外的功能。g4466际上Set确确g4466g4466就是一个Collection——只不过行为方式不同g13622了。(这是继承g2656多g5589g5627的g4448g13666运用：表达不同地行为。)Set会g6310绝持有多个具有相同值的对象的g4466g1375(对象的g256值g257又是g11013什么决定的g2614g731
这个问题g8616g17751g3809g7446，我们以g2530会g16774的)。
Set (接g2487) g2164入Set的每个g1815g13044g5529g20047是唯一的g727否则，
Set是不会把g4439g2164进去的。要想g2164进Set，
Objectg5529g20047定g1053equals( )，这样才能标g7138
对象的唯一g5627。Set的接g2487g2656Collection的一模一样。Set的接g2487不保证g4439会用g2750种顺序来g4396g1660g1815g13044。
HashSet* 为优g2282查询g17907g5242而g16786计的Set。要放进
HashSetg18336面的Objectg17836得定g1053
hashCode( )。
TreeSet 是一个有序的Set，g1866底g4630是一g7881g7653。这样你就能从Setg18336面提取一个有序序g2027了。
LinkedHashSet
(JDK 1.4)
一个在内g18108g1363用链表的Set，既有HashSet
的查询g17907g5242，又能保g4396g1815g13044g15999g2164进去的顺序
(插入顺序)。用Iteratorg17953g2394Set的时候，
g4439是按插入顺序进行g16787问的。
g991面这段程序没有g2027出Set的所有方法，g11013于g4439的接g2487g2656Collection
的是g4448g1852相同的，所以前面g18039个g1375g4388g5062g13475g16774过了。g10628在，g4439要g9448g12046的是
Setg994g1259不同的地方,
//,c11:Set1.java
// Things you can do with Sets,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class Set1 {
private static Test monitor = new Test( );
static void fill(Set s) {
s.addAll(Arrays.asList(
"one two three four five six seven".split("
")));
}
public static void test(Set s) {
// Strip qualifiers from class name,
System.out.println(
s.getClass( ).getName( ).replaceAll("\\w+\\.",
""));
fill(s); fill(s); fill(s);
System.out.println(s); // No duplicates!
// Add another set to this one,
Chapter 11,Collections of Objects
g12544 54 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
s.addAll(s);
s.add("one");
s.add("one");
s.add("one");
System.out.println(s);
// Look something up,
System.out.println("s.contains(\"one\")," +
s.contains("one"));
}
public static void main(String[] args) {
test(new HashSet( ));
test(new TreeSet( ));
test(new LinkedHashSet( ));
monitor.expect(new String[] {
"HashSet",
"[one,two,five,four,three,seven,six]",
"[one,two,five,four,three,seven,six]",
"s.contains(\"one\"),true",
"TreeSet",
"[five,four,one,seven,six,three,two]",
"[five,four,one,seven,six,three,two]",
"s.contains(\"one\"),true",
"LinkedHashSet",
"[one,two,three,four,five,six,seven]",
"[one,two,three,four,five,six,seven]",
"s.contains(\"one\"),true"
});
}
} ///:~
我们往Setg18336面g2164了些g18337g3809的g1815g13044，g1306是g6183g2372的时候，你就会看到，同一个值，Set只接g6922一个g4466g1375。
程序运行的时候，你就会g2469g10628HashSet保g4396对象的顺序是g2656TreeSet
g2656LinkedHashSet不一样的。这是因为g4439们是用不同的方式来g4396g1660g2656
查g6226g1815g13044的。(TreeSet用了一种叫g13430g21669g7653的数据g13479g7512『red-black tree
data structure』来为g1815g13044g6502序，而HashSet则用了g256专为g5567g17907查g6226
而g16786计g257的g6967g2027g2001数。LinkedHashSet在内g18108用g6967g2027来提g20652查询g17907
g5242，g1306是g4439看上去像是用链表来保g4396g1815g13044的插入顺序。)你g1901自己的类的时候，一定要g16772g1315，Set要有一个判断以什么顺序来g4396g1660g1815g13044的标准，也就是说你g5529g20047g4466g10628Comparable接g2487，并g1000定g1053compareTo( )方法。g991面就是g1042g1375,
//,c11:Set2.java
// Putting your own type in a Set,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class Set2 {
private static Test monitor = new Test( );
public static Set fill(Set a,int size) {
for(int i = 0; i < size; i++)
a.add(new MyType(i));
Thinking in Java 3rd Edition
g12544 55 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
return a;
}
public static void test(Set a) {
fill(a,10);
fill(a,10); // Try to add duplicates
fill(a,10);
a.addAll(fill(new TreeSet( ),10));
System.out.println(a);
}
public static void main(String[] args) {
test(new HashSet( ));
test(new TreeSet( ));
test(new LinkedHashSet( ));
monitor.expect(new String[] {
"[2,4,9,8,6,1,3,7,5,0 ]",
"[9,8,7,6,5,4,3,2,1,0 ]",
"[0,1,2,3,4,5,6,7,8,9 ]"
});
}
} ///:~
我们会在g7424g12468的g2530面g18108g2010g16774解怎样定g1053equals( )g2656hashCode( )。
g7092论是用g2750种Set，你都g5224g16825定g1053equals( )，g1306是只有在g256要把对象放进HashSetg257的情况g991，你才需要定g1053hashCode( )(g7380好g17836是定
g1053一个，因为通常情况g991HashSet是Set的首g17885)。g1306是g1328为一种编程
g20130g7696，你g5224g16825在覆g1901equals( )的同时把hashCode( )也覆g1901了。这个过程g4570在g7424g12468的g2530面g18108g2010g1582g1889g1328深入探讨。
g8892意一g991，我没在compareTo( )g18336面用g256g12628g2345g7138了g257的return i-
i2。g15441g9994这是一个很常见的编程错误，g1306是g3926果ig2656i2都是
g256unsignedg257 int的g16817(Javag18336面没有，g1306是g1563g16786g4439有)，g18039g4439g17836是能正常工g1328的。可是Java的singed int把g4439给g8597了，因为g4439太小了，不能用来表g12046两个signed int的差。g1563g3926i是一个很大的正g6984数而j是一个很大的g17139g6984数，g18039么i－j就会g9334出，并g17832g3250一个g17139值，于是程序就出错了。
SortedSet
SortedSet(只有TreeSet这一个g4466g10628可用)g1025的g1815g13044一定是有序的。
这g1363得SortedSet接g2487多了一些方法,
Comparator comparator( )：g17832g3250Set所g1363用的Comparator
对象，或者用null表g12046g4439g1363用Object自有的g6502序方法。
Object first( ),g17832g3250g7380小的g1815g13044。
Object last( ),g17832g3250g7380大的g1815g13044。
Chapter 11,Collections of Objects
g12544 56 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
SortedSet subSet(fromElement,toElement),g17832g3250Set的g4388
g19610，g1866g1025的g1815g13044从fromElementg5332g3999到toElement为止(g2265g6336
fromElement，不g2265g6336toElement)。
SortedSet headSet(toElement)：g17832g3250Set的g4388g19610，g1866g1025的g1815g13044
都g5224小于toElement。
SortedSet headSet(toElement)：g17832g3250Set的g4388g19610，g1866g1025的g1815g13044
都g5224大于fromElement。
g991面是一个g12628g2345的g12046g1375,
//,c11:SortedSetDemo.java
// What you can do with a TreeSet,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class SortedSetDemo {
private static Test monitor = new Test( );
public static void main(String[] args) {
SortedSet sortedSet = new TreeSet(Arrays.asList(
"one two three four five six seven
eight".split(" ")));
System.out.println(sortedSet);
Object
low = sortedSet.first( ),
high = sortedSet.last( );
System.out.println(low);
System.out.println(high);
Iterator it = sortedSet.iterator( );
for(int i = 0; i <= 6; i++) {
if(i == 3) low = it.next( );
if(i == 6) high = it.next( );
else it.next( );
}
System.out.println(low);
System.out.println(high);
System.out.println(sortedSet.subSet(low,high));
System.out.println(sortedSet.headSet(high));
System.out.println(sortedSet.tailSet(low));
monitor.expect(new String[] {
"[eight,five,four,one,seven,six,three,
two]",
"eight",
"two",
"one",
"two",
"[one,seven,six,three]",
"[eight,five,four,one,seven,six,three]",
"[one,seven,six,three,two]"
});
}
} ///:~
Thinking in Java 3rd Edition
g12544 57 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g8892意，SortedSet意思是g256根据对象的g8616g17751顺序g257，而不是g256插入顺序g257 进行g6502序。
Map的功能
ArrayList能g16765你用数字在一个对象序g2027g18336面进行g17885g6333，所以从某种意
g1053上g16774，g4439是g4570数字g2656对象关联g17227来。g1306是，g3926果你想根据g1866他条g1226在一个对象序g2027g18336面进行g17885g6333的g16817，g18039又g16825怎么g1582g2614g731g7644就是一个g1375g4388。g4439的标准是g256g17885取g7380g2530一个g15999g2399入g7644的对象g257。我们常用的g7427语map，
dictionary，或associative array就是一种非常g5390大的，能在序g2027g18336面进行g6373g17885的工具(前一g12468的AssociativeArray.javag18336面g5062g13475有一个g12628
g2345的g1375g4388了)。从g8022念上g16774，g4439看上去像是一个ArrayList，g1306g4439不用数字，而是用g2490一个对象来查g6226对象g701这是一种至关g18337要的编程技g5051。
这一g8022念在Javag1025表g10628为Map。put(Object key,Object value)
方法会往Mapg18336面g2164一个值，并g1000把这个值同键(你查g6226时所用的对象)
联系g17227来。给出键g1055g2530，get(Object key)就会g17832g3250g994g1055相关联的值。
你也可以用containsKey( ) g2656 containsValue( )g8991g16809Map是否
g2265含有某个键或值。
Java标准类库g18336有好几种Map：HashMap，TreeMap，
LinkedHashMap，WeakHashMap，以g2462 IdentityHashMap。
g4439们都g4466g10628了Map的g3534g7424接g2487，g1306是在行为方式方面有着g7138g7186的差异。
这些差异体g10628在，g6940g10587，持有g2656表g12046对象pair的顺序，持有对象的时间
g19283短，以g2462g3926何决定键的相g12573g5627。
g5627能是Map所要面对的一个大问题。g3926果你知道get( )是怎么工g1328
的，你就会g2469觉(g8616方说)在ArrayListg18336面g6226对象会是相当g5942的。而这正是HashMap的g5390项。g4439不是g5942g5942地一个个地g6226这个键，而是用了一种g15999g12228为hash code的特殊值来进行查g6226的。g6967g2027(hash)是一种g12651法，
g4439会从g11458标对象当g1025提取一些信息，g9994g2530g10995成一个表g12046这个对象的g256相对
g10432特g257的int。hashCode( )是Object根类的方法，因此所有Java
对象都能g10995成hash code。HashMap则g2045用对象的hashCode( )来进行g5567g17907的查g6226。这样g5627能就有了急剧的提g20652。8
Map (接g2487) 维持键－值的关联(即pairs)，这样就能用键来g6226值了。
HashMap* g3534于hash表的g4466g10628。(用g4439来g1207替
8g3926g7536g17837g980g5627g14033g1185g993g14033g9397g17287g1332g11352g16213g8726g712g1332g2499g1209g1038g1332g14270g5061g11352g12879g4462g2058g980g1022Mapg712g17837g7691g4613g14033g18003g1825g12879g3423g1268g17894g6164g5353g17227
g11352g5322g7114g712g1186g13792g17839g980g8505g6564g20652g7609g16822g11352g17907g5242g452g3926g7536g17836g5831g14731g5483g7368g20652g11352g5627g14033g712g17907g5242g10390g1216g2499g1209g2454g13783Donald Knuthg11352The
Art of Computer Programmingg712g12544g1120g10268g11352g12544g989g2379g726Sorting and Searchingg712g11004g6980g13464g7481g1207g7379g256g9334g1998g11352g7754g2027g15932
(overflow bucket lists)g257g727g17837g7691g1582g1262g7389g1016g1022g3921g3800g726g980g7171g14033g19036g4557g11925g11436g4396g1660g1582g1260g2282g712g1120g7171g3324g2031g5326g2656g3250g6922g2345g10432g16772g5417
g11352g7114g1517g14033g14422g11477g5468g3822g7114g19400g452
Chapter 11,Collections of Objects
g12544 58 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
Hashtable。)提供时间恒定的插入g994查询。在g7512造g2001数g1025可以g16786置hash表的
capacityg2656load factor。可以通过g7512造
g2001数来g16855节g1866g5627能。
LinkedHashMap
(JDK 1.4)
很像HashMap，g1306是用Iterator进行
g17953g2394的时候，g4439会按插入顺序或g7380g1820g1363用的顺序(least-recently-used (LRU)
order)进行g16787问。g19512了用Iterator外，
g1866他情况g991，只是g8616HashMapg12257g5942一点。用Iterator的情况g991，g11013于是g1363用链表来保g4396内g18108顺序，因此g17907g5242会更g5567。
TreeMap g3534于g13430g21669g7653数据g13479g7512的g4466g10628。当你查看键或pair时，会g2469g10628g4439们是按顺序 (根据
Comparable或Comparator，我们过一会g16774)g6502g2027的。TreeMap的特点是，你所得到的是一个有序的Map。TreeMap
是Mapg1025唯一有subMap( )方法的g4466
g10628。这个方法能g16765你g14731取这个g7653g1025的一g18108
g2010。
WeakHashMap 一个weak key的Map，是为某些特殊问题而g16786计的。g4439能g16765Mapg18334放g1866所持有的对象。g3926果某个对象g19512了在Map当g1025g1817当键g1055外，在g1866g4439地方都没有g1866reference
的g16817，g18039g4439g4570g15999当g1328g3415g3346g3250g6922。
IdentityHashMap
(JDK 1.4)
一个用==，而不是equals( )来g8616g17751键的hash map。不是为我们g5191常g1363用而g16786
计的，是用来解决特殊问题的。
g6967g2027是往Mapg18336g4396数据的常用g12651法。有时你会需要知道g6967g2027g12651法的工g1328
细节，所以我们会g12257g2530g1889g16774。
g991面这段程序用到了Collections2.fill( )方法，以g2462我们前面准g3803的
g8991g16809数据,
//,c11:Map1.java
// Things you can do with Maps,
import java.util.*;
import com.bruceeckel.util.*;
public class Map1 {
private static Collections2.StringPairGenerator
geo =
Collections2.geography;
private static
Collections2.RandStringPairGenerator
rsp = Collections2.rsp;
Thinking in Java 3rd Edition
g12544 59 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
// Producing a Set of the keys,
public static void printKeys(Map map) {
System.out.print("Size = " + map.size( ) + ",");
System.out.print("Keys,");
System.out.println(map.keySet( ));
}
public static void test(Map map) {
// Strip qualifiers from class name,
System.out.println(
map.getClass( ).getName( ).replaceAll("\\w+\\.",
""));
Collections2.fill(map,geo,25);
// Map has 'Set' behavior for keys,
Collections2.fill(map,geo.reset( ),25);
printKeys(map);
// Producing a Collection of the values,
System.out.print("Values,");
System.out.println(map.values( ));
System.out.println(map);
String key = CountryCapitals.pairs[4][0];
String value = CountryCapitals.pairs[4][1];
System.out.println("map.containsKey(\"" + key +
"\")," + map.containsKey(key));
System.out.println("map.get(\"" + key + "\"),"
+ map.get(key));
System.out.println("map.containsValue(\""
+ value + "\")," + map.containsValue(value));
Map map2 = new TreeMap( );
Collections2.fill(map2,rsp,25);
map.putAll(map2);
printKeys(map);
key =
map.keySet( ).iterator( ).next( ).toString( );
System.out.println("First key in map," + key);
map.remove(key);
printKeys(map);
map.clear( );
System.out.println("map.isEmpty( )," +
map.isEmpty( ));
Collections2.fill(map,geo.reset( ),25);
// Operations on the Set change the Map,
map.keySet( ).removeAll(map.keySet( ));
System.out.println("map.isEmpty( )," +
map.isEmpty( ));
}
public static void main(String[] args) {
test(new HashMap( ));
test(new TreeMap( ));
test(new LinkedHashMap( ));
test(new IdentityHashMap( ));
test(new WeakHashMap( ));
}
} ///:~
PrintKeys( )g2656printValues( )不g1306是非常g4466用的工具，而g1000g17836g9448g12046
了怎样g4570Mapg17728g6454成Collection。KeySet( )方法g17832g3250了一个g11013
Chapter 11,Collections of Objects
g12544 60 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
Map的键所组成的Set。values( )也差不多，g4439g17832g3250的是g11013Map的值所组成的Collection。(g8892意，键g5529g20047是唯一的，而值却可以有g18337
g3809。)g11013于这些Collection的g2530台都是Map，因此对Collection的任何g1474g6925都会反映到Map上。
接g991来，我们g12628g2345地g12046g14551了一g991各种Map的g6817g1328，g9994g2530g6396个g8991g16809了一g991
Map。
g1042一个g5224用HashMap的g1375g4388，想一想，怎样才能g1901一个g7828g8991Java
Random类的g19555g7438g5627的程序。在理想情况g991，g4439g5224g16825能g10995成一个g2010布g3355
匀的g19555g7438数。不过这只是一个g8991g16809，所以我们只要数一g991g19555g7438数落在各个
g2318域的g8437数就可以了。要把两个对象关联g17227来，用HashMap正合g17878。
(这g18336要map的就是Math.random( )所g17832g3250的g19555g7438数，以g2462这个数字出g10628的g8437数),
//,c11:Statistics.java
// Simple demonstration of HashMap,
import java.util.*;
class Counter {
int i = 1;
public String toString( ) { return
Integer.toString(i); }
}
public class Statistics {
private static Random rand = new Random( );
public static void main(String[] args) {
Map hm = new HashMap( );
for(int i = 0; i < 10000; i++) {
// Produce a number between 0 and 20,
Integer r = new Integer(rand.nextInt(20));
if(hm.containsKey(r))
((Counter)hm.get(r)).i++;
else
hm.put(r,new Counter( ));
}
System.out.println(hm);
}
} ///:~
main( )会把g19555g7438数g17728g6454成Integer，这样HashMap就有
reference可用了。(g4493g3132不能g4396g1660primitive，只能g4396g1660对象的
reference。)containsKey( )会g7828查这个键是不是g5062g13475在g4493g3132g18336了(也就是说，g6226没g6226到这个数)。g3926果g6226到了，get( )方法就会g17832g3250g994这个键相关联的值，也就是Counter对象。Counter是一个计数g3132，每g6226到一个g19555g7438数的时候，g4439就对ig1582g17894g3698。
Thinking in Java 3rd Edition
g12544 61 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g3926果没有g6226到这个键，put( )方法就会往HashMapg18336面插一个新的
pair。Counter会自动地g4570g2476量i的值g2033g3999g2282为1，这表g12046g12544一g8437插入了这个g19555g7438数。
g3926果想观察HashMap，直接g6183g2372就是了。HashMap的toString( )
方法会g17953g2394每一个pair，g9994g2530g16855用g4439们的toString( )方法。
Integer.toString( )方法g5062g13475g20056g1820定g1053过了，这样你就能看g6038
Counter的toString( )了。g991面就是某g8437运行的g17767出,
{15=529,4=488,19=518,8=487,11=501,16=487,
18=507,3=524,7=474,12=485,17=493,2=490,13=540,
9=453,6=512,1=466,14=522,10=471,5=522,0=531}
也g16780你会觉得g3867g5630，为什么要用Counter类g2614，好像g4439的功能g17836没有
Integer的wrapperg5390，为什么不用int或Integerg2614g731好，首g1820我们不能g1363用int，因为g4493g3132只能持有Object对象。知道了这点，你或g16780
会g16760为g5224g16825用wrapper类，因为你可以通过g4439把primitive放入g4493g3132。
g1306是对Java的wrapper类来说，你唯一能g1582的就是用某个值来对g4439进行g2033g3999g2282，g9994g2530把这个值读出来。也就是说一g7098创建了一个wrapper类对象，你就g1889也不能g1474g6925g4439的值了。就这个问题而言，Integer的
wrapper类是g7092能为力的。所以我们只能创建一个类来解决这个问题。
SortedMap
SortedMap(只有TreeMap这一个g4466g10628)的键肯定是有序的，因此这个接g2487g18336面就有一些g19480g2164功能的方法了。
Comparator comparator( )：g17832g3250Map所g1363用的
comparator，g3926果是用Object内置的方法的g16817，则g17832g3250null。
Object firstKey( ),g17832g3250g12544一个键。
Object lastKey( ),g17832g3250g7380g2530一个键。
SortedMap subMap(fromKey,toKey),g17832g3250这个Map的一个g4388
g19610，g1866键从fromKeyg5332g3999到toKey为止，g2265g6336前者，不g2265g6336g2530者。
SortedMap headMap(toKey),g17832g3250这个Map的一个g4388g19610，g1866键
g3355小于toKey。
SortedMap tailMap(fromKey),g17832g3250这个Map的一个g4388g19610，g1866键
g3355大于g12573于fromKey。
Chapter 11,Collections of Objects
g12544 62 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g991面这个g1375g4388，有点像SortedSetDemo.java，g4439g9448g12046了TreeMap
的这些g19480g2164功能,
//,c11:SimplePairGenerator.java
import com.bruceeckel.util.*;
//import java.util.*;
public class SimplePairGenerator implements
MapGenerator {
public Pair[] items = {
new Pair("one","A"),new Pair("two","B"),
new Pair("three","C"),new Pair("four","D"),
new Pair("five","E"),new Pair("six","F"),
new Pair("seven","G"),new Pair("eight","H"),
new Pair("nine","I"),new Pair("ten","J")
};
private int index = -1;
public Pair next( ) {
index = (index + 1) % items.length;
return items[index];
}
public static SimplePairGenerator gen =
new SimplePairGenerator( );
} ///:~
//,c11:SortedMapDemo.java
// What you can do with a TreeMap,
import com.bruceeckel.simpletest.*;
import com.bruceeckel.util.*;
import java.util.*;
public class SortedMapDemo {
private static Test monitor = new Test( );
public static void main(String[] args) {
TreeMap sortedMap = new TreeMap( );
Collections2.fill(
sortedMap,SimplePairGenerator.gen,10);
System.out.println(sortedMap);
Object
low = sortedMap.firstKey( ),
high = sortedMap.lastKey( );
System.out.println(low);
System.out.println(high);
Iterator it = sortedMap.keySet( ).iterator( );
for(int i = 0; i <= 6; i++) {
if(i == 3) low = it.next( );
if(i == 6) high = it.next( );
else it.next( );
}
System.out.println(low);
System.out.println(high);
System.out.println(sortedMap.subMap(low,high));
System.out.println(sortedMap.headMap(high));
System.out.println(sortedMap.tailMap(low));
monitor.expect(new String[] {
"{eight=H,five=E,four=D,nine=I,one=A,
seven=G," +
Thinking in Java 3rd Edition
g12544 63 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
" six=F,ten=J,three=C,two=B}",
"eight",
"two",
"nine",
"ten",
"{nine=I,one=A,seven=G,six=F}",
"{eight=H,five=E,four=D,nine=I," +
"one=A,seven=G,six=F}",
"{nine=I,one=A,seven=G,six=F," +
"ten=J,three=C,two=B}"
});
}
} ///:~
这g18336，pair是按key的顺序g4396g1660的。g11013于TreeMap有顺序的g8022念，因此g256位置g257是有意g1053的，所以你可以去g14731取g4439的g12544一个g2656g7380g2530一个g1815g13044，
以g2462g4439的g4388g19610。
LinkedHashMap
为为为为为为为LinkedHashMap对所有g1008g16211都g1328了hash，而g1000g17953g2394
的时候(println( )会g17953g2394g6984个Map，所以你能看到这个过程)g17836会按插入顺序g17832g3250pair。此外，你g17836可以在LinkedHashMap的g7512造g2001数g18336
面进行配置，g16765g4439g1363用g3534于g16787问的LRU(least-recently-used)g12651法，这样g17836没g15999g16787问过的g1815g13044(同时也是要g2036g19512的候g17885对象)就会出g10628在队g2027的g7380
前头。这样，为节省资源而g1901一个定时g9177理的程序就g2476得很g12628g2345了。g991面这段程序就g9448g12046了这两个特g5627,
//,c11:LinkedHashMapDemo.java
// What you can do with a LinkedHashMap,
import com.bruceeckel.simpletest.*;
import com.bruceeckel.util.*;
import java.util.*;
public class LinkedHashMapDemo {
private static Test monitor = new Test( );
public static void main(String[] args) {
LinkedHashMap linkedMap = new LinkedHashMap( );
Collections2.fill(
linkedMap,SimplePairGenerator.gen,10);
System.out.println(linkedMap);
// Least-recently used order,
linkedMap = new LinkedHashMap(16,0.75f,true);
Collections2.fill(
linkedMap,SimplePairGenerator.gen,10);
System.out.println(linkedMap);
for(int i = 0; i < 7; i++) // Cause accesses,
linkedMap.get(SimplePairGenerator.gen.items[i].key);
System.out.println(linkedMap);
linkedMap.get(SimplePairGenerator.gen.items[0].key);
System.out.println(linkedMap);
Chapter 11,Collections of Objects
g12544 64 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
monitor.expect(new String[] {
"{one=A,two=B,three=C,four=D,five=E," +
"six=F,seven=G,eight=H,nine=I,ten=J}",
"{one=A,two=B,three=C,four=D,five=E," +
"six=F,seven=G,eight=H,nine=I,ten=J}",
"{eight=H,nine=I,ten=J,one=A,two=B," +
"three=C,four=D,five=E,six=F,seven=G}",
"{eight=H,nine=I,ten=J,two=B,three=C," +
"four=D,five=E,six=F,seven=G,one=A}"
});
}
} ///:~
你可以从程序的g17767出看到，g17953g2394的顺序真的就是pair插入的顺序，甚至
LRU版的也是。g1306是g1177g1177g16787问过前七个g1815g13044g1055g2530，g2530面g989个就g15999g12239到了队g2027的g7380前头。g1306是当我们g16787问了g1866g1025的某个g1055g2530，g4439又g15999g12239到队g2027的g2530
面去了。
散列算法与Hash数
Statistics.java用标准类库的Integer来g1817当HashMap的键。g11013
于g4439具g3803了键所g5224g5529g3803的一切功能，因此这个程序能很正常地运行。g1306是当你用自己g1901的类来g1817当键的时候，就会有一些问题了。g8616g3926在一个气象
g20056报系统g18336面，你把Groundhogg2656Prediction对象配对。这种g16786计
g1296乎很g12628g2345，你创建两个类，g9994g2530把Groundhog当g1328键，把
Prediction当g1328值。
//,c11:Groundhog.java
// Looks plausible,but doesn't work as a HashMap
key,
public class Groundhog {
protected int number;
public Groundhog(int n) { number = n; }
public String toString( ) {
return "Groundhog #" + number;
}
} ///:~
//,c11:Prediction.java
// Predicting the weather with groundhogs,
public class Prediction {
private boolean shadow = Math.random( ) > 0.5;
public String toString( ) {
if(shadow)
return "Six more weeks of Winter!";
else
return "Early Spring!";
}
Thinking in Java 3rd Edition
g12544 65 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
} ///:~
//,c11:SpringDetector.java
// What will the weather be?
import com.bruceeckel.simpletest.*;
import java.util.*;
import java.lang.reflect.*;
public class SpringDetector {
private static Test monitor = new Test( );
// Uses a Groundhog or class derived from
Groundhog,
public static void
detectSpring(Class groundHogClass) throws
Exception {
Constructor ghog =
groundHogClass.getConstructor(
new Class[] {int.class});
Map map = new HashMap( );
for(int i = 0; i < 10; i++)
map.put(ghog.newInstance(
new Object[]{ new Integer(i) }),new
Prediction( ));
System.out.println("map = " + map + "\n");
Groundhog gh = (Groundhog)
ghog.newInstance(new Object[]{ new
Integer(3) });
System.out.println("Looking up prediction for "
+ gh);
if(map.containsKey(gh))
System.out.println((Prediction)map.get(gh));
else
System.out.println("Key not found," + gh);
}
public static void main(String[] args) throws
Exception {
detectSpring(Groundhog.class);
monitor.expect(new String[] {
"%% map = \\{(Groundhog #\\d=" +
"(Early Spring!|Six more weeks of Winter!)" +
"(,)?){10}\\}",
"",
"Looking up prediction for Groundhog #3",
"Key not found,Groundhog #3"
});
}
} ///:~
每个Groundhog都有一个标g16794值，这样你就可以用这种方式，g256给我
g994Groundhog #3相关联的Predictiong257，在HashMapg18336面查
g6226Prediction了。Prediction类g2265含了一个用Math.random( )
g2033g3999g2282的boolean值，g2656一个把g13479果翻译出来的toString( )方法。
detectSpring( )要用reflection的方式创建Groundhog或是g1866派
Chapter 11,Collections of Objects
g12544 66 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g10995类的g4466g1375，并g1000g16855用g1866方法。这所以要用这种方法是因为，就这个问题而言，g3926果要继承Groundhog的g16817，用这种方法会很顺手。我们用
Groundhogg2656g994g1055相关的Predicitong3647HashMap。接g991来我们要
g6183g2372HashMap，这样你就能看到g4439真的是g15999g3647g9397了。g9994g2530我们就要用标g16794为#3的Groundhog来查g6226Prediction了(g4439肯定在Mapg18336
面)。
好像很g12628g2345，g1306是就是不能运行。毛病就出在，Groundhog是继承
Object根类的(g3926果你不指g7138g4439的父类，g4439就自动继承根类，而g7380终所有的类都继承Object)。这样，对象的hash数是g11013Object的
hashCode( )g10995成的，g13582省情况g991这就是对象的内g4396地g3348。这样
Groundhog(3)的g12544一个g4466g1375的hash数会g994g1866g12544二个g4466g1375的hash
数不相g12538。而g2530者正是我们用来查g6226的键。
或g16780你会g16760为，你所要g1582的就是覆g1901一个合g17878的hashCode( )。g1306是g19512
非你g1889g1328g2490一g1226事，把同属Object的equals( )方法也覆g1901了，否则
g17836是不行。HashMap要用equals( )来判断查询用的键是不是g994表g18336
面的g1866g4439键相g12573。
一个合g17878的equals( )g5529g20047g1582到以g991g1128点,
1,反g17535g5627：对任何x，x.equals(x)g5529g20047是true的。
2,对g12228g5627：对任何xg2656y，g3926果y.equals(x)是 true的，g18039么
x.equals(y)也g5529g20047是true的。
3,传g17894g5627：对任何x，yg2656z，g3926果x.equals(y)是true的，g1000
y.equals(z)也是true的，g18039么x.equals(z)也g5529g20047是true的。
4,一g14280g5627：对任何xg2656y，g3926果对象g18336面用来判断相g12573g5627的信息没有g1474
g6925过，g18039么g7092论g16855用多少g8437x.equals(y)，g4439都g5529g20047一g14280地g17832g3250
true或false。
5,对于任何非空的x，x.equals(null)g5529g20047g17832g3250false。
g21676g16760的Object.equals( )只是g12628g2345地g8616g17751两个对象的地g3348，所以一个
Groundhog(3)会不g12573于g2490一个Groundhog(3)。因此，g3926果你想把你自己g1901的类当HashMap的键来用的g16817，你就g5529g20047把
hashCode( )g2656equals( )都给覆g1901了，就像g991面这个程序,
//,c11:Groundhog2.java
// A class that's used as a key in a HashMap
// must override hashCode( ) and equals( ),
public class Groundhog2 extends Groundhog {
public Groundhog2(int n) { super(n); }
public int hashCode( ) { return number; }
public boolean equals(Object o) {
return (o instanceof Groundhog2)
&& (number == ((Groundhog2)o).number);
}
} ///:~
Thinking in Java 3rd Edition
g12544 67 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
//,c11:SpringDetector2.java
// A working key,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class SpringDetector2 {
private static Test monitor = new Test( );
public static void main(String[] args) throws
Exception {
SpringDetector.detectSpring(Groundhog2.class);
monitor.expect(new String[] {
"%% map = \\{(Groundhog #\\d=" +
"(Early Spring!|Six more weeks of Winter!)" +
"(,)?){10}\\}",
"",
"Looking up prediction for Groundhog #3",
"%% Early Spring!|Six more weeks of Winter!"
});
}
} ///:~
Groundhog2.hashCode( ) 会以groundhog的序号为hash数，
并g1000g17832g3250这个数字。在这个程序g18336，程序员要g17143任两个groundhog不能
g6329有相同的序号。HashCode( )并不要求你一定要g17832g3250一个唯一的标g16794
g12538(这g12468g4410g4448g1055g2530你就会有更深的g16760g16794了)，可是equals( )方法就g5529g20047
能准确地判断两个对象是否相g12573了。这个equals( )是根据
groundhog的序号来g1328判断的，所以g3926果HashMap的键g18336有两个序号相同的Groundhog2的g16817，程序就出错了。
g15441g9994equals( )好像只g7828查了g2454数是不是Groundhog2类型的(用了
g12544十g12468g16774的instanceof关键词)，g1306g4466际上g4439g17836悄悄地g1328了一个g1593g1852g5627
g7828查，也就是g7828查一g991这个对象是不是null的，因为g3926果g12573号的左g17805是
null的g16817，instanceof会g17832g3250false。g3926果类型正确g1000不为空，
equals( )就要根据ghNumber进行g8616g17751了。你可以从程序的g17767出看到，g10628在运行正常了。
在HashSetg1025g1363用自建对象所g5224g8892意的问题，同把g4439用于HashMap
的键是相同的。
理解hashCode( )
前面g18039个g1375g4388只是在解决问题的正确方向上迈出了一小步。g4439告诉我们，
g3926果你不覆g1901键的hashCode( )g2656equals( )的g16817，g6967g2027数据g13479g7512
(HashSet，HashMap，LinkedHashSet，或 LinkedHashMap)
就没法正确地处理键。g1306是要想提供一个好的解决方g7708，你g17836g5529g20047知道g6967
g2027数据g13479g7512究竟是怎样运行的。
Chapter 11,Collections of Objects
g12544 68 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
首g1820想想我们为什么要用g6967g2027：要通过一个对象来查g6226g2490一个对象。不过
TreeSet或TreeMap也能g1582这g1226事。当g9994，你也可以g4466g10628一个你自己的Map。这么g1582的前提是，g1820得定g1053一个会g17832g3250Map.Entry对象g19610合的Map.entrySet( )方法。我们为Map.Entry定g1053一个新的MPair
类。要想把g4439放到TreeSetg18336面，就得定g1053g4439的equals( )，并g1000g4466g10628
Comparable,
//,c11:MPair.java
// A new type of Map.Entry,
import java.util.*;
public class MPair implements Map.Entry,Comparable
{
private Object key,value;
public MPair(Object k,Object v) {
key = k;
value = v;
}
public Object getKey( ) { return key; }
public Object getValue( ) { return value; }
public Object setValue(Object v) {
Object result = value;
value = v;
return result;
}
public boolean equals(Object o) {
return key.equals(((MPair)o).key);
}
public int compareTo(Object rv) {
return
((Comparable)key).compareTo(((MPair)rv).key);
}
} ///:~
g8892意，g4439只对键进行g8616g17751，因此值g4448g1852可以是g18337g3809的。
g991面用一对ArrayListg4466g10628一个Map。
//,c11:SlowMap.java
// A Map implemented with ArrayLists,
import com.bruceeckel.simpletest.*;
import java.util.*;
import com.bruceeckel.util.*;
public class SlowMap extends AbstractMap {
private static Test monitor = new Test( );
private List
keys = new ArrayList( ),
values = new ArrayList( );
public Object put(Object key,Object value) {
Object result = get(key);
if(!keys.contains(key)) {
keys.add(key);
values.add(value);
Thinking in Java 3rd Edition
g12544 69 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
} else
values.set(keys.indexOf(key),value);
return result;
}
public Object get(Object key) {
if(!keys.contains(key))
return null;
return values.get(keys.indexOf(key));
}
public Set entrySet( ) {
Set entries = new HashSet( );
Iterator
ki = keys.iterator( ),
vi = values.iterator( );
while(ki.hasNext( ))
entries.add(new MPair(ki.next( ),vi.next( )));
return entries;
}
public String toString( ) {
StringBuffer s = new StringBuffer("{");
Iterator
ki = keys.iterator( ),
vi = values.iterator( );
while(ki.hasNext( )) {
s.append(ki.next( ) + "=" + vi.next( ));
if(ki.hasNext( )) s.append(",");
}
s.append("}");
return s.toString( );
}
public static void main(String[] args) {
SlowMap m = new SlowMap( );
Collections2.fill(m,Collections2.geography,15);
System.out.println(m);
monitor.expect(new String[] {
"{ALGERIA=Algiers,ANGOLA=Luanda,BENIN=Porto-
Novo,"+
" BOTSWANA=Gaberone,BURKINA FASO=Ouagadougou,
" +
"BURUNDI=Bujumbura,CAMEROON=Yaounde," +
"CAPE VERDE=Praia,CENTRAL AFRICAN
REPUBLIC=Bangui,"+
" CHAD=N'djamena,COMOROS=Moroni," +
"CONGO=Brazzaville,DJIBOUTI=Dijibouti," +
"EGYPT=Cairo,EQUATORIAL GUINEA=Malabo}"
});
}
} ///:~
put( )只是g12628g2345地把键g2656值放入相g5224的ArrayList。main( )会g16025g17745并g6183
g2372一个SlowMap，并以此证g7138g4439真的能工g1328。
这段程序告诉我们，造一个新的Map并不是很g19602。g1306是就像g4439的名字所说的，SlowMap不可能g5567，所以g3926果g17836有g1866g4439g17885g6333，g7380好不要用g4439。
Chapter 11,Collections of Objects
g12544 70 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
问题就出在查g6226键的g12651法上g727键的g6502g2027是g7092序的，所以只能按照顺序一个一个地g6226，而这是g7380g5942的方法。
g6967g2027的g1227值就在于g17907g5242：g6967g2027g12651法能很g5567地g6226出g1008g16211。g11013于问题是出在键的查g6226g17907g5242上，g18039么我们就可以用g991面这个办法，把键按顺序g6502好，g9994g2530
用Collections.binarySearc( )进行查g6226(g7424g12468的g7380g2530会有一个练习，g4439会g5114着你走g4448这个过程)。
g6967g2027则走得更g17840，g4439的意思是，你不用管了，我会帮你把键g4396到某个你能很g5567g6226到的地方。正g3926g7424g12468前面所说的，数组是g7380g5567的数据g13479g7512，所以我们用g4439表g12046键的信息(g8892意我说g256键的信息g257，而不是键g7424g17535)。此外，g7424
g12468g17836说了，数组一g13475g2010配就不能g16855g6984大小，所以这g18336又有一个问题：
Map要能g4396g1660任意数量的pair，而键的数量又g15999数组的大小给定死了，
g16825怎么办g2614g731
答g7708就是，不用数组来g4396g1660键。键对象会g10995成一个数字，而我们要用这个数字g1328g991标来g16787问数组。这个数字就是所g16871的hash数。g4439是g11013Object
定g1053的hashCode( )g10995成的(用计g12651g7438科g4410的g7427语，就是g6967g2027g2001数)，而
g1820前我们g5062g13475要求你在类的定g1053g18336面覆g1901这个方法了。要想解决定g19283数组的问题，就得g1813g16780多个键g10995成同一个hash数。也就是说会有冲突。于是数组多大就g2476得g7092关紧要了g727每个键对象都会落到数组的某个位置上了。
所以查g6226过程是从计g12651hash数g5332g3999的，g12651g4448g1055g2530g1889用这个数在数组g18336定位。g3926果g6967g2027g2001数能g3827确保不g1147g10995冲突(g3926果对象数量是g3278定的g16817，g18039么这是有可能的)，g18039么g4439就g15999g12228为g256g4448g1852g6967g2027g2001数g257，不过这只是特g1375。
通常情况g991，冲突是g11013g256外g18108链(external chaining)g257处理的：数组并不是直接指向对象，而是指向一个对象的g2027表。g9994g2530g1889用equals( )在这个g2027表g1025一个一个地g6226。当g9994，这一步是g8616g17751g5942的，g1306g3926果g6967g2027g2001数定
g1053得好，每个hash数就会只对g5224几个对象。这样，g994搜g4559g6984个序g2027相
g8616，你能很g5567地跳到这个组，g9994g2530只g8616g17751几个对象。这样会g5567g16780多，而这也是HashMap为什么这么g5567的原因了。
知道这些g3534g11796知g16794g1055g2530，你就能用hashg4466g10628一个g12628g2345Map了,
//,c11:SimpleHashMap.java
// A demonstration hashed Map,
import java.util.*;
import com.bruceeckel.util.*;
public class SimpleHashMap extends AbstractMap {
// Choose a prime number for the hash table
// size,to achieve a uniform distribution,
private static final int SZ = 997;
private LinkedList[] bucket = new LinkedList[SZ];
public Object put(Object key,Object value) {
Object result = null;
int index = key.hashCode( ) % SZ;
if(index < 0) index = -index;
Thinking in Java 3rd Edition
g12544 71 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
if(bucket[index] == null)
bucket[index] = new LinkedList( );
LinkedList pairs = bucket[index];
MPair pair = new MPair(key,value);
ListIterator it = pairs.listIterator( );
boolean found = false;
while(it.hasNext( )) {
Object iPair = it.next( );
if(iPair.equals(pair)) {
result = ((MPair)iPair).getValue( );
it.set(pair); // Replace old with new
found = true;
break;
}
}
if(!found)
bucket[index].add(pair);
return result;
}
public Object get(Object key) {
int index = key.hashCode( ) % SZ;
if(index < 0) index = -index;
if(bucket[index] == null) return null;
LinkedList pairs = bucket[index];
MPair match = new MPair(key,null);
ListIterator it = pairs.listIterator( );
while(it.hasNext( )) {
Object iPair = it.next( );
if(iPair.equals(match))
return ((MPair)iPair).getValue( );
}
return null;
}
public Set entrySet( ) {
Set entries = new HashSet( );
for(int i = 0; i < bucket.length; i++) {
if(bucket[i] == null) continue;
Iterator it = bucket[i].iterator( );
while(it.hasNext( ))
entries.add(it.next( ));
}
return entries;
}
public static void main(String[] args) {
SimpleHashMap m = new SimpleHashMap( );
Collections2.fill(m,Collections2.geography,25);
System.out.println(m);
}
} ///:~
g11013于hash表的g256槽位g257常常g15999g12228为bucket(桶)，因此g1207表这个hash
表的数组就g15999命名为bucket。为了提g20652g2010配的g5191g3355g5627，bucket的数g11458
Chapter 11,Collections of Objects
g12544 72 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
通常是一个质数。9g8892意g4439是一个LinkedList的数组，而这个
LinkedList是为冲突准g3803的g727新的对象会g15999直接g2164到list的g7380g2530。
put( )的g17832g3250值要么是null，要么，g3926果键g5062g13475在listg18336面的g16817，就是原g1820g18039个g994键相关联的值。g17832g3250值result会g15999g1820g2033g3999g2282为null，g1306是g3926
果在listg18336g2469g10628键的g16817，g4439会g18337新g16786置这个键的值。
put( )g2656get( )g1582的g12544一g1226事都是g16855用键的hashCode( )。g3926果
hashCode( )g17832g3250的是g17139数的g16817，g4439g17836要把这个g17139数g17728g6454成正数。接着，g4439用数组的大小对这个数取模，并以此确定要把这对pair放到
bucket的g2750个位置上。g3926果这个位置g17836是null的g16817，就说g7138此前g17836没有g2047的g1815g13044g15999hash到这g18336，因此要创建了一个新的LinkedList来持有这对pair。g1306是一般情况g991是g1820搜索list，看看是否有g18337g3809g1815g13044，g3926果有，就把原g1820g18039个值赋给result，g1889用新的值来g1207替g7099的。foundg17139g17143
g17331踪是否g2469g10628g7099的pair，g3926果没g2469g10628，g4439就会把新pair会g2164到list的g7380
g2530。
你会g2469g10628，get( )的g1207码同put( )的很相g1296，只是g12257g16780g12628g2345了一些。
index也是用来计g12651bucket数组g18336的位置的，g3926果这g18336有
LinkedList，g4439就进行搜索，g9994g2530g6226出一个匹配的。
entrySet( ) 会g6226出所有的list，并g1000一个一个地进行g17953g2394，g9994g2530把g13479
果g2164进要g17832g3250的Set。g1901g4448这个方法g1055g2530，你就能往Mapg18336面g3647数据了，于是也能进行g6183g2372g2656g8991g16809了。
影响HashMap性能的因素
要想听g6038这个问题，g7186得了解g991面几个g7427语,
Capacity：hash表g18336面的bucket的数量。
Initial capacity：创建hash表时，bucket的数量。HashMapg2656
HashSet都有能g16765你指定Initial capacity的g7512造g2001数。
Size：当前hash表的g16772g5417的数量。
Load factor：size/capacity。load factor为0表g12046这是一个空表，
0.5表g12046这是一个半g9397的表，以此类推。一个g17139g17745g17751轻表会有g17751少的冲突，因此插入g2656查g6226的g17907g5242会g8616g17751g5567(g1306是在用g17857g1207g3132g17953g2394的时候会g8616g17751
g5942)。HashMap g2656 HashSet都提供了能指定load factor的g7512造g2001
9g1119g4466g16789g7138g17148g6980g4466g19481g990g5194g993g7171g980g1022g10714g5831g11352hash bucketsg11352g6980g11458g712(g13475g17819g5203g8879g8991g16809)Javag7380g7044g11352hashg4466g10628g1363g11004g1120
g11352g6984g6980g8437g7053g452g4557g3800g10714g3132g7481g16840g712g19512g8873g2656g2474g8181g7171g7380g5942g11352g1016g12193g6817g1328g712g6164g1209g3926g7536hashg15932g11352g19283g5242g7171g1120g11352g6984g6980g8437g7053g11352
g16817g712g4439g4613g14033g11004g6525g11733g7481g1207g7379g19512g8873g1114g452g11013g1122get( )g11352g1363g11004g20069g10587g16213g8616g1866g4439g6817g1328g3822g11352g3822g712g3252g8504g5468g3835g980g18108g2010g6817g1328g18129g16213
g10313g9053g2052g2474g8181(%)g712g13792g17837g12193g7053g8873g14033g19492g2058g4439g4557g5627g14033g6164g1147g10995g11352g9052g7509g5445g2721 (g1075g7389g2499g14033g1262g4557hashCode( )g7053g8873g1147g10995g980g1135
g5445g2721g452)
Thinking in Java 3rd Edition
g12544 73 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
数，也就是说当load factor达到这个阀值的时候，g4493g3132会自动地g4570
capacity(bucket的数量) g3698g2164大约一倍，g9994g2530g4570g10628有的对象g2010配到新的
bucketg18336面(这就是所g16871的rehash。)
缺缺缺缺缺HashMap 0.75会会会 会load factor(也就是说，当表的3/4
g15999g3647g9397的时候，g4439g1889g5332g3999rehash)。这看上去是一个不错的折g1025。laod
factorg1889g20652上去的g16817，确g4466会g19489g1314对g4396g1660空间的要求，g1306是这样g1582会g1363查询的g17907g5242g2476g5942。这个g5445g2721就大了，因为绝大多数情况g991，你都要用到查询
(g2265g6336get( )g2656put( ))。
g3926果你知道要在HashMapg18336面g4396g1660很多g16772g5417，g18039么创建的时候就g5224g16825
把initial capacityg16786成一个g8616g17751合g17878的大小，这样就能g20056防自动的
rehash所引g17227的g5627能g5332g19156了。10
覆写hashCode( )
g10628在你g5062g13475知道HashMap都涉g2462了g2750些功能，因此我们可以g16774
hashCode( )了。
首g1820，你g6523g2058的不是g18039个在bucket数组g18336面进行g7828索的值。这个值要取决于HashMap的capacity，load factor，以g2462g19555g4493g3132g4396g1660对象的数量g2476g2282而引g17227的capacity的g2476g2282。hashCode( )所g17832g3250的值g17836要g1582进一步处理，这样才能得到bucket数组的g991标(在SimpleHashMapg1375
程g1025，我们只是g12628g2345地对bucket数组的g4493量取模)。
创建hashCode( )g7380g18337要的一点就是，对同一个对象，g7092论在什么时候
g16855用hashCode( )，g4439都g5224g16825g17832g3250同一个值。g3926果对象g15999put( )进
HashMap的时候，hashCode( )是一个值，get( )出来的时候，
hashCode( )是g2490一个值，g18039么你就没法提取对象了。所以，g3926果
hashCode( )用到了对象的可g2476数据的g16817，你就g5224g16825g16765用户知道，g11013于
hashCode( )的缘g6937，g1474g6925这些数据g4466际上是在创建一个不同的键。
此外，你大g8022也不会根据对象的g256唯一g5627信息(unique object
information)g257来g10995成hashCode( )——特g2047是this，这会是一个很糟糕的hashCode( )。因为一般情况g991，你会把一个『键－值 pair』
直接put( )进HashMap，而用了这种hashCode( )g1055g2530，你就不能这么g1582了。SpringDetector.javag16774的就是这个问题。g11013于g13582省的
10g12181g991g18336g712Joshua Blochg1901g17959:"...g6117g11468g1461g712g16765g11004g6155g17902g17819APIg7481g16855g6984g4466g10628g11352g13466g14422g712(g8616g3926hashg15932g11352g3835g4579g712load
factorg7171g3822g4581g12573g12573)g712g7171g3324g10371g19181g16835g452g2499g14033g7171g5224g16825g16765g4470g6155g7481g1927g4462g1194g16213g3822g3835g11352g4493g18339g712g6117g1216g5224g16825g3324g17837g12193g3332g7053g2560g2474g1194
g1216g11352g16213g8726g452g16213g2495g4470g6155g2447g6373g17885g2454g6980g712g18039g1194g1216g3822g2334g1262g17885g19181g452g1042g1022g7509g12483g11352g1375g4388g712Vectorg11352capacityIncrementg452g8821
g1166g1262g2447g2172g4439g712g6117g1216g1075g993g6564g1391g5049g1867g452g1306g7171g3926g7536g1332g6238g4439g16786g6116g19762g19658g11352g1552g11352g16817g712g20046g5219g9167g2164g6817g1328g11352g17805g19481g1207g1227g1262g1186g13459g5627
g11352g2476g6116g1016g8437g11352(asymptotic cost of a sequence of appends goes from linear to quadratic)g452g12628g13792g16340g1055g712g5627g14033g2475g6451
g1114g452g7114g19400g16765g6117g1216g3324g17837g12193g1119g5785g990g2476g13886g7138g1114g452g3926g7536g1332g1889g2447g11487IdentityHashMapg712g4613g1262g2469g10628g712g1332g5062g13475g993g14033g16855g6984g4439
g11352g5225g4630g4466g10628g11352g2454g6980g1114g452"
Chapter 11,Collections of Objects
g12544 74 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
hashCode( )用的就是对象的地g3348，因此你g5224g16825在hashCode( )g18336面用一些能标g16794对象的有意g1053的信息。
用Stringg1042个g1375。String有个特点，g3926果程序g1025的多个内g4493相同的
String对象会g15999映射到同一块内g4396(g19480g5417Ag16774的就是这个g7438g2058)。所以两个用new String(“hello”)创建的String对象，g5224g16825g17832g3250相同的
hashCode( )，这是天g13475地g1053的。g991面这段程序就是g16774这g1226事的,
//,c11:StringHashCode.java
import com.bruceeckel.simpletest.*;
public class StringHashCode {
private static Test monitor = new Test( );
public static void main(String[] args) {
System.out.println("Hello".hashCode( ));
System.out.println("Hello".hashCode( ));
monitor.expect(new String[] {
"69609650",
"69609650"
});
}
} ///:~
很g7138g7186，String是根据g1866内g4493计g12651hashCode( )的。
所以要想g16765hashCode( )g1817g2010g2469挥g1328用，g4439g5529g20047既g5567又有意g1053g727也就是说g4439g5529g20047根据g1866内g4493g10995成值。g16772g1315，这个值可以是不唯一的，——在g17907g5242
g2656唯一g5627g1055间，你g5224g16825更倾向于g17907g5242——g1306是g13475过hashCode( )g2656
equals( )这两道处理，对象的g17535份g5224g16825g15999g4448g1852确g16760g991来。
g11013于hashCode( )在g10995成bucket数组的g991标g1055前g17836要进行进一步的处理，因此g4439的取值g14551g3272并不g18337要g727只要是int就行了。
g17836有一点：好的hashCode( )g5224g16825能g10995成g3355匀g2010布的值。g3926果这些值都
g13479成了块，g18039么HashMapg2656HashSet的g17139g17745就会g15999g19610g1025在一些特定的g2318域，相g8616g3355匀g2010布的hashg2001数，g1866g5627能自g9994会g6183一些折扣。
Joshua Block在Effective Java g18336面(Addison-Wesley，2001年出版)给怎样g1901像样的hashCode( )出了个方g4388,
1,给intg2476量result赋一个非零的常量，g8616g392617。
2,对每个g18337要的数据成员f，(也就是equals( )要会用到的所有的数据成员)，g2010g2047计g12651g1866int型的hash值c,
数据字段类型 计算方法
Boolean c = (f? 0,1)
Thinking in Java 3rd Edition
g12544 75 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
Byte,char,
short,或 int
c = (int)f
Long c = (int)(f ^ (f >>>32))
Float c = Float.floatToIntBits(f);
Double long l =
Double.doubleToLongBits(f);
c = (int)(l ^ (l >>> 32))
g4439的equals( )g16855用了g1866g1025的数据字段的
equals( )的
Object
c = f.hashCode( )
数组 对于g1866g1025每个g1815g13044都g1363用上述规则
1,g13479合上面的hash值，计g12651,
result = 37 * result + c;
2,g17832g3250result,
3,g1889g7828查一g991这个hashCode( )g2001数，要确保相同的g4466g1375会g10995成相同的
hash值。
g991面就是照这个方抓的药,
//,c11:CountedString.java
// Creating a good hashCode( ),
import com.bruceeckel.simpletest.*;
import java.util.*;
public class CountedString {
private static Test monitor = new Test( );
private static List created = new ArrayList( );
private String s;
private int id = 0;
public CountedString(String str) {
s = str;
created.add(s);
Iterator it = created.iterator( );
// Id is the total number of instances
// of this string in use by CountedString,
while(it.hasNext( ))
if(it.next( ).equals(s))
id++;
}
public String toString( ) {
return "String," + s + " id," + id +
" hashCode( )," + hashCode( );
}
public int hashCode( ) {
// Very simple approach,
// return s.hashCode( ) * id;
// Using Joshua Bloch's recipe,
int result = 17;
Chapter 11,Collections of Objects
g12544 76 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
result = 37*result + s.hashCode( );
result = 37*result + id;
return result;
}
public boolean equals(Object o) {
return (o instanceof CountedString)
&& s.equals(((CountedString)o).s)
&& id == ((CountedString)o).id;
}
public static void main(String[] args) {
Map map = new HashMap( );
CountedString[] cs = new CountedString[10];
for(int i = 0; i < cs.length; i++) {
cs[i] = new CountedString("hi");
map.put(cs[i],new Integer(i));
}
System.out.println(map);
for(int i = 0; i < cs.length; i++) {
System.out.println("Looking up " + cs[i]);
System.out.println(map.get(cs[i]));
}
monitor.expect(new String[] {
"{String,hi id,4 hashCode( ),146450=3," +
" String,hi id,10 hashCode( ),146456=9," +
" String,hi id,6 hashCode( ),146452=5," +
" String,hi id,1 hashCode( ),146447=0," +
" String,hi id,9 hashCode( ),146455=8," +
" String,hi id,8 hashCode( ),146454=7," +
" String,hi id,3 hashCode( ),146449=2," +
" String,hi id,5 hashCode( ),146451=4," +
" String,hi id,7 hashCode( ),146453=6," +
" String,hi id,2 hashCode( ),146448=1}",
"Looking up String,hi id,1 hashCode( ),
146447",
"0",
"Looking up String,hi id,2 hashCode( ),
146448",
"1",
"Looking up String,hi id,3 hashCode( ),
146449",
"2",
"Looking up String,hi id,4 hashCode( ),
146450",
"3",
"Looking up String,hi id,5 hashCode( ),
146451",
"4",
"Looking up String,hi id,6 hashCode( ),
146452",
"5",
"Looking up String,hi id,7 hashCode( ),
146453",
"6",
"Looking up String,hi id,8 hashCode( ),
146454",
"7",
"Looking up String,hi id,9 hashCode( ),
146455",
"8",
Thinking in Java 3rd Edition
g12544 77 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
"Looking up String,hi id,10 hashCode( ),
146456",
"9"
});
}
} ///:~
CountedStringg2265含一个Stringg2656一个id。这个id的意思是，有多少CountedString对象g2265含了g994这个对象相同的String。计数过程是通过g256g16765g7512造g2001数去g17953g2394g18039个保g4396着所有String的static
ArrayListg257来g4466g10628的。
hashCode( )g2656equals( )要用这两个数据来g10995成g17832g3250值g727g3926果你只
g1363用String或id的g16817，不同的对象就会g1147g10995相同的值了。
main( )用同一个String创建了一大堆CountedString。g1055所以要用相同的String，是想以此证g7138，g11013于id的不同，hashCode( )g1147g10995
了不同的值。我们把HashMapg6183g2372了出来，这样你就能看到g4439的内g18108
g4396g1660顺序了(没什么规律)。接g991来，我们要一个一个地查g6226键，并以此证
g7138g4439能正常工g1328。
为类g1901一个合g17878的hashCode( )g2656equals( )，是有一g1226技g5051g5627很g5390
的事。Apache的g256Jakarta Commonsg257项g11458g18336有很多很g4466用的工具。
就在jakata.apache.org/commons的“lang”g991面(这个项g991g17836g2265g6336了一些可能会非常有用的类库，而g1000g4439像是Java社g2318对C++的
www.boost.orgg1328出的g5224战)。
持有reference
java.lang.ref类库g18336有一g3883能g3698进g3415g3346g3250g6922g3132工g1328的g9801g8975g5627的类。一
g7098碰到了g256对象大到要耗光内g4396g257的时候，这些类就会g7186得g7696外有用。有
g989个类是继承g6289象类Reference的：SoftReference，
WeakReferenceg2656PhantomReference。g3926果g5465处理的对象只能通过这些Reference进行g16787问的g16817，g18039么这些Reference对象就会向g3415g3346g3250g6922g3132提供一些不同g13435g2047的暗g12046。
g3926果对象还能访问的到，g18039么在程序的某个地方g5224g16825g17836能g6226到这个对象。
或g16780g7644g18336g17836有一个g7234通的reference直接指着这个对象，或g16780在你g256引用(reference)g257的对象g18336面g17836有一个指向g18039个要g6226的对象的
referenceg727这g1025间可能会有很多g4630。g1306是，只要对象g17836能g16787问的到，也就是说程序g17836要用，g3415g3346g3250g6922g3132就不能g3250g6922。g3926果对象g5062g13475g16787问不到了，
程序也就g7092从g1363用了，因此g3250g6922就g5224g16825是安g1852的了。
Chapter 11,Collections of Objects
g12544 78 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
你可以用Reference对象来持有g18039个你想继续持有的g18039个对象的
referenceg727你要能g16787问g18039个对象，g1306是有g1813g16780g3415g3346g3250g6922g3132g3250g6922g4439。于是，你就有了一种g256能继续g1363用g18039个对象，g1306是当内g4396即g4570耗尽的时候，
又能g18334放g18039个对象g257的方法了。
要达到这个g11458的，你可以把Reference对象当g1328你g2656『g7234通的
reference』g1055间的g1025g1183，此外g18039个对象上面g17836不能g19480有g1866g4439『g7234通的
reference』(指没有用Reference类g2265覆的reference)。g3926果g3415g3346g3250
g6922g3132g2469g10628你g17836可以通过『g7234通的reference』g16787问某个对象，g18039g4439就不会
g18334放g18039个对象了。
从SoftReference到WeakReference，到
PhantomRefernce，g4439们的功能依g8437减弱，而g256g16787问g13435g2047(level of
reachability)g257又各自不同。SoftReference是为内g4396敏感的缓g4396而
g4466g10628的。WeakReference是为了g256规g14551g2282映射(canonical
mappings)g257而g4466g10628的，也就是为了节省g4396g1660空间，对象的g4466g1375可以g15999
同时用于程序的多个地方，这样你就不用g18337新申请g4439的键(或值)了。
PhantomReference则用于g16855g5242g256g3250g6922前的g9177理工g1328(premortem
cleanup action)g257，这种g9177理可以g8616Java的finalization的g7438g2058更为
g9801g8975。
对于SoftReferenceg2656WeakReference，你可以g17885g6333是不是把g4439
们放进ReferenceQueue(一个用于g256g3250g6922前的g9177理工g1328g257的工具)，
g1306是对于PhantomReference，你只能把g4439放进
ReferenceQueue。g991面就是一个g12628g2345的g9448g12046,
//,c11:References.java
// Demonstrates Reference objects
import java.lang.ref.*;
class VeryBig {
private static final int SZ = 10000;
private double[] d = new double[SZ];
private String ident;
public VeryBig(String id) { ident = id; }
public String toString( ) { return ident; }
public void finalize( ) {
System.out.println("Finalizing " + ident);
}
}
public class References {
private static ReferenceQueue rq = new
ReferenceQueue( );
public static void checkQueue( ) {
Object inq = rq.poll( );
if(inq != null)
System.out.println("In queue," +
(VeryBig)((Reference)inq).get( ));
}
public static void main(String[] args) {
Thinking in Java 3rd Edition
g12544 79 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
int size = 10;
// Or,choose size via the command line,
if(args.length > 0)
size = Integer.parseInt(args[0]);
SoftReference[] sa = new SoftReference[size];
for(int i = 0; i < sa.length; i++) {
sa[i] = new SoftReference(
new VeryBig("Soft " + i),rq);
System.out.println("Just created," +
(VeryBig)sa[i].get( ));
checkQueue( );
}
WeakReference[] wa = new WeakReference[size];
for(int i = 0; i < wa.length; i++) {
wa[i] = new WeakReference(
new VeryBig("Weak " + i),rq);
System.out.println("Just created," +
(VeryBig)wa[i].get( ));
checkQueue( );
}
SoftReference s =
new SoftReference(new VeryBig("Soft"));
WeakReference w =
new WeakReference(new VeryBig("Weak"));
System.gc( );
PhantomReference[] pa = new
PhantomReference[size];
for(int i = 0; i < pa.length; i++) {
pa[i] = new PhantomReference(
new VeryBig("Phantom " + i),rq);
System.out.println("Just created," +
(VeryBig)pa[i].get( ));
checkQueue( );
}
}
} ///:~
运行这个程序的时候(你g5224g16825g4570用g256moreg257把g17767出g18337定向到一个管道g18336，
这样就能看到g2010页的g17767出了)，你会g2469g10628，尽管你g17836能通过Reference
对象进行g16787问(要想g14731取真g4466对象的reference，你得用get( ))，g1306对象g17836是g15999g3250g6922了。你g17836会看到ReferenceQueue总是会g17832g3250保g4396null
对象的Reference对象。要g2045用g4439，你可以继承某个你感g1864g17271的
Reference类，并g1000给新的Reference类型g2164上一些有用的方法。
WeakHashMap
g4493g3132类库g18336面g17836有一种特殊的，持有weak reference的Map：
WeakHashMap。这个类是为g256g12628g2282创建规g14551g2282映射g257而g16786计的。在这种映射g1025，你可以用g256只创建某个值的一个g4466g1375g257来节省g4396g1660空间。当程序需要g1363用这个值的时候，g4439会在映射表g1025查g6226g5062有的对象(而不是从头g5332g3999创建)，并g1000g1363用g18039个对象。可以在对映射进行g2033g3999g2282的时候就把值g16786置好，g1306是常见的g17836是按需来g16786置。
Chapter 11,Collections of Objects
g12544 80 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g11013于这是一种节省内g4396空间的技g7427，所以g16765g3415g3346g3250g6922g3132来自动g9177理
WeakHashMap的键g2656值是很g4493g7143的。你不g5529对放进
WeakHashMap的键g2656值g1328什么特殊处理g727g4439们会g11013map自动g2265g16025
成WeakReference。g9177理的触g2469条g1226是，不需要g1889g1363用这个键了，就像这样,
//,c11:CanonicalMapping.java
// Demonstrates WeakHashMap,
import java.util.*;
import java.lang.ref.*;
class Key {
private String ident;
public Key(String id) { ident = id; }
public String toString( ) { return ident; }
public int hashCode( ) { return
ident.hashCode( ); }
public boolean equals(Object r) {
return (r instanceof Key)
&& ident.equals(((Key)r).ident);
}
public void finalize( ) {
System.out.println("Finalizing Key "+ ident);
}
}
class Value {
private String ident;
public Value(String id) { ident = id; }
public String toString( ) { return ident; }
public void finalize( ) {
System.out.println("Finalizing Value " + ident);
}
}
public class CanonicalMapping {
public static void main(String[] args) {
int size = 1000;
// Or,choose size via the command line,
if(args.length > 0)
size = Integer.parseInt(args[0]);
Key[] keys = new Key[size];
WeakHashMap map = new WeakHashMap( );
for(int i = 0; i < size; i++) {
Key k = new Key(Integer.toString(i));
Value v = new Value(Integer.toString(i));
if(i % 3 == 0)
keys[i] = k; // Save as "real" references
map.put(k,v);
}
System.gc( );
}
} ///:~
Thinking in Java 3rd Edition
g12544 81 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
正g3926前面所g16774的，g11013于要用于hash数据g13479g7512，Keyg5529g20047有
hashCode( )g2656equals( )方法。
运行程序的时候，你会看到g3415g3346g3250g6922g3132会每隔g989个跳g5332一个，这是因为g18039
个键的referenceg5062g13475g15999放进keys数组，因此g18039个对象是不能g3250g6922
的。
重访Iterator
g10628在我们可以来看Iterator的真正威力了：把序g2027的g17953g2394过程同这个序
g2027的底g4630g13479g7512g2010隔g5332来。PrintData(g7424g12468的前面定g1053的)用Iterator
g17953g2394了一个序g2027，并g1000对每个对象都g1363用toString( )方法。g991面这段程序创建了两个g4493g3132——ArrayListg2656HashMap，g9994g2530g2010g2047用
Mouseg2656Hamster进行g3647g1817。(这两个类是在g7424g12468的前面g18108g2010定g1053
的。)g11013于Iterator隐g15267了在g1866背g2530的g18039个g4493g3132的g13479g7512，因此
Printer.printAll( )既不知道也不关g5527g4439到底是g2750个g4493g3132的
Iterator,
//,c11:Iterators2.java
// Revisiting Iterators,
import com.bruceeckel.simpletest.*;
import java.util.*;
public class Iterators2 {
private static Test monitor = new Test( );
public static void main(String[] args) {
List list = new ArrayList( );
for(int i = 0; i < 5; i++)
list.add(new Mouse(i));
Map m = new HashMap( );
for(int i = 0; i < 5; i++)
m.put(new Integer(i),new Hamster(i));
System.out.println("List");
Printer.printAll(list.iterator( ));
System.out.println("Map");
Printer.printAll(m.entrySet( ).iterator( ));
monitor.expect(new String[] {
"List",
"This is Mouse #0",
"This is Mouse #1",
"This is Mouse #2",
"This is Mouse #3",
"This is Mouse #4",
"Map",
"4=This is Hamster #4",
"3=This is Hamster #3",
"2=This is Hamster #2",
"1=This is Hamster #1",
"0=This is Hamster #0"
},Test.IGNORE_ORDER);
}
} ///:~
Chapter 11,Collections of Objects
g12544 82 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
HashMap的entrySet( )方法会g17832g3250Map.entry对象的Set，这个对象既g2265g6336键也g2265g6336值，因此你会看到这两者都g15999g6183g2372出来了。
g8892意PrintData.print( )用到了g991面这条有g2045条g1226，g256g4493g3132g18336的对象都是Object，所以System.out.println( )会自动g16855用g4439的
toString( )方法g257。g1306是在解决g4466际问题的时候，你很可能会面对
g256Iterator所g16787问的是某种类型的g4493g3132g257的情况。g8616方说，g4493g3132g18336的对象都是能draw( )出来的Shape。于是你g17836得g1820把Iterator.next( )
所g17832g3250的Objectg991传给Shape。
选择实现
g10628在你g5224g16825g7138g11345了，g4466际上只有g989种g4493g3132组g1226：Map，Listg2656Set，g1306
是每种组g1226又有多个g4466g10628。所以，g3926果你要用到某个组g1226的g16817，又g16825g17885g6333
g1866g1025的g2750个g4466g10628g2614g731
要想g3250答这个问题，你g5529g20047g1820了解，各种g4466g10628都有g4439自己的特g5627，g4439所g10432
有的g5390项g2656弱点。g8616方说，你可以从g3282表得知，Hashtable，Vector
g2656Stack属于老版g7424留g991来的类，g11458的是g16765老g1207码g17836能运行g991去。所以，g1901新程序的时候就不g5224g16825g1889用了。
g4493g3132g994g4493g3132的差g2047，g5414根g13479蒂g17836是在g1866g256背g2530g257的g4466g10628g727 也就是说，真正g4466g10628这个interface的数据g13479g7512是什么。g8616方说，ArrayListg2656
LinkedList都g4466g10628了List接g2487，所以不论你用g4439们g1025的g2750个，g1866g3534g7424
的功能都是一样的。g1306是，ArrayList的背g2530是数组，而LinkedList
是用所g16871的双向链表来g4466g10628的，也就是每个对象，g19512了保g4396数据g1055外，g17836
保g4396着在g4439前面g2656g2530面的g18039两个对象的reference。所以，g3926果你要在
List的g1025间g1582很多插入g2656g2036g19512的g16817，LinkedList就g8616g17751合g17878了。
(LinkedList也g17836有一些AbstractSequenialList的g19480g2164的功能。)
否则，ArrayList会更g5567一些。
g1889g1042一个g1375g4388，Set有g989个g4466g10628，TreeSet，HashSetg2656
LinkedHashSet。g4439们的工g1328方式都不一样：HashSet是我们通常所用的Set，我们会把用当g256查询g5627能的g3534准(raw speed on
lookup)g257，LinkedHashSet会按插入顺序保g4396pair，而TreeSet
的背g2530是TreeMap，因此g4439能提供恒定有序的Set。g1055所以要这么g16786
计，是想g16765你能根据需要g17885用具体的g4466g10628。绝大多数情况g991，HashSet
就g3827用了，所以g13582省情况g991，你g5224g16825用g4439。
如何挑选List
Thinking in Java 3rd Edition
g12544 83 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
要想观察List的各种g4466g10628g1055间的g2318g2047，g7380具说g7393力的办法g17836是g1582一个g5627
能g8991g16809。g991面这段程序创建了一个g15999用g1328g8991g16809g7706架的内g18108类g3534类，g9994g2530创建了一个g1207表各种g8991g16809的匿名内g18108类的数组。你可以g16855用这些内g18108类的
test( )方法来启动g8991g16809，这样就能很方便地g9167g2164g2656g2036g19512新的g8991g16809了。
//,c11:ListPerformance.java
// Demonstrates performance differences in Lists,
// {Args,500}
import java.util.*;
import com.bruceeckel.util.*;
public class ListPerformance {
private static int reps = 10000;
private static int quantity = reps / 10;
private abstract static class Tester {
private String name;
Tester(String name) { this.name = name; }
abstract void test(List a);
}
private static Tester[] tests = {
new Tester("get") {
void test(List a) {
for(int i = 0; i < reps; i++) {
for(int j = 0; j < quantity; j++)
a.get(j);
}
}
},
new Tester("iteration") {
void test(List a) {
for(int i = 0; i < reps; i++) {
Iterator it = a.iterator( );
while(it.hasNext( ))
it.next( );
}
}
},
new Tester("insert") {
void test(List a) {
int half = a.size( )/2;
String s = "test";
ListIterator it = a.listIterator(half);
for(int i = 0; i < reps * 10; i++)
it.add(s);
}
},
new Tester("remove") {
void test(List a) {
ListIterator it = a.listIterator(3);
while(it.hasNext( )) {
it.next( );
it.remove( );
}
}
},
};
public static void test(List a) {
// Strip qualifiers from class name,
System.out.println("Testing " +
Chapter 11,Collections of Objects
g12544 84 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
a.getClass( ).getName( ).replaceAll("\\w+\\.",
""));
for(int i = 0; i < tests.length; i++) {
Collections2.fill(a,
Collections2.countries.reset( ),
quantity);
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis( );
tests[i].test(a);
long t2 = System.currentTimeMillis( );
System.out.println("," + (t2 - t1));
}
}
public static void testArrayAsList(int reps) {
System.out.println("Testing array as List");
// Can only do first two tests on an array,
for(int i = 0; i < 2; i++) {
String[] sa = new String[quantity];
Arrays2.fill(sa,
Collections2.countries.reset( ));
List a = Arrays.asList(sa);
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis( );
tests[i].test(a);
long t2 = System.currentTimeMillis( );
System.out.println("," + (t2 - t1));
}
}
public static void main(String[] args) {
// Choose a different number of
// repetitions via the command line,
if(args.length > 0)
reps = Integer.parseInt(args[0]);
System.out.println(reps + " repetitions");
testArrayAsList(reps);
test(new ArrayList( ));
test(new LinkedList( ));
test(new Vector( ));
}
} ///:~
g13783g15397到内g18108类Tester是各项具体g8991g16809的g3534类，因此g4439g15999定g1053成
abstract的。g4439g2265含了一个g256要在g8991g16809g5332g3999的时候g15999g6183g2372出来g257的
String，以g2462真正用于g8991g16809的abstract的test( )方法。所有g8991g16809都
g15999g19610g1025在tests数组g18336面。我们用继承Tester的匿名内g18108类来对数组进行g2033g3999g2282。要想g3698g2164或g2036g19512g8991g16809，直接往数组g18336g2164减内g18108类就可以了，
接g991来的g1008g16211都是自动的。
为了在数组g2656g4493g3132g1055间进行g8616g17751(g1039要是针对ArrayList的)，我们用
Arrays.asList( )把数组g2265g16025成List，并以此为数组创建了一个特殊的
g8991g16809。g8892意，g11013于你没法在数组g18336面插入g2656g2036g19512g1815g13044，因此你只能进行前两个课g11458的g8991g16809。
Thinking in Java 3rd Edition
g12544 85 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
我们g1820把Listg3647g9397，g1889传给test( )，g9994g2530程序g1889为各项g8991g16809标g8892时间。g8991g16809g13479果会g19555g7438g3132的不同而不同g727因此我们只关g5527g4439们在顺序，以g2462
大数方面的差异。g991面是某g8437运行的g13479果,
Type Get Iteration Insert Remove
array 172 516 na na
ArrayList 281 1375 328 30484
LinkedList 5828 1047 109 16
Vector 422 1890 360 30781
g13479果同我们的估计差不多，数组在g19555g7438g16787问g2656顺序g16787问方面g8616任何g4493g3132都
g5567。ArrayList的g19555g7438g16787问(get( ))要g8616LinkedListg5567。(g1306g3867g5630的是LinkedList的顺序g16787问居g9994会g8616ArrayList的g5567，真是有点不可思
g16770。)g2490一方面，LinkedList的插入g2656g2036g19512，特别是g2036g19512，要g8616
ArrayList的g5567得多的多。通常情况g991，Vector的g17907g5242g8616不上
ArrayList的，所以你就不要g1889用了g727g4439g1055所以g17836呆在类库g18336面，只是为了要对g17963留g991来的老g1207码提供支持(这g18336g17836能g8991g16809Vector，也只是因为g4439在Java 2g18336摇g17535一g2476为List了)。也g16780g7380佳的g1582法就是，g1820g17885用
ArrayList，当g2469g10628g256在g2027表的g1025间进行插入g2656g2036g19512的g6817g1328太多所引g2469
的g257g5627能问题时，把g4439g6925成LinkedList。当g9994，处理g3278定数量的g1815g13044
时，g17836是用数组。
如何挑选Set (Choosing between Sets)
你可以根据需要，在TreeSet，HashSetg2656LinkedHashSetg1025间
g17885一个g6333。g991面这项g8991g16809揭g12046了这几种g4466g10628在g5627能方面的侧g18337点,
//,c11:SetPerformance.java
// {Args,500}
import java.util.*;
import com.bruceeckel.util.*;
public class SetPerformance {
private static int reps = 50000;
private abstract static class Tester {
String name;
Tester(String name) { this.name = name; }
abstract void test(Set s,int size);
}
private static Tester[] tests = {
new Tester("add") {
void test(Set s,int size) {
for(int i = 0; i < reps; i++) {
s.clear( );
Collections2.fill(s,
Collections2.countries.reset( ),size);
}
}
},
Chapter 11,Collections of Objects
g12544 86 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
new Tester("contains") {
void test(Set s,int size) {
for(int i = 0; i < reps; i++)
for(int j = 0; j < size; j++)
s.contains(Integer.toString(j));
}
},
new Tester("iteration") {
void test(Set s,int size) {
for(int i = 0; i < reps * 10; i++) {
Iterator it = s.iterator( );
while(it.hasNext( ))
it.next( );
}
}
},
};
public static void test(Set s,int size) {
// Strip qualifiers from class name,
System.out.println("Testing " +
s.getClass( ).getName( ).replaceAll("\\w+\\.",
"") +
" size " + size);
Collections2.fill(s,
Collections2.countries.reset( ),size);
for(int i = 0; i < tests.length; i++) {
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis( );
tests[i].test(s,size);
long t2 = System.currentTimeMillis( );
System.out.println("," +
((double)(t2 - t1)/(double)size));
}
}
public static void main(String[] args) {
// Choose a different number of
// repetitions via the command line,
if(args.length > 0)
reps = Integer.parseInt(args[0]);
System.out.println(reps + " repetitions");
// Small,
test(new TreeSet( ),10);
test(new HashSet( ),10);
test(new LinkedHashSet( ),10);
// Medium,
test(new TreeSet( ),100);
test(new HashSet( ),100);
test(new LinkedHashSet( ),100);
// Large,
test(new TreeSet( ),1000);
test(new HashSet( ),1000);
test(new LinkedHashSet( ),1000);
}
} ///:~
g991面的表g7696g9448g12046了运行的g13479果。(当g9994，g4439会g19555你所g1363用的计g12651g7438g2656JVM
的不同而不同g727你也g5224g16825自己运行一g991),
Thinking in Java 3rd Edition
g12544 87 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
Type Test
size
Add Contains Iteration
10 25.0 23.4 39.1
TreeSet 100 17.2 27.5 45.9
1000 26.0 30.2 9.0
10 18.7 17.2 64.1
HashSet 100 17.2 19.1 65.2
1000 8.8 16.6 12.8
10 20.3 18.7 64.1
LinkedHashSet 100 18.6 19.5 49.2
1000 10.0 16.3 10.0
总的说来，HashSet的各项g5627能都g8616TreeSet的好 (g4600g1866是在g256g2164
入g257g2656g256查询g257这两个g7380g18337要的方面)。而TreeSet的意g1053在于，g4439会按顺序保g4396g1815g13044，因此只有在需要有序的Set时，你才g5224g16825用g4439。
g8892意LinkedHashSet的插入g8616HashSet的g12257g5942一些。这是因为g4439要承担维护链表g2656hashg4493g3132的双g18337g1207g1227。g1306是g11013于链接表的缘g6937，
LinkedHashSet的g17953g2394g8616g17751g5567。
如何挑选Maps
对Map来说，g4493量是g5445g2721g1866g5627能的g7380g18337要的因g13044，g991面我们用这个程序
g8991g16809一g991g4439对g5627能的g5445g2721,
//,c11:MapPerformance.java
// Demonstrates performance differences in Maps,
// {Args,500}
import java.util.*;
import com.bruceeckel.util.*;
public class MapPerformance {
private static int reps = 50000;
private abstract static class Tester {
String name;
Tester(String name) { this.name = name; }
abstract void test(Map m,int size);
}
private static Tester[] tests = {
new Tester("put") {
void test(Map m,int size) {
for(int i = 0; i < reps; i++) {
m.clear( );
Collections2.fill(m,
Collections2.geography.reset( ),size);
}
}
},
Chapter 11,Collections of Objects
g12544 88 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
new Tester("get") {
void test(Map m,int size) {
for(int i = 0; i < reps; i++)
for(int j = 0; j < size; j++)
m.get(Integer.toString(j));
}
},
new Tester("iteration") {
void test(Map m,int size) {
for(int i = 0; i < reps * 10; i++) {
Iterator it = m.entrySet( ).iterator( );
while(it.hasNext( ))
it.next( );
}
}
},
};
public static void test(Map m,int size) {
// Strip qualifiers from class name,
System.out.println("Testing " +
m.getClass( ).getName( ).replaceAll("\\w+\\.",
"") +
" size " + size);
Collections2.fill(m,
Collections2.geography.reset( ),size);
for(int i = 0; i < tests.length; i++) {
System.out.print(tests[i].name);
long t1 = System.currentTimeMillis( );
tests[i].test(m,size);
long t2 = System.currentTimeMillis( );
System.out.println("," +
((double)(t2 - t1)/(double)size));
}
}
public static void main(String[] args) {
// Choose a different number of
// repetitions via the command line,
if(args.length > 0)
reps = Integer.parseInt(args[0]);
System.out.println(reps + " repetitions");
// Small,
test(new TreeMap( ),10);
test(new HashMap( ),10);
test(new LinkedHashMap( ),10);
test(new IdentityHashMap( ),10);
test(new WeakHashMap( ),10);
test(new Hashtable( ),10);
// Medium,
test(new TreeMap( ),100);
test(new HashMap( ),100);
test(new LinkedHashMap( ),100);
test(new IdentityHashMap( ),100);
test(new WeakHashMap( ),100);
test(new Hashtable( ),100);
// Large,
test(new TreeMap( ),1000);
test(new HashMap( ),1000);
test(new LinkedHashMap( ),1000);
test(new IdentityHashMap( ),1000);
test(new WeakHashMap( ),1000);
Thinking in Java 3rd Edition
g12544 89 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
test(new Hashtable( ),1000);
}
} ///:~
g11013于要g13783g15397Map的大小对g5627能的g5445g2721，因此我们用g19512以g4493量的方法对g8991
g16809数据g1582了一些g1474正。g991面是某g8437g8991g16809的运行g13479果。(你的g8991g16809g13479g7512可能会不同。)
Type Test
size
Put Get Iteration
10 26.6 20.3 43.7
TreeMap 100 34.1 27.2 45.8
1000 27.8 29.3 8.8
10 21.9 18.8 60.9
HashMap 100 21.9 18.6 63.3
1000 11.5 18.8 12.3
10 23.4 18.8 59.4
LinkedHashMap 100 24.2 19.5 47.8
1000 12.3 19.0 9.2
10 20.3 25.0 71.9
IdentityHashMap 100 19.7 25.9 56.7
1000 13.1 24.3 10.9
10 26.6 18.8 76.5
WeakHashMap 100 26.1 21.6 64.4
1000 14.7 19.2 12.4
10 18.8 18.7 65.7
Hashtable 100 19.4 20.9 55.3
1000 13.1 19.9 10.8
正g3926你所g20056料的，Hashtable的g5627能同HashMap的不相上g991。(可能你也g8892意到了，一般情况g991HashMap会g12257g5567些g727HashMap是用来g1207
替Hashtable的。)TreeMap通常要g8616HashMapg5942，g18039么为什么
g17836要g4439g2614g731答g7708是，g4439是用来创建有序g2027表的。g7653总是有序的，所以根g7424
用不着为g4439去g1582g6502序。往TreeMapg18336面g3647g4448数据g1055g2530，你就能用
keySet( )g14731取g2265含这个Map的键的Set了，接g991来用toArray()把这个Setg17728g6454成数组。g9994g2530就能用static的
Arrays.binarySearch( )方法(g991面g1889g16774)在有序数组g18336面进行g5567g17907查
g6226对象了。当g9994，这一切是在g7092法g1363用HashMap的情况g991g1582的，因为
HashMap就是为g5567g17907查g6226而g16786计的。此外，你g17836能轻而g7143g1042地用
Chapter 11,Collections of Objects
g12544 90 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
TreeMap创建一个HashMap。g13479论是，g17885g6333Map的时候，首g17885g5224
g16825是HashMap，只有在要用恒定有序的Map的情况g991，你才g5224g16825g17885用
TreeMap。
LinkedHashMapg8616HashMapg12257g5942一些，这是因为g4439g19512了要保g4396
hash数据g13479g7512g1055外，g4439g17836要保g4396链表。IdentityHashMapg2656上面没法g1328g8616g17751，因为g4439是用 == 而不是equals( )来g8616g17751对象的相g12573g5627的。
List的排序与查询
用于List的g6502序g2656查询工具g2656用于数组的有着相同的名g12228g2656特g5461签名，
只是g4439们不是Arrays的，而是Collections的static方法。g991面我们就用这些方法来g6925g1901ArraySearching.java,
//,c11:ListSortSearch.java
// Sorting and searching Lists with 'Collections.'
import com.bruceeckel.util.*;
import java.util.*;
public class ListSortSearch {
public static void main(String[] args) {
List list = new ArrayList( );
Collections2.fill(list,Collections2.capitals,
25);
System.out.println(list + "\n");
Collections.shuffle(list);
System.out.println("After shuffling," + list);
Collections.sort(list);
System.out.println(list + "\n");
Object key = list.get(12);
int index = Collections.binarySearch(list,key);
System.out.println("Location of " + key +
" is " + index + ",list.get(" +
index + ") = " + list.get(index));
AlphabeticComparator comp = new
AlphabeticComparator( );
Collections.sort(list,comp);
System.out.println(list + "\n");
key = list.get(12);
index = Collections.binarySearch(list,key,
comp);
System.out.println("Location of " + key +
" is " + index + ",list.get(" +
index + ") = " + list.get(index));
}
} ///:~
这些方法的用法同Arrays的g4448g1852相同，只不过是用于List而不是数组。同数组一样，g3926果你用Comparator进行g6502序，g18039么你得用一个
Comparator来binarySearch( )。
Thinking in Java 3rd Edition
g12544 91 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
这个程序g17836g9448g12046了Collections的shuffle( )方法，g4439的功能就是把
List的顺序g6183乱。
实用工具
Collections类g17836有很多很g4466用的工具,
max(Collection)
min(Collection)
用自g9994对象内置的g12651法进行g8616g17751，
g17832g3250Collectiong1025g7380大g2656g7380小的
g1815g13044。
max(Collection,
Comparator)
min(Collection,
Comparator)
用Comparator进行g8616g17751，g17832g3250
g7380大或g7380小的g1815g13044。
indexOfSubList(List
source,List target)
g14731取targetg12544一g8437出g10628在
sourceg1025的位置。
lastIndexOfSubList(List
source,List target)
g17832g3250targetg7380g2530一g8437出g10628在
sourceg1025的位置。
replaceAll(List list,
Object oldVal,Object
newVal)
g4570所有的oldVal 替g6454成
newVal,
reverse( ) 颠倒List的顺序。
rotate(List list,int
distance)
把所有的g1815g13044向g2530g12239distance位，
g4570g7380g2530面的g1815g13044接到g7380前面。
copy(List dest,List src) g4570src的g1815g13044g6347g17137到dest。
swap(List list,int i,int j) 互g6454list的ig2656 j 位置上的g1815g13044。
可能会g8616你g1901g1207码要g5567。
fill(List list,Object o) 把listg18336面的g1852g18108g1815g13044g1852都替g6454成
o。
nCopies(int n,Object o) g17832g3250一个有n个g1815g13044的不可g2476的
List，而g1000这个Listg1025的所有g1815g13044
g1852都指向o。
enumeration(Collection) g17832g3250一个老式的Enumeration。
list(Enumeration e) 用这个Enumerationg10995成一个
ArrayList，并g1000g17832g3250这个
ArrayList。是用来处理g17963留g991来的老g1207码的。
Chapter 11,Collections of Objects
g12544 92 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g8892意，min( )g2656max( )是针对Collection 的，g4439不是只为Listg7393
g2165的，所以你不用担Collection是不是有序。(我们前面g5062g13475提到过了，在binarySearch( )g1055前，你一定得先sort( )这个List或数组。)
//,c11:Utilities.java
// Simple demonstrations of the Collections
utilities,
import com.bruceeckel.simpletest.*;
import java.util.*;
import com.bruceeckel.util.*;
public class Utilities {
private static Test monitor = new Test( );
public static void main(String[] args) {
List list = Arrays.asList(
"one Two three Four five six one".split(" "));
System.out.println(list);
System.out.println("max," +
Collections.max(list));
System.out.println("min," +
Collections.min(list));
AlphabeticComparator comp = new
AlphabeticComparator( );
System.out.println("max w/ comparator," +
Collections.max(list,comp));
System.out.println("min w/ comparator," +
Collections.min(list,comp));
List sublist =
Arrays.asList("Four five six".split(" "));
System.out.println("indexOfSubList," +
Collections.indexOfSubList(list,sublist));
System.out.println("lastIndexOfSubList," +
Collections.lastIndexOfSubList(list,sublist));
Collections.replaceAll(list,"one","Yo");
System.out.println("replaceAll," + list);
Collections.reverse(list);
System.out.println("reverse," + list);
Collections.rotate(list,3);
System.out.println("rotate," + list);
List source =
Arrays.asList("in the matrix".split(" "));
Collections.copy(list,source);
System.out.println("copy," + list);
Collections.swap(list,0,list.size( ) - 1);
System.out.println("swap," + list);
Collections.fill(list,"pop");
System.out.println("fill," + list);
List dups = Collections.nCopies(3,"snap");
System.out.println("dups," + dups);
// Getting an old-style Enumeration,
Enumeration e = Collections.enumeration(dups);
Vector v = new Vector( );
while(e.hasMoreElements( ))
v.addElement(e.nextElement( ));
// Converting an old-style Vector
// to a List via an Enumeration,
ArrayList arrayList =
Collections.list(v.elements( ));
Thinking in Java 3rd Edition
g12544 93 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
System.out.println("arrayList," + arrayList);
monitor.expect(new String[] {
"[one,Two,three,Four,five,six,one]",
"max,three",
"min,Four",
"max w/ comparator,Two",
"min w/ comparator,five",
"indexOfSubList,3",
"lastIndexOfSubList,3",
"replaceAll,[Yo,Two,three,Four,five,six,
Yo]",
"reverse,[Yo,six,five,Four,three,Two,
Yo]",
"rotate,[three,Two,Yo,Yo,six,five,
Four]",
"copy,[in,the,matrix,Yo,six,five,Four]",
"swap,[Four,the,matrix,Yo,six,five,in]",
"fill,[pop,pop,pop,pop,pop,pop,pop]",
"dups,[snap,snap,snap]",
"arrayList,[snap,snap,snap]"
});
}
} ///:~
程序的g17767出g5062g13475g16774解了这些工具的用法。g8892意一g991
AlphabeticComparator对min( ) g2656max( )的g5445g2721，这是g11013于大小g1901的缘g6937。
把Collection和Map设成不可修改的
通常情况g991，创建只读的Collection或Map是很方便的。
Collections有专门的方法，你可以传一个g4493g3132给g4439，g4439会g17832g3250这个g4493
g3132的只读版。这个方法有g3247种g2476形，Collection(g3926果你没法g7138确指g7138g4439
是g2750种Collection的g16817)，List，Setg2656Map各一个。g991面我们用一个g1375g4388来g9448g12046一g991g3926何创建只读的g4493g3132,
//,c11:ReadOnly.java
// Using the Collections.unmodifiable methods,
import java.util.*;
import com.bruceeckel.util.*;
public class ReadOnly {
private static Collections2.StringGenerator gen =
Collections2.countries;
public static void main(String[] args) {
Collection c = new ArrayList( );
Collections2.fill(c,gen,25); // Insert data
c = Collections.unmodifiableCollection(c);
System.out.println(c); // Reading is OK
//! c.add("one"); // Can't change it
List a = new ArrayList( );
Collections2.fill(a,gen.reset( ),25);
Chapter 11,Collections of Objects
g12544 94 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
a = Collections.unmodifiableList(a);
ListIterator lit = a.listIterator( );
System.out.println(lit.next( )); // Reading is
OK
//! lit.add("one"); // Can't change it
Set s = new HashSet( );
Collections2.fill(s,gen.reset( ),25);
s = Collections.unmodifiableSet(s);
System.out.println(s); // Reading is OK
//! s.add("one"); // Can't change it
Map m = new HashMap( );
Collections2.fill(m,Collections2.geography,25);
m = Collections.unmodifiableMap(m);
System.out.println(m); // Reading is OK
//! m.put("Ralph","Howdy!");
}
} ///:~
编译g3132不会因为你g16855用了g256unmodifiableg257方法而去g1582g20081外的g7828查，g1306
是g17728g6454g4448g8617g1055g2530，你g1889想去g1474g6925这个g4493g3132的时候，g4439就会抛出
UnsupportedOperationException了。
任何情况g991，你都g5224g16825先准g3803好数据，再把g4493g3132g16786成只读的。g1582g4448g1055g2530，
你就g5224g16825用g256unmodifiableg257方法所g17832g3250的reference来替g6454原g1820g18039个
reference了。这样你就不会在g7092意g1055g1025把不g16825g6925的g1008g16211给g6925了。此外，
你g17836能g2045用这个方法，在类g18336以private的权限保g4396可g1474g6925的g4493g3132。这样，你可以g1474g6925，而g1866他人就只能读了。
Collection和Map的同步
synchronized关键词是多g13459程的一个g18337要组成g18108g2010，我们要到g1254413
g12468才g1582更详细的g16774解。这g18336，我只想指出，Collectionsg18336面也有一个能自动对g4493g3132g1582同步的方法。g4439的语法g994g256unmodifiableg257方法的有些相g1296,
//,c11:Synchronization.java
// Using the Collections.synchronized methods,
import java.util.*;
public class Synchronization {
public static void main(String[] args) {
Collection c =
Collections.synchronizedCollection(new
ArrayList( ));
List list =
Collections.synchronizedList(new ArrayList( ));
Set s = Collections.synchronizedSet(new
HashSet( ));
Map m = Collections.synchronizedMap(new
HashMap( ));
Thinking in Java 3rd Edition
g12544 95 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
}
} ///:~
这样，你就能通过合g17878的g256synchronizedg257方法来传g17894g4493g3132了g727于是，
你就g1889也不用担g5527会g8856g9443尚未同步的g1008g16211了。
Fail fast
Javag4493g3132g17836有一种能防止多个进程同时g1474g6925g4493g3132内g4493的g7438g2058。g1563g16786你正在g17953g2394某个g4493g3132，这时g2490一个进程插了进来，对g4493g3132g1328了插入，g2036g19512或是
g1474g6925g18336g17805的对象，于是这个问题就来了。或g16780你g5062g13475把对象传出去了，g1306
是g4439抢在你头g18336把g4439给g2036了g727或g16780你g16855用了size( )，g1306是g4493g3132g5062g13475g13565水了——会引g2469灾g19602的可能g5627太多了。Javag4493g3132类库g19610成了一个叫fail-
fast(g2462早报告错误)g7438g2058，g4439能g6226出所有不g5224g11013进程g17139g17143的g4493g3132的g2476g2282。
g3926果g4439g2469g10628有人在g1474g6925g4493g3132，g4439会立即g17832g3250一个
ConcurrentModificationException。这就是g4439g256fail-fastg257的地方，g4439不会g12573出了问题g1055g2530g1889去用很g3809g7446的g12651法去g6226问题了。
要想观察fail-fast很g4493g7143——只要创建一个g17857g1207g3132，g9994g2530在iterator的位置上往Collectiong18336面g2164g1008g16211就行了，就像这样,
//,c11:FailFast.java
// Demonstrates the "fail fast" behavior,
// {ThrowsException}
import java.util.*;
public class FailFast {
public static void main(String[] args) {
Collection c = new ArrayList( );
Iterator it = c.iterator( );
c.add("An object");
// Causes an exception,
String s = (String)it.next( );
}
} ///:~
g1055所以会有这种异常，是因为你是在g5062g13475g14731取g4493g3132的iterator的情况g991往
g18336面g2164对象的。程序的两个g18108g2010会g1474g6925同一个g4493g3132的这种可能g5627，会g4560g14280
程序处于不确定的状g5589，因此g4439抛出一个异常来通知你，你g5224g16825g1474g6925g1207码了——碰到这种情况，你g5224g16825g1820往g4493g3132g18336面g2164g1815g13044，g1889去g14731取g4493g3132的
iterator。
提g12046一g991，g3926果你是在用get( )g16787问List，g18039么fail-fast就帮不上什么忙了。
Chapter 11,Collections of Objects
g12544 96 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
可以不支持的操作
可以用Arrays.asList( )方法把数组g6925造成List,
//,c11:Unsupported.java
// Sometimes methods defined in the
// Collection interfaces don't work!
// {ThrowsException}
import java.util.*;
public class Unsupported {
static List a = Arrays.asList(
"one two three four five six seven
eight".split(" "));
static List a2 = a.subList(3,6);
public static void main(String[] args) {
System.out.println(a);
System.out.println(a2);
System.out.println("a.contains(" + a.get(0) + ")
= " +
a.contains(a.get(0)));
System.out.println("a.containsAll(a2) = " +
a.containsAll(a2));
System.out.println("a.isEmpty( ) = " +
a.isEmpty( ));
System.out.println("a.indexOf(" + a.get(5) + ")
= " +
a.indexOf(a.get(5)));
// Traverse backwards,
ListIterator lit = a.listIterator(a.size( ));
while(lit.hasPrevious( ))
System.out.print(lit.previous( ) + " ");
System.out.println( );
// Set the elements to different values,
for(int i = 0; i < a.size( ); i++)
a.set(i,"47");
System.out.println(a);
// Compiles,but won't run,
lit.add("X"); // Unsupported operation
a.clear( ); // Unsupported
a.add("eleven"); // Unsupported
a.addAll(a2); // Unsupported
a.retainAll(a2); // Unsupported
a.remove(a.get(0)); // Unsupported
a.removeAll(a2); // Unsupported
}
} ///:~
你会g2469g10628，g4466际上g4439只是g18108g2010地g4466g10628了Collectiong2656List接g2487。g16855用
g1866g4439方法会引g2469一个UnsupportedOperationException异常。
Collection接g2487——以g2462Javag4493g3132类库的g1866g4439接g2487——都g2265含了一些
g256可g17885的g257方法，也就是说在implements这个interface的g4466体类
Thinking in Java 3rd Edition
g12544 97 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g18336可以g256支持g257也可以不g256支持g257这些方法。g3926果g16855用了不支持的方法，
g4439就会用UnsupportedOperationException来表g12046错误。
g256什么?!?g257，你一定会觉得真是不可思g16770。g256interfaceg2656g3534类的意g1053
就在于，g4439们能确保这些方法会g1582一些有意g1053的事情g701而这一点g6183破了这一条g727g4439的意思是，这些方法不g1306不能g1328有意g1053的事情，而g1000g17836会g16765程序停g991来g701类型安g1852则g15999撇在一g17805了g701g257
g17836不至于g18039么糟糕。就是对Collection，List，Set或Map，编译g3132
也只g1813g16780你去g16855用g4439们的interface的方法，所以这一点同Smalltalk
不太一样(g4439g1813g16780g16855用任何对象的任何方法，因此只有在运行时才能知道这个g16855用是不是管用)。此外，绝大多数g6355Collection当g2454数的方法只是要从g18336面读g1008g16211——而Collection的g256readg257不属于可g17885的。
这个方法能防止接g2487数量的爆炸。g1866g4439g4493g3132类都是用一个接g2487去描述一种
g4493g3132的g2476形，g7380g2530总是g5336得接g2487多得不得了，于是g2476得很g19602g4410。g1306是要g16765
interface去g8022g6336所有的具体g4466g10628又是不太可能的，于是总会有人去g2469
g7138新的interface。Java用g256不支持的g6817g1328g257达成了一项g18337要g11458的：g1363
g4493g3132类g2476得g7143g4410g7143用g727不支持的g6817g1328属于特g1375，可以以g2530g1889g4410。g1306是要g16765
这种g16786计能g17227g1328用,
1,UnsupportedOperationException只能偶尔为g1055。也就是说，绝大多数类g5224g16825具g3803所有功能，只有在特殊情况g991，才可以不提供某些功能。对于Javag4493g3132类库就属于这种情况因为百g2010g1055九十九的情况g991，你要用到的g18039些类—ArrayList，LinkedList，HashSetg2656HashMap
以g2462g1866g4439g4466g10628，都是g1852功能的。g3926果你想不去定g1053Collection
interfaceg18336的g1852g18108方法就创建一个新的Collection，同时又要g16765g4439融入g10628有的类库g18336面，g18039么这种g16786计确g4466能为你提供了一扇g256g2530门g257就能
g16765g4439融入g10628有的类库。
2,g3926果这是一种不受支持的g6817g1328，g18039么
UnsupportedOperationExceptiong7380好是出g10628在g4466g10628的时候，而不是g1147g2709交给g4470户g1055g2530。g8617竟这是一个编程错误：你用错了g4466g10628。这一点不是g18039么g13475得g17227推敲，因此是g4439g4466验g5627的一面。只有时间才能告诉我们
g4439的g6940果怎么样。
在上述g1375程g1025，Arrays.asList( )g17832g3250的是一个g11013g3278定g4493量的数组支撑的List。因此，你就g7138g11345了，为什么g4439支持的都是g18039些不g6925g2476数组g4493量的g6817g1328了。g1306是g6454一个角g5242看，g3926果要用新的interface来表述这种特殊行为的g16817(或g16780可以g12228为g256FixedSizeListg257)，g3809g7446g5627就有g7438可乘了，这样用不了多久，g1889用到这个类库的时候，你就不知道从何g5332g3999了。
g8892意，g3926果你要想创建g7234通g4493g3132，g19555时都可以把Arrays.asList( )的g13479
果当g1328g7512造g2001数的g2454数传给List或Set，这样就能g1363用g4439的g4448g6984接g2487
了。
Chapter 11,Collections of Objects
g12544 98 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
在为g256用Collection，List，Set或Mapg1328g2454数的方法g257g1901文g7735的时候，g5529g20047指g7138，一定要g4466g10628g18039些可g17885的方法。g8616g3926g6502序会用到set( )g2656
Iterator.set( )方法，g1306是不会用到add( )g2656remove( )。
Java 1.0/1.1容器
不幸的是很多g1207码都是用Java 1.0/1.1的g4493g3132g1901的，有时甚至g1901新g1207码的时候也用到了这些库。所以尽管你可以不用老g4493g3132去g1901新g1207码，g1306是g17836
是g5224g16825对g4439们有点了解。不过g7099g4493g3132是相当g12628陋 的，所以也没有更多可说的了。(因为都过去了，所以我也不想g1889去g5390g16855g4439的g16786计有多糟糕。)
Vector和Enumeration
Java 1.0/1.1 g18336面，唯一可以自动g6205g4649的g4493g3132就只有Vector了，所以用得g7380多的也是g4439。g4439的g13582点多到这g18336都没法g16774的地步
(www.BruceEckel.com有g7424g1082的g12544一版可供g991g17745)。g3534g7424上你可以把g4439
理解成是一个ArrayList，只是g4439的方法的名字都很g19283，很滑稽。Java
2对Vectorg1328了些g1474g6925，把g4439g5414到Collectiong2656Listg18336面，所以
Collections2.fill( )方法也可以用于g991面这些程序。这样g1582不是太合
g17878，因为会g16765人误g16760为Vector可能更好，g4466际上这么g1582只是为了支持
Java 2以前的g1207码。
Java 1.0/1.1用一个新g2469g7138的g256enumerationg257来表g12046大g4490都g5062g13475很熟悉的iterator。Enumeration接g2487g8616Iterator的小，g4439只有两个名字很g19283方法。一个是g256只要enumerationg17836有g1866g4439的g1815g13044，就会g17832g3250
trueg257的boolean hasMoreElements( )，g2490一个是g256只要
enumerationg18336面g17836有g991一个g1815g13044，g4439就会g17832g3250这个g1815g13044g257的Object
nextElement( )(反g1055则抛出异常)。
Enumeration是接g2487而不是g4466g10628，所以有时新的类库仍g9994会用g7099的
Enumeration，这真是太糟了，g1306是也没什么关系。g15441g9994你g5224g16825尽量在新g1207码g18336g1363用Iterator，g1306也要对g256类库可能会交给你一个
Enumerationg257有所准g3803。
此外，你g17836可以用Collections.enumeration( )方法从Collection
g18039g18336g14731取一个Enumeration，就像g991面这段程序,
//,c11:Enumerations.java
// Java 1.0/1.1 Vector and Enumeration,
import java.util.*;
import com.bruceeckel.util.*;
public class Enumerations {
public static void main(String[] args) {
Vector v = new Vector( );
Collections2.fill(v,Collections2.countries,
100);
Thinking in Java 3rd Edition
g12544 99 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
Enumeration e = v.elements( );
while(e.hasMoreElements( ))
System.out.println(e.nextElement( ));
// Produce an Enumeration from a Collection,
e = Collections.enumeration(new ArrayList( ));
}
} ///:~
Java 1.0/1.1的Vector只有一个addElement( )方法，g1306是fill( )
用的却是add( )。这是Vector在g17728g6454成List的过程g1025g5114过去的。g16855
用elements( )会g17832g3250一个Enumeration，g9994g2530用g4439来进行g17953g2394。
g7380g2530一行创建了一个ArrayList，g9994g2530用enumeration( )把
ArrayList的Iteratorg17728g2282成Enumeration。 这样，即便你有g256要用Enumeration的g7099g1207码g257，仍g9994可以g1363用新的g4493g3132。
Hashtable
正g3926你在g5627能g8616g17751g18336面所看到的，Hashtableg2656HashMapg3534g7424相同，甚至是在方法的名字上。没理g11013g1889在新g1207码g18336用Hashtable，而不是HashMap了。
Stack
我们在g16774LinkedList的时候g5062g13475g16774过g7644了。g1306是Java 1.0/1.1的
Stack有一个非常g3867g5630的地方，g18039就是g4439不是把Vector用g1328g7644的内
g18108，而是继承了Vector。g11013此Stackg6329有了Vector的g1852g18108特g5461g2656功能，并g1000g1889g2164上一点Stack的功能。真不知道g16786计者们是很g9177醒地g16760为这是一种特殊g16786计，或者只是一种幼稚的g16786计g727g1306不管怎么说，很g7138g7186，
在g2469布g1055前，这个方g7708没有g15999g16760真地g7828讨过。造成的恶果就是，直到g10628在
g4439g17836吊在g18039g18336(g1306是你g8716g17840也g2047去用g4439)。
g991面我们g12628g2345地g9448g12046一g991Stack，g4439会逐行把String数组的内g4493g2399入
g7644,
//,c11:Stacks.java
// Demonstration of Stack Class,
import com.bruceeckel.simpletest.*;
import java.util.*;
import c08.Month;
public class Stacks {
private static Test monitor = new Test( );
public static void main(String[] args) {
Stack stack = new Stack( );
for(int i = 0; i < Month.month.length; i++)
stack.push(Month.month[i] + " ");
System.out.println("stack = " + stack);
Chapter 11,Collections of Objects
g12544 100 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
// Treating a stack as a Vector,
stack.addElement("The last line");
System.out.println("element 5 = " +
stack.elementAt(5));
System.out.println("popping elements:");
while(!stack.empty( ))
System.out.println(stack.pop( ));
monitor.expect(new String[] {
"stack = [January,February,March,April,
May "+
",June,July,August,September,
October," +
"November,December ]",
"element 5 = June ",
"popping elements:",
"The last line",
"December ",
"November ",
"October ",
"September ",
"August ",
"July ",
"June ",
"May ",
"April ",
"March ",
"February ",
"January "
});
}
} ///:~
months数组g18336的每一行都会g15999push( )进Stack，g9994g2530g1889pop( )出来。要指出一点，Stackg6329有Vector的g1852g18108功能。这是g4448g1852可能的，
因为继承的意思是，Stack就是Vector。所以Vector都g1582的事
Stack都能g1582，就像elementAt( )。
正g3926前面所说的，需要g7644的时候，你g5224g16825g1363用LinkedList。
BitSet
g3926果你想g20652g6940地g4396g1660g16780多g256是非(on-off)g257信息的g16817，可以g1363用
BitSet。g20652g6940只是对g4493量说的g727g3926果指g16787问g17907g5242的g16817，primitive的数组会g8616g17751g5567。
此外，BitSet的g7380小g4493量g17331long一样：64位。也就是说，g3926果你要g4396
g1660更小的数据，g8616g3926说8位的，BitSet就会很浪费g727所以g3926果g4493量是个问题，你g7380好g17836是创建一个自己的类，或者用数组来g4396g1660标志信息。
g7234通的g4493g3132会g19555g1815g13044的g9167g2164而g6205g4649，这点BitSet g1328得很好。g991面这段程序g9448g12046了BitSet是g3926何工g1328的,
Thinking in Java 3rd Edition
g12544 101 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
//,c11:Bits.java
// Demonstration of BitSet,
import java.util.*;
public class Bits {
public static void printBitSet(BitSet b) {
System.out.println("bits," + b);
String bbits = new String( );
for(int j = 0; j < b.size( ) ; j++)
bbits += (b.get(j)? "1","0");
System.out.println("bit pattern," + bbits);
}
public static void main(String[] args) {
Random rand = new Random( );
// Take the LSB of nextInt( ),
byte bt = (byte)rand.nextInt( );
BitSet bb = new BitSet( );
for(int i = 7; i >= 0; i--)
if(((1 << i) & bt) != 0)
bb.set(i);
else
bb.clear(i);
System.out.println("byte value," + bt);
printBitSet(bb);
short st = (short)rand.nextInt( );
BitSet bs = new BitSet( );
for(int i = 15; i >= 0; i--)
if(((1 << i) & st) != 0)
bs.set(i);
else
bs.clear(i);
System.out.println("short value," + st);
printBitSet(bs);
int it = rand.nextInt( );
BitSet bi = new BitSet( );
for(int i = 31; i >= 0; i--)
if(((1 << i) & it) != 0)
bi.set(i);
else
bi.clear(i);
System.out.println("int value," + it);
printBitSet(bi);
// Test bitsets >= 64 bits,
BitSet b127 = new BitSet( );
b127.set(127);
System.out.println("set bit 127," + b127);
BitSet b255 = new BitSet(65);
b255.set(255);
System.out.println("set bit 255," + b255);
BitSet b1023 = new BitSet(512);
b1023.set(1023);
b1023.set(1024);
System.out.println("set bit 1023," + b1023);
}
} ///:~
Chapter 11,Collections of Objects
g12544 102 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
我们用g19555g7438数g10995成g3132g10995成了byte，shortg2656int，g9994g2530把g4439们g17728g6454成相
g5224的bit形式，g1889g4396g1660到BitSetg18336面。这种g1582法很不错，因为BitSet
是64位的，而g4439们都不会g17241出这个g14551g3272。接着g4439创建了一个512位的
BitSet。g7512造g2001数会g2010配两倍的大小的g4396g1660空间。g1306是你也可以g16786置
1024位或者更多。
总结
总g13479Java标准类库的g4493g3132类g727
1,数组把对象g2656数字形式的g991标联系g17227来。g4439持有的是类型确定的对象，
这样提取对象的时候就不用g1889g1328类型传g17894了。g4439可以是多维的，也可以持有primitive。g1306是创建g1055g2530g4439的g4493量不能g6925了。
2,Collection持有g2345个g1815g13044，而Map持有相关联的pair。
3,g2656数组一样，List也把数字g991标同对象联系g17227来，你可以把数组g2656List
想成有序的g4493g3132。List会g19555g1815g13044的g3698g2164自动g16855g6984g4493量。g1306是List只能持有Object reference，所以不能g4396放primitive，而g1000把Object提取出来g1055g2530，g17836要g1582类型传g17894。
4,g3926果要g1328很多g19555g7438g16787问，g18039么请用ArrayList，g1306是g3926果要在List的g1025
间g1328很多插入g2656g2036g19512的g16817，就g5224g16825用LinkedList了。
5,LinkedList能提供队g2027，双向队g2027g2656g7644的功能。
6,Map提供的不是对象g994数组的关联，而是对象g2656对象的关联。
HashMap看g18337的是g16787问g17907g5242，而TreeMap更看g18337键的顺序，因而g4439
不g3926HashMapg18039么g5567。而LinkedHashMap则保持对象插入的顺序，g1306是也可以用LRUg12651法为g4439g18337新g6502序。
7,Set只接受不g18337g3809的对象。HashSet提供了g7380g5567的查询g17907g5242，而
TreeSet则保持g1815g13044有序。LinkedHashSet保持g1815g13044的插入顺序。
8,没g5529要g1889在新g1207码g18336g1363用g7099类库留g991来的Vector，Hashtableg2656
Stack了。
g4493g3132类库是你每天都会用到的工具，g4439能g1363程序更g12628g8917，更g5390大并g1000更g20652
g6940。
练习
g2494g16213g1196g5468g4579g980g12520g17165g11004g4613g14033g1186www.BruceEckel.comg991g17745g2529g1038The Thinking in Java
Annotated Solution Guideg11352g11017g4388g7003g7735g712g17837g990g19766g7389g980g1135g1076g20076g11352g12584g7708g452
1,创建一个double类型的数组，g9994g2530用RandDoubleGeneratorg2656
fill( )把g4439g3647g9397。
Thinking in Java 3rd Edition
g12544 103 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
2,创建一个新的，g5114int gerbilNumber的 Gerbil类,g9994g2530在g7512造g2001数
g18336面进行g2033g3999g2282 (就像g7424g12468的Mouse.java)。定g1053一个hop( )方法，g16765
g4439g6183g2372gerbilNumber，以g2462g256g4439正在跳g257的信息。创建一个
ArrayList，g1889往g18336面g2164一g1030Gerbil对象。接g991来用get( )方法g17953g2394一
g17953List，g1889g16855用每个Gerbil对象的hop( )。
3,g1474g6925练习2，g6925用Iterator来g17953g2394List。
4,把练习2的Gerbil类放入Map，把表g12046Gerbil对象名字的
String(也就是键)，g994这个Gerbil对象(值)关联g17227来。g14731取keySet( )
的Iterator，g9994g2530用g4439来g17953g2394Map，根据键查g6226各个Gerbil，g1889g16855用
g1866hop( )。
5,创建一个List(ArrayListg2656LinkedList都g4593g16809一g991)，g9994g2530用
Collections2.countries来进行g3647g1817。对List进行g6502序，g9994g2530把g4439g6183
g2372出来，接g991来g1889用Collections.shuffle( )把顺序g6183乱，g1889g6183g2372这个
List，多g16809几g8437，看看每g8437g16855用shuffle( )的时候，g4439都是怎么把顺序
g6183乱的。
6,证g7138一g991，g19512了Mouseg1055外，MouseList不接受任何对象。
7,g1474g6925MouseList.java，g16765g4439不是通过合成g1363用ArrayList，而是继承
ArrayList。证g7138一g991这么g1582是有问题的。
8,创建一个只接g6922g2656g17832g3250Cat对象的Catsg4493g3132(g1363用ArrayList)，并以此来
g1474补CatsAndDogs.java。
9,用键值的pair来g3647g1817HashMap。把这个HashMapg6183g2372出来，g2372证一g991g4439是按hash数g6502序的，g9994g2530把g4439放入LinkedHashMap。g2372证一
g991，g4439是按插入顺序g6502序的。
10,用HashSetg2656LinkedHashSetg18337g1582上面g18039个练习。
11,创建一种新的g4493g3132，用private ArrayList来保g4396对象。用Class
reference来判断g4493g3132g1025的g12544一个对象的类型，g9994g2530只g1813g16780用户插入g18039种类型的对象。
12,用String数组创建一个只能g4396取String的g4493g3132，这样g1363用的时候就没有类型g17728g6454的问题了。当g4493g3132g2469g10628数组不g3827大的时候，g5224g16825能自动g16855g6984
g1866内g18108数组的大小。用main( )g1328一g991g8991g16809，看看是你自g2058的g4493g3132的g5627
能好，g17836是ArrayList的g5627能好。
13,g18337g1582练习12，这g8437是g1582一个int的g4493g3132，g9994g2530g8616g17751g4439g2656保g4396Integer对象的ArrayList的g5627能。g5627能g8991g16809g5224g16825g2265g6336g256对g4493g3132g1025的每个对象都g1582
g17894g3698g257的g6817g1328。
14,g1363用com.bruceeckel.utilg1025的g4466用工具，为每种primitive，以g2462
String对象各创建一个数字，g9994g2530用generatorg3647g1817这个数组，g1889g1363用合g17878的print( )方法g6183g2372这个数组。
15,创建一个能g10995成你g7380g2928g8438的电g5445的名字的generator(g4466在g6226不到，就用
g11345g19646g1856g1039，g7155g10711大战g1055类的)，g3926果名字用光了，就g13481到g7380前面去。g1363用
Chapter 11,Collections of Objects
g12544 104 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
com.bruceeckel.utilg18336面的g4466用工具来g3647补数组，ArrayList，
LinkedList，以g2462两种Set，g9994g2530把这些g4493g3132g6183g2372出来。
16,创建一个g2265g6336两个String对象的类，g9994g2530g1582一个只g8616g17751g12544一个字g12538g1030
的Comparable。用geography的generator来g10995成这种对象，g9994g2530
用这种对象来g3647g1817数组g2656ArrayList。验证一g991，g6502序能正常工g1328。g1889
g1582一个只g8616g17751g12544二个String的Comparator，g9994g2530验证一g991g6502序也能正常工g1328。g9994g2530用Comparator进行以此binarySearch( )。
17,g1474g6925练习16，g16765g4439按字母顺序g6502序。
18,用Arrays2.RandStringGeneratorg10995成的字g12538g1030，按字母顺序g3647g1817
TreeSet。把TreeSetg6183g2372出来，看看g4439是按什么顺序g6502g2027的。
19,g2010g2047创建一个ArrayListg2656LinkedList，用Collections2.captials
generator来g3647g1817这个g4493g3132。用g7234通的Iteratorg6183g2372这个g2027表，g9994g2530用
ListIterator，按照隔一个位置插一个对象的方式，把两个g2027表合并g17227
来。g9994g2530从g2027表的g7423g4626g5332g3999向前g12239动，并g1000g6203行插入g6817g1328。
20,g1901一个用Iteratorg17953g2394Collection，并g1000g6183g2372g1866g1025每个对象的
hashCode( )的方法。把对象g3647到各种Collectiong18336面，g9994g2530g8991g16809这个方法。
21,g1474g3809InfiniteRecursion.java的问题。
22,g1820创建一个类，g1889创建一个用这个类的对象进行g2033g3999g2282的数组。把数组
g18336的对象g3647到Listg18336面，g1889用subList( )创建一个这个List的g4388g19610，
g9994g2530用removeAll( )g4388g19610从Listg18336面g2036g19512。
23,g1474g6925g12544七g12468的练习6，用ArrayList保g4396Rodent，用Iteratorg17953g2394
这个序g2027。g16772g1315，ArrayList只保g4396Object，所以要想g16787问
Rodent，g1820得g1582类型g17728g6454。
24,模g1235Queue.java，创建一个Deque类，g9994g2530g1889g8991g16809一g991。
25,用TreeMapg6925g1901Statistics.java。g1889g2164入g8991g16809g1207码，g8616g17751一g991
HashMapg2656TreeMap的g5627能。
26,创建一个保g4396名字以g256Ag257g5332头的g3281g4490的Mapg2656Set。
27,用Collections2.countriesg18337g3809g3647补Set，并以此来验证，Set不接受g18337g3809的对象。两种Set各g16809一g8437。
28,g1474g6925Statistics.java，创建一个g18337g3809进行g8991g16809的程序，看看一个数是不是g8616g2490一个数出g10628的g20069g10587g20652。
29,用Couter对象的HashSetg18337g1901Statistics.java(要对Counter类进行g1474g6925，这样g4439才能g15999放入HashSetg18336面)。g8616g17751一g991，g2750种方法更好。
30,用String当键，你自己g17885g6333的对象当值，g3647g1817LinkedHashMap。把键值pair提取出来，根据键g6502序，g9994g2530把g4439们g18337新插到Mapg18336面。
Thinking in Java 3rd Edition
g12544 105 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
31,g1474g6925练习16的类，g16765g4439能g17878用于HashSet，并g1000能在HashMapg18336面
g1817当键。
32,g2454g13783SlowMap.java，创建一个SlowSet。
33,创建一个FastTraversalLinkedList，g16765g4439在内g18108用LinkedList进行g5567g17907的插入g2656g2036g19512，用ArrayList进行g5567g17907的g17953g2394g2656get( )g6817g1328。g2454
g13783ArrayPerformance.java编g1901程序进行g8991g16809。
34,对SlowMap进行Map1.java的g8991g16809，看看g4439是不是能正常工g1328。g1474
g6925SlowMap，g16765g4439能进行通过这个g8991g16809。
35,g1474g6925SlowMap，g16765g4439g4466g10628Map的g1852g18108接g2487。
36,g1474g6925MapPerformance.java，用g4439来g8991g16809一g991SlowMap的g5627能。
37,g1474g6925SlowMap，g6925用MPair对象的ArrayList，而不是两个
ArrayList来g4466g10628。看看g1474g6925g2530的版g7424是不是也能正常工g1328。用
MapPerformance.javag8991g16809一g991新Map的g17907g5242。g1474g6925put( )方法，
g16765g4439g1820sort( )g1889插入，g9994g2530g1474g6925get( )，g16765g4439用
Collections.binarySearch( )来查询键。g1889g8616g17751一g991新g7099两个版g7424的
g17907g5242。
38,往CountedStringg18336面g2164入一个也是用g7512造g2001数进行g2033g3999g2282的char
成员，g1474g6925hashCode( )g2656equals( )方法，g16765g4439们把这个char也g2265
g6336进去。
39,g1474g6925SimpleHashMap，g16765g4439报告冲突，g9994g2530往g18336面g2164g18337g3809的对象，
并g1000观察冲突。
40,g1474g6925SimpleHashMap，g16765g4439报告需要g13475过几g8437g8991g16809才能g2469g10628冲突。
也就是说，为了g4559g6226相同的对象，g17953g2394LinkedList的时候要g16855用几g8437
Iterator的next( )。
41,g4466g10628SimpleHashMap的clear( )g2656remove( )方法。
42,g4466g10628SimpleHashMap的g1866g4439Map接g2487。
43,为SimpleHashMapg2164一个private rehash( )方法，当load factor
g17241过0.75的时候，就自动g16855用这个方法。rehash的时候，要g1820对
bucket的数量乘以二，g1889g6226出g12544一个g8616这个数大的质数，这个质数就是新的 bucket的数量了。
44,g2454照SimpleHashMap.java，创建一个SimpleHashSet，并进行g8991
g16809。
45,g1474g6925SimpleHashMap，g16765g4439g1363用ArrayList，而不是
LinkedList。g1474g6925MapPerformance.java，g16765g4439g8616g17751这两种g4466g10628的
g5627能。
46,查g19417JDK文g7735g1025HashMap的内g4493。创建一个HashMap，g16786定g1866
load factor，g1889用各种g1815g13044进行g3647g1817。g8991g16809一g991这个Map的查询g17907g5242。
Chapter 11,Collections of Objects
g12544 106 g20041 g1861 106 g20041 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com
g9994g2530创建一个新的HashMap，并g1000把g4439的initial capacityg2164大，g1889把相同的g1815g13044g2164入这个Map，g8991g16809一g991查询g17907g5242，看看是不是更g5567了。
47,g6226出g12544八g12468的GreenhouseController.java，g8892意，总g1861有g3247个文
g1226。Controller.java用了ArrayList，把g4439g6925成LinkedList，并g1000
用Iterator来处理事g1226。
48,(g6373战g13435) g1901一个你自己的，专为特定类型的键(g8616方说String)定g2058的
hashed map。不g16780继承Map。而g1000g17836要g16765put( )g2656get( )g6355String而不是Object当键。g10313涉到键的一切g6817g1328都不能g1363用泛型g727相反，g17836要
g16765g4439只g17878用于String，这样就能省g991上传g2656g991传的g5332g19156了。g11458标是要g1901
出g7380g5567的定g2058的g4466g10628。g1474g6925MapPerformance.java，g9994g2530进行g8991
g16809。
49,(g6373战g13435) Java的g2469布版g18336g5114着源g1207码。g6226到List的源g1207码，g6347g17137一份，g1889把g4439g6925g1901成专门保g4396int的intList。思g13783一g991，g3926果要g1901一个能保g4396所有primitive的List的g16817，需要g13783g15397g2750些问题。接g991来g1889想想，
要g1901一个能保g4396所有primitive数据的linked list的g16817，又要g13783g15397g2750些事情。
50,g1474g6925c08:Month.java，g16765g4439g4466g10628Comparable接g2487。
51,g1474g6925CountedString.java的hashCode( )，用id来g1207替乘法运g12651，
证g7138一g991，CountedString仍g9994能用g1328键。g1306是这种g1582法有什么问题g731