java容器类-1【Z】

 对象的集合
如果程序的对象数量有限，且寿命可知，那么这个程序是相当简单的。

数组
数组与其它容器的区别体现在三个方面：效率，类型识别以及可以持有 primitives。数组是Java提供的，能随机存储和访问reference序列的诸多方法中的，最高效的一种。数组是一个简单的线性序列，所有它 可以快速的访问其中的元素。但是速度是有代价的；当你创建了一个数组之后，它的容量就固定了，而且在其生命周期里不能改变。也许你会提议先创建一个数组， 等到快不够用的时候，再创建一个新的，然后将旧的数组里的reference全部导到新的里面。其实（我们以后会讲的）ArrayList就是这么做的。 但是这种灵活性所带来的开销，使得ArrayList的效率比起数组有了明显下降。
Java对数组和容器都做边界检查；如果过了界，它旧会给一个RuntimeException。这种异常表明这个错误是由程序员造成的，这样你就用不着再在程序里面检查了。
还 有一些泛型容器类包括List，Set和Map。他们处理对象的时候就好像这些对象都没有自己的具体类型一样。也就是说，容器将它所含的元素都看成是 （Java中所有类的根类）Object的。这样你只需要建一种容器，就能把所有类型的对象全都放进去。从这个角度来看，这种做法很不错（只是苦了 primitive。如果是常量，你还可以用Java的primitive的Wrapper类；如果是变量，那就只能放在你自己的类里了）。与其他泛型容 器相比，这里体现数组的第二革优势：创建数组的时候，你也同时指明了它所持有的对象的类型（这又引出了第三点－－数组可以持有primitives，而容 器却不行）。也就是说，它会在编译的时候作类型检查，从而防止你插入错误类型的对象，或者是在提取对象的时候把对象的类型给搞错了。Java在编译和运行 时都能阻止你将一个不恰当的消息传给对象。所有这并不是说使用容器就有什么危险，只是如果编译器能够帮你指定，那么程序运行会更快，最终用户也会较少收到 程序运行异常的骚扰。
从效率和类型检查的角度来看，使用数组总是没错的。但是，如果你在解决一个更为一般的问题，那数组就会显得功能太弱了点。

数组是第一流的对象
不管你用的是那种类型的数组，数组的标识符实际上都是一个“创建在堆（heap）里的实实在在的对象的”reference。实际上是那 个对象持有其他对象的reference。你即可以用数组的初始化语句，隐含地创建这个对象，也可以用new表达式，明确地创建这个对象，只读的 length属性能告诉你数组能存储多少元素。它是数组对象的一部分（实际上也是你唯一能访问的属性或方法）。‘[]’语法是另一条访问数组对象的途径。
你 没法知道数组里面究竟放了多少元素，因为length只是告诉你数组能放多少元素，也就是说是数组对象的容量，而不是它真正已经持有的元素的数量。但是， 创建数组对象的时候，它所持有的reference都会被自动地初始化为null，所以你可以通过检查数组的某个“槽位”是否为null，来判断它是否持 有对象。以此类推，primitive的数组，会自动来数字初始化为零，字符初始化为(char)0，boolean初始化为false。

primitive容器
容器类只能持有Object对象的 reference。而数组除了能持有Objects的reference之外，还可以直接持有primitive。当然可以使用诸如 Integer，Double之类的wrapper类。把primitive的值放到容器中，淡这样总有点怪怪的。此外， primitive数组的效率要比wrapper类容器的高出许多。
当然，如果你使用primitive的时候，还需要那种“能随需要自动扩展的”容器类的灵活性，那就不能用数组了。你只能用容器来存储primitive的wrapper类。

返回一个数组
假设你写了一个方法，它返回的不是一个而是一组东西。那么在Java中就可以返回的“就是一个数组”。与C++不同，你永远也不必为Java的数组操心－－只要你还需要它，它就还在；一旦你用完了，垃圾回收器会帮你把它打扫干净。

Arrays类
java.util里面有一个Arrays类，它包括了一组 可用于数组的static方法，这些方法都是一些实用工具。其中有四个基本方法：用来比较两个数组是否相等的equals()；用来填充的fill()； 用来对数组进行排序的sort()；以及用于在一个已排序的数组中查找元素的 binarySearch()。所有这些方法都对primitive和Object进行了重载。此外还有一个asList()方法，它接受一个数组，然后 把它转成一个List容器。
虽然Arrays还是有用的，但它的功能并不完整。举例来说，如果它能让我们不用写for循环就能直接打印数组，那就好了。此外，正如你所看到的fill()只能用一个值填数组。所以，如果你想把随即生成的数字填进数组的话，fill()是无能为力的。

复制一个数组
Java标准类库提供了一个System.arraycopy()的static方法。相比for循环，它能以更快的速度拷贝数组。System.arraycopy()对所有类型都作了重载。
对象数组和primitive数组都能拷贝。但是如果你拷贝的是对象数组，那么你只拷贝了它们的reference－－对象本身不会被拷贝。这被成为浅拷贝（shallow copy）。

数组的比较
为了能比较数组是否完全相等，Arrays提供了经重载的 equals()方法。当然，也是针对各种primitive以及Object的。两个数组要想完全相等，他们必须有相同数量的元素，而且数组的每个元素 必须与另一个数组的相对应的位置上的元素相等。元素的相等姓，用equals()判断。（对于 primitive，它会使用其wrapper类的equals()；比如int使用Integer.equals()。）。

数组元素的比较
Java里面有两种能让你实现比较功能的方法。一是实现 java.lang.Comparable接口，并以此实现类“自有的”比较方法。这是一个很简单的接口，它只有一个方法compareTo()。这个方 法能接受另一个对象作为参数，如果现有对象比参数小，它就会返回一个负数，如果相同则返回零，如果现有的对象比参数大，它就返回一个正数。
static randInt()方法会生成一个介于0到100之间的正数。
现 在架设，有人给你一个没有实现Comparable接口的类，或者这个类实现了Comparable接口，但是你发现它的工作方式不是你所希望的，于是要 重新定义一个新的比较方法。Java没有强求你一定要把比较代码塞进类里，它的解决方案是使用“策略模式（strategy design pattern）”。有了策略之后，你就能把会变的代码封装到它自己的类里（即所谓的策略对象strategy object）。你把策略对象交给不会变的代码，然后用它运用策略完成整个算法。这样，你就可以用不同的策略对象来表示不同的比较方法，然后把它们都交给 同一个排序程序了。接下来就要“通过实现Comparator接口”来定义策略对象了。这个接口有两个方法compare()和equals()。但是除 非是有特殊的性能要求，否则你用不着去实现equals()。因为只要是类，它就都隐含地继承自Object，而Object里面已经有了一个 equals()了。所以你尽可以使用缺省的Object的equals()，这样就已经满足接口的要求了。
Collections类里专门有一个会返回与对象自有的比较法相反的Comparator的方法。它能很轻易地被用到CompType上面。
Collections.reverseOrder()返回了一个Comparator的reference。
compare()方法会根据第一个参数是小于，等于还是大于第二个参数，分别返回负整数，零或是正整数。

数组的排序
有了内置的排序方法之后，你就能对任何数组排序了，不论是primitive的还是对象数组的，只要它实现了Comparable接口或有一个与之相关的Comparator对象就行了。
Java标准类库所用的排序算法已经作了优化－－对primitive，它用的是“快速排序（Quicksort）”，对对象，它用的是“稳定合并排序（stable merge sort）”。所以除非是prolier表明排序算法是瓶颈，否则你不用为性能担心。

查询有序数组
一旦数组排完序，你就能用Arrays.binarySearch()进行快速查询了。但是切忌对一个尚未排序的数组使用binarySearch()；因为这么做的结果是没意义的。
如果Arrays.binarySearch()找到了，它就返回一个大于或等于0的值。否则它就返回一个负值，而这个负值要表达的意思是，如果你手动维护这个数组的话，这个值应该插在哪个为止。这个值就是：
-(插入点)-1
“插入点”就是，在所有“比要找的那个值”更大值中，最小的那个值的下标，或者，如果数组中所有的值都比要找的值小，它就是a.size()。
如 果数组里面有重复元素，那它不能保证会返回哪一个。这个算法不支持重复元素，不过它也不报错。所以，如果你需要的是一个无重复元素的有序序列的话，那么可 以考虑使用本章后面所介绍的TreeSet（支持【排序顺序“sorted order”】）和LinkedHashSet（支持【插入顺序“sorted order”】）。这两个类会帮你照看所有细节。只有在遇到性能瓶颈的时候，你才应该用手动维护的数组来代替这两个类。
如果排序的时候用到了Comparator（针对对象数组，primitive数组不允许使用Comparator），那么binarySearch()的时候，也必须使用同一个Comparator（用这个方法的重载版）。

数组部分的总结
总而言之，如果你要持有一组对象，首选，同时也是效率最高的选择，应该是数组。而且，如果这是一组primitive的话，你也只能用数 组。还有一些更为一般的情况，也就是写程序的时候还不知道要用多少对象，或者要用一种更复杂方式来存储对象情况。为此，Java提供了“容器类 （container class）”。其基本类型有List，Set和Map。
它们还有一些别的特性。比方说Set所持有的对象，个个都不同，Map则是一个“关联性数组（associative array）”，它能在两个对象之间建立联系。此外，与数组不同，它们还能自动调整大小，所以你可以往里面放任意数量的对象。

容器简介
Java2的重新设计了1.0和1.1里面那个表现差劲的容器类。新的设计更紧凑也更合理。同时它也补齐了容器类库的功能，提供了链表（linked list），队列（queue）和双向队列（deques，读成“decks”）这几种数据结构的功能。
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，依此类推）。
Java的容器类分成两种基本类型。它们的区别就在，每个位 置能放多少对象。Collection只允许每个位置上放一个对象（这个名字有点误导，因为容器类库也常被统称为collections）。它包括“以一 定顺序持有一组对象”的List，以及“只能允许添加不重复的对象”的Set。 ArrayList是一种List，而HashSet则是一种Set。你可以用add()方法往Collection里面加对象。
Map保存的是“键（key）－－值”形式的pair，很像是一个微型数据库。
Map又被称为关联性数组（associative array）。你可以用put()方法往Map里面加元素。它接受键－－值形式pair作参数。
fill()方法还为Collection和Map作了重载。输出在默认情况下使用容器类的toString()方法。打印出来的Collection会用方括号括起来，元素与元素之间用逗号分开。Map会用花括号括起来，键和值之间用等号联起来（键在左边，值在右边）。
List 会老老实实地持有你所输入的所有对象，既不做排序也不做编辑。Set则每个对象只接受一次，而且还要用它自己的规则对元素进行重新排序（一般情况下，你关 心的只是Set包没包括某个对象，而不是它到底排在哪里－－如果是那样，你最好还是用List）。而Map也不接收重复的pair，至于是不是重复，要由 key来决定。此外，它也有它自己的内部排序规则，不会受输入顺序影响。如果插入顺序是很重要的，那你就只能使用LinkedHashSet或 LinkedHashMap了。

填充容器
和Arrays一样，Collection也有一个叫Collections的辅助类，它包含了一些静态的实用工具方法，其中 就有一个fill()。这个 fill()也只是把同一个对象的reference复制到整个容器，而且它还只能为List，不能为Set和Map工作。

容器的缺点：不知道对象的类型
Java的容器有个缺点，就是往容器里面放对象的时候，会把对象的类型信息给弄丢了。这是因为开发容器类 的程序员不会知道你要用它来保存什么类型的对象，而让容器仅只保存特定类型的对象又会影响它的通用性。所以容器被做成只有持有Object，也就是所有对 象的根类的reference，这样它就能持有任何类型的对象了。（当然不包括primitive，因为它们不是对象，也没有继承别的对象。）这是一个很 了不起的方案，只是：
1，由于在将对象放入容器的时候，它的类型信息被扔掉了，所以容器对“能往里面加什么类型的对象”没有限制。比方说，即使你想让它只持有cat，别人也能很轻易地把dog放进去。
2，由于对象的类型信息没了，容器只知道它持有的Object的reference，所以对象在使用之前还必须进行类型转换。
好 的一面是，Java不会让你误用放进容器里的对象。假设你往cat的容器里面扔了个dog，然后要把这个容器里的所有对象都当cat来用，当你把dog 的reference从cat的容器里面拉出来，并且试图将它转换成cat的时候，就会引发一个RuntimeException。
ArrayList 的用法也是很简单：先创建一个，用add()把对象放进去，要用的时候再给get()传一个下标－－就跟用数组差不多，只是不需要用方括号了。 ArrayList也有一个size()方法，它会告诉你容器里面有多少对象，这样你就不会粗心大意地过了界然后引发异常了。

有时即使不正确它也能运行
有时，即使不把对象转换成原先的类型，它好像也能正常工作。有一种情况比较特殊：String能从编译器哪里 得到一些能使之平稳工作的特殊帮助。只要编译器没能得到它所期望的String对象，它就会调用toString()。这个方法油Object定义，能被 任何Java类覆写。它所返回的String 对象，会被用到任何要用它的地方。
于是只要覆写了类的toString()方法，你就能打印对象了。

做一个类型敏感的ArrayList

参数化类型（Parameterized types）

迭代器
无论是哪种容器，你都得有办法既能放东西进去，也能拿东西出来。毕竟，容器的主要任务就是存放对象。ArrayList的 add()就是用来放东西的，而 get()则是把对象拿出来的办法。ArrayList恨灵活；你可以随时提取任何东西，并且换一个下标，马上就能选择另一个元素。
“迭代器 （iterator 又是一个设计模式）”是一个对象，它的任务是，能在让“客户程序在不知道，或者不关心他所处理的是什么样的底层序列结构”的情况下，就能在一个对象序列中 前后移动，并选取其中的对象。此外迭代器还是一种通常所说的“轻量级”的对象，既创建代价很小的对象。
Java的Iterator就属于有这种限制的迭代器。它做不了很多事情，除了：
1，用iterator()方法叫容器传给你一个Iterator对象。第一次调用Iterator的next()方法的时候，它就会传给你序列中的第一个元素。
2，用next()方法获取序列中的下一个对象。
3，用hasNext()方法查询序列中是否还有其他对象。
4，用remove()方法删除迭代器所返回的最后一个元素。
就这么多了。这只是迭代器的一个恨简单的实现，不过还是很强大（对List来说，还有一个更精巧的ListIterator）。

不经意的递归（Unintended recursion）
由于Java的标准容器类（同其它类一样）也是继承Object的，因此它 们也有一个toString()方法。这个方法已经被覆写了，所以它能生成一个表示它自己以及所有它所保存的对象的String。比如ArrayList 的toString()方法就会遍历ArrayList的每个元素，然后调用它们的toString()方法。假设你要打印类的地址。好像最直接的办法就 是使用this。但是会出现很多异常，解决的办法就是去调用Object的 toString()方法，它就是干这活的。所以不要用this，应该写super.toString()。

容器分类学
根据编程的需要，Collection和Map分别有好几个实现。实际上只有三种容器组件－－Map，List和Set，而每种又有两到三个实现。
与存放对象有关的接口包括Collection, List, Set和Map。在理想情况下，绝大多数代码应该只同这些接口打交道，只是在创建容器的时候才要精确地指明它的确切类型。
add()， 就像它的名字告诉我们的，会把新的元素放进Collection。但是文档里面特别仔细地声明，“add()会确保容器包含指定的元素”。这句话是说给 Set的，因为它只添加原先没有的元素，对ArrayList或其他List，add()总是“把它放进去”，因为List并不关心它是不是保存了相同的 元素。
Collection都能用iterator()方法产生一个Iterator。这里，我们用Iterator来遍历整个Collection，然后把他们打印出来。

Collection的功能
下面这张表给出了Collection的所有功能，也就是你能用Set和List做什么事（不包括从Object自动继承过来的方法）。（List还有一些额外的功能。）Map不是继承Collection的，所以我们会区别对待。

boolean add(Object)：确保容器能持有你传给它的那个参数。如果没有把它加进去，就返回false。（这是个“可选”的方法，本章稍后会再作解释。）
boolean addAll(Collection)：加入参数Collection所含的所有元素。只要加了元素，就返回true。
void clear()：清除容器所保存的所有元素。（“可选”）
boolean contains(Object)：如果容器持有参数Object，就返回true。
boolean containsAll(Collection)：如果容器持有参数Collection所含的全部元素，就返回true。
boolean isEmpty()：如果容器里面没有保存任何元素，就返回true。
Iterator iterator()：返回一个可以在容器的各元素之间移动的Iterator。
boolean removeAll(Collection)：删除容器里面所有参数Collection所包含的元素。只要删过东西，就返回true。（“可选”）
boolean retainAll(Collection)：只保存参数Collection所包括的元素（集合论中“交集”的概念）。如果发生过变化，则返回true。（“可选”）
int size()：返回容器所含元素的数量。
Object[] toArray()：返回一个包含容器中所有元素的数组。
Object[] toArray(Object[] a)：返回一个包含容器中所有元素的数组，且这个数组不是普通的Object数组，它的类型应该同参数数组a的类型相同（要做类型转换）。
注意，这里没有能进行随机访问的get()方法。这是因为Collection还包括Set。而Set有它自己的内部顺序（因此随即访问事毫无意义的）。所以如果你要检查Collection的元素，你就必须使用迭代器。
接下来讲List, Set和Map的各种实现了，每讲一种容器，我都会（用星号）告诉你默认情况下应该选用哪种实现。

List的功能
List的基本用法事相当将但的。虽然绝大多数时候，你只是用add()加对象，用get()取对象，用iterator()获取这个序列的Iterator，但List还有一些别的很有用的方法。
实际上有两种List：擅长对元素进行随机访问的，较常用的ArrayList，和更强大的LinkedList。LinkedList不是为快速的随机访问而设计的，但是它却有一组更加通用的方法。
Lisk（接 口）：List的最重要的特征就是有序；它会确保以一定的顺序保存元素。List在Collection的基础上添加了大量方法，使之能在序列中间插入和 删除元素。（只对LinkedList推荐使用。）List可以制造ListIterator对象，你除了能用它在List的中间插入和删除元素之外，还 能用它沿两个方法遍历List。
ArrayList*：一个用数组实现的List。能进行快速的随机访问，但是往列表中间插入和删除元素的时候比 较慢。ListIterator只能用在反向遍历ArrayList的场合，不要用它来插入和删除元素，因为相比LinkedList，在 ArrayList里面用ListIterator的系统开销比较高。
LinkedList：对顺序访问进行了优化。在List中间插入和删除元 素的代价也不高。随机访问的速度相对较慢。（用ArrayList吧。）此外它还有 addFirst()，addLast()，getFirst()，getLast()，removeFirst()和removeLast()等方法 （这些方法，接口和基类均未定义），你能把它当成栈（stack），队列（queue）或双向队列（deque）来用。
记住，容器只是一个存储对 象的盒子。如果这个笑盒子能帮你解决所有的问题，那你就用不着取管它事怎么实现的（在绝大多数情况下，这是使用对象的基本概念）。如果开发环境里面还有一 些别的，会造成固定的性能开销的因素存在，那么ArrayList和LinkedList之间的性能差别就会变得不那么重要了。你只需要它们中的一个，你 甚至可以想象有这样一种“完美”的抽象容器；它能根据用途，自动地切换其底层的实现。

用LinkedList做一个栈
“栈（stack）”有时也被称为“后进先出”（LIFO）的容器。就是说，最后一个被“压”进栈中的东西，会第一个“弹”出来。同其他Java容器一样，压进去和弹出来的东西都是Object，所以除非你只用Object的功能，否则就必须对弹起来的东西进行类型转换。
LinkedList的方法能直接实现栈的功能，所以你完全可以不写Stack而直接使用LinkedList。
如果你只想要栈的功能，那么继承就不太合适了，因为继承出来的是一个拥有LinkedList的所有方法的类。

用LinkedList做一个队列
队列（queue）是一个“先进先出”（FIFO）容器。也就是，你把一端把东西放进去，从另一端把东西取出来。所以你放东西的顺序也就是取东西的顺序。LinkedList有支持队列的功能的方法，所以它也能被当作Queue来用。
还能很轻易地用LinkedList做一个deque（双向队列）。它很像队列，只是你可以从任意一端添加和删除元素。

Set的功能
Set的接口就是Collection的，所以不像那两个List，它没有额外的功能。实际上Set确确实实就是一个 Collection－－只不过行为方式不同罢了。（这是继承和多态性的完美运用：表达不同地行为。）Set会拒绝持有多个具有相同值的对象的实例（对象 的“值”又是由什么决定的呢？这个问题比较复杂，我们以后会讲）。
Set（接口）：加入Set的每个元素必须是唯一的；否则，Set是不会把它加进去的。要想加进Set，Object必须定义equals()，这样才能标明对象的唯一性。Set的接口和Collection的一摸一样。Set的接口不保证它会用哪种顺序来存储元素。
HashSet*：为优化查询速度而设计的Set。要放进HashSet里面的Object还得定义hashCode()。
TreeSet：是一个有序的Set，其底层是一颗树。这样你就能从Set里面提取一个有序序列了。
LinkedHashSet(JDK 1.4)：一个在内部使用链表的Set，既有HashSet的查询速度，又能保存元素被加进去的顺序（插入顺序）。用Iterator遍历Set的时候，它是按插入顺序进行访问的。
HashSet 保存对象的顺序是和TreeSet和LinkedHashSet不一样的。这是因为它们是用不同的方法来存储和查找元素的。（TreeSet用了一种叫红 黑树的数据结构【red-black tree data structure】来为元素排序，而HashSet则用了“专为快速查找而设计”的散列函数。LinkedHashSet在内部用散列来提高查询速度， 但是它看上去像是用链表来保存元素的插入顺序的。）你写自己的类的时候，一定要记住，Set要有一个判断以什么顺序来存储元素的标准，也就是说你必须实现 Comparable接口，并且定义compareTo()方法。

SortedSet
SortedSet（只有TreeSet这一个实现可用）中的元素一定是有序的。这使得SortedSet接口多了一些方法：
Comparator comparator()：返回Set锁使用的Comparator对象，或者用null表示它使用Object自有的排序方法。
Object first()：返回最小的元素。
Object last()：返回最大的元素。
SortedSet subSet(fromElement, toElement)：返回Set的子集，其中的元素从fromElement开始到toElement为止（包括fromElement，不包括toElement）。
SortedSet headSet(toElement)：返回Set的子集，其中的元素都应小于toElement。
SortedSet headSet(toElement)：返回Set的子集，其中的元素都应大于fromElement。
注意，SortedSet意思是“根据对象的比较顺序”，而不是“插入顺序”进行排序。

Map的功能
ArrayList能让你用数字在一愕嘎对象序列里面进行选择，所以从某种意义上讲，它是将数字和对象关联起来。但是，如 果你想根据其他条件在一个对象序列里面进行选择的话，那又该怎么做呢？栈就是一个例子。它的标准是“选取最后一个被压入栈的对象”。我们常用的术语 map，dictionary，或 associative array就是一种非常强大的，能在序列里面进行挑选的工具。从概念上讲，它看上去像是一个ArrayList，但它不用数字，而是用另一个对象来查找对 象！这是一种至关重要的编程技巧。
这一概念在Java中表现为Map。put(Object key, Object value)方法会往Map里面加一个值，并且把这个值同键（你查找时所用的对象）联系起来。给出键之后，get(Object key)就会返回与之相关的值。你也可以用containsKey()和containsValue()测试Map是否包含有某个键或值。
Java 标准类库里有好几种Map：HashMap，TreeMap，LinkedHashMap，WeakHashMap，以及 IdentityHashMap。它们都实现了Map的基本接口，但是在行为方式方面有着明显的诧异。这些差异体现在，效率，持有和表示对象pair的顺 序，持有对象的时间长短，以及如何决定键的相等性。
性能时Map所要面对的一个大问题。如果你知道get()时怎么工作的，你就会发觉（比方说） 在ArrayList里面找对象会是相当慢的。而这正是 HashMap的强项。它不是慢慢地一个个地找这个键，而是用了一种被称为hash code的特殊值来进行查找的。散列（hash）时一种算法，它会从目标对象当中提取一些信息，然后生成一个表示这个对象的“相对独特”的int。 hashCode()是Object根类的方法，因此所有Java对象都能生成hash code。HashMap则利用对象的hashCode()来进行快速的查找。这样性能就有了急剧的提高。
Map（接口）：维持键－－值的关系（既pairs），这样就能用键来找值了。
HashMap*：基于hash表的实现。（用它来代替Hashtable。）提供时间恒定的插入与查询。在构造函数种可以设置hash表的capacity和load factor。可以通过构造函数来调节其性能。
LinkedHashMap(JDK 1.4)：很像HashMap，但是用Iterator进行遍历的时候，它会按插入顺序或最先使用的顺序（least-recently-used (LRU)order）进行访问。除了用Iterator外，其他情况下，只是比HashMap稍慢一点。用Iterator的情况下，由于是使用链表来 保存内部顺序，因此速度会更快。
TreeMap：基于红黑树数据结构的实现。当你查看键或pair时，会发现它们时按顺序（根据 Comparable或Comparator，我们过一会讲）排列的。TreeMap的特点时，你锁得到的时一个有序的Map。TreeMap是Map中 唯一有subMap()方法的实现。这个方法能让你获取这个树中的一部分。
WeakHashMap：一个weak key的Map，是为某些特殊问题而设计的。它能让Map释放其所持有的对象。如果某个对象除了在Map当中充当键之外，在其他地方都没有其reference的话，那它将被当作垃圾回收。
IdentityHashMap(JDK 1.4)：一个用＝＝，而不是equals()来比较键的hash map。不是为我们平常使用而设计的，是用来解决特殊问题的。
散列是往Map里存数据的常用算法。

SortedMap
SortedMap（只有TreeMap这一个实现）的键肯定是有序的，因此这个接口里面就有一些附加功能的方法了。
Comparator comparator()：返回Map所使用的comparator，如果是用Object内置的方法的话，则返回null。
Object firstKey()：返回第一个键。
Object lastKey()：返回最后一个键。
SortedMap subMap(fromKey, toKey)：返回这个Map的一个子集，其键从fromKey开始到toKey为止，包括前者，不包括后者。
SortedMap headMap(toKey)：返回这个Map的一愕嘎子集，其键均小于toKey。
SortedMap tailMap(fromKey)：返回这个Map的一个子集，其键均大于等于fromKey。
pair是按key的顺序存储的，由于TreeMap有顺序的概念，因此“位置”是有意义的，所以你可以去获取它的第一个和最后一个元素，以及它的子集。

LinkedHashMap
为了提高速度，LinkedHashMap对所 有东西都做了hash，而且遍历的时候（println()会遍历整个Map，所以你能看到这个过程）还会按插入顺序返回pair。此外，你还可以在 LinkedHashMap的构造函数里面进行配置，让它使用基于访问的LRU（least-recently -used）算法，这样还没被访问过的元素（同时也是要删除的候选对象）就会出现在队列的最前头。这样，为节省资源而写一个定时清理的程序就变得很简单 了。

散列算法与Hash数
一个合适的equals()必须做到一下五点：
1 反身性：对任何x, x.equals(x)必须是true的。
2 对称性：对任何x和y，如果y.equals(x)是true的，那么
x.equals(y)也必须是true的。
3 传递性：对任何x，y和z，如果x.equals(y)是true的，且
y.equals(z)也是true的，那么x.equals(z)也必须是true的。
4 一致性：对任何x和y，如果对象里面用来判断相等姓的信息没有修
改过，那么无论调用多少次x.equals(y)，它都必须一致地返回
true或false。
5 对于任何非空的x，x.equals(null)必须返回false。
默认的Object.equals()只是简单地比较两个对象的地址。
如果你想把子集写的类当HashMap的键来用的话，你就必须把hashCode()和equals（）都给覆写了。

理解hashCode()
如果你不覆写键的hashCode()和equals()的话，散列数据结构（HashSet，HashMap，LinkedHashSet，或LinkedHashMap）就没法正确地处理键。
散列的价值就在于速度：散列算法能很快地找出东西。
数组是最快的数据结构。

持有reference
java.lang.ref类库里有一套能增进垃圾回收器工作的灵活性的类。一旦碰到了“对象达到要耗光内存”的时候，这些类就会闲的格 外有用。有三个类是继承抽象类Reference的：SoftReference，WeakReference和PhantomReference。如果 待处理的对象只能通过这些Reference进行访问的话，那么这些Reference对象就会向垃圾回收器提供一些不同级别的暗事。

……

总结Java标准类库的容器类：
1。数组把对象和数字形式的下标联系起来。它持有的是类型确定的对象，这样提取对象的时候就不用再作类型传递了。它可以是多维的，也可以持有primitive。但是创建之后它的容量不能改了。
2。Collection持有单个元素，而Map持有相关联的pair。
3。 和数组一样，List也把数字下标同对象联系起来，你可以把数组和List想成有序的容器。List会随元素的增加自动调整容量。但是List只能持有 Object reference，所以不能存放primitive，而且把Object提取出来之后，还要做类型传递。
4。如果要做很多随机访问，那么请用ArrayList，但是如果要再List的中间做很多插入和删除的话，就应该用LinkedList了。
5。LinkedList能提供队列，双向队列和栈的功能。
6。Map提供的不是对象与数组的关联，而是对象和对象的关联。
HashMap看重的是访问速度，而TreeMap各国那看重键的顺序，因而它不如HashMap那么快。而LinkedHashMap则保持对象插入的顺序，但是也可以用LRU算法为它重新排序。
7。Set只接受不重复的对象。HashSet提供了最快的查询速度。而TreeSet则保持元素有序。LinkedHashSet保持元素的插入顺序。
8。没必要再在新代码里使用旧类库留下来的Vector，Hashtable和Stack了。
容器类库是你每天都会用到的工具，它能使程序更简介，更强大并且更搞笑。