HashMap ArrayList LinkedList

HashMap中的源码分析：

1.HashMap底层是基于数组+链表（升级成红黑树来实现的），通过数组实现的 Hash桶，默认数组的HASH桶长度为16个，负载因子为0.75，元素容量超过这个（长度*负载因子）就会扩容（resize()方法 ，扩1倍），链表升级成红黑树（treeifyBin（）方法）条件是hash桶大于64且桶中的元素长度大于等于8，再次扩容后重新处理原桶中的数据若桶中的元素小于等于6的时候将红黑树转回链表。

2.put新增，将key进行hash运算再取模，根据取模得到的索引落在指定的hash桶中，发生hash冲突时会将该值追加在链表中。（涉及到扩容+链表转树）

3.get查找，将key进行hash运算再取模找到对应的hash桶，如果是桶中的数据结构是链表通过循环链表来查询，如果是红黑树则查找树节点查询数据。

4.remove删除，将key进行hash运算再取模找到对应的hash桶，如果是桶中的数据结构是链表，遍历链表，找到key删除了重新移动链表的指针，如果是红黑树则查找树节点后删除节点，根据红黑树的结构实现一些旋转或节点变更。

ArrayList中的源码分析：

1.ArrayList底层是基于数组实现的，数组的空间是连续性的，所有查询比较快，一般用于读取，只需要get（下标索引）。数组中的默认容量为10，超过这个容量会开始扩容，每次扩容是上次的一半，使用 Arrays.copyOf（）方法到新的数组中，所以一般的增删需要扩容或者移动数组的下标索引， System.arraycopy()方法在大量的数据是非常耗性能的。（查找快，增删耗费时间（中间位置））

2.add新增操作，先判断是否需要扩容，不需要直接将索引+1，将索引赋值，若不需要扩容则时间复杂度为O(1），扩容则O(N）。

3.remove删除操作，时间复杂O(N），若需要释放空间调用list.trimToSize();

4.get查找操作，时间复杂O(1），根据索引将数据返回。

LinkedList中的源码分析：

1.LinkedList是通过双向链表去实现的，那么它可以被当作堆栈、队列或双端队列进行操作。并且其顺序访问非常高效，而随机访问效率比较低。

2.add 通过尾插法直接将元素插入队尾。

3.get 查找分尾部和头部查找，查最后和第一个元素复杂度为O(1）通过index查找看index所在位置，从尾部查和头部查找。

4.remove删除操作，如果为对象为“null”从头部遍历找到删除，非“null” 循环比对，调用unlink方法删除并移动指针。