在开始正文之前，先和大家聊点闲话：这是我关注简书以来写的第一篇笔记，当然我坚信这只是一个开始，以后会坚持写更多的笔记。有写笔记的想法是受周围的一些优秀伙伴们的影响，他们有些是我学习后台开发的启蒙老师，有些是我从未谋面却很敬佩的技术大神。他们都是这个行业里的佼佼者，当我看到如此优秀的他们仍然每天在工作之余更新技术博客，学习新技术，关注这个行业的飞速发展。我想作为一个刚入门的小白，唯一的优势就是有着一颗年轻的心和敢于拼搏和探索的朝气。为所有在路上拼搏努力的朋友加油，最有意义的事情总是需要我们通过自己的努力一步一步脚踏实地的去慢慢完成，坚持做成它，近乎完美的实现它，你就是最棒的。
==========================================================================
目录索引
1. java容器之间的关系简介
2.ArrayList源码中的一些细节总结
3.LinkendList源码中的一些细节总结
4.最后聊聊写时拷贝技术
1.1 java容器总框架图
注：图片来源 http://alexyyek.github.io/2015/04/06/Collection/
1.2 简单总结一下各容器之间的联系：
java容器中包含了List列表、Set集合、Map、工具类（包含一些迭代器、枚举类、条件类等）；按元素是否成对出现容器可分为两类：Colletion（独立元素构成的序列）和Map（以键值对组成的散列表），它们作为容器类的顶层接口分别实现了集合的基本操作：添加、删除、清空、遍历(读取)、是否为空、获取大小、是否保护某元素和散列表的基本操作：添加、查找、删除等等。
Colletion集合又按照元素是否随机存储被分为List（元素可以重复，按一定顺序保存起来）、Set（元素不可以重复，无序的保存所有元素）；我对这两种集合的抽象理解是：List是一整条，一整条的存储（不一定连续内存存储），而Set是被圈在一个“”大圆”中。具体关联可参考下面的图片：
注：图片来源 http://alexyyek.github.io/2015/04/06/Collection/
实现List接口的类有Arraylist、LinkedList、Vector、Stack。下面主要说说ArrayList和 LinkedList在JDK中的具体实现。
2. 1.ArrayList定义
ArrayList:是一个数组列表，相比数组的优势是它可以动态扩容 ，另外它是非线程安全的，当多个线程同时操作一个ArrayList对象时不保证同步。
2.2 transient关键字
阻止一个可以被序列化的类中某些变量不被序列化 ， 这样使得该属性在被反序列化时不会恢复以及持久化。例如，当反序列化对象——数据流（例如，文件）可能不存在，原因是你的对象中存在类型为java.io.InputStream的变量时，序列化一个输入流是毫无意义的，因为在反序列化时大多数情况下，输入流对象中都是不存在数据的。有些变量在使用该类的时候有作用 用完之后就没有作用了，持久化只能多占用点内存空间
transient Object[]elementData; // non-private to simplify nested class access
为什么不直接序列化elementData：
因为elementDate是一个缓存数组，大多数情况下 该数组 中有很多空闲的位置，并没有保存实际数据，序列化这些位置是没有意义的，为了节省空间ArrayList采用WriteObject 和 ReadObject两个方法进行序列化和反序列化，这两个方法会遍历临时数组中的每一个元素，并且把他们序列化，这样比直接序列化整个缓存空间要节省空间。
2.3 源码分析
ArrayList包含了两个重要的对象：elementData 和 size。
transient Object[] elementData : ArrayList容器，保存添加到ArrayList中的元素。
private int size ：The size of the ArrayList（元素个数）
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
解释一下它的默认长度为什么是Integer.MAX_VALUE-8：有些虚拟机在数组中保留了一些头信息。避免内存溢出！
2.3.1、在指定位置插入一个元素：
public void add(int index, E element) {
* //判断index是否合法
rangeCheckForAdd(index);
* //扩容，分为两步：首先判断添加元素后需要的数组空间是否超过数组本身长度
* //如果超过则需要扩容调用grow()
* ensureCapacityInternal(size + 1); // Increments modCount!!
* //从index开始后面的元素一次后移一位 复制实现移动
* System.arraycopy(elementData, index, elementData, index + 1,
* size - index);
* elementData[index] = element;
* size++;
* }
2.3.2、扩容
* private void grow(int minCapacity) {
* // overflow-conscious code
* int oldCapacity = elementData.length;
* //原数组长度加上原数组的长度的0.5倍 1.8将除法改进为右移位运算
* 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 = Arrays.copyOf(elementData, newCapacity);
* }
2.3.3、 modCount的作用：修改次数计数器
在一个改变ArrayList的结构的方法中需要对modCount进行自增，比如一些添加， 删除的方法中。在ArrayList的迭代器中需要使用这个字段，如果在迭代过程 中modCount发生了改变，（通常在多线程的环境下发生）在迭代的时候就会抛出ConcurrentModificationException异常。因为如果持续迭代读取的数据可能不是 最新的数据，已经过期 。
值的注意的一些细节：
* 1.遍历ArrayList时，使用随机访问(即通过索引序号访问)效率最高，而使用迭代器的效率最低
* 2.ListItr继承自Itr，添加了向前遍历的功能，当获取了iterator实例后，list就不可改变。当ArrayList使用了ListIterator()方法产生自身对应的Iterator后，只能使用Iterator自身的remove() 和add()方法来修改ArrayList的结构，因为这些方法对expectedModCount和modCount变量自动同步。
* 3.默认ArrayList的长度是10个，所以如果你要往list里添加20个元素肯定要扩充一次newCapacity 扩充 为原来的1.5倍，但和输入的minCapacity相比发现小于minCapacity，于是 newCapacity = minCapacity，所以只扩容一次。
* 4.Vector的实现基本上和ArrayList相同，不过ArrayList是线程不安全的 Vector是线程安全的
3.1 LinkedList定义
LinkedList和ArrayList一样都是实现了List接口，只是ArrayList是List接口的大小可变数组的实现，LinkedList是List接口链表的实现。基于链表实现的方式使得LinkedList在插入和删除时更优于ArrayList，而随机访问则比ArrayList逊色些。 LinkedList继承AbstractSequentialList（双向链表抽象类） 可以被当作堆栈、队列或双端队列进行操作。
3.2 很细节的一个方法：返回标记值为index的节点，从所有元素的最中间开始遍历
如果index的值小于size的一半则从头结点开始向中间查找 直到找到index为止
相反如果index的值大于size的一半则从尾节点开始向中间遍历 直到找到index为止
* Node node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
* Node x = first;
* for (int i = 0; i < index; i++)
* x = x.next;
* return x;
* } else {
* Node x = last;
* for (int i = size - 1; i > index; i--)
* x = x.prev;
* return x;
* }
* }
3.3 添加一整个集合
* 基本思路是首先定义两个临时节点前驱节点和后续节点，后继指向要插入的位置
* 连接index后面的所有节点，前驱节点一直指向index位置的前一个节点
* 每次要插入一个新节点，如果前驱节点为空，则将新插入的节点当做头结点
* 如果不为空，前驱节点的后继指向新节点，最后让前驱节点指向新插入的节点
* 直到遍历完所有要插入的节点后，在判断后继节点是否为空，如果是空，则将
* 最后一个节点指向前驱节点 如果不是空，直接将前驱节点和后继节点相连
* public boolean addAll(int index, Collectionc) {
* //若插入的位置小于0或者大于链表长度，则抛出IndexOutOfBoundsException异常
* checkPositionIndex(index);
* //首先将集合变为对象数组
* Object[] a = c.toArray();
* int numNew = a.length;//插入元素个数
* if (numNew == 0)
* return false;
* Node pred, succ; //定义临时前驱和后继
* if (index == size) { //如果在链表尾部插入
* 1.1 succ = null; //后继置空
* 1.2 pred = last; //前驱指向队尾元素last
* } else { //在指定位置插入
* succ = node(index); //后继指向该位置，后继一直连接当前位置后面的所有节点
* pred = succ.prev; //前驱指向前一个元素 前驱一直连接当前位置前面的所有节点
* }
* for (Object o : a) {
* @SuppressWarnings("unchecked") E e = (E) o;
* Node newNode = new Node<>(pred, e, null);//创建一个新节点，指定前驱，后继置空
* if (pred == null)//如果前驱不存在，说明当前要插入的位置是头
* first = newNode;//表头first指向此节点
* else
* pred.next = newNode;//前驱存在，则将其next指向新节点
* pred = newNode;//前驱向后移动，继续创建新节点
* }
* if (succ == null) {
* last = pred;//如果后继为空，说明当前插入的节点应该在链表尾部
* } else {
* //后继不为空，那么前驱节点和后继节点相连
* pred.next = succ;
* succ.prev = pred;
* }
* size += numNew;
* modCount++;
* return true;
* }
3.4 关于线程不安全的讨论：从fil-fast到写时拷贝
ArrayList和LinkedList共同的特点是他们都是线程不安全的， 在多个线程同时操作一个集合对象时就会发生数据脏读和数据覆盖等问题，同时再调用它们的迭代器时，都会记录当前的修改版本modCount的值，如果在迭代的过程中该值发生了变化，迭代器立马抛出一个ConcurrentModificationException异常。 像这种迭代时修改抛异常的情况被称为fil-fast机制；当然在在日常开发中我们是不希望看到这种情况发生的，多线程并发在迭代器遍历列表时只是简单的读取容器里面的数据而不做任何修改，凭什么不允许其他线程操作该列表对象，CPU大哥的时间可是很宝贵的，我们应该抓住CPU大哥的每一ms时间，让它做更多有意义的事，而不是做大量的空闲等待。
4、写时拷贝
基于上面的争议我们引入写时拷贝技术，注意它是一项技术，不归属于任何语言，也不归属于任何领域，只不过大多数情况下被运用到计算机的相关领域，比如Linux操作系统fork的内存分配，还有就是现在说的CopyOnWriteArrayList,该类在ArrayList的基础上引用了写时拷贝技术。
具体引用过程如下：对于多个线程操作同一个列表时，如果某个线程只是简单读取列表的值而不做任何修改，那么当前线程将不需要获得该对象的锁，这样就不会阻塞其他线程对该对象进行其他操作。当某个线程想要修改一个列表对象的元素时，该线程将会获得列表对象的锁 并且从主存中拿到当前数组对象的一份副本，所有的修改操作都是对副本而言的，对于主存中的实际数据并不会产生新的影响，在修改完成后将修改后的副本更新到主存 释放对象锁；则其他线程可以任意读取数组对象中的数据，但是不能修改，因为该对象的锁不能同时被两个线程所拥有。
需要注意的是这里的没有修改是片面的，也就是说当一个线程修改这个数组对象时 虽然操作的是一个副本，但是真正想修改的还是主存中的真实数据，只不过暂时还没有把修改的结果更新到主存中，所以在其他线程无锁读取数组元素时，有可能会读到已经过期的数据，只不过这个过期数据在主存中体现出了一种没有改变的假象 同样的原理，在CopyOnWriteArrayList中的迭代器也做了一定的优化，COWIterator是list迭代器的子类，它不支持获得迭代器的线程对数组元素做任何的修改，在迭代过程中其他线程对该数组的更新也不会体现在迭代器中，也就是说迭代器中的数组相当于是不可变的，获得迭代器的线程如果想修改数组元素必须获得对象的锁，而这又违背了多个线程同时迭代的初衷；换言之，COWIterator仅仅保证了在调用迭代器的同时其他线程在修改数据则不会抛出异常，仅此而已。
至此就是今天关于java容器类的一些学习心得，文章中可能会出现很多的错误，小白初犯还望各位大神谅解。下篇将会记录一片HashMap相关的一些笔记，敬请期待 !
