Java编程思想第4版[中文版](PDF格式)-第63部分

快捷操作: 按键盘上方向键 ← 或 → 可快速上下翻页 按键盘上的 Enter 键可回到本书目录页 按键盘上方向键 ↑ 可回到本页顶部! 如果本书没有阅读完，想下次继续接着阅读，可使用上方 "收藏到我的浏览器" 功能 和 "加入书签" 功能！


为理解这个问题，必须认识到每种不同的实施方案都有自己的特点、优点和缺点。比如在那张示意图中，可　

以看到Hashtable，Vector　和Stack　的“特点”是它们都属于“传统”类，所以不会干扰原有的代码。但在　

另一方面，应尽量避免为新的（Java　1。2　）代码使用它们。　　

其他集合间的差异通常都可归纳为它们具体是由什么“后推”的。换言之，取决于物理意义上用于实施目标　

接口的数据结构是什么。例如，ArrayList，LinkedList　以及Vector　（大致等价于ArrayList）都实现了　

List　接口，所以无论选用哪一个，我们的程序都会得到类似的结果。然而，ArrayList　（以及Vector）是由　

一个数组后推得到的；而LinkedList　是根据常规的双重链接列表方式实现的，因为每个单独的对象都包含了　

数据以及指向列表内前后元素的句柄。正是由于这个原因，假如想在一个列表中部进行大量插入和删除操　

作，那么LinkedList　无疑是最恰当的选择（LinkedList　还有一些额外的功能，建立于　

AbstractSequentialList　中）。若非如此，就情愿选择ArrayList　，它的速度可能要快一些。　　

作为另一个例子，Set　既可作为一个ArraySet　实现，亦可作为HashSet　实现。ArraySet　是由一个ArrayList　

后推得到的，设计成只支持少量元素，特别适合要求创建和删除大量　Set　对象的场合使用。然而，一旦需要　

在自己的Set　中容纳大量元素，ArraySet　的性能就会大打折扣。写一个需要　Set　的程序时，应默认选择　

HashSet。而且只有在某些特殊情况下（对性能的提升有迫切的需求），才应切换到ArraySet　。　　

　　

1。　决定使用何种List　　

为体会各种　List　实施方案间的差异，最简便的方法就是进行一次性能测验。下述代码的作用是建立一个内部　

基础类，将其作为一个测试床使用。然后为每次测验都创建一个匿名内部类。每个这样的内部类都由一个　

test（）方法调用。利用这种方法，可以方便添加和删除测试项目。　　

　　

//：　ListPerformance。java　　

//　Demonstrates　performance　differences　in　Lists　　

package　c08。newcollections；　　

import　java。util。*；　　

　　

public　class　ListPerformance　｛　　

　　private　static　final　int　REPS　=　100；　　

　　private　abstract　static　class　Tester　｛　　

　　　　String　name；　　

　　　　int　size；　//　Test　quantity　　

　　　　Tester（String　name；　int　size）　｛　　　

　　　　　　this。name　=　name；　　

　　　　　　this。size　=　size；　　

　　　　｝　　

　　　　abstract　void　test（List　a）；　　

　　｝　　

　　private　static　Tester＇＇　tests　=　｛　　

　　　　new　Tester（〃get〃；　300）　｛　　　

　　　　　　void　test（List　a）　｛　　

　　　　　　　　for（int　i　=　0；　i　《　REPS；　i＋＋）　｛　　

　　　　　　　　　　for（int　j　=　0；　j　《　a。size（）；　j＋＋）　　

　　　　　　　　　　　　a。get（j）；　　

　　　　　　　　｝　　

　　　　　　｝　　

　　　　｝；　　



　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　247　


…………………………………………………………Page　249……………………………………………………………

　　　　new　Tester（〃iteration〃；　300）　｛　　　

　　　　　　void　test（List　a）　｛　　

　　　　　　　　for（int　i　=　0；　i　《　REPS；　i＋＋）　｛　　

　　　　　　　　　　Iterator　it　=　a。iterator（）；　　

　　　　　　　　　　while（it。hasNext（））　　

　　　　　　　　　　　　it。next（）；　　

　　　　　　　　｝　　

　　　　　　｝　　

　　　　｝；　　

　　　　new　Tester（〃insert〃；　1000）　｛　　　

　　　　　　void　test（List　a）　｛　　

　　　　　　　　int　half　=　a。size（）/2；　　

　　　　　　　　String　s　=　〃test〃；　　

　　　　　　　　ListIterator　it　=　a。listIterator（half）；　　

　　　　　　　　for（int　i　=　0；　i　《　size　*　10；　i＋＋）　　

　　　　　　　　　　it。add（s）；　　

　　　　　　｝　　

　　　　｝；　　

　　　　new　Tester（〃remove〃；　5000）　｛　　　

　　　　　　void　test（List　a）　｛　　

　　　　　　　　ListIterator　it　=　a。listIterator（3）；　　

　　　　　　　　while（it。hasNext（））　｛　　

　　　　　　　　　　it。next（）；　　

　　　　　　　　　　it。remove（）；　　

　　　　　　　　｝　　

　　　　　　｝　　

　　　　｝；　　

　　｝；　　

　　public　static　void　test（List　a）　｛　　

　　　　//　A　trick　to　print　out　the　class　name：　　

　　　　System。out。println（〃Testing　〃　＋　　　

　　　　　　a。getClass（）。getName（））；　　

　　　　for（int　i　=　0；　i　《　tests。length；　i＋＋）　｛　　

　　　　　　Collection1。fill（a；　tests＇i＇。size）；　　

　　　　　　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）　｛　　

　　　　test（new　ArrayList（））；　　

　　　　test（new　LinkedList（））；　　

　　｝　　

｝　///：~　　

　　

内部类Tester　是一个抽象类，用于为特定的测试提供一个基础类。它包含了一个要在测试开始时打印的字　

串、一个用于计算测试次数或元素数量的size　参数、用于初始化字段的一个构建器以及一个抽象方法　

test（）。test（）做的是最实际的测试工作。各种类型的测试都集中到一个地方：tests　数组。我们用继承于　

Tester　的不同匿名内部类来初始化该数组。为添加或删除一个测试项目，只需在数组里简单地添加或移去一　

个内部类定义即可，其他所有工作都是自动进行的。　　



　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　248　


…………………………………………………………Page　250……………………………………………………………

首先用元素填充传递给　test（）的List，然后对tests　数组中的测试计时。由于测试用机器的不同，结果当然　

也会有所区别。这个程序的宗旨是揭示出不同集合类型的相对性能比较。下面是某一次运行得到的结果：　　

　　

　　



Type　　　　　　　Get　　Iteration　Insert　Remove　　



ArrayList　110　　490　　　　　　　　3790　　　8730　　



LinkedList　1980　220　　　　　　　110　　　　110　　



　　

可以看出，在ArrayList　中进行随机访问（即get（））以及循环反复是最划得来的；但对于LinkedList　却是　

一个不小的开销。但另一方面，在列表中部进行插入和删除操作对于　LinkedList　来说却比ArrayList　划算得　

多。我们最好的做法也许是先选择一个ArrayList　作为自己的默认起点。以后若发现由于大量的插入和删除　

造成了性能的降低，再考虑换成LinkedList　不迟。　　

　　

2。　决定使用何种　Set　　

可在ArraySet　以及HashSet　间作出选择，具体取决于Set　的大小（如果需要从一个Set　中获得一个顺序列　

表，请用TreeSet；注释⑧）。下面这个测试程序将有助于大家作出这方面的抉择：　　

　　

//：　SetPerformance。java　　

package　c08。newcollections；　　

import　java。util。*；　　

　　

public　class　SetPerformance　｛　　

　　private　static　final　int　REPS　=　200；　　

　　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（）；　　

　　　　　　　　　　Collection1。fill（s；　size）；　　

　　　　　　　　｝　　

　　　　　　｝　　

　　　　｝；　　

　　　　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（）；　　

　　　　　　　　｝　　



　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　249　


…………………………………………………………Page　251……………………………………………………………

　　　　　　｝　　

　　　　｝；　　

　　｝；　　

　　public　static　void　test（Set　s；　int　size）　｛　　

　　　　//　A　trick　to　print　out　the　class　name：　　

　　　　System。out。println（〃Testing　〃　＋　　　

　　　　　　s。getClass（）。getName（）　＋　〃　size　〃　＋　size）；　　

　　　　Collection1。fill（s；　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）　｛　　

　　　　//　Small：　　

　　　　test（new　TreeSet（）；　10）；　　

　　　　test（new　HashSet（）；　10）；　　

　　　　//　Medium：　　

　　　　test（new　TreeSet（）；　100）；　　

　　　　test（new　HashSet（）；　100）；　　

　　　　//　Large：　　

　　　　test（new　HashSet（）；　1000）；　　

　　　　test（new　TreeSet（）；　1000）；　　

　　｝　　

｝　///：~　　

　　

⑧：TreeSet　在本书写作时尚未成为一个正式的特性，但在这个例子中可以很轻松地为其添加一个测试。　　

　　

最后对ArraySet　的测试只有500　个元素，而不是　1000　个，因为它太慢了。　　

　　

类型　测试大小　添加　包含　反复　　

　　

　　



Type　　　　Test　size　Add　　Contains　Iteration　　



　　　　　　　　10　　　　　　　　22。0　11。0　　　　　16。0　　



TreeSet　100　　　　　　　22。5　13。2　　　　　12。1　　



　　　　　　　　1000　　　　　　31。1　18。7　　　　　11。8　　



　　　　　　　　10　　　　　　　　5。0　　6。0　　　　　　27。0　　



HashSet　100　　　　　　　6。6　　6。6　　　　　　10。9　　



　　　　　　　　1000　　　　　　7。4　　6。6　　　　　　9。5　　



　　

　　

进行add（）以及contains（）操作时，HashSet　显然要比ArraySet　出色得多，而且性能明显与元素的多寡关系　

不大。一般编写程序的时候，几乎永远用不着使用　ArraySet　。　　

　　

3。　决定使用何种Map　　



　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　250　


…………………………………………………………Page　252……………………………………………………………

选择不同的　Map　实施方案时，注意　Map　的大小对于性能的影响是最大的，下面这个测试程序清楚地阐示了这　

一点：　　

　　

//：　MapPerformance。java　　

//　Demonstrates　performance　differences　in　Maps　　

package　c08。newcollections；　　

import　java。util。*；　　

　　

public　class　MapPerformance　｛　　

　　private　static　final　int　REPS　=　200；　　

　　public　static　Map　fill（Map　m；　int　size）　｛　　

　　　　for（int　i　=　0；　i　《　size；　i＋＋）　｛　　

　　　　　　String　x　=　Integer。toString（i）；　　

　　　　　　m。put（x；　x）；　　

　　　　｝　　

　　　　return　m；　　

　　｝　　

　　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（）；　　

　　　　　　　　　　fill（m；　size）；　　

　　　　　　　　｝　　

　　　　　　｝　　

　　　　｝；　　

　　　　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。entries（）。iterator（）；　　

　　　　　　　　　　while（it。hasNext（））　　

　　　　　　　　　　　　it。next（）；　　

　　　　　　　　｝　　

　　　　　　｝　　

　　　　｝；　　

　　｝；　　

　　public　static　void　test（Map　m；　int　size）　｛　　

　　　　//　A　trick　to　print　out　the　class　name：　　

　　　　System。out。println（〃Testing　〃　＋　　　

　　　　　　m。getClass（）。getName（）　＋　〃　size　〃　＋　size）；　　



　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　　251　


…………………………………………………………Page　253……………………………………………………………

　　　　fill（m；　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）　｛　　

　　　　//　Small：　　

　　　　test（new　Hashtable（）；　10）；　　

　　　　test（new　HashMap（）；　10）；　　

　　　　test（new　TreeMap（）；　10）；　　

　　　　//　Medium：　　

　　　　test（new　Hashtable（）；　100）；　　

　　　　test（new　HashMap（）；　100）；　　

　　　　test（new　TreeMap（）；　100）；　　

　　　　//　Large：　　

　　　　test（new　HashMap（）；　1000）；　　

　　　　test（new　Hashtable（）；　1000）；　　

　　　　test（new　TreeMap（）；　1000）；　　

　　｝　　

｝　///：~　　

　　

由于Map　的大小是最严重的问题，所以程序的计时测试按Map　的大小（或容量）来分割时间，