Java集合类

数组
数组与其它容器的区别体现在三个方面：效率，类型识别以及可以持有primitives (类型)。
数组是Java提供的，能随机存储和访问reference序列的诸多方法中的，最高效的一种。
数组是一个简单的线性序列，所以它可以快速的访问其中的元素。
但是当你创建了一个数组之后，它的容量就固定了，而且在其生命周期里不能改变。
Java对数组和容器都做边界检查；如果过了界，它就会给一个RuntimeException。表明这个错误是由程序员造成的。

Java2的重新设计了1.0和1.1里面那个表现差劲的容器类。新的设计更紧凑也更合理。同时它也补齐了容器类库的功能，提供了链表（linked list），队列（queue）和双向队列（deques，读成“decks”）这几种数据结构的功能。
Java2的容器类要解决“怎样持有对象”，而它把这个问题分成两类：
1。Collection：通常是一组有一定规律的独立元素。List必须按照特定的顺序持有这些元素，而Set则不能保存重复的元素。（bag没有这个限制，但是Java的容器类库没有实现它，因为List已经提供这种功能了）
2。Map：一组以“键－－值”（key-value）形式出现的pair。 Map可以返回“键（key）的”Set，值的Collection，或者pair的Set。和数组一样，Map不需要什么修改，就能很容易地扩展成多维。你只要直接把Map的值设成Map就可以了（然后它的值再是Map，依此类推）。
Java的容器类分成两种基本类型。它们的区别就在，每个位置能放多少对象。Collection只允许每个位置上放一个对象。它包括“以一定顺序持有一组对象”的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，由于在将对象放入容器的时候，它的类型信息被扔掉了，所以容器对“能往里面加什么类型的对象”没有限制。
2，由于对象的类型信息没了，容器只知道它持有的Object的reference，所以对象在使用之前还必须进行类型转换。
好的一面是，Java不会让你误用放进容器里的对象。
ArrayList的用法也是很简单：先创建一个，用add()把对象放进去，要用的时候再给get()传一个下标－－就跟用数组差不多，只是不需要用方括号了。ArrayList也有一个size()方法，它会告诉你容器里面有多少对象，这样你就不会粗心大意地过了界然后引发异常了。

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

迭代器
无论是哪种容器，你都得有办法既能放东西进去，也能拿东西出来。毕竟，容器的主要任务就是存放对象。ArrayList的add()就是用来放东西的，而 get()则是把对象拿出来的办法。ArrayList恨灵活；你可以随时提取任何东西，并且换一个下标，马上就能选择另一个元素。
“迭代器”是一个对象，它的任务是，能在让“客户程序在不知道，或者不关心他所处理的是什么样的底层序列结构”的情况下，就能在一个对象序列中前后移动，并选取其中的对象。此外迭代器还是一种通常所说的“轻量级”的对象，既创建代价很小的对象。
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做什么事。（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，而且遍历的时候还会按插入顺序返回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了。

集合接口


队列接口 按照先进先出原则，规定可以在队列尾部添加元素，在队列头部删除元素。

队列实现：

1、使用循环数组；2、使用链表

集合类的基本接口是java.util.Collection<E>接口，该接口的基本方法：

boolean add()
用于向集合中添加元素。如果添加元素后，该集合发生了改变，则返回true；如果集合无任何变化，则返回false

Iterator<E> iterator()
用于返回一个实现了Iterator接口的对象。可以用iterator方法所返回的对象逐个访问集合的各个元素。

迭代器java.util.Iterator<E>接口，该接口的基本方法：

E next()
可以逐个访问集合中的各个元素。

boolean hasNext()
如果迭代器iterator对象仍然有可以访问的元素，则返回true。

如果想查看集合中的所有元素，可以先请求一个迭代器对象，然后在hasNext方法返回true时调用next方法

void remove()
将会移除上次调用next方法时返回的元素。

调用顺序：hasNext-->next-->remove，即调用next方法之前要调用hasNext方法，调用remove方法之前要先调用next方法。

具体的集合

链表
java.util.LinkedList<E>
可以在任何位置进行高效的插入和移除操作的有序集合

数组列表
java.util.ArrayList<E>
可以动态增长和缩减的索引序列
java.util.List<E>
通过两种协议方法用来访问各个元素：
1、通过迭代器；
2、使用get和set方法来随机访问这些元素


散列表
java.util.HashSet<E>
没有重复元素的无序集合

树集
java.util.TreeSet<E>
有序集合

枚举集
java.util.EnumSet<E extens Enum<E>>
包含枚举类型的元素集合

链接散列集
java.util.LinkedHashSet<E>
可以记住元素被插入顺序的集合

优先级队列
java.util.PriorityQueue
可以高效地移除最小元素的集合

散列映射表
HashMap
一种存储键/值关联的数据结构

树状映射表
TreeMap
键有序的Map集合

枚举映射表
java.util.EnumMap<K extends Enum<K>,V>
键属于枚举类型的Map集合

链接散列映射表
java.util.LinkedHashMap<K,V>
可以记住键/值项被添加顺序的Map集合

弱散列映射表
java.util.WeakHashMap<K,V>
该Map集合中的值如果没有在其他地方被使用，则可以被垃圾回收器回收

标识散列映射表
java.util.IdentityHashMap<K,V>
该Map集合中的键是用“==”比较，而不是用equals来比较