《Thinking in Java》中文版 第十一章 对象的集合

Thinking in Java 3Edition after sorting, a = Arrays asList(a))i }///:~ compare()方法会根据第一个参数是小于,等于还是大于第二个参 数,分别返回负整数,零或是正整数 数组的排序 有了内置的排序方法之后,你就能对任何数组排序了,不论是 primitive 的还是对象数组,只要它实现了 Comparable接口或有一个与之相关 的 Comparator对象就行了。这个功能填补了Java类库的一个大漏 洞。信不信由你,Java1.0和1.1连字符串的排序都没有。下面是一个 随机生成 String并对其排序的程序 //: c11: StringSorting java Sorting an array of strings import com. bruceeckel.util.*i import java.util.* public class stringSorting t public static void main(String[] args)i String [ sa new string[30]i Array fill(sa Arrays2. RandstringGenerator(5))i Syst Before sorting: " Arrays asList(sa))i Arrays. sort(sa)i System. out. println( After sorting:"+ Arrays. asList(sa) }///:~ 你可以从程序的输出看到,这个算法是按字典顺序进行排序的。就是把首 字母大写的单词放在前面,小写字母开头的放在后面。(电话簿就是这么 排的。)或许你想忽略大小写进行排序,那就自己定义一个 Comparator类吧,只要覆写默认的 String Comparable的行为就 可以了。考虑到将来的复用,我们把这个类放进了“utl” package: 77: com: bruceeckel: util: AlphabeticComparator java / Keeping upper and lowercase letters together package com. bruceeckelutili publ s Alphabeticcomparator implements Comparator public int compare(Object ol, object o2)I String sl =(String)oli String s2 =(string)o2; 第21页共106页 www.wgqqh.com/shhgs/tij.html

Thinking in Java 3rd Edition 第 21 页 共 106 页 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com "after sorting, a = " + Arrays.asList(a)); } } ///:~ compare( )方法会根据第一个参数是小于，等于还是大于第二个参 数，分别返回负整数，零或是正整数。 数组的排序 有了内置的排序方法之后，你就能对任何数组排序了，不论是 primitive 的还是对象数组，只要它实现了 Comparable 接口或有一个与之相关 的 Comparator 对象就行了。这个功能填补了 Java 类库的一个大漏 洞。信不信由你，Java1.0 和 1.1 连字符串的排序都没有。下面是一个 随机生成 String 并对其排序的程序： //: 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)); } } ///:~ 你可以从程序的输出看到，这个算法是按字典顺序进行排序的。就是把首 字母大写的单词放在前面，小写字母开头的放在后面。(电话簿就是这么 排的。)或许你想忽略大小写进行排序，那就自己定义一个 Comparator 类吧，只要覆写默认的 String Comparable 的行为就 可以了。考虑到将来的复用，我们把这个类放进了“util”package： //: 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 sl.tolowercaSe().compareto(s2.tolowercaSe())i 程序开头做了个类型转换,这样如果你传了个错误的类型,它就会抛出异 常。字符串会先被转换成小写,再进行比较。接下来用 String内置的 compareTo()方法进行比较。 下面就是 Alphabetic Comparator的测试代码: //:c11:A1 tissot Keeping upper and lowercase letters together import java.util.*i public class AlphabeticSorting t public static void main(String[] args)i String[ sa new String [30] Arrays2. fill(sa,new Arrays2. RandstringGenerator(5)) System. out. printin( Before sorting: Arrays asList(sa))i Arrays. sort(sa, new Alphabeticcomparator( ))i System. out. println( After sorting Arrays asList (sa)) }///:~ Java标准类库所用的排序算法已经作了优化——对 primitive,它用的是 “快速排序( Quicksort)”,对对象,它用的是“稳定合并排序( stable merge sort)”。所以除非是 roller表明排序算法是瓶颈,否则你不用 为性能担心 查询有序数组 一旦数组排完序,你就能用 Arrays binary Search()进行快速查询 了。但是切忌对一个尚未排序的数组使用 binary Search():因为这么 做的结果是没意义的。接下来,我们用 RandIntGenerator来填数 组,然后用同一个 generator生成一个随机数,再在数组里面找这个数 //: c11: Arraysearching java Using Arrays. b Search() import com. bruceeckel.util.*i import java.util.* public class ArraySearching i 第22页共106页 www.wgqqh.com/shhgs/tij.html emailshhgsasohu.com

Chapter 11: Collections of Objects 第 22 页 共 106 页 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com return s1.toLowerCase( ).compareTo(s2.toLowerCase( )); } } ///:~ 程序开头做了个类型转换，这样如果你传了个错误的类型，它就会抛出异 常。字符串会先被转换成小写，再进行比较。接下来用 String 内置的 compareTo( )方法进行比较。 下面就是 AlphabeticComparator 的测试代码： //: 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 标准类库所用的排序算法已经作了优化——对 primitive，它用的是 “快速排序(Quicksort)”，对对象，它用的是“稳定合并排序(stable merge sort)”。所以除非是 prolier 表明排序算法是瓶颈，否则你不用 为性能担心。 查询有序数组 一旦数组排完序，你就能用 Arrays.binarySearch( )进行快速查询 了。但是切忌对一个尚未排序的数组使用 binarySearch( )；因为这么 做的结果是没意义的。接下来，我们用 RandIntGenerator 来填数 组，然后用同一个 generator 生成一个随机数，再在数组里面找这个数 字： //: c11:ArraySearching.java // Using Arrays.binarySearch( ). import com.bruceeckel.util.*; import java.util.*; public class ArraySearching {

Thinking in Java 3Edition public static void main(String[] args)i nt[ new int[100] Arrays2. RandIntGenerator gen Arr yo rays2. RandIntGenerator(1000) new A Ar lys. sort(a) System. out. println( Sorted array Arrays tostring(a))i while(true)[ t gen next( )i int location Arrays binarysearch(a, r)i if(location > System. out. println("Location of"+ location +" a["+ location += a[location]) }///:~ while循环会不断地生成随机数,直到它找到为止。 如果 Arrays binary search()找到了,它就返回一个大于或等于0 的值。否则它就返回一个负值,而这个负值要表达的意思是,如果你手动 维护这个数组的话,这个值应该插在哪个位置。这个值就是: “插入点”就是,在所有“比要找的那个值”更大值中,最小的那个值 的下标,或者,如果数组中所有的值都比要找的值小,它就是 asize 如果数组里面有重复元素,那它不能保证会返回哪一个。这个算法不支持 重复元素,不过它也不报错。所以,如果你需要的是一个无重复元素的有 序序列的话,那么可以考虑使用本章后面所介绍的 Treeset(支持「排序 顺序“ sorted order”J)和 LinkedHash set(支持「插入顺序 sorted order”」)。这两个类会帮你照看所有细节。只有在遇到性能 瓶颈的时候,你才应该用手动维护的数组来代替这两个类。 如果排序的时候用到了 Comparator(针对对象数组, primitive数组 不允许使用 Comparator),那么 binary search()的时候,也必须 使用同一个 Comparator(用这个方法的重载版)。比方说,我们修改了 AlphabeticSorting java //: c11: AlphabeticSearch. java / Searching with a Comparator 第23页共106页 www.wgqqh.com/shhgs/tij.html emailshhgsasohu.com

Thinking in Java 3rd Edition 第 23 页 共 106 页 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 } } } } ///:~ while 循环会不断地生成随机数，直到它找到为止。 如果 Arrays.binarySearch( )找到了，它就返回一个大于或等于 0 的值。否则它就返回一个负值，而这个负值要表达的意思是，如果你手动 维护这个数组的话，这个值应该插在哪个位置。这个值就是： -(插入点)-1 “插入点”就是，在所有“比要找的那个值”更大值中，最小的那个值 的下标，或者，如果数组中所有的值都比要找的值小，它就是 a.size( )。 如果数组里面有重复元素，那它不能保证会返回哪一个。这个算法不支持 重复元素，不过它也不报错。所以，如果你需要的是一个无重复元素的有 序序列的话，那么可以考虑使用本章后面所介绍的 TreeSet(支持『排序 顺序“sorted order”』)和 LinkedHashSet(支持『插入顺序 “sorted order”』)。这两个类会帮你照看所有细节。只有在遇到性能 瓶颈的时候，你才应该用手动维护的数组来代替这两个类。 如果排序的时候用到了 Comparator (针对对象数组，primitive 数组 不允许使用 Comparator)，那么 binarySearch( )的时候，也必须 使用同一个 Comparator (用这个方法的重载版)。比方说，我们修改了 AlphabeticSorting.java： //: c11:AlphabeticSearch.java // Searching with a Comparator

Chapter 11: Collections of Objects import com. bruceeckel. simpletest* import com. bruceeckel.util.*i import java.util.*i public class AlphabeticSearch t private static Test monitor new Test( public static void main(String[] args) i String [] sa new tring [30]i Arrays2. fill(sa,new Arrays2. RandstringGenerator(5))i AlphabeticComparator comp =new AlphabeticComparator( t(sa, comp) int index Arrays binarySearch(sa, sa[10], System. out. println("Index monitor.expect(new String[] t }///:~ 必须把 Comparator当作 binaraysearch()的第三个参数传给它 在这个例子里,由于要找的东西是从数组里面挑的,因此肯定能找到 数组部分的总结 总而言之,如果你要持有一组对象,首选,同时也是效率最高的选择,应 该是数组。而且,如果这是一组 primitive的话,你也只能用数组。接下 来,我们要讲一些更为一般的情况,也就是写程序的时候还不知道要用多 少对象,或者要用一种更复杂方式来存储对象情况。为此,]ava提供了 “容器类( container class)”。其基本类型有List,Set和Map。有了 这些工具,你就能解决很多问题了 它们还有一些别的特性。比方说Set所持有的对象,个个都不同,Map 则是一个“关联性数组( associative array)”,它能在两个对象之间建 立联系。此外,与数组不同,它们还能自动调整大小,所以你可以往里面 放任意数量的对象。这样写程序的时候,就不用操心要开多大的空间了 容器简介 就我个人的感受,容器类能极大地増强我的编程能力,是软件开发领域最 得力的工具之一。Java2的重新设计了1.0和1.1里面那个表现差劲的 容器类。新的设计更紧凑也更合理。同时它也补齐了容器类库的功能,提 供了链表( linked list)、队列( queue)和双向队列( deques,读成 “ decks”)这几种数据结构的功能。 3由Sun的 Joshua bloch负责设计 第24页共106页 www.wgqqh.com/shhgs/tij.html emailshhgsasohu.com

Chapter 11: Collections of Objects 第 24 页 共 106 页 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" }); } } ///:~ 必须把 Comparator 当作 binaraySearch( )的第三个参数传给它。 在这个例子里，由于要找的东西是从数组里面挑的，因此肯定能找到。 数组部分的总结 总而言之，如果你要持有一组对象，首选，同时也是效率最高的选择，应 该是数组。而且，如果这是一组 primitive 的话，你也只能用数组。接下 来，我们要讲一些更为一般的情况，也就是写程序的时候还不知道要用多 少对象，或者要用一种更复杂方式来存储对象情况。为此，Java 提供了 “容器类(container class)”。其基本类型有 List, Set 和 Map。有了 这些工具，你就能解决很多问题了。 它们还有一些别的特性。比方说 Set 所持有的对象，个个都不同，Map 则是一个“关联性数组(associative array)”，它能在两个对象之间建 立联系。此外，与数组不同，它们还能自动调整大小，所以你可以往里面 放任意数量的对象。这样写程序的时候，就不用操心要开多大的空间了。 容器简介 就我个人的感受，容器类能极大地增强我的编程能力，是软件开发领域最 得力的工具之一。Java2 的重新设计5了 1.0 和 1.1 里面那个表现差劲的 容器类。新的设计更紧凑也更合理。同时它也补齐了容器类库的功能，提 供了链表(linked list)、队列(queue)和双向队列(deques，读成 “decks”)这几种数据结构的功能。 5由 Sun 的 Joshua Bloch 负责设计

Thinking in Java 3Edition 要设计容器类库是很难的(对绝大多数类库,设计总是很难的)。C++的 容器类库里包括了很多各色各样的类。相比原先什么都没有,这种设计当 然好出不少,但是它并不适合Java。也有走另一个极端的。我就曾看到 过一个只包括“ container”类的容器类库。它的工作方式既象线性序 列,又象关联性数组。Java2的容器类库则取了个折中:它实现了“成 熟的容器类库所应实现”的一切功能,同时它又比C++或其它类似的容 器类库更易学易用。所以这个类库可能会有些怪。不像早期的Java类 库,这些怪异之处并不是什么设计缺陷,相反它是在仔细斟酌了各种复杂 因素之后才作的决定。或许你得花一点时间来熟悉这个类库,但是我相 信,你很快就会学会容器类,然后把它们派上用场。 Java2的容器类要解决“怎样持有对象”,而它把这个问题分成两类 1. Collection:通常是一组有一定规律的独立元素。Iist必须按照特定的 顺序持有这些元素,而Set则不能保存重复的元素。(bag没有这个限 制,但是Java的容器类库没有实现它,因为Iist已经提供这种功能 Map:一组以“键——值”(key- value)形式出现的pair。初看上去,它 应该是一个pair的 Collection,但是真这么去做的话,它就会变得很 滑稽,所以还是把这个概念独立列出来为好。退一步说,真的要用到 Map的某个子集的时候,创建一个 Collection也是很方便的。Map 可以返回“键(key)的”Set,值的 Collection,或者pair的Set。和数 组一样,Map不需要什么修改,就能很容易地扩展成多维。你只要直接 把Map的值设成Map就可以了(然后它的值再是Map,以此类推)。 我们先来看看容器的一般特性,然后深入细节,最后再看为什么会有这么 多版本,以及如何进行选择。 打印容器 不像数组,容器不需要借助别的类就能清清楚楚地把自己给打印出来。下 面这个例子还介绍了几种基本的容器: //: c11: PrintingContainers java Containers print themselves automatically import com. bruceeckel. simpletest. ublic class Printing containers i Test() (Col return c Map fill( 第25页共106页 www.wgqqh.com/shhgs/tij.html

Thinking in Java 3rd Edition 第 25 页 共 106 页 www.wgqqh.com/shhgs/tij.html email:shhgs@sohu.com 要设计容器类库是很难的(对绝大多数类库，设计总是很难的)。C++的 容器类库里包括了很多各色各样的类。相比原先什么都没有，这种设计当 然好出不少，但是它并不适合 Java。也有走另一个极端的。我就曾看到 过一个只包括“container”类的容器类库。它的工作方式既象线性序 列，又象关联性数组。Java 2 的容器类库则取了个折中：它实现了“成 熟的容器类库所应实现”的一切功能，同时它又比 C++或其它类似的容 器类库更易学易用。所以这个类库可能会有些怪。不像早期的 Java 类 库，这些怪异之处并不是什么设计缺陷，相反它是在仔细斟酌了各种复杂 因素之后才作的决定。或许你得花一点时间来熟悉这个类库，但是我相 信，你很快就会学会容器类，然后把它们派上用场。 Java2 的容器类要解决“怎样持有对象”，而它把这个问题分成两类： 1. Collection: 通常是一组有一定规律的独立元素。List 必须按照特定的 顺序持有这些元素，而 Set 则不能保存重复的元素。(bag 没有这个限 制，但是 Java 的容器类库没有实现它，因为 List 已经提供这种功能 了。) 2. Map: 一组以“键——值”(key-value)形式出现的 pair。初看上去，它 应该是一个 pair 的 Collection，但是真这么去做的话，它就会变得很 滑稽，所以还是把这个概念独立列出来为好。退一步说，真的要用到 Map 的某个子集的时候，创建一个 Collection 也是很方便的。Map 可以返回“键(key)的”Set，值的 Collection，或者 pair 的 Set。和数 组一样，Map 不需要什么修改，就能很容易地扩展成多维。你只要直接 把 Map 的值设成 Map 就可以了(然后它的值再是 Map，以此类推)。 我们先来看看容器的一般特性，然后深入细节，最后再看为什么会有这么 多版本，以及如何进行选择。 打印容器 不像数组，容器不需要借助别的类就能清清楚楚地把自己给打印出来。下 面这个例子还介绍了几种基本的容器： //: 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");