ArrayList
一.构造
List list = new?ArrayList();
默认构造一个初始容量为10的空列表
List list = new?ArrayList(100);
按指定的容量构造列表,如果指定为0和默认的一致,如果指定的数小于0异常
二.扩容
调用add方法时会判断是否需要进行扩容,判断条件为:要存放的数据量超过了数组的长度
minCapacity -elementData.length >0
1.如果采用默认构造,添加第一个元素时，会直接把我们需要的容量改为10
2.超过10以后,按照1.5倍进行扩容
3.如果minCapacity >MAX_ARRAY_SIZE) ?Integer.MAX_VALUE :MAX_ARRAY_SIZE
扩容成功后 最终会复制旧的数组中的数据项到新的扩充后的数组中?
elementData = Arrays.copyOf(elementData, newCapacity);
MAX_ARRAY_SIZE的说明：?MAX_ARRAY_SIZE = Integer.MAX_VALUE -8;
要分配的最大数组大小。一些VM在数组中保留一些头字。尝试分配较大的阵列可能会导致OutOfMemoryError:请求的数组大小超过VM限制
下表描述了扩容的过程
三.删除
remove有两个重载的方法，一个是根据索引开始移除，一个是根据元素开始移除，归根到底都是根据索引移除
1.判断是否需要移动，比如index为最后一个元素时，只需要最后一个元素置为null即可，不需要移动
2.删除项后面的所有元素都向前移动一位
3.最后一个数据项置为null，尽快让GC回收，并且ArrayList的size减一
注意:当按照元素进行查找时,需要先找到元素下标,但是遍历时只找到第一个就返回进行删除操作
四.其他常用方法
clear、indexOf、lastIndexOf、contains、isEmpty
Vector
Vector和ArrayList很多方法的实现都是一样的，部分只是在方法上加了synchronized，因此只介绍和ArrayList不同的API
一.构造
Vector vecotr = new Vecore();
vecotr?对象一创建就会初始化一个容量为10的数组，而ArrayList是初始化一个容量为0的数组，添加第一个元素才会扩充容量为10
二.扩容
每次扩容大小为2倍,ArrayList为1.5
三.其他常用方法
remove、clear、set、get 、contains、isEmpty都增加了synchronize
indexOf??增加了synchronize ，可以从指定索引向后开始查找，这种设计要比ArrayList要好
lastIndexOf 增加了synchronize ，可以从指定索引向前开始查找，这种设计要比ArrayList要好
LinkedList
linkedList是一个双向链表,同时实现了List接口和Deque接口,所以?linkedList 也是一个双端队列
既然是双端队列,除了list的操作外，还包括的队列的所有操作?(offer,poll,peek)
双端队列也可以是一个栈?(push,pop,peek)
LinkedList没有实现同步（synchronized），如果需要多个线程并发访问，可以先采用Collections.synchronizedList()方法对其进行包装。（SynchronizedList 就是在 List的操作外包加了一层synchronize同步控制, 注意使用 Iterator遍历列表时，Collections.synchronizedList可能发生 错误!?必须手动同步）
synchronized (list) {?
????Iterator i = list.iterator(); // Must be in synchronized block?
? ? while (i.hasNext())?
?????????foo(i.next());?
?}?
ArrayDeque
详细参考:?https://baijiahao.baidu.com/s?id=1738368707665352004&wfr=spider&for=pc
ArrayDeque是采用数组方式实现的双端队列。
? ArrayDeque的出队入队是通过头尾指针循环，利用数组实现的。
? ArrayDeque容量不足时是会扩容的，每次扩容容量增加一倍。
? ArrayDeque可以直接作为栈使用。当用作栈时，性能优于Stack，当用于队列时，性能优于LinkedList。
? 无容量大小限制，容量按需增长。
? 非线程安全队列，无同步策略，不支持多线程安全访问。
? 具有fail-fast特性，不能存储null值，支持双向迭代器遍历。
构造
1.默认 ArrayDeque ad = new?ArrayDeque();??默认创建 长度16的数组??
2.指定元素个数?ArrayDeque ad = new?ArrayDeque(x);
如果 x<8 默认指定8个长度
如果x>=8 ,会找到与当前指定长度最近最大的2的次幂的数(详细解释: https://www.jianshu.com/p/98080edc787d)
Stack?
java中栈的实现? 是Vector 的子类
栈的相关操作应该由?Deque?接口来提供，推荐使用?Deque?的子类?ArrayDeque?代替?Stack。使用?Deque?接口来实现栈的功能有以下好处：
1.速度比?Stack?快
这个类作为栈使用时可能比?Stack?快，作为队列使用时可能比?LinkedList?快。因为原来的 Java 的?Stack?继承自?Vector，而?Vector?在每个方法中都加了锁，而?Deque?的子类?ArrayDeque?并没有锁的开销。
2.屏蔽掉无关的方法(作为栈使用最好自己封装一层,只提供栈的相关操作)
原来的 Java 的?Stack，包含了在任何位置添加或者删除元素的方法，这些不是栈应该有的方法，所以需要屏蔽掉这些无关的方法。
声明为?Deque?接口可以解决这个问题，在接口中声明栈需要用到的方法，无需管子类是如何是实现的，对于上层使用者来说，只可以调用和栈相关的方法。
PriorityQueue
优先级队列,数据放入后自动排队,数据可以实现Comparable,适合 插入后 取出时有顺序的场景
LinkedHashMap?
https://www.jianshu.com/writer#/notebooks/53201285/notes/106035552
HashSet
1.HashSet中不能有相同的元素，可以有一个null元素，存入的元素是无序的。
2.HashSet如何保证唯一性
1).HashSet底层数据结构是哈希表，哈希表就是存储唯一系列的表，而哈希值是由对象的hashCode()方法生成。
2).确保唯一性的两个方法：hashCode()和equals()方法。
3.添加、删除操作时间复杂度都是O(1)。
4.非线程安全
LinkedHashSet
1.LinkedHashSet中不能有相同元素，可以有一个Null元素，元素严格按照放入的顺序排列。
2.LinkedHashSet如何保证有序和唯一性
1).底层数据结构由哈希表和链表组成。
2).链表保证了元素的有序即存储和取出一致，哈希表保证了元素的唯一性。
3.添加、删除操作时间复杂度都是O(1)。
4.非线程安全
TreeSet
1.TreeSet是中不能有相同元素，不可以有Null元素，根据元素的自然顺序进行排序。
2.TreeSet如何保证元素的排序和唯一性
底层的数据结构是红黑树
3.添加、删除操作时间复杂度都是O(log(n))
4.非线程安全
ConcurrentHashMap?
JDK1.7 中的 ConcurrentHashMap 是由 Segment 数组结构和 HashEntry 数组结构组成，即 ConcurrentHashMap 把哈希桶数组切分成小数组（Segment ），每个小数组有 n 个 HashEntry 组成。
Segment 继承了 ReentrantLock，所以 Segment 是一种可重入锁，扮演锁的角色。Segment 默认为 16，也就是并发度为 16。存放元素的 HashEntry，也是一个静态内部类，主要的组成如下，其中，用 volatile 修饰了 HashEntry 的数据 value 和 下一个节点 next，保证了多线程环境下数据获取时的可见性！
JDK1.8 在数据结构上,ConcurrentHashMap 选择了与 HashMap 相同的Node数组+链表+红黑树结构；在锁的实现上，抛弃了原有的 Segment 分段锁，采用CAS + synchronized实现更加细粒度的锁。
将锁的级别控制在了更细粒度的哈希桶数组元素级别，也就是说只需要锁住这个链表头节点（红黑树的根节点），就不会影响其他的哈希桶数组元素的读写，大大提高了并发度。
在 JDK1.6 中，对 synchronized 锁的实现引入了大量的优化，并且 synchronized 有多种锁状态，会从无锁 -> 偏向锁 -> 轻量级锁 -> 重量级锁一步步转换。
减少内存开销 。假设使用可重入锁来获得同步支持，那么每个节点都需要通过继承 AQS 来获得同步支持。但并不是每个节点都需要获得同步支持的，只有链表的头节点（红黑树的根节点）需要同步，这无疑带来了巨大内存浪费。
hashMap
jdk1.8?HashMap
底层实现:?数组?Node<K,V>[]?+?链表?+?黑红树
默认?数组长度16?扩容因子0.75
当数组长度>64?且?链表长度>=8时,链表转换位黑红树
考虑到性能问题,?查询效率和空间占用率的平衡，如果不到64还可以通过扩容使得链表缩短,
链表长度超过8，查询效率?性能不如黑红树,但是黑红树的实现占用的空间比链表多
--------------------
通常如果?hash?算法正常的话，那么链表的长度也不会很长，那么红黑树也不会带来明显的查询时间上的优势，反而会增加空间负担。所以通常情况下，并没有必要转为红黑树，所以就选择了概率非常小，小于千万分之一概率，也就是长度为?8?的概率，把长度?8?作为转化的默认阈值。
所以如果平时开发中发现?HashMap?或是?ConcurrentHashMap?内部出现了红黑树的结构，这个时候往往就说明我们的哈希算法出了问题，需要留意是不是我们实现了效果不好的?hashCode?方法，并对此进行改进，以便减少冲突
--------------------
每次扩容resize()为原数组大小的2倍,??为什么是2倍
扩容后若黑红树重新分配且长度<6,会将黑红树转换位链表
-----------------------------------
容量n为2的幂次方，n-1的二进制会全为1，位运算时可以充分散列，避免不必要的哈希冲突。
所以扩容必须2倍就是为了维持容量始终为2的幂次方。
----------------------------------
如何定位一个元素在数组中的下标,简单说:?数组长度和key的hashcode作与运算,获取到数组的下标
-----------------------------------
index?:?(n-1)&hash(key)???[?(数组长度-1)?与?(key的hash值)]
hash?(key)?：?(key?==?null)???0?:?(h?=?key.hashCode())?^?(h?>>>?16)
-----------------------------------
key.hashCode()?调用的是Objec类的hashCode()方法,这个值与key的内存地址有关系,保证每个对象有唯一的hashCode
h>>>>16??65536,?我们一般情况是使用map时,数组长度都没有这么大,?就是说当计算数组下标的时候只使用了hashCode()的前16位参与?与?运算,?hashCode()的高位根本没有用到,打个不恰当的例子,?123，223，323?这个三个数百位数在计算时用不到，这就是hashCode没有充分散列,所以取下标之前先用key?的hashCode与高位做一次异或操作,
然后再?和(数组长度-1)?作与运算,最终取得数组下标.
h>>>>16这里为什么是异或运算呢?大概是异或运算获取的值是0或1的概率是平衡的
----------------------------------------------------------------
hashMap?put的流程
1.获取key的hashcode()
2.判断当前数组是否为null,若为null,初始化数组
3.数组长度-1?和?key的?hashCode()进行?与运算?得到数组的下标i
4.获取指定下标的元素tab[i]
?①若为null?,将key,?value封装成node,?赋值给tab[i]
?②若不为null,获取当前位置元素的key,?与?待存储的key进行比较,?若相等,更新value
??????若不相等,判读当前节点的类型
Ⅰ.若为TreeNode结构,遍历黑红树,比较key,不存在则增加，若存在,更新
Ⅱ.?若为链表结构,变量链表,比较key,不存在则增加至尾部,若数组长度>64且链表元素个数>=8时，将链表转为黑红树
5.modCount++,元素个数size+1,
6.如果size大于扩容的值,则进行扩容
----------------------------------------------------------------
hashMap?get的流程
1.获取get的hashCode()
2.判读当前数组是否为null,若为null,返回null
3.数组长度-1?和?key的?hashCode()进行?与运算?得到数组的下标i
4.获取指定下标的元素tab[i]
①若为null?,返回null
②若不为null,tab[i].key?与?查询的key?比较，
Ⅰ.相同则返回该元素，并?获取value
Ⅱ.不等则判读该元素.next?，若为null?返回null,?若有判断类型,黑红树遍历或链表遍历
找到此元素,若没有返回null,????
----------------------------------------------------------------
头插法?尾插法,??说的put?元素的时候?放在链表的头部还是尾部
jdk1.8中有黑红树，采用尾插法,当然?头插法?高效，但是jdk1.7HashMap链表头插法导致的死循环