第一次写博客，有些知识点还是得记录下，不然过了段时间难免忘记曾经发现的问题，和是否解决过和研究到多深入（还不懂的一律用！！！表示）。我写的内容只记录到我最后发现知识点的认知，肯定是宏观不全或者说有讲解不到点上，但是没关系，认知是循序渐进的。
说到Java集合，第一反应是List，ArrayList，如下代码：
好，那就以这段代码为切入点，ArrayList有三种构造方法
看到这三种构造器想起一个问题，为什么创建容器的时候要指定大小？
第三种构造方法不做对比，跟进代码就知道这个方法相当于克隆或者是类型的互转。
直接说结论，因为我觉得这个很基础，没必要大废文章。指定大小创建容器时就初始化好数组的长度，不用后续add操作时对数组进行扩容，提高了使用效率。
说到扩容，ArrayList是怎么扩容的？
直接跟进add方法：
minCapacity：当前add操作需要的最小容量大小
newCapacity：新的容量大小newCapacity = oldCapacity +oldCapacity /2，那就是扩容1.5倍
if (newCapacity - minCapacity <0) 这个if暂时认为是就只是判断一下，因为我现在觉得这个判断是不会成立的。
Arrays.copyOf调用了两个本地方法，一个是创建newCapacity 大小的数组，一个是复制数组。
好，再来看下add的另一个重载方法
rangeCheckForAdd是校验index的值是不是在0到size之间（都是闭区间），否则会报错，这么做的目的只有一个，前面的必须填满，否则将增加维护逻辑。
System.arraycopy是将下标为index开始的区间值复制到从index+1开始，也就是下标为index到size的值右移一位。
问题点记录！！！arraycopy的本地方法是怎么实现的尚未可知，可以猜想是遍历赋值，但是是不是不知道。
好，有add就有remove，直接看remove怎么实现的。
一看很清晰，就是将下标为index+1开始的区间值的全部复制到index开始，也就是左移一位，然后再将多余的最后一个设为null。另一个重载方法如下，代码逻辑很清晰
好，四种读写操作讲完，那么问题来了，四种操作的时间复杂度是多少？答案我就不写了，如果真的看懂了就能知道，死记是记不住的，get、set就不说了。
接着说LinkedList吧，记住下面几个结论。（我发现写博客很浪费时间，还不如直接点进源码看看就什么都知道了）
1、遍历不要用for(int i = 0;i<length;i++)这种形式，LinkedList是用链表实现，所以index不能确定位置，要用迭代器或者foreach。
2、ArrayList的get、set快，直接数组定位。至于add不一定，ArrayList是数组尾部插入，除了要扩容没什么损耗，而LinkedList需要new Node，remove正常来说是LinkedList快。
接着说Map吧，直接看put方法
hash方法的作用是将hashcode的高区间的16位和低区间的16位做异或运算，目的是为了降低hash冲突。
好，看完图，问题来了，嘿嘿嘿。。
1、为什么数组槽被占用后要用链表结构，不继续用数组结构？
数组和链表都需要遍历，时间复杂度都是O(n)，增删数组需要扩容加复制。
2、为什么链表长度大于8就要进行转树结构处理？为什么是8？（图片的7有误，binCount是从0开始）
为什么是8，好问题，我也不知道，找找注释，嗯..大概意思是说和数据分布概率有关系，关键字，follows a Poisson distribution
这个是what？？？不管，以后再说，这里记下！！！
3、这个modCount变量是干嘛用的？
迭代器使用的，有关于fail-fast概念。
好接着讲resize()方法
resize方法是初始化和扩容方法，这部分看完可以得到这几个信息
1、数组最大容量为MAXIMUM_CAPACITY =1 <<30，左移31位会超出int的大小。
2、数组是两倍扩容，newCap = oldCap <<1。
3、初始数组容量为DEFAULT_INITIAL_CAPACITY =1 <<4，初始阈值threshold为DEFAULT_LOAD_FACTOR *DEFAULT_INITIAL_CAPACITY，即0.75*16 = 12。
4、threshold也是两倍扩容，newThr = oldThr <<1; // double threshold，可以得出threshold = 0.75*newCap依旧不变。
剩下的就是扩容之后结构的重建了，为啥要重建？因为计算元素的下标 = hash & (n-1) ,n是数组长度，长度发生变化，下标值肯定也是发生变化了。
这部分有两个难点，一个是树结构数据的转移，这个暂时看不懂，后续看下，先不管！！！
另外一个是链表的元素转移，那就讲讲链表的元素的转移。
do while是遍历原来链表元素，假如让我来实现，我会遍历链表，得到每一个元素的index = hash & （newCap -1)，然后拿到newTab[index] 的值去做判断，链表就插入尾部，树就进行树结构的插入。但是发现hashmap没有这么处理，看懂之后才发现hashmap的处理更加简洁，这就是值得借鉴的地方。
(e.hash & oldCap) ==0 这是什么意思呢？看下数据就很清晰了，假设由16扩容到32
我们计算下标是这么计算的，发现规律没有，因为相同key的hash值是相同的，扩容前后和扩容后的下标定位差异是在倒数第5位，那么也就是说原数组长度的二进制数的最高位所对应的hash值对应的位置的值是0说明扩容后的数组下标不变（这句话有点绕，就看图的hash的倒数第5位），如果是1说明扩容后的元素下标为原下标值+原数组长度（就是01011+10000）。
好这里搞懂了，那再来看为啥是oldCap，很简单，oldCap = 16 = 10000就是拿到最高位判断hash值对应位置是0还是1，是0那就是说元素下标扩容前后不变，为1就是newindex = 原下标值+原数组长度。
对比下我的思路和HashMap的解决思路，比我的思路少了一步拿到newTab[index] 的值然后判断再去做插入。
