一、前言

Java 容器集合框架
上面这幅图是Java集合框架涉及到的类的继承关系，从集合类的角度来看，它分为两个大类：Collection和Map。

1.1 Collection

Collection是List和Set抽象出来的接口，它包含了这些集合的基本操作。

(1) List

List接口通常表示一个列表（数组、队列、链表，栈等），其中的元素可以重复，常用的实现类为ArrayList、LinkedList和Vector。

(2) Set

Set接口通常表示一个集合，集合中的元素不允许重复（通过hashCode和equals函数保证），常用的实现类有HashSet和TreeSet，HashSet是通过Map中的HashMap来实现的，而TreeSet则是通过Map中的TreeMap实现的，另外TreeSet还实现了SortedSet接口，因此是有序的集合。

(3) List 和 Set 的区别

• Set接口存储的是无序的、不重复的数据
• List接口存储的是有序的、可以重复的数据
• Set检索效率低，删除和插入效率高，插入和删除不会引起元素位置改变。
• List查找元素效率高，删除和插入效率低，List和数组类似，可以动态增长，根据实际存储的长度自动增长List的长度。

(4) 使用的设计模式

抽象类AbstractCollection、AbstractList和AbstractSet分别实现了Collection、List和Set接口，这就是在Java集合框架中用的很多的适配器设计模式，用这些抽象类去实现接口，在抽象类中实现接口中的若干或全部方法，这样下面的一些类只需直接继承该抽象类，并实现自己需要的方法即可，而不用实现接口中的全部抽象方法。

1.2 Map

Map是一个映射接口，其中的每个元素都是一个Key-Value键值对，同样抽象类AbstractMap通过适配器模式实现了Map接口的大部分函数，TreeMap、HashMap和WeakHashMap等实现类都通过继承AbstractMap来实现。

1.3 Iterator

Iterator是遍历集合的迭代器，它可以用来遍历Collection，但是不能用来遍历Map。Collection的实现类都实现了iterator()函数，它返回一个Iterator对象，用来遍历集合，ListIterator则专门用来遍历List。而Enumeration则是JDK 1.0时引入的，作用与Iterator相同，但它的功能比Iterator要少，它只能在Hashtable、Vector和Stack中使用。

1.4 Arrays 和 Collections

Arrays和Collections是用来操作数组、集合的两个工具类，例如在ArrayList和Vector中大量调用了Arrays.Copyof()方法，而Collections中有很多静态方法可以返回各集合类的synchronized版本，即线程安全的版本，当然了，如果要用线程安全的集合类，首选concurrent并发包下的对应的集合类。

二、ArrayList

ArrayList是基于一个能动态增长的数组实现，ArrayList并不是线程安全的，在多线程的情况下可以考虑使用Collections.synchronizedList(List T)函数返回一个线程安全的ArrayList类，也可以使用并发包下的CopyOnWriteArrayList类。

ArrayList<T>类继承于AbstractList<T>，并实现了以下四个接口：

• List<T>
• RandomAccess：支持快速随机访问
• Cloneable：能够被克隆
• Serializable：支持序列化

ArrayList 的扩容

由于ArrayList是基于数组实现的，因此当我们通过addXX方法向数组中添加元素之前，都要保证有足够的空间容纳新的元素，这一过程是通过ensureCapacityInternal来实现的，传入的参数为所要求的数组容量：

• 如果当前数组为空，并且要求的容量小于10，那么将要求的容量设为10
• 接着尝试将数组大小扩充为当前大小的2.5倍
• 如果仍然无法满足要求，那么将数组大小设为要求的容量
• 如果要求的容量大于预设的整型的最大值减8，那么调用hugeCapacity方法，将数组的容量设为整型的最大值
• 最后，调用Arrays.copyOf将原有数组中的元素复制到新的数组中。

Arrays.copyOf最终会调用到System.arraycopy()方法。该Native函数实际上最终调用了C语言的memmove()函数，因此它可以保证同一个数组内元素的正确复制和移动，比一般的复制方法的实现效率要高很多，很适合用来批量处理数组，Java强烈推荐在复制大量数组元素时用该方法，以取得更高的效率。

ArrayList 转换为静态数组

ArrayList中提供了两种转换为静态数组的方法：

• Object[] toArray()
  该方法有可能会抛出java.lang.ClassCastException异常，如果直接用向下转型的方法，将整个ArrayList集合转变为指定类型的Array数组，便会抛出该异常，而如果转化为Array数组时不向下转型，而是将每个元素向下转型，则不会抛出该异常，显然对数组中的元素一个个进行向下转型，效率不高，且不太方便。
• T[] toArray(T[] a)
  该方法可以直接将ArrayList转换得到的Array进行整体向下转型，且从该方法的源码中可以看出，参数a的大小不足时，内部会调用Arrays.copyOf方法，该方法内部创建一个新的数组返回，因此对该方法的常用形式如下：

public static Integer[] vectorToArray2(ArrayList<Integer> v) {    
    Integer[] newText = (Integer[])v.toArray(new Integer[0]);    
    return newText;    
}   

元素访问方式

ArrayList基于数组实现，可以通过下标索引直接查找到指定位置的元素，因此查找效率高，但每次插入或删除元素，就要大量地移动元素，插入删除元素的效率低。

在查找给定元素索引值等的方法中，源码都将该元素的值分为null和不为null两种情况处理，ArrayList中允许元素为null。

三、LinkedList

LinkedList是基于双向循环链表实现的，除了可以当作链表来操作外，它还可以当作栈，队列和双端队列来使用。

LinkedList同样是非线程安全的，在多线程的情况下可以考虑使用Collections.synchronizedList(List T)函数返回一个线程安全的LinkedList类，LinkedList继承于AbstractSequentialList类，同时实现了以下四个接口：

• List<T>
• Deque和Queue：双端队列
• Cloneable：支持克隆操作
• Serializable：支持序列化

链表节点

LinkedList的实现是基于双向循环链表的，且头结点voidLink中不存放数据，所以它也不存在扩容的方法，只需改变节点的指向即可，每个链表节点包含该节点的数据，以及前驱和后继节点的引用，其定义如下所示：

    private static final class Link<ET> {
        //该节点的数据。
        ET data;
        //前驱节点和后继节点。
        Link<ET> previous, next;
        Link(ET o, Link<ET> p, Link<ET> n) {
            data = o;
            previous = p;
            next = n;
        }
    }

查找和删除操作

当需要根据位置寻找对应节点的数据时，会先比较待查找位置和链表的大小，如果小于一半，那么从头节点的后继节点开始向后寻找，反之则从头结点的前驱节点开始往前寻找，因此对于查找操作来说，它的效率很低，但是向头尾节点插入和删除数据的效率较高。

四、Vector

Vector也是基于数组实现的，其容量能够动态增长。它的许多实现方法都加入了同步语句，因此是 线程安全 的。

Vector继承于AbstractList类，并且实现了下面四个接口：

• List<E>
• RandomAccess：支持随机访问
• Cloneable, java.io.Serializable：支持Clone和序列化。

Vector的实现大体和ArrayList类似，它有以下几个特点：

• Vector有四个不同的构造方法，无参构造方法的容量为默认值10，仅包含容量的构造方法则将容量增长量置为0。
• 当Vector的容量不足以容纳新的元素时，将进行扩容操作。首先判断容量增长值是否为0，如果为0，那么就将新容量设为旧容量的两倍，否则就设置新容量为旧容量加上容量增长值。假如新容量还不够，那么就直接设置新量容量为传入的参数。
• 在存入和读取元素时，会根据元素值是否为null进行处理，也就是说，Vector允许元素为null。

五、HashSet

HashSet具有以下特点：

• 不能保证元素的排列顺序，顺序有可能发生变化
• 不是同步的
• 集合元素可以是null，但只能放入一个null

当向HashSet集合中存入一个元素时，HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值，然后根据hashCode值来决定该对象在HashSet中存储位置。
简单的说，HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等，并且两个对象的hashCode()方法返回值相等。

注意，如果要把一个对象放入HashSet中，重写该对象对应类的equals方法，也应该重写其hashCode()方法。其规则是如果两个对象通过equals方法比较返回true时，其hashCode也应该相同。另外，对象中用作equals比较标准的属性，都应该用来计算hashCode的值。

六、TreeSet

TreeSet是SortedSet接口的唯一实现类，TreeSet可以确保集合元素处于排序状态。TreeSet支持两种排序方式，自然排序 和 定制排序，其中自然排序为默认的排序方式。

向TreeSet中加入的应该是同一个类的对象。TreeSet判断两个对象不相等的方式是两个对象通过equals方法返回false，或者通过CompareTo方法比较没有返回0。

自然排序

自然排序使用要排序元素的CompareTo(Object obj)方法来比较元素之间大小关系，然后将元素按照升序排列。
Java提供了一个Comparable接口，该接口里定义了一个compareTo(Object obj)方法，该方法返回一个整数值，实现了该接口的对象就可以比较大小。

obj1.compareTo(obj2)方法如果返回0，则说明被比较的两个对象相等，如果返回一个正数，则表明obj1大于obj2，如果是负数，则表明obj1小于obj2。如果我们将两个对象的equals方法总是返回true，则这两个对象的compareTo方法返回应该返回0.

定制排序

自然排序是根据集合元素的大小，以升序排列，如果要定制排序，应该使用Comparator接口，实现int compare(T o1,T o2)方法。

• TreeSet是二叉树实现的，Treeset中的数据是自动排好序的，不允许放入null值。
• HashSet是哈希表实现的，HashSet中的数据是无序的，可以放入null，但只能放入一个null，两者中的值都不能重复，就如数据库中唯一约束。
• HashSet要求放入的对象必须实现hashCode()方法，放入的对象，是以hashcode()码作为标识的，而具有相同内容的String对象，hashcode是一样，所以放入的内容不能重复。但是同一个类的对象可以放入不同的实例 。

七、HashMap

HashMap是基于哈希表实现的，每一个元素都是一个key-value对，其内部通过单链表解决冲突问题，容量不足时，同样会自动增长。HashMap是非线程安全的，只是用于单线程环境下，多线程环境下可以采用并发包下的ConcurrentHashMap。

HashMap继承于AbstractMap，同时实现了Cloneable和Serializable接口，因此，它支持克隆和序列化。

HashMap 的整体结构

HashMap是基于数组和链表来实现的：

它的基本原理为：

• 首先根据Key的hashCode方法，计算出在数组中的坐标。

//计算 Key 的 hash 值。
int hash = sun.misc.Hashing.singleWordWangJenkinsHash(key);
//根据 Key 的 hash 值和链表的长度来计算下标。
int i = indexFor(hash, table.length);

• 判断在数组的当前位置是否已经有元素，如果没有，那么就将Key/Value封装成HashMapEntry数据结构，并将其作为数组在该位置上的元素。否则就先从头节点开始遍历该链表，如果 满足下面的两个条件，那么就替换链表该节点的Value

//Value 替换的条件
//条件1：hash 值完全相同
//条件2：key 指向同一块内存地址 或者 key 的 equals 方法返回为 true
(e.hash == hash && ((k = e.key) == key || key.equals(k)))

• 遍历完整个链表都没有找到可替代的节点，那么将这个新的HashMapEntry作为链表的头节点，并且也是数组在该位置上的元素，原先的头节点则作为它的后继节点。

HashMapEntry 的数据结构

HashMapEntry的定义如下：

static class HashMapEntry<K,V> implements Map.Entry<K,V> {
        //Key
        final K key;
        //Value
        V value;
        //后继节点。
        HashMapEntry<K,V> next;
        //如果 Key 不为 null ，那么就是它的哈希值，否则为0。
        int hash;
        //....
}

元素写入

在第一小节中，我们简要的计算了HashMap的整体结构，由此我们可以推断出在设计的时候应当尽可能地使元素均匀分布，使得数组每个位置上的链表尽可能地短，避免从链表头结点开始遍历的过程。

而元素是否分布均匀就取决于根据Key的Hash值计算数组下标的过程，首先我们看一下Hash值的计算，这里首先调用对象的hashCode方法，再通过二次Hash算法获得一个Hash值：

    public static int secondaryHash(Object key) {
        return secondaryHash(key.hashCode());
    }

    private static int secondaryHash(int h) {
        h += (h <<  15) ^ 0xffffcd7d;
        h ^= (h >>> 10);
        h += (h <<   3);
        h ^= (h >>>  6);
        h += (h <<   2) + (h << 14);
        return h ^ (h >>> 16);
    }

之后，再通过这个计算出来Hash值 与上当前数组长度减一 进行取余，获得对应的数组下标：

hash & (tab.length - 1)

由于HashMap在扩容的时候，保证了数组的长度适中为2的n幂，因此length - 1的二进制表示始终为全1，因此进行&操作的结果既保证了最终的结果不会超过数组的长度范围，同时也保证了两个Hash值相同的元素不会映射到数组的同一位置，再加上上面二次Hash的过程加上了高位的计算优化，从而使得数据的分布尽可能地平均。

元素读取

理解了上面存储的过程，读取自然也就很好理解了，其实通过Key计算数组下标，遍历该位置上数组元素的链表进行查找的过程。

扩容

当HashMap中的元素越来越多的时候，hash冲突的几率也就越来越高，因为数组的长度是固定的，所以为了提高查询的效率，就要对HashMap的数组进行扩容。

当HashMap中的元素个数超过数组大小 * loadFactor时，loadFactor的默认值为0.75，就会进行数组扩容，扩容后的大小为原先的2倍，然后重新计算每个元素在数组中的位置，原数组中的数据必须重新计算其在新数组中的位置，并放进去。

扩容是一个相当耗费性能的操作，因此如果我们已经预知HashMap中元素的个数，那么预设元素的个数能够有效的提高HashMap的性能。

Fail-Fast 机制

HashMap并不是线程安全的，因此如果在使用迭代器的过程中有其他线程修改了map，那么将抛出ConcurrentModificationException，这就是所谓fail-fast策略。

这一策略在源码中的实现是通过modCount域，modCount顾名思义就是修改次数，对HashMap内容的修改都将增加这个值，那么在迭代器初始化过程中会将这个值赋给迭代器的expectedModCount。

在迭代过程中，判断modCount跟expectedModCount是否相等，如果不相等就表示已经有其他线程修改了Map，那么就会通过下面的方法抛出异常：

    HashMapEntry<K, V> nextEntry() {
        if (modCount != expectedModCount)
            throw new ConcurrentModificationException();
           //省略...
    }

modCount声明为volatile，保证了多线程情况下的内存可见性。

在迭代器创建之后，如果从结构上对映射进行修改，除非通过迭代器本身的remove方法，其他任何时间任何方式的修改，迭代器都将抛出ConcurrentModificationException。因此，面对并发的修改，迭代器很快就会完全失败，而不保证在将来不确定的时间发生任意不确定行为的风险

八、HashTable

HashTable经常用来和HashMap进行比较，前者是线程安全的，而后者则不是，其实HashTable要比HashMap出现得要早，它实现线程安全的原理并没有什么高级的地方，只不过是在写入和读取时加上了synchronized关键字用于同步，并且也不推荐使用了，因为在并发包中提供了更好的解决方案ConcurrentHashMap，它内部的实现比较复杂，之后我们再通过一篇文章进行分析。

这里简单地总结一下它和HashMap之间的区别：

• HashTable基于Dictionary类，而HashMap是基于AbstractMap。Dictionary是任何可将键映射到相应值的类的抽象父类，而AbstractMap基于 Map接口的实现，它以最大限度地减少实现此接口所需的工作。
• HashMap的key和value都允许为null，而Hashtable的key和value都不允许为null。HashMap遇到key为null的时候，调用putForNullKey方法进行处理，而对value没有处理，Hashtable遇到null，直接返回 NullPointerException。
• Hashtable方法是同步，而HashMap则不是。我们可以看一下源码，Hashtable中的几乎所有的public的方法都是synchronized的，而有些方法也是在内部通过synchronized代码块来实现。所以有人一般都建议如果是涉及到多线程同步时采用HashTable，没有涉及就采用HashMap，但是在 Collections类中存在一个静态方法：synchronizedMap()，该方法创建了一个线程安全的Map对象，并把它作为一个封装的对象来返回。

九、TreeMap

TreeMap是一个有序的key-value集合，它是通过 红黑树 实现的。TreeMap继承于AbstractMap，所以它是一个Map，即一个key-value集合。TreeMap实现了NavigableMap接口，意味着它支持一系列的导航方法，比如返回有序的key集合。TreeMap实现了Cloneable和Serializable接口，意味着它可以被Clone和序列化。

TreeMap基于红黑树实现，该映射根据其键的自然顺序进行排序，或者根据创建映射时提供的 Comparator进行排序，具体取决于使用的构造方法。TreeMap的基本操作containsKey、get、put和remove的时间复杂度是log(n) ，另外，TreeMap是非同步的， 它的iterator方法返回的迭代器是Fail-Fastl的。

十、LinkedHashMap

• LinkedHashMap是HashMap的子类，与HashMap有着同样的存储结构，但它加入了一个双向链表的头结点，将所有put到LinkedHashmap的节点一一串成了一个双向循环链表，因此它保留了节点插入的顺序，可以使节点的输出顺序与输入顺序相同。
• LinkedHashMap可以用来实现LRU算法。
• LinkedHashMap同样是非线程安全的，只在单线程环境下使用。

十一、LinkedHashSet

LinkedHashSet是具有可预知迭代顺序的Set接口的哈希表和链接列表实现。此实现与HashSet的不同之处在于，后者维护着一个运行于所有条目的双重链接列表。此链接列表定义了迭代顺序，该迭代顺序可为插入顺序或是访问顺序。

LinkedHashSet的实现：对于LinkedHashSet而言，它继承与HashSet、又基于LinkedHashMap来实现的。