数组是第一流的对象

不管你用的是那种类型的数组，数组的标识符实际上都是一个“创建在堆（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了。

容器类库是你每天都会用到的工具，它能使程序更简介，更强大并且更搞笑。

Collection接口

Collection是最基本的集合接口，一个Collection代表一组Object，即Collection的元素（Elements）。一些 Collection允许相同的元素而另一些不行。一些能排序而另一些不行。Java SDK不提供直接继承自Collection的类，Java SDK提供的类都是继承自Collection的“子接口”如List和Set。

所有实现Collection接口的类都必须提供两个标准的构造函数：无参数的构造函数用于创建一个空的Collection，有一个 Collection参数的构造函数用于创建一个新的Collection，这个新的Collection与传入的Collection有相同的元素。后 一个构造函数允许用户复制一个Collection。

如何遍历Collection中的每一个元素？不论Collection的实际类型如何，它都支持一个iterator()的方法，该方法返回一个迭代子，使用该迭代子即可逐一访问Collection中每一个元素。典型的用法如下：

Iterator it = collection.iterator(); // 获得一个迭代子

while(it.hasNext()) {

Object obj = it.next(); // 得到下一个元素

}

由Collection接口派生的两个接口是List和Set。

List接口

List是有序的Collection，使用此接口能够精确的控制每个元素插入的位置。用户能够使用索引（元素在List中的位置，类似于数组下标）来访问List中的元素，这类似于Java的数组。

和下面要提到的Set不同，List允许有相同的元素。

除了具有Collection接口必备的iterator()方法外，List还提供一个listIterator()方法，返回一个 ListIterator接口，和标准的Iterator接口相比，ListIterator多了一些add()之类的方法，允许添加，删除，设定元素， 还能向前或向后遍历。

实现List接口的常用类有LinkedList，ArrayList，Vector和Stack。

LinkedList类

LinkedList实现了List接口，允许null元素。此外LinkedList提供额外的get，remove，insert方法在 LinkedList的首部或尾部。这些操作使LinkedList可被用作堆栈（stack），队列（queue）或双向队列（deque）。

注意LinkedList没有同步方法。如果多个线程同时访问一个List，则必须自己实现访问同步。一种解决方法是在创建List时构造一个同步的List：

List list = Collections.synchronizedList(new LinkedList(…));

**ArrayList类

**　　ArrayList实现了可变大小的数组。它允许所有元素，包括null。ArrayList没有同步。

size，isEmpty，get，set方法运行时间为常数。但是add方法开销为分摊的常数，添加n个元素需要O(n)的时间。其他的方法运行时间为线性。

每个ArrayList实例都有一个容量（Capacity），即用于存储元素的数组的大小。这个容量可随着不断添加新元素而自动增加，但是增长算法 并没有定义。当需要插入大量元素时，在插入前可以调用ensureCapacity方法来增加ArrayList的容量以提高插入效率。

和LinkedList一样，ArrayList也是非同步的（unsynchronized）。

**Vector类

**　　Vector非常类似ArrayList，但是Vector是同步的。由Vector创建的Iterator，虽然和 ArrayList创建的Iterator是同一接口，但是，因为Vector是同步的，当一个Iterator被创建而且正在被使用，另一个线程改变了 Vector的状态（例如，添加或删除了一些元素），这时调用Iterator的方法时将抛出 ConcurrentModificationException，因此必须捕获该异常。

Stack 类

Stack继承自Vector，实现一个后进先出的堆栈。Stack提供5个额外的方法使得Vector得以被当作堆栈使用。基本的push和pop 方法，还有peek方法得到栈顶的元素，empty方法测试堆栈是否为空，search方法检测一个元素在堆栈中的位置。Stack刚创建后是空栈。

**Set接口

**　　Set是一种不包含重复的元素的Collection，即任意的两个元素e1和e2都有e1.equals(e2)=false，Set最多有一个null元素。

很明显，Set的构造函数有一个约束条件，传入的Collection参数不能包含重复的元素。

请注意：必须小心操作可变对象（Mutable Object）。如果一个Set中的可变元素改变了自身状态导致Object.equals(Object)=true将导致一些问题。

Map接口

请注意，Map没有继承Collection接口，Map提供key到value的映射。一个Map中不能包含相同的key，每个key只能映射一个 value。Map接口提供3种集合的视图，Map的内容可以被当作一组key集合，一组value集合，或者一组key-value映射。

Hashtable类

Hashtable继承Map接口，实现一个key-value映射的哈希表。任何非空（non-null）的对象都可作为key或者value。

添加数据使用put(key, value)，取出数据使用get(key)，这两个基本操作的时间开销为常数。

Hashtable通过initial capacity和load factor两个参数调整性能。通常缺省的load factor 0.75较好地实现了时间和空间的均衡。增大load factor可以节省空间但相应的查找时间将增大，这会影响像get和put这样的操作。

使用Hashtable的简单示例如下，将1，2，3放到Hashtable中，他们的key分别是”one”，”two”，”three”：

Hashtable numbers = new Hashtable();

numbers.put(“one”, new Integer(1));

numbers.put(“two”, new Integer(2));

numbers.put(“three”, new Integer(3));

要取出一个数，比如2，用相应的key：

Integer n = (Integer)numbers.get(“two”);

System.out.println(“two = ” + n);

由于作为key的对象将通过计算其散列函数来确定与之对应的value的位置，因此任何作为key的对象都必须实现hashCode和equals方 法。hashCode和equals方法继承自根类Object，如果你用自定义的类当作key的话，要相当小心，按照散列函数的定义，如果两个对象相 同，即obj1.equals(obj2)=true，则它们的hashCode必须相同，但如果两个对象不同，则它们的hashCode不一定不同，如 果两个不同对象的hashCode相同，这种现象称为冲突，冲突会导致操作哈希表的时间开销增大，所以尽量定义好的hashCode()方法，能加快哈希 表的操作。

如果相同的对象有不同的hashCode，对哈希表的操作会出现意想不到的结果（期待的get方法返回null），要避免这种问题，只需要牢记一条：要同时复写equals方法和hashCode方法，而不要只写其中一个。

Hashtable是同步的。

HashMap类

HashMap和Hashtable类似，不同之处在于HashMap是非同步的，并且允许null，即null value和null key。，但是将HashMap视为Collection时（values()方法可返回Collection），其迭代子操作时间开销和HashMap 的容量成比例。因此，如果迭代操作的性能相当重要的话，不要将HashMap的初始化容量设得过高，或者load factor过低。

WeakHashMap类

WeakHashMap是一种改进的HashMap，它对key实行“弱引用”，如果一个key不再被外部所引用，那么该key可以被GC回收。

**总结

**　　如果涉及到堆栈，队列等操作，应该考虑用List，对于需要快速插入，删除元素，应该使用LinkedList，如果需要快速随机访问元素，应该使用ArrayList。

如果程序在单线程环境中，或者访问仅仅在一个线程中进行，考虑非同步的类，其效率较高，如果多个线程可能同时操作一个类，应该使用同步的类。

要特别注意对哈希表的操作，作为key的对象要正确复写equals和hashCode方法。

尽量返回接口而非实际的类型，如返回List而非ArrayList，这样如果以后需要将ArrayList换成LinkedList时，客户端代码不用改变。这就是针对抽象编程。

同步性

Vector是同步的。这个类中的一些方法保证了Vector中的对象是线程安全的。而ArrayList则是异步的，因此ArrayList中的对象并 不是线程安全的。因为同步的要求会影响执行的效率，所以如果你不需要线程安全的集合那么使用ArrayList是一个很好的选择，这样可以避免由于同步带 来的不必要的性能开销。

数据增长

从内部实现机制来讲ArrayList和Vector都是使用数组(Array)来控制集合中的对象。当你向这两种类型中增加元素的时候，如果元素的数目 超出了内部数组目前的长度它们都需要扩展内部数组的长度，Vector缺省情况下自动增长原来一倍的数组长度，ArrayList是原来的50%,所以最 后你获得的这个集合所占的空间总是比你实际需要的要大。所以如果你要在集合中保存大量的数据那么使用Vector有一些优势，因为你可以通过设置集合的初 始化大小来避免不必要的资源开销。

使用模式

在ArrayList和Vector中，从一个指定的位置（通过索引）查找数据或是在集合的末尾增加、移除一个元素所花费的时间是一样的，这个时间我们用 O(1)表示。但是，如果在集合的其他位置增加或移除元素那么花费的时间会呈线形增长：O(n-i)，其中n代表集合中元素的个数，i代表元素增加或移除 元素的索引位置。为什么会这样呢？以为在进行上述操作的时候集合中第i和第i个元素之后的所有元素都要执行位移的操作。这一切意味着什么呢？

这意味着，你只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是其他操作，你最好选择其他 的集合操作类。比如，LinkList集合类在增加或移除集合中任何位置的元素所花费的时间都是一样的?O(1)，但它在索引一个元

《Android学习笔记总结+最新移动架构视频+大厂安卓面试真题+项目实战源码讲义》

【docs.qq.com/doc/DSkNLaERkbnFoS0ZF】 完整内容开源分享

素的使用缺比较慢 －O(i),其中i是索引的位置.使用ArrayList也很容易，因为你可以简单的使用索引来代替创建iterator对象的操作。LinkList也 会为每个插入的元素创建对象，所有你要明白它也会带来额外的开销。