Java  集合框架

Java集合框架图 

简化图： 

 
 
Java平台提供了一个全新的集合框架。“集合框架”主要由一组用来操作对象的接口组成。
不同接口描述一组不同数据类型。 
 
 
1、Java 2集合框架图 
 
①集合接口：6个接口（短虚线表示），表示不同集合类型，是集合框架的基础。 
 
②抽象类：5个抽象类（长虚线表示），对集合接口的部分实现。可扩展为自定义集合类。 
 
实现类：8个实现类（实线表示），对接口的具体实现。 
 
在很大程度上，一旦您理解了接口，您就理解了框架。虽然您总要创建接口特定的实现，但访
问实际集合的方法应该限制在接口方法的使用上；因此，允许您更改基本的数据结构而不必改
变其它代码。 
 
· Collection 接口是一组允许重复的对象。 
 
· Set 接口继承 Collection，但不允许重复，使用自己内部的一个排列机制。 
 
 
· List 接口继承 Collection，允许重复，以元素安插的次序来放置元素，不会重新排列。 
 
· Map接口是一组成对的键－值对象，即所持有的是key-value pairs。Map中不能有重复的
key。拥有自己的内部排列机制。 
 
· 容器中的元素类型都为Object。从容器取得元素时，必须把它转换成原来的类型。 
 
 
Java 2简化集合框架图 
 
集合接口 
 
1.Collection 接口 
 
用于表示任何对象或元素组。想要尽可能以常规方式处理一组元素时，就使用这一接口。 
 
 
 
(1) 单元素添加、删除操作： 
 
 
boolean add(Object o):将对象添加给集合 
 
boolean remove(Object o): 如果集合中有与o相匹配的对象，则删除对象o 
 
(2) 查询操作： 
 
int size() ：返回当前集合中元素的数量 
 
boolean isEmpty() ：判断集合中是否有任何元素 
 
boolean contains(Object o) ：查找集合中是否含有对象o 
 
Iterator iterator() ：返回一个迭代器，用来访问集合中的各个元素 
 
(3) 组操作 ：作用于元素组或整个集合 
 
boolean containsAll(Collection c): 查找集合中是否含有集合c 中所有元素 
 
boolean addAll(Collection c) : 将集合c 中所有元素添加给该集合 
 
void clear(): 删除集合中所有元素 
 
void removeAll(Collection c) : 从集合中删除集合c 中的所有元素 
 
void retainAll(Collection c) : 从集合中删除集合c 中不包含的元素 
 
(4) Collection转换为Object数组 ： 
 
Object[] toArray() ：返回一个内含集合所有元素的array 
 
Object[] toArray(Object[] a) ：返回一个内含集合所有元素的array。运行期返回的array
和参数a的型别相同，需要转换为正确型别。 
 
此外，您还可以把集合转换成其它任何其它的对象数组。但是，您不能直接把集合转换成基本
数据类型的数组，因为集合必须持有对象。 
 
“斜体接口方法是可选的。因为一个接口实现必须实现所有接口方法，调用程序就需要一种途
径来知道一个可选的方法是不是不受支持。如果调用一种可选方法 时，一个 
UnsupportedOperationException 被抛出，则操作失败，因为方法不受支持。此异常类继承 
RuntimeException 类，避免了将所有集合操作放入 try-catch 块。” 
 
Collection不提供get()方法。如果要遍历Collectin中的元素，就必须用Iterator。 
 
 
1.1.AbstractCollection 抽象类 
 
AbstractCollection 类提供具体“集合框架”类的基本功能。虽然您可以自行实现 
Collection 接口的所有方法，但是，除了iterator()和size()方法在恰当的子类中实现以外，
其它所有方法都由 AbstractCollection 类来提供实现。如果子类不覆盖某些方法，可选的如
add()之类的方法将抛出异常。 
 
1.2.Iterator 接口 
 
Collection 接口的iterator()方法返回一个 Iterator。Iterator接口方法能以迭代方式逐
个访问集合中各个元素，并安全的从Collection 中除去适当的元素。 
 
 
 
(1) boolean hasNext(): 判断是否存在另一个可访问的元素 
 
Object next(): 返回要访问的下一个元素。如果到达集合结尾，则抛出
NoSuchElementException异常。 
 
(2) void remove(): 删除上次访问返回的对象。本方法必须紧跟在一个元素的访问后执行。
如果上次访问后集合已被修改，方法将抛出IllegalStateException。 
 
“Iterator中删除操作对底层Collection也有影响。” 
 
迭代器是 故障快速修复（fail-fast）的。这意味着，当另一个线程修改底层集合的时候，如
果您正在用 Iterator 遍历集合，那么，Iterator就会抛出 
ConcurrentModificationException （另一种 RuntimeException异常）异常并立刻失败 
  2.List接口 
 
List 接口继承了 Collection 接口以定义一个允许重复项的有序集合。该接口不但能够对列
表的一部分进行处理，还添加了面向位置的操作。 
 
 
 
 
(1) 面向位置的操作包括插入某个元素或 Collection 的功能，还包括获取、除去或更改元素
的功能。在 List 中搜索元素可以从列表的头部或尾部开始，如果找到元素，还将报告元素所
在的位置 : 
 
void add(int index, Object element): 在指定位置index上添加元素element 
 
boolean addAll(int index, Collection c): 将集合c的所有元素添加到指定位置index 
 
Object get(int index): 返回List中指定位置的元素 
 
int indexOf(Object o): 返回第一个出现元素o的位置，否则返回-1 
 
int lastIndexOf(Object o) ：返回最后一个出现元素o的位置，否则返回-1 
 
Object remove(int index) ：删除指定位置上的元素 
 
Object set(int index, Object element) ：用元素element取代位置index上的元素，并且
返回旧的元素 
 
(2) List 接口不但以位置序列迭代的遍历整个列表，还能处理集合的子集： 
 
ListIterator listIterator() : 返回一个列表迭代器，用来访问列表中的元素 
 
 
ListIterator listIterator(int index) : 返回一个列表迭代器，用来从指定位置index开
始访问列表中的元素 
 
List subList(int fromIndex, int toIndex) ：返回从指定位置fromIndex（包含）到toIndex
（不包含）范围中各个元素的列表视图 
 
“对子列表的更改（如 add()、remove() 和 set() 调用）对底层 List 也有影响。” 
 
2.1.ListIterator接口 
 
ListIterator 接口继承 Iterator 接口以支持添加或更改底层集合中的元素，还支持双向访
问。ListIterator没有当前位置，光标位于调用previous和next方法返回的值之间。一个
长度为n的列表，有n+1个有效索引值： 
 
 
 
 
(1) void add(Object o): 将对象o添加到当前位置的前面 
 
void set(Object o): 用对象o替代next或previous方法访问的上一个元素。如果上次调用
后列表结构被修改了，那么将抛出IllegalStateException异常。 
 
(2) boolean hasPrevious(): 判断向后迭代时是否有元素可访问 
 
Object previous()：返回上一个对象 
 
int nextIndex(): 返回下次调用next方法时将返回的元素的索引 
 
int previousIndex(): 返回下次调用previous方法时将返回的元素的索引 
 
“正常情况下，不用ListIterator改变某次遍历集合元素的方向 — 向前或者向后。虽然在
技术上可以实现，但previous() 后立刻调用next()，返回的是同一个元素。把调用 next()
和previous()的顺序颠倒一下，结果相同。” 
 
 
“我们还需要稍微再解释一下 add() 操作。添加一个元素会导致新元素立刻被添加到隐式光
标的前面。因此，添加元素后调用 previous() 会返回新元素，而调用 next() 则不起作用，
返回添加操作之前的下一个元素。” 
 
2.2.AbstractList和AbstractSequentialList抽象类 
 
有两个抽象的 List 实现类：AbstractList 和 AbstractSequentialList。像 AbstractSet 类
一样，它们覆盖了 equals() 和 hashCode() 方法以确保两个相等的集合返回相同的哈希码。
若两个列表大小相等且包含顺序相同的相同元素，则这两个列表相等。这里的 hashCode() 实
现在 List 接口定义中指定，而在这里实现。 
 
除了equals()和hashCode()，AbstractList和 AbstractSequentialList实现了其余 List 方
法的一部分。因为数据的随机访问和顺序访问是分别实现的，使得具体列表实现的创建更为容
易。需要定义的一套方法取决于您希望支持的行为。您永远不必亲自 提供的是 iterator方
法的实现。 
 
2.3. LinkedList类和ArrayList类 
 
在“集合框架 ”中有两种常规的 List 实现：ArrayList 和 LinkedList。使用两种 List 实
现的哪一种取决于您特定的需要。如果要支持随机访问，而不必在除尾部的任何位置插入或除
去元素，那么，ArrayList 提供了可选的集合。但如果，您要频繁的从列表的中间位置添加和
除去元素，而只要顺序的访问列表元素，那么，LinkedList 实现更好。 
 
“ArrayList 和 LinkedList 都实现 Cloneable 接口，都提供了两个构造函数，一个无参的，
一个接受另一个Collection” 
 
2.3.1. LinkedList类 
 
LinkedList类添加了一些处理列表两端元素的方法。 
 
 
 
(1) void addFirst(Object o): 将对象o添加到列表的开头 
 
void addLast(Object o)：将对象o添加到列表的结尾 
 
(2) Object getFirst(): 返回列表开头的元素 
 
 
Object getLast(): 返回列表结尾的元素 
 
(3) Object removeFirst(): 删除并且返回列表开头的元素 
 
Object removeLast():删除并且返回列表结尾的元素 
 
(4) LinkedList(): 构建一个空的链接列表 
 
LinkedList(Collection c): 构建一个链接列表，并且添加集合c的所有元素 
 
“使用这些新方法，您就可以轻松的把 LinkedList 当作一个堆栈、队列或其它面向端点的数
据结构。” 
 
2.3.2. ArrayList类 
 
ArrayList类封装了一个动态再分配的Object[]数组。每个ArrayList对象有一个capacity。
这个capacity表示存储列表中元素的数组的容量。当元素添加到ArrayList时，它的capacity
在常量时间内自动增加。 
 
在向一个ArrayList对象添加大量元素的程序中，可使用ensureCapacity方法增加capacity。
这可以减少增加重分配的数量。 
 
(1) void ensureCapacity(int minCapacity): 将ArrayList对象容量增加minCapacity 
 
(2) void trimToSize(): 整理ArrayList对象容量为列表当前大小。程序可使用这个操作减
少ArrayList对象存储空间。 
 
2.3.2.1. RandomAccess接口 
 
一个特征接口。该接口没有任何方法，不过你可以使用该接口来测试某个集合是否支持有效的
随机访问。ArrayList和Vector类用于实现该接口 
  3.Set接口 
 
Set 接口继承 Collection 接口，而且它不允许集合中存在重复项，每个具体的 Set 实现类
依赖添加的对象的 equals()方法来检查独一性。Set接口没有引入新方法，所以Set就是一
个Collection，只不过其行为不同。 
 
 
 
 
3.1. Hash表 
 
Hash表是一种数据结构，用来查找对象。Hash表为每个对象计算出一个整数，称为Hash 
Code(哈希码)。Hash表是个链接式列表的阵列。每个列表称为一个buckets(哈希表元)。对象
位置的计算 index = HashCode % buckets (HashCode为对象哈希码，buckets为哈希表元总
数)。 
 
当你添加元素时，有时你会遇到已经填充了元素的哈希表元，这种情况称为Hash 
Collisions(哈希冲突)。这时，你必须判断该元素是否已经存在于该哈希表中。 
 
如果哈希码是合理地随机分布的，并且哈希表元的数量足够大，那么哈希冲突的数量就会减少。
同时，你也可以通过设定一个初始的哈希表元数量来更好地控制哈 希表的运行。初始哈希表
元的数量为 buckets = size * 150% + 1 (size为预期元素的数量)。 
 
如果哈希 表中的元素放得太满，就必须进行rehashing(再哈希)。再哈希使哈希表元数增倍，
并将原有的对象重新导入新的哈希表元中，而原始的哈希表元被删 除。load factor(加载因
子)决定何时要对哈希表进行再哈希。在Java编程语言中，加载因子默认值为0.75，默认哈
希表元为101。 
 
3.2. Comparable接口和Comparator接口 
 
在“集合框架”中有两种比较接口：Comparable接口和Comparator接口。像String和Integer
等Java内建类实现 Comparable接口以提供一定排序方式，但这样只能实现该接口一次。对
于那些没有实现Comparable接口的类、或者自定义的类，您可以通过 Comparator接口来定
义您自己的比较方式。 
 
3.2.1. Comparable接口 
 
在java.lang包中，Comparable接口适用于一个类有自然顺序的时候。假定对象集合是同一
类型，该接口允许您把集合排序成自然顺序。 
 
 
 
 
(1) int compareTo(Object o): 比较当前实例对象与对象o，如果位于对象o之前，返回负
值，如果两个对象在排序中位置相同，则返回0，如果位于对象o后面，则返回正值 
 
在 Java 2 SDK版本1.4中有二十四个类实现Comparable接口。下表展示了8种基本类型的
自然排序。虽然一些类共享同一种自然排序，但只有相互可比的类才能排序。 
类  排序 
BigDecimal,BigInteger,Byte, Double, 
Float,Integer,Long,Short 
按数字大小排序 
Character  按 Unicode 值的数字大小排序 
String  按字符串中字符 Unicode 值排序 
 
利用Comparable接口创建您自己的类的排序顺序，只是实现compareTo()方法的问题。通常
就是依赖几个数据成员的自然排序。同时类也应该覆盖equals()和hashCode()以确保两个相
等的对象返回同一个哈希码。 
 
3.2.2. Comparator接口 
 
若一个类不能用于实现java.lang.Comparable，或者您不喜欢缺省的Comparable行为并想提
供自己的排序顺序(可能多种排序方式)，你可以实现Comparator接口，从而定义一个比较器。 
 
 
 
 
(1)int compare(Object o1, Object o2): 对两个对象o1和o2进行比较，如果o1位于o2
的前面，则返回负值，如果在排序顺序中认为o1和o2是相同的，返回0，如果o1位于o2的
后面，则返回正值 
 
“与Comparable相似，0返回值不表示元素相等。一个0返回值只是表示两个对象排在同一
位置。由Comparator用户决定如何处理。如果两个不相等的元素比较的结果为零，您首先应
该确信那就是您要的结果，然后记录行为。” 
 
 
(2)boolean equals(Object obj): 指示对象obj是否和比较器相等。 
 
“该方法覆写Object的equals()方法，检查的是Comparator实现的等同性，不是处于比较
状态下的对象。” 
  3.3. SortedSet接口 
 
“集合框架”提供了个特殊的Set接口：SortedSet，它保持元素的有序顺序。SortedSet接
口为集的视图(子集)和它的两端（即头和尾） 提供了访问方法。当您处理列表的子集时，更
改视图会反映到源集。此外，更改源集也会反映在子集上。发生这种情况的原因在于视图由两
端的元素而不是下标元素 指定，所以如果您想要一个特殊的高端元素（toElement）在子集中，
您必须找到下一个元素。 
 
添加到SortedSet实现类的元素必须实现Comparable接口，否则您必须给它的构造函数提供
一个Comparator接口的实现。TreeSet类是它的唯一一份实现。 
 
“因为集必须包含唯一的项，如果添加元素时比较两个元素导致了0返回值（通过Comparable
的compareTo()方法或Comparator 的compare()方法），那么新元素就没有添加进去。如果
两个元素相等，那还好。但如果它们不相等的话，您接下来就应该修改比较方法，让比较方法
和 equals() 的效果一致。” 
 
 
 
(1) Comparator comparator(): 返回对元素进行排序时使用的比较器，如果使用Comparable
接口的compareTo()方法对元素进行比较，则返回null 
 
(2) Object first(): 返回有序集合中第一个(最低)元素 
 
(3) Object last(): 返回有序集合中最后一个(最高)元素 
 
(4) SortedSet subSet(Object fromElement, Object toElement): 返回从fromElement(包
括)至toElement(不包括)范围内元素的SortedSet视图(子集) 
 
(5) SortedSet headSet(Object toElement): 返回SortedSet的一个视图，其内各元素皆小
于toElement 
 
(6) SortedSet tailSet(Object fromElement): 返回SortedSet的一个视图，其内各元素皆
大于或等于fromElement 
 
 
3.4. AbstractSet抽象类 
 
AbstractSet类覆盖了Object类的equals()和hashCode()方法，以确保两个相等的集返回相
同的哈希码。若两个集大小相等 且包含相同元素，则这两个集相等。按定义，集的哈希码是
集中元素哈希码的总和。因此，不论集的内部顺序如何，两个相等的集会有相同的哈希码。 
 
3.4.1. Object类 
 
(1) boolean equals(Object obj): 对两个对象进行比较，以便确定它们是否相同 
 
(2) int hashCode(): 返回该对象的哈希码。相同的对象必须返回相同的哈希码 
 
3.5. HashSet类类和TreeSet类 
 
“集合框架”支持Set接口两种普通的实现：HashSet和TreeSet(TreeSet实现SortedSet接
口)。在更多情况下，您会使用 HashSet 存储重复自由的集合。考虑到效率，添加到 HashSet 
的对象需要采用恰当分配哈希码的方式来实现hashCode()方法。虽然大多数系统类覆盖了 
Object中缺省的hashCode()和equals()实现，但创建您自己的要添加到HashSet的类时，别
忘了覆盖 hashCode()和equals()。 
 
当您要从集合中以有序的方式插入和抽取元素时，TreeSet实现会有用处。为了能顺利进行，
添加到TreeSet的元素必须是可排序的。 
 
3.5.1.HashSet类 
 
(1) HashSet(): 构建一个空的哈希集 
 
(2) HashSet(Collection c): 构建一个哈希集，并且添加集合c中所有元素 
 
(3) HashSet(int initialCapacity): 构建一个拥有特定容量的空哈希集 
 
(4) HashSet(int initialCapacity, float loadFactor): 构建一个拥有特定容量和加载因子
的空哈希集。LoadFactor是0.0至1.0之间的一个数 
 
3.5.2. TreeSet类 
 
(1) TreeSet():构建一个空的树集 
 
(2) TreeSet(Collection c): 构建一个树集，并且添加集合c中所有元素 
 
(3) TreeSet(Comparator c): 构建一个树集，并且使用特定的比较器对其元素进行排序 
 
“comparator比较器没有任何数据，它只是比较方法的存放器。这种对象有时称为函数对象。
 
函数对象通常在“运行过程中”被定义为匿名内部类的一个实例。” 
 
TreeSet(SortedSet s): 构建一个树集，添加有序集合s中所有元素，并且使用与有序集合s
相同的比较器排序 
 
3.6. LinkedHashSet类 
 
LinkedHashSet扩展HashSet。如果想跟踪添加给HashSet的元素的顺序，LinkedHashSet实
现会有帮助。 LinkedHashSet的迭代器按照元素的插入顺序来访问各个元素。它提供了一个
可以快速访问各个元素的有序集合。同时，它也增加了实现的代价，因为 哈希表元中的各个
元素是通过双重链接式列表链接在一起的。 
 
(1) LinkedHashSet(): 构建一个空的链接式哈希集 
 
(2) LinkedHashSet(Collection c): 构建一个链接式哈希集，并且添加集合c中所有元素 
 
(3) LinkedHashSet(int initialCapacity): 构建一个拥有特定容量的空链接式哈希集 
 
(4) LinkedHashSet(int initialCapacity, float loadFactor): 构建一个拥有特定容量和加
载因子的空链接式哈希集。LoadFactor是0.0至1.0之间的一个数 
 
“为优化HashSet空间的使用，您可以调优初始容量和负载因子。TreeSet不包含调优选项，
因为树总是平衡的。” 
  4. Map接口 
 
Map接口不是Collection接口的继承。Map接口用于维护键/值对(key/value pairs)。该接口
描述了从不重复的键到值的映射。 
 
 
 
(1) 添加、删除操作： 
 
 
Object put(Object key, Object value): 将互相关联的一个关键字与一个值放入该映像。如
果该关键字已经存在，那么与此关键字相关的新值将取代旧值。方法返回关键字的旧值，如果
关键字原先并不存在，则返回null 
 
Object remove(Object key): 从映像中删除与key相关的映射 
 
void putAll(Map t): 将来自特定映像的所有元素添加给该映像 
 
void clear(): 从映像中删除所有映射 
 
“键和值都可以为null。但是，您不能把Map作为一个键或值添加给自身。” 
 
(2) 查询操作： 
 
Object get(Object key): 获得与关键字key相关的值，并且返回与关键字key相关的对象，
如果没有在该映像中找到该关键字，则返回null 
 
boolean containsKey(Object key): 判断映像中是否存在关键字key 
 
boolean containsValue(Object value): 判断映像中是否存在值value 
 
int size(): 返回当前映像中映射的数量 
 
boolean isEmpty() ：判断映像中是否有任何映射 
 
(3) 视图操作 ：处理映像中键/值对组 
 
Set keySet(): 返回映像中所有关键字的视图集 
 
“因为映射中键的集合必须是唯一的，您用Set支持。你还可以从视图中删除元素，同时，关
键字和它相关的值将从源映像中被删除，但是你不能添加任何元素。” 
 
Collection values():返回映像中所有值的视图集 
 
“因为映射中值的集合不是唯一的，您用Collection支持。你还可以从视图中删除元素，同
时，值和它的关键字将从源映像中被删除，但是你不能添加任何元素。” 
 
Set entrySet(): 返回Map.Entry对象的视图集，即映像中的关键字/值对 
 
“因为映射是唯一的，您用Set支持。你还可以从视图中删除元素，同时，这些元素将从源映
像中被删除，但是你不能添加任何元素。” 
 
4.1. Map.Entry接口 
 
 
Map的entrySet()方法返回一个实现Map.Entry接口的对象集合。集合中每个对象都是底层
Map中一个特定的键/值对。 
 
 
 
通过这个集合的迭代器，您可以获得每一个条目(唯一获取方式)的键或值并对值进行更改。当
条目通过迭代器返回后，除非是迭代器自身的remove()方 法或者迭代器返回的条目的
setValue()方法，其余对源Map外部的修改都会导致此条目集变得无效，同时产生条目行为未
定义。 
 
(1) Object getKey(): 返回条目的关键字 
 
(2) Object getValue(): 返回条目的值 
 
(3) Object setValue(Object value): 将相关映像中的值改为value，并且返回旧值 
 
4.2. SortedMap接口 
 
“集合框架”提供了个特殊的Map接口：SortedMap，它用来保持键的有序顺序。 
 
 
 
SortedMap接口为映像的视图(子集)，包括两个端点提供了访问方法。除了排序是作用于映射
的键以外，处理SortedMap和处理SortedSet一样。 
 
添加到SortedMap实现类的元素必须实现Comparable接口，否则您必须给它的构造函数提供
一个Comparator接口的实现。TreeMap类是它的唯一一份实现。 
 
“因为对于映射来说，每个键只能对应一个值，如果在添加一个键/值对时比较两个键产生了
0返回值（通过Comparable的compareTo()方 法或通过Comparator的compare()方法），那
么，原始键对应值被新的值替代。如果两个元素相等，那还好。但如果不相等，那么您就应该
修改 比较方法，让比较方法和 equals() 的效果一致。” 
 
 
(1) Comparator comparator(): 返回对关键字进行排序时使用的比较器，如果使用
Comparable接口的compareTo()方法对关键字进行比较，则返回null 
 
(2) Object firstKey(): 返回映像中第一个(最低)关键字 
 
(3) Object lastKey(): 返回映像中最后一个(最高)关键字 
 
(4) SortedMap subMap(Object fromKey, Object toKey): 返回从fromKey(包括)至toKey(不
包括)范围内元素的SortedMap视图(子集) 
 
(5) SortedMap headMap(Object toKey): 返回SortedMap的一个视图，其内各元素的key皆
小于toKey 
 
(6) SortedSet tailMap(Object fromKey): 返回SortedMap的一个视图，其内各元素的key
皆大于或等于fromKey 
 
4.3. AbstractMap抽象类 
 
和其它抽象集合实现相似，AbstractMap 类覆盖了equals()和hashCode()方法以确保两个相
等映射返回相同的哈希码。如果两个映射大小相等、包含同样的键且每个键在这两个映射中对 
应的值都相同，则这两个映射相等。映射的哈希码是映射元素哈希码的总和，其中每个元素是
Map.Entry接口的一个实现。因此，不论映射内部顺序如何， 两个相等映射会报告相同的哈
希码。 
 
4.4. HashMap类和TreeMap类 
 
“集合框架”提供两种常规的 Map实现：HashMap和TreeMap (TreeMap实现SortedMap接口)。
在Map 中插入、删除和定位元素，HashMap 是最好的选择。但如果您要按自然顺序或自定义
顺序遍历键，那么TreeMap会更好。使用HashMap要求添加的键类明确定义了hashCode()和 
equals()的实现。 
 
这个TreeMap没有调优选项，因为该树总处于平衡状态。 
 
4.4.1. HashMap类 
 
为了优化HashMap空间的使用，您可以调优初始容量和负载因子。 
 
(1) HashMap(): 构建一个空的哈希映像 
 
(2) HashMap(Map m): 构建一个哈希映像，并且添加映像m的所有映射 
 
(3) HashMap(int initialCapacity): 构建一个拥有特定容量的空的哈希映像 
 
 
(4) HashMap(int initialCapacity, float loadFactor): 构建一个拥有特定容量和加载因子
的空的哈希映像 
 
4.4.2. TreeMap类 
 
TreeMap没有调优选项，因为该树总处于平衡状态。 
 
(1) TreeMap():构建一个空的映像树 
 
(2) TreeMap(Map m): 构建一个映像树，并且添加映像m中所有元素 
 
(3) TreeMap(Comparator c): 构建一个映像树，并且使用特定的比较器对关键字进行排序 
 
(4) TreeMap(SortedMap s): 构建一个映像树，添加映像树s中所有映射，并且使用与有序映
像s相同的比较器排序 
 
4.5. LinkedHashMap类 
 
LinkedHashMap扩展HashMap，以插入顺序将关键字/值对添加进链接哈希映像中。象
LinkedHashSet一样，LinkedHashMap内部也采用双重链接式列表。 
 
(1) LinkedHashMap(): 构建一个空链接哈希映像 
 
(2) LinkedHashMap(Map m): 构建一个链接哈希映像,并且添加映像m中所有映射 
 
(3) LinkedHashMap(int initialCapacity): 构建一个拥有特定容量的空的链接哈希映像 
 
(4) LinkedHashMap(int initialCapacity, float loadFactor): 构建一个拥有特定容量和加
载因子的空的链接哈希映像 
 
(5) LinkedHashMap(int initialCapacity, float loadFactor, 
 
boolean accessOrder): 构建一个拥有特定容量、加载因子和访问顺序排序的空的链接哈希映
像 
 
“如果将accessOrder设置为true,那么链接哈希映像将使用访问顺序而不是插入顺序来迭 
 
代各个映像。每次调用get或者put方法时，相关的映射便从它的当前位置上删除，然后放到
链接式映像列表的结尾处（只有链接式映像列表中的位置才会受到影响，哈希表元则不受影响。
哈希表映射总是待在对应于关键字的哈希码的哈希表元中）。” 
 
“该特性对于实现高速缓存的“删除最近最少使用”的原则很有用。例如，你可以希望将最常
访问的映射保存在内存中，并且从数据库中读取不经常访问的对象。 当你在表中找不到某个
映射，并且该表中的映射已经放得非常满时，你可以让迭代器进入该表，将它枚举的开头几个
 
映射删除掉。这些是最近最少使用的映射。” 
 
(6) protected boolean removeEldestEntry(Map.Entry eldest): 如果你想删除最老的映射，
则覆盖该方法，以便返回true。当某个映射已经添加给映像之后，便调用该方法。它的默认
实现方法返回false，表示默认条件 下老的映射没有被删除。但是你可以重新定义本方法，
以便有选择地在最老的映射符合某个条件，或者映像超过了某个大小时，返回true。 
 
4.6. WeakHashMap类 
 
WeakHashMap是Map的一个特殊实现，它使用WeakReference(弱引用)来存放哈希表关键字。
使用这种方式时，当映射的键在 WeakHashMap 的外部不再被引用时，垃圾收集器会将它回收，
但它将把到达该对象的弱引用纳入一个队列。WeakHashMap的运行将定期检查该队列，以便找
出新到达的 弱应用。当一个弱引用到达该队列时，就表示关键字不再被任何人使用，并且它
已经被收集起来。然后WeakHashMap便删除相关的映射。 
 
(1) WeakHashMap(): 构建一个空弱哈希映像 
 
(2) WeakHashMap(Map t): 构建一个弱哈希映像,并且添加映像t中所有映射 
 
(3) WeakHashMap(int initialCapacity): 构建一个拥有特定容量的空的弱哈希映像 
 
(4) WeakHashMap(int initialCapacity, float loadFactor): 构建一个拥有特定容量和加载
因子的空的弱哈希映像 
 
4.6. IdentityHashMap类 
 
IdentityHashMap也是Map的一个特殊实现。在这个类中，关键字的哈希码不应该由hashCode()
方法来计算，而应该由 System.identityHashCode方法进行计算(即使已经重新定义了
hashCode方法)。这是Object.hashCode根据对象 的内存地址来计算哈希码时使用的方法。
另外，为了对各个对象进行比较，IdentityHashMap将使用==，而不使用equals方法。 
 
换句话说，不同的关键字对象，即使它们的内容相同，也被视为不同的对象。IdentityHashMap
类可以用于实现对象拓扑结构转换 (topology-preserving object graph 
transformations)(比如实现对象的串行化或深度拷贝)，在进行转换时，需要一个“节点表”
跟踪那些已经处理过的对象的引用。即使碰巧有对 象相等，“节点表”也不应视其相等。另
一个应用是维护代理对象。比如，调试工具希望在程序调试期间维护每个对象的一个代理对象。 
 
“IdentityHashMap类不是一般意义的Map实现！它的实现有意的违背了Map接口要求通过
equals方法比较对象的约定。这个类仅使用在很少发生的需要强调等同性语义的情况。” 
 
(1) IdentityHashMap (): 构建一个空的全同哈希映像，默认预期最大尺寸为21 
 
“预期最大尺寸是映像期望把持的键/值映射的最大数目” 
 
 
(2) IdentityHashMap (Map m): 构建一个全同哈希映像,并且添加映像m中所有映射 
 
(3) IdentityHashMap (int expectedMaxSize): 构建一个拥有预期最大尺寸的空的全同哈希
映像。放置超过预期最大尺寸的键/值映射时，将引起内部数据结构的增长，有时可能很费时。

数据结构是以某种形式将数据组织在一起的集合，它不仅存储数据，还支持访问和处理数据的操作。Java提供了几个能有效地组织和操作数据的数据结构，这些数据结构通常称为Java集合框架。在平常的学习开发中，灵活熟练地使用这些集合框架，可以很明显地提高我们的开发效率，当然仅仅会用还是不够的，理解其中的设计思想与原理才能更好地提高我们的开发水平。下面是自己对Java集合框架方面的学习总结。

一、概述
二、Collection接口
   1.List
   2.Set
   3.Queue
三、Map接口
   1.HashMap实现原理
   2.其它Map实现类
四、其它集合类
五、总结

一、概述

在Java 2之前，Java是没有完整的集合框架的。它只有一些简单的可以自扩展的容器类，比如Vector，Stack，Hashtable等。这些容器类在使用的过程中由于效率问题饱受诟病，因此在Java 2中，Java设计者们进行了大刀阔斧的整改，重新设计，于是就有了现在的集合框架。需要注意的是，之前的那些容器类库并没有被弃用而是进行了保留，主要是为了向下兼容的目的，但我们在平时使用中还是应该尽量少用。

Java集合框架

从上面的集合框架图可以看到，Java集合框架主要包括两种类型的容器，一种是集合（Collection），存储一个元素集合，另一种是图（Map），存储键/值对映射。Collection接口又有3种子类型，List、Set和Queue，再下面是一些抽象类，最后是具体实现类，常用的有ArrayList、LinkedList、HashSet、LinkedHashSet、HashMap、LinkedHashMap等等。

二、Collection接口

Collection接口是处理对象集合的根接口，其中定义了很多对元素进行操作的方法，AbstractCollection是提供Collection部分实现的抽象类。下图展示了Collection接口中的全部方法。

Collection接口结构

其中，有几个比较常用的方法，比如方法add()添加一个元素到集合中，addAll()将指定集合中的所有元素添加到集合中，contains()方法检测集合中是否包含指定的元素，toArray()方法返回一个表示集合的数组。Collection接口有三个子接口，下面详细介绍。

1.List

List接口扩展自Collection，它可以定义一个允许重复的有序集合，从List接口中的方法来看，List接口主要是增加了面向位置的操作，允许在指定位置上操作元素，同时增加了一个能够双向遍历线性表的新列表迭代器ListIterator。AbstractList类提供了List接口的部分实现，AbstractSequentialList扩展自AbstractList，主要是提供对链表的支持。下面介绍List接口的两个重要的具体实现类，也是我们可能最常用的类，ArrayList和LinkedList。

ArrayList

通过阅读ArrayList的源码，我们可以很清楚地看到里面的逻辑，它是用数组存储元素的，这个数组可以动态创建，如果元素个数超过了数组的容量，那么就创建一个更大的新数组，并将当前数组中的所有元素都复制到新数组中。假设第一次是集合没有任何元素，下面以插入一个元素为例看看源码的实现。

1、方法add(E e)向集合中添加指定元素。

   public boolean add(E e) {
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        elementData[size++] = e;
        return true;
    }

2、此方法主要是确定将要创建的数组大小。

  private void ensureCapacityInternal(int minCapacity) {
        if (elementData =http://www.mamicode.com/= DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {"hljs-function">private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }

3、最后是创建数组，可以明显的看到先是确定了添加元素后的大小之后将元素复制到新数组中。

    private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = http://www.mamicode.com/Arrays.copyOf(elementData, newCapacity);>

LinkedList

同样，我们打开LinkedList的源文件，不难看到LinkedList是在一个链表中存储元素。

在学习数据结构的时候，我们知道链表和数组的最大区别在于它们对元素的存储方式的不同导致它们在对数据进行不同操作时的效率不同，同样，ArrayList与LinkedList也是如此，实际使用中我们需要根据特定的需求选用合适的类，如果除了在末尾外不能在其他位置插入或者删除元素，那么ArrayList效率更高，如果需要经常插入或者删除元素，就选择LinkedList。

2.Set

Set接口扩展自Collection，它与List的不同之处在于，规定Set的实例不包含重复的元素。在一个规则集内，一定不存在两个相等的元素。AbstractSet是一个实现Set接口的抽象类，Set接口有三个具体实现类，分别是散列集HashSet、链式散列集LinkedHashSet和树形集TreeSet。

散列集HashSet

散列集HashSet是一个用于实现Set接口的具体类，可以使用它的无参构造方法来创建空的散列集，也可以由一个现有的集合创建散列集。在散列集中，有两个名词需要关注，初始容量和客座率。客座率是确定在增加规则集之前，该规则集的饱满程度，当元素个数超过了容量与客座率的乘积时，容量就会自动翻倍。

下面看一个HashSet的例子。

/**
 * @author JackalTsc
 */
public class TestHashSet {

    public static void main(String[] args) {

        Set<String> set = new HashSet<>();

        set.add("11111");
        set.add("22222");
        set.add("33333");
        set.add("44444");
        set.add("22222");

        System.out.println(set.size());

        for (String e : set) {
            System.out.println(e);
        }
    }
}

从输出结果我们可以看到，规则集里最后有4个元素，而且在输出时元素还是无序的。

链式散列集LinkedHashSet

LinkedHashSet是用一个链表实现来扩展HashSet类，它支持对规则集内的元素排序。HashSet中的元素是没有被排序的，而LinkedHashSet中的元素可以按照它们插入规则集的顺序提取。

树形集TreeSet

TreeSet扩展自AbstractSet，并实现了NavigableSet，AbstractSet扩展自AbstractCollection，树形集是一个有序的Set，其底层是一颗树，这样就能从Set里面提取一个有序序列了。在实例化TreeSet时，我们可以给TreeSet指定一个比较器Comparator来指定树形集中的元素顺序。树形集中提供了很多便捷的方法。

下面是一个TreeSet的例子。

/**
 * @author JackalTsc
 */
public class TestSet {

    public static void main(String[] args) {

        TreeSet<Integer> set = new TreeSet<>();

        set.add(1111);
        set.add(2222);
        set.add(3333);
        set.add(4444);
        set.add(5555);

        System.out.println(set.first()); // 输出第一个元素
        System.out.println(set.lower(3333)); //小于3333的最大元素
        System.out.println(set.higher(2222)); //大于2222的最大元素
        System.out.println(set.floor(3333)); //不大于3333的最大元素
        System.out.println(set.ceiling(3333)); //不小于3333的最大元素

        System.out.println(set.pollFirst()); //删除第一个元素
        System.out.println(set.pollLast()); //删除最后一个元素
        System.out.println(set);
    }
}

3.Queue

队列是一种先进先出的数据结构，元素在队列末尾添加，在队列头部删除。Queue接口扩展自Collection，并提供插入、提取、检验等操作。

Queue接口结构

上图中，方法offer表示向队列添加一个元素，poll()与remove()方法都是移除队列头部的元素，两者的区别在于如果队列为空，那么poll()返回的是null，而remove()会抛出一个异常。方法element()与peek()主要是获取头部元素，不删除。

接口Deque，是一个扩展自Queue的双端队列，它支持在两端插入和删除元素，因为LinkedList类实现了Deque接口，所以通常我们可以使用LinkedList来创建一个队列。PriorityQueue类实现了一个优先队列，优先队列中元素被赋予优先级，拥有高优先级的先被删除。

/**
 * @author JackalTsc
 */
public class TestQueue {

    public static void main(String[] args) {

        Queue<String> queue = new LinkedList<>();

        queue.offer("aaaa");
        queue.offer("bbbb");
        queue.offer("cccc");
        queue.offer("dddd");

        while (queue.size() > 0) {
            System.out.println(queue.remove() + "");
        }
    }
}

三、Map接口

Map，图，是一种存储键值对映射的容器类，在Map中键可以是任意类型的对象，但不能有重复的键，每个键都对应一个值，真正存储在图中的是键值构成的条目。下面是接口Map的类结构。

接口Map的结构

从上面这张图中我们可以看到接口Map提供了很多查询、更新和获取存储的键值对的方法，更新包括方法clear()、put()、putAll()、remove()等等，查询方法包括containsKey、containsValue等等。Map接口常用的有三个具体实现类，分别是HashMap、LinkedHashMap、TreeMap。

1.HashMap

HashMap是基于哈希表的Map接口的非同步实现，继承自AbstractMap，AbstractMap是部分实现Map接口的抽象类。在平时的开发中，HashMap的使用还是比较多的。我们知道ArrayList主要是用数组来存储元素的，LinkedList是用链表来存储的，那么HashMap的实现原理是什么呢？先看下面这张图：

HashMap原理.jpg

在之前的版本中，HashMap采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当链表中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。而JDK1.8中，HashMap采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

下面主要通过源码介绍一下它的实现原理。

HashMap存储元素的数组

transient Node<K,V>[] table;

数组的元素类型是Node<K,V>，Node<K,V>继承自Map.Entry<K,V>，表示键值对映射。

static class Node<K,V> implements Map.Entry<K,V> {
        final int hash;
        final K key;
        V value;
        Node<K,V> next;

        //构造函数 ( Hash值键值下一个节点 )
        Node(int hash, K key, V value, Node<K,V> next) {
            this.hash = hash;
            this.key = key;
            this.value = http://www.mamicode.com/value;"hljs-keyword">this.next = next;
        }

        public final K getKey()        { return key; }
        public final V getValue()      { return value; }
        public final String toString() { return key + "=" + value; }

        public final int hashCode() {
            return Objects.hashCode(key) ^ Objects.hashCode(value);
        }

        public final V setValue(V newValue) {
            V oldValue = http://www.mamicode.com/value;"hljs-keyword">return oldValue;
        }

        public final boolean equals(Object o) {
            if (o == this)
                return true;
            if (o instanceof Map.Entry) {
                Map.Entry<?,?> e = (Map.Entry<?,?>)o;
                if (Objects.equals(key, e.getKey()) &&
                    Objects.equals(value, e.getValue()))
                    return true;
            }
            return false;
        }
    }

接下来我们看下HashMap的put操作。

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
        boolean evict) {
        Node<K,V>[] tab; Node<K,V> p; int n, i;
        if ((tab = table) == null || (n = tab.length) == 0)
            n = (tab = resize()).length;  //如果没有初始化则初始化table
        if ((p = tab[i = (n - 1) & hash]) == null)
            //这里 (n-1)&hash 是根据hash值得到这个元素在数组中的位置（即下标）
            tab[i] = newNode(hash, key, value, null);
        //如果数组该位置上没有元素，就直接将该元素放到此数组中的该位置上
        else {
            Node<K,V> e; K k;
            //第一节节点hash值同，且key值与插入key相同
            if (p.hash == hash &&
                ((k = p.key) == key || (key != null && key.equals(k))))
                e = p;
            else if (p instanceof TreeNode)
                //属于红黑树处理冲突
                e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
            else {
                /链表处理冲突
                for (int binCount = 0; ; ++binCount) {
                    if ((e = p.next) == null) {
                        p.next = newNode(hash, key, value, null);
                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
                        //新增节点后如果节点个数到达阈值，则将链表转换为红黑树
                            treeifyBin(tab, hash);
                        break;
                    }
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                        break;
                    p = e;
                }
            }
            //更新hash值和key值均相同的节点Value值
            if (e != null) { // existing mapping for key
                V oldValue = http://www.mamicode.com/e.value;"hljs-keyword">if (!onlyIfAbsent || oldValue =http://www.mamicode.com/= null)
                    e.value = http://www.mamicode.com/value;"hljs-keyword">return oldValue;
            }
        }
        ++modCount;
        if (++size > threshold)
            resize();
        afterNodeInsertion(evict);
        return null;
    }

接下来我们看下HashMap的get操作。

final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        if ((tab = table) != null && (n = tab.length) > 0 &&
            (first = tab[(n - 1) & hash]) != null) {
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
            if ((e = first.next) != null) {
                //如果第一个节点是TreeNode,说明采用的是数组+红黑树结构处理冲突
    //遍历红黑树，得到节点值
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                do {
                    if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && 
                                                       key.equals(k))))
                        return e;
                } while ((e = e.next) != null);
            }
        }
        return null;
    }

到这里HashMap的大致实现原理应该很清楚了，有几个需要关注的重点是：HashMap存储元素的方式以及根据Hash值确定映射在数组中的位置还有JDK 1.8之后加入的红黑树的。

在HashMap中要找到某个元素，需要根据key的hash值来求得对应数组中的位置。对于任意给定的对象，只要它的hashCode()返回值相同，那么程序调用hash(int h)方法所计算得到的hash码值总是相同的。我们首先想到的就是把hash值对数组长度取模运算，这样一来，元素的分布相对来说是比较均匀的。但是，“模”运算的消耗还是比较大的，在HashMap中，(n - 1) & hash 用于计算对象应该保存在table数组的哪个索引处。HashMap底层数组的长度总是2的n次方，当数组长度为2的n次幂的时候，(n - 1) & hash 算得的index相同的几率较小，数据在数组上分布就比较均匀，也就是说碰撞的几率小，相对的，查询的时候就不用遍历某个位置上的链表，这样查询效率也就较高了。

2.LinkedHashMap

LinkedHashMap继承自HashMap，它主要是用链表实现来扩展HashMap类，HashMap中条目是没有顺序的，但是在LinkedHashMap中元素既可以按照它们插入图的顺序排序，也可以按它们最后一次被访问的顺序排序。

3.TreeMap

TreeMap基于红黑树数据结构的实现，键值可以使用Comparable或Comparator接口来排序。TreeMap继承自AbstractMap，同时实现了接口NavigableMap，而接口NavigableMap则继承自SortedMap。SortedMap是Map的子接口，使用它可以确保图中的条目是排好序的。

在实际使用中，如果更新图时不需要保持图中元素的顺序，就使用HashMap，如果需要保持图中元素的插入顺序或者访问顺序，就使用LinkedHashMap，如果需要使图按照键值排序，就使用TreeMap。

四、其它集合类

上面主要对Java集合框架作了详细的介绍，包括Collection和Map两个接口及它们的抽象类和常用的具体实现类，下面主要介绍一下其它几个特殊的集合类，Vector、Stack、HashTable、ConcurrentHashMap以及CopyOnWriteArrayList。

1.Vector

前面我们已经提到，Java设计者们在对之前的容器类进行重新设计时保留了一些数据结构，其中就有Vector。用法上，Vector与ArrayList基本一致，不同之处在于Vector使用了关键字synchronized将访问和修改向量的方法都变成同步的了，所以对于不需要同步的应用程序来说，类ArrayList比类Vector更高效。

2.Stack

Stack，栈类，是Java2之前引入的，继承自类Vector。

3.HashTable

HashTable和前面介绍的HashMap很类似，它也是一个散列表，存储的内容是键值对映射，不同之处在于，HashTable是继承自Dictionary的，HashTable中的函数都是同步的，这意味着它也是线程安全的，另外，HashTable中key和value都不可以为null。

上面的三个集合类都是在Java2之前推出的容器类，可以看到，尽管在使用中效率比较低，但是它们都是线程安全的。下面介绍两个特殊的集合类。

4.ConcurrentHashMap

Concurrent，并发，从名字就可以看出来ConcurrentHashMap是HashMap的线程安全版。同HashMap相比，ConcurrentHashMap不仅保证了访问的线程安全性，而且在效率上与HashTable相比，也有较大的提高。关于ConcurrentHashMap的设计，我将会在下一篇关于并发编程的博客中介绍，敬请关注。

5.CopyOnWriteArrayList

CopyOnWriteArrayList，是一个线程安全的List接口的实现，它使用了ReentrantLock锁来保证在并发情况下提供高性能的并发读取。

五、总结

到这里，对于Java集合框架的总结就结束了，还有很多集合类没有在这里提到，更多的还是需要大家自己去查去用。通过阅读源码，查阅资料，收获很大。

• Java集合框架主要包括Collection和Map两种类型。其中Collection又有3种子类型，分别是List、Set、Queue。Map中存储的主要是键值对映射。

• 规则集Set中存储的是不重复的元素，线性表中存储可以包括重复的元素，Queue队列描述的是先进先出的数据结构，可以用LinkedList来实现队列。

• 效率上，规则集比线性表更高效。

• ArrayList主要是用数组来存储元素，LinkedList主要是用链表来存储元素，HashMap的底层实现主要是借助数组+链表+红黑树来实现。

• Vector、HashTable等集合类效率比较低但都是线程安全的。包java.util.concurrent下包含了大量线程安全的集合类，效率上有较大提升。

1、Java容器类库的简化图，下面是集合类库更加完备的图。包括抽象类和遗留构件（不包括Queue的实现）：

2、ArrayList初始化时不可指定容量，如果以new ArrayList()方式创建时，初始容量为10个；如果以new ArrayList(Collection c)初始化时，容量为c.size()*1.1，即增加10%的容量；当向ArrayList中添加一个元素时，先进行容器的容量调整，如果容量不够时，则增加至原来的1.5倍加1，再然后把元素加入到容器中，即以原始容量的0.5倍比率增加。

3、Vector：初始化时容量可以设定，如果以new Vector()方式创建时，则初始容量为10，超过容量时以2倍容量增加。如果以new Vector(Collection c)方式创建时，初始容量为c.size()*1.1，超过时以2倍容量增加。如果以new Vector(int initialCapacity, int capacityIncrement)，则以capacityIncrement容量增加。

4、集合特点：

• List：保证以某种特定插入顺序来维护元素顺序，即保持插入的顺序，另外元素可以重复。
• ArrayList：是用数组实现的，读取速度快，插入与删除速度慢（因为插入与删除时要移动后面的元素），适合于随机访问。
• Vector：功能与ArrayList几乎相同，也是以数组实现，添加，删除，读取，设置都是基于线程同步的。
• LinkedList：双向链表来实现，删除与插入速度快，读取速度较慢，因为它读取时是从头向尾（如果节点在链的前半部分），或尾向头（如果节点在链的后半部分）查找元素。因此适合于元素的插入与删除操作。
• Set：维持它自己的内部排序，随机访问不具有意义。另外元素不可重复。
• HashSet：是最常用的，查询速度最快，因为 内部以HashMap来实现，所以插入元素不能保持插入次序。
• LinkedHashSet：继承了HashSet，保持元素的插入次序，因为内部使用LinkedHashMap实现，所以能保持元素插入次序。
• TreeSet：基于TreeMap，生成一个总是处于排序状态的set，它实现了SortedSet接口，内部以 TreeMap来实现
• TreeMap：键以某种排序规则排序，内部以red-black（红-黑）树数据结构实现，实现了SortedMap接口，具体可参《RED-BLACK(红黑)树的实现TreeMap源码阅读 》
• HashMap: 以哈希表数据结构实现，查找对象时通过哈希函数计算其位置，它是为快速查询而设计的，其内部定义了一个hash表数组（Entry[] table），元素会通过哈希转换函数将元素的哈希地址转换成数组中存放的索引，如果有冲突，则使用散列链表的形式将所有相同哈希地址的元素串起来，可能通过查看HashMap.Entry的源码它是一个单链表结构。
• Hashtable:也是以哈希表数据结构实现的，解决冲突时与HashMap也一样也是采用了散列链表的形式，不过性能比HashMap要低。
• LinkedHashMap:继承HashMap，内部实体LinkedHashMap.Entry继承自HashMap.Entry，LinkedHashMap.Entry在HashMap.Entry的基础上新增了两个实体引用（Entry before, after），这样实体可以相互串链起来形成链，并且在LinkedHashMap中就定义了一个头节点（Entry header）用来指向循环双向链的第一个元素（通过after指向）与最后一个元素（通过before指向）。在添加一个元素时，先会通过父类HashMap将元素加入到hash表数组里，然后再会在链尾（header.before指向位置）添加（当然这一过程只是调整LinkedHashMap.Entry对象内部的before, after而已，而不是真真创建一个什么新的链表结构向里加那样）；删除先从hash表数组中删除，再将被删除的元素彻底的从双向链中断开。其实在链中添加与删除操作与LinkedList是一样的，可以参考《Java集合框架之LinkedList及ListIterator实现源码分析 》

5、Hashtable和HashMap的区别：

• Hashtable中的方法是同步的，而HashMap中的方法在缺省情况下是非同步的。在多线程应用程序中，我们应该使用Hashtable；而对于HashMap，则需要额外的同步机制。但HashMap的同步问题可通过Collections的一个静态方法得到解决：Map Collections.synchronizedMap(Map m)，当然与可以自己在使用地方加锁。

• 在HashMap中，可以允许null作为键，且只可以有一个，否则覆盖，但可以有一个或多个值为null。因为当get()方法返回null值时，即可以表示 HashMap中没有该键，也可以表示该键所对应的值为null，所以HashMap不能由get()方法来判断否存在某个键，而应该用containsKey()方法来判断；而Hashtable不允许null键与null值。

• HashTable使用Enumeration，HashMap使用Iterator。

• Hashtable是Dictionary的子类，HashMap是Map接口的一个实现类；

• HashTable中hash table数组默认大小是11，增加的方式是 int newCapacity = oldCapacity * 2 + 1;,即增加至2倍（而不是2倍加1，因为扩容是在增加元素前进行的，在扩容后会将新增元素放入容器中）。HashMap中hash数组的默认大小是16，而且一定是2的多少次方;另外两者的默认负载因子都是0.75。

• 求哈希地址与哈希地址转hash数组（Entry table[]）索引方法不同：

HashTable直接使用对象的hashCode：

Java代码  

1. int hash = key.hashCode();//直接使用键的hashCode方法求哈希值  
2. //哈希地址转hash数组索引，先使用最大正int数与，这样将负转正数，再与数组长度求模得到存入的hash数组索引位置  
3. int index = (hash & 0x7FFFFFFF) % tab.length;  

而HashMap重新计算hash值，而且用位运算&代替求模：

Java代码  

1. int hash = hash(k);  
2. int i = indexFor(hash, table.length);  
3.   
4. static int hash(Object x) {  
5. //以键本身的hash码为基础求哈希地址，但看不懂是什么意思  
6. 　　int h = x.hashCode();  
7. 　　h += ~(h << 9);  
8. 　　h ^= (h >>> 14);  
9. 　　h += (h << 4);  
10. 　　h ^= (h >>> 10);  
11. 　　return h;  
12. }  
13. static int indexFor(int h, int length) {  
14. 　　return h & (length-1);//将哈希地址转换成哈希数组中存入的索引号  
15. }  

  HashMap实现图：

6、集合中键值是否允许null小结

• List：可以有多个null，可以有重复值。
• HashSet：能插入一个null（因为内部是以 HashMap实现 ），忽略不插入重复元素。
• TreeSet：不能插入null （因为内部是以 TreeMap 实现 ） ，元素不能重复，如果待插入的元素存在，则忽略不插入，对元素进行排序。
• HashMap：允许一个null键与多个null值，若重复键，则覆盖以前值。
• TreeMap：不允许null键(实际上可以插入一个null键，如果这个Map里只有一个元素是不会报错的，因为一个元素时没有进行排序操作，也就不会报空指针异常，但如果插入第二个时就会立即报错)，但允许多个null值，覆盖已有键值。
• HashTable：不允许null键与null值(否则运行进报空指针异常)。也会覆盖以重复值。基于线程同步。

7、对List的选择：

• 对于随机查询与迭代遍历操作，数组比所有的容器都要快。
• 从中间的位置插入和删除元素，LinkedList要比ArrayList快，特别是删除操作。
• Vector通常不如ArrayList快，则且应该避免使用，它目前仍然存在于类库中的原因是为了支持过去的代码。
• 最佳实践：将ArrayList作为默认首选，只有当程序的性能因为经常从list中间进行插入和删除而变差的时候，才去选择LinkedList。当然了，如果只是使用固定数量的元素，就应该选择数组了。

8、对Set的选择：

• HashSet的性能总比TreeSet好(特别是最常用的添加和查找元素操作)。
• TreeSet存在的唯一原因是，它可以维持元素的排序状态，所以只有当你需要一个排好序的Set时，才应该使用TreeSet。
• 对于插入操作，LinkedHashSet比HashSet略微慢一点：这是由于维护链表所带来额外开销造成的。不过，因为有了链表，遍历LinkedHashSet会比HashSet更快。

9、对Map的选择：

• Hashtable和HashMap的效率大致相同(通常HashMap更快一点，所以HashMap有意取代Hashtable)。
• TreeMap通常比HashMap慢，因为要维护排序。
• HashMap正是为快速查询而设计的。
• LinkedHashMap比HashMap慢一点，因为它维护散列数据结构的同时还要维护链表。

10、Stack基于线程安全，Stack类是用Vector来实现的(public　class Stack extends Vector)，但最好不要用集合API里的这个实现栈，因为它继承于Vector，本就是一个错误的设计，应该是一个组合的设计关系。

11、Iterator对ArrayList(LinkedList)的操作限制：

• 刚实例化的迭代器如果还没有进行后移(next)操作是不能马上进行删除与修改操作的。
• 可以用ListIterator对集合连续添加与修改，但不能连续删除。
• 进行添加操作后是不能立即进行删除与修改操作的。
• 进行删除操作后可以进行添加，但不能进行修改操作。
• 进行修改后是可以立即进行删除与添加操作的。

12、当以自己的对象做为HashMap、HashTable、LinkedHashMap、HashSet 、LinkedHashSet 的键时，一定要重写hashCode ()与equals ()方法，因为Object的hashCode()是返回内存地址，且equals()方法也是比较内存地址，所以当要在这些hash集合中查找时，如果是另外new出的新对象是查不到的，除非重写这两个方法。因为AbstractMap类的containsKey(Object key)方法实现如下：

Java代码  

1. if (e.hash == hash && eq(k, e.key))//先比对hashcode，再使用equals  
2.     return true;  
3.   
4. static boolean eq(Object x, Object y) {  
5.     return x == y || x.equals(y);  
6. }  

String对象是可以准确做为键的，因为已重写了这两个方法。

因此，Java中的集合框架中的哈希是以一个对象查找另外一个对象，所以重写hasCode与equals方法很重要。

13、重写hashCode()与equals()这两个方法是针对哈希类，至于其它集合，如果要用public boolean contains(Object o)或containsValue(Object value)查找时，只需要实现equals()方法即可，他们都只使用对象的 equals方法进行比对，没有使用 hashCode方法。

14、TreeMap/TreeSet：放入其中的元素一定要具有自然比较能力(即要实现java.lang.Comparable接口)或者在构造TreeMap/TreeSet时传入一个比较器(实现java.util.Comparator接口)，如果在创建时没有传入比较器，而放入的元素也没有自然比较能力时，会出现类型转换错误(因为在没有较器时，会试着转成Comparable型)。

两种比较接口：

Java代码  

1. //自然比较器  
2. public interface java.lang.Comparable {  
3.     public int compareTo(Object o);  
4. }  
5.   
6. public interface java.util.Comparator {  
7.     int compare(Object o1, Object o2);  
8.     boolean equals(Object obj);  
9. }  

15、Collection或Map的同步控制：可以使用Collections类的相应静态方法来包装相应的集合类，使他们具线程安全，如public static Collection synchronizedCollection (Collection c)方法实质返回的是包装后的SynchronizedCollection子类，当然你也可以使用Collections的synchronizedList、synchronizedMap、synchronizedSet方法来获取不同的经过包装了的同步集合，其代码片断：

Java代码  

1. public class Collections {  
2.   
3.     //...  
4.   
5.     static Collection synchronizedCollection(Collection c, Object mutex) {  
6.         return new SynchronizedCollection(c, mutex);  
7.     }  
8.   
9.     public static List synchronizedList(List list) {  
10.         //...  
11.     }  
12.   
13.     static Set synchronizedSet(Set s, Object mutex) {  
14.         //...  
15.     }  
16.   
17.     public static Map synchronizedMap(Map m) {  
18.         return new SynchronizedMap(m);  
19.     }  
20.   
21.     //...  
22.     static class SynchronizedCollection implements Collection, Serializable {  
23.   
24.         Collection c; // 对哪个集合进行同步（包装）  
25.         Object mutex; // 对象锁，可以自己设置  
26.   
27.         //...  
28.         SynchronizedCollection(Collection c, Object mutex) {  
29.             this.c = c;  
30.             this.mutex = mutex;  
31.         }  
32.   
33.         public int size() {  
34.             synchronized (mutex) {  
35.                 return c.size();  
36.             }  
37.         }  
38.   
39.         public boolean isEmpty() {  
40.             synchronized (mutex) {  
41.                 return c.isEmpty();  
42.             }  
43.         }  
44.         //...  
45.     }  
46.   
47.     static class SynchronizedList extends SynchronizedCollection implements List {  
48.   
49.         List list;  
50.   
51.         SynchronizedList(List list, Object mutex) {  
52.             super(list, mutex);  
53.             this.list = list;  
54.         }  
55.   
56.         public Object get(int index) {  
57.             synchronized (mutex) {  
58.                 return list.get(index);  
59.             }  
60.         }  
61.         //...  
62.     }  
63.   
64.     static class SynchronizedSet extends SynchronizedCollection implements Set {  
65.         SynchronizedSet(Set s) {  
66.             super(s);  
67.         }  
68.         //...  
69.     }  
70.     //...  
71. }  

由包装的代码可以看出只是把原集合的相应方法放在同步块里调用罢了。

16、通过迭代器修改集合结构
在使用迭代器遍历集合时，我们不能通过集合本身来修改集合的结构（添加、删除），只能通过迭代器来操作，下面是拿对HashMap删除操作的测试，其它集合也是这样：

Java代码  

1. public static void main(String[] args) {  
2.  Map map = new HashMap();  
3.  map.put(1, 1);  
4.  map.put(2, 3);  
5.  Set entrySet = map.entrySet();  
6.  Iterator it = entrySet.iterator();  
7.  while (it.hasNext()) {  
8.   Entry entry = (Entry) it.next();  
9.   /* 
10.    * 可以通过迭代器来修改集合结构，但前提是要在已执行过 next 或 
11.    * 前移操作，否则会抛异常：IllegalStateException 
12.    */  
13.   // it.remove();  
14.   /* 
15.    * 抛异常：ConcurrentModificationException 因为通过 迭代 器操 
16.    * 作时，不能使用集合本身来修 
17.    * 改集合的结构 
18.    */  
19.   // map.remove(entry.getKey());  
20.  }  
21.  System.out.println(map);  
22. }

     

     

主要结构图：

Java 集合框架