Java集合源码学习（一）集合框架
原文地址：https://yq.aliyun.com/articles/38397?spm=5176.8091938.0.0.fRUCzz
集合框架
Java集合框架包含了大部分Java开发中用到的数据结构，主要包括
List列表、Set集合、Map映射、迭代器（Iterator、Enumeration）、工具类（Arrays、Collections）几个部分。
Collection系列
Collection接口
Collection是List、Set等集合高度抽象出来的接口，它包含了这些集合的基本操作，主要分为List和Set以及Queue。
List接口
List是一个继承于Collection的接口，即List是集合中的一种。List是有序的队列，List中的每一个元素都有一个索引；第一个元素的索引值是0，往后的元素的索引值依次+1。和Set不同，List中允许有重复的元素。
Set接口
Set是一个继承于Collection的接口，即Set也是集合中的一种。Set是没有重复元素的集合。
Queue接口
队列接口，拥有队列的性质,出队跟进队。
Iterator接口
Iterator集合的迭代器。集合可以通过Iterator去遍历集合中的元素。Iterator提供的API接口，包括：是否存在下一个元素、获取下一个元素、删除当前元素。
LinkedList类
LinkedList的本质是双向链表。
LinkedList继承于AbstractSequentialList，并且实现了
Dequeue接口。LinkedList包含两个重要的成员：header和size。
header是双向链表的表头，它是双向链表节点所对应的类Entry的实例。Entry中包含成员变量：previous,next,element。其中，previous是该节点的上一个节点，next是该节点的下一个节点，element是该节点所包含的值。
size是双向链表中节点的个数。
LinkedList支持多种遍历方式。不要采用随机访问的方式去遍历LinkedList，而采用foreach逐个遍历的方式。
对元素的插入、添加、移除操作，与ArrayList相比，LinkedList 更快，因为，当一个元素被添加到集合内部的任意位置时，LinkedList 不需要重新调整数组大小或者更新索引。
ArrayList类
ArrayList是一个数组列表，相当于动态数组。与Java中的数组相比，它的容量能动态增长。它继承于AbstractList，实现了List、RandomAccess、Cloneable、java.io.Serializable这些接口。
ArrayList实际上是通过一个数组去保存数据的。当我们构造ArrayList时；若使用默认构造函数，则ArrayList的默认容量大小是10。
当ArrayList容量不足以容纳全部元素时，ArrayList会重新设置容量：新的容量=“(原始容量x3)/2 + 1”。
Vector类
Vector是矢量队列，和ArrayList一样，它也是一个动态数组，由数组实现。但是ArrayList是非线程安全的，而Vector是线程安全的。
Stack类
Stack是栈，它继承于Vector。它的特性是：先进后出(FILO, First In Last Out)。
Map系列
Map接口
HashMap类
- HashMap基于哈希表的Map接口的实现。，它存储的内容是键值对(key-value)映射。
- HashMap继承于AbstractMap，实现了Map、Cloneable、java.io.Serializable接口。
- HashMap实际上是一个“链表散列”的数据结构，即数组和链表的结合体。
- HashMap的实现不是同步的，这意味着它不是线程安全的。它的key、value都可以为null。此外，HashMap中的映射不是有序的。
- HashMap是通过”拉链法”实现的哈希表。
TreeMap类
TreeMap是有序的散列表，它是通过红黑树实现的。它一般用于单线程中存储有序的映射。
WeakHashMap类
WeakHashMap也是基于“拉链法”实现的散列表，它一般也用于单线程程序中。相比HashMap，WeakHashMap中的键是“弱键”，当“弱键”被GC回收时，它对应的键值对也会被从WeakHashMap中删除；而HashMap中的键是强键。
HashTable类
- Hashtable也是基于“拉链法”实现的散列表。Hashtable的几乎所有函数都是同步的，即它是线程安全的，支持多线程。
- Hashtable的key、value都不可以为null，否则，会抛出异常NullPointerException。
Directionary抽象类
Enumeration接口
Collections和Arrays工具类
Arrays和Collections是用来操作数组、集合的两个工具类，
- 例如在ArrayList和Vector中大量调用了Arrays.Copyof()方法，而Collections中有很多静态方法可以返回各集合类的synchronized版本，即线程安全的版本。