集合

ArrayList就是数组列表，主要用来装载数据，当我们装载的是基本类型的数据int，long，boolean，short，byte…的时候我们只能存储他们对应的包装类

arraylist可以存null吗?  ArrayList存储的类型是object,null属于object类型。

和LinkedList相比，它的查找和访问元素的速度较快，但新增，删除的速度较慢。

特点：ArrayList底层是用数组实现的存储，查询效率高，增删效率低，线程不安全。使用频率很高

初始化大小

扩容

新增

删除

线程不安全

ArrayList不适合做队列，数组适合用来做队列

遍历

两种数组复制方法的区别在于：
arraycopy()需要目标数组，将原数组拷贝到你自己定义的数组里，而且可以选择拷贝的起点和长度以及放入新数组中的位置
copyOf()是系统自动在内部新建一个数组，调用arraycopy()将original内容复制到copy中去，并且长度为newLength。返回copy; 即将原数组拷贝到一个长度为newLength的新数组中，并返回该数组。
总结
Array.copyOf()可以看作是受限的System.arraycopy(),它主要是用来将原数组全部拷贝到一个新长度的数组，适用于数组扩容。

底层是双向链表，只能从头开始逐个遍历

底层也是用数组来实现的，基本每个方法都加Synchronized,已经废弃了

一是考虑数据结构是否能完成需要的功能；
如果都能完成，二是考虑哪种更高效。

线程安全

默认情况下它是扩容两倍。

采用 Hashmap 的 key 来储存元素，主要特点是无序的，基本操作都是 O(1) 的时间复杂度，很快。

HashSet + LinkedList 的结构，特点就是既拥有了 O(1) 的时间复杂度，又能够保留插入的顺序。

TreeSet

实现「普通队列 - 先进先出」的语义

ArrayDeque

实现「优先队列」的语义

总结来说就是推荐使用 ArrayDeque，因为效率高，而 LinkedList 还会有其他的额外开销（overhead）。

ArrayDeque 是一个可扩容的数组，LinkedList 是链表结构；
ArrayDeque 里不可以存 null 值，但是 LinkedList 可以；
ArrayDeque 在操作头尾端的增删操作时更高效，但是 LinkedList 只有在当要移除中间某个元素且已经找到了这个元素后的移除才是 O(1) 的；
ArrayDeque 在内存使用方面更高效。
所以，只要不是必须要存 null 值，就选择 ArrayDeque 吧！

jdk 8之前是头插法

jdk8之后是尾插法

因素

扩容

为了位运算的方便，位与运算比算数计算的效率高了很多

实现均匀分布。

只要输入的HashCode本身分布均匀，Hash算法的结果就是均匀的。

二叉树

当二叉树多次插入新的节点，导致的不平衡，红黑树应用而生。

1.节点是红色或黑色。

2.根节点是黑色。

3.每个叶子节点都是黑色的空节点（NIL节点）。

4 每个红色节点的两个子节点都是黑色。(从每个叶子到根的所有路径上不能有两个连续的红色节点)

5.从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。

如何保证红黑树始终是红黑树

在极限状态下,HashMap在同一索引中放入第十一个元素时才会转变为红黑二叉树

那么由此我们会想为什么会这样呢?Java中明明预设了阈值"8",怎么会到第十一才转为红黑二叉树呢?

其实在HashMap中存在扩容机制,
它一开始默认是长度为16的数组,
当某一个索引中的元素超过到8时,它优先会选择将长度扩容2倍(即长度为32)的数组,
它会认为是不是由于数组的长度不够才导致一个索引中元素过多;
但当它发现长度为32时,某一个索引中的元素还是超过9时,
它还是会优先选择将长度再次扩容到2倍(即长度为64)的数组,
在长度为64的数组中,它发现某一个索引中的元素还是超过10时,它就会对该索引所在的链表转化为红黑二叉树.
所以在第十一个元素时,就会对该索引所在的链表转化为红黑二叉树.

在java中，所有的对象都是继承于Object类。Object类中有两个方法equals、hashCode，这两个方法都是用来比较两个对象是否相等的

在未重写equals方法我们是继承了object的equals方法，那里的 equals是比较两个对象的内存地址，显然我们new了2个对象内存地址肯定不一样

对于值对象，==比较的是两个对象的值

对于引用对象，比较的是两个对象的地址

大家是否还记得我说的HashMap是通过key的hashCode去寻找index的，那index一样就形成链表了，也就是说”帅丙“和”丙帅“的index都可能是2，在一个链表上的。

我们去get的时候，他就是根据key去hash然后计算出index，找到了2，那我怎么找到具体的”帅丙“还是”丙帅“呢？

equals！是的，所以如果我们对equals方法进行了重写，建议一定要对hashCode方法重写，以保证相同的对象返回相同的hash值，不同的对象返回不同的hash值。

HashTable

CurrentHashMap

Collections.synchronizedMap(Map)

Hashtable 是不允许键或值为 null 的，HashMap 的键值则都可以为 null。

Hashtable在我们put 空值的时候会直接抛空指针异常，但是HashMap却做了特殊处理。

实现方式不同：Hashtable 继承了 Dictionary类，而 HashMap 继承的是 AbstractMap 类。

初始化容量不同：HashMap 的初始容量为：16，Hashtable 初始容量为：11，两者的负载因子默认都是：0.75。

扩容机制不同：当现有容量大于总容量 * 负载因子时，HashMap 扩容规则为当前容量翻倍，Hashtable 扩容规则为当前容量翻倍 + 1。

迭代器不同：HashMap 中的 Iterator 迭代器是 fail-fast 的，而 Hashtable 的 Enumerator 不是 fail-fast 的。

总结：当其他线程改变了HashMap 的结构，如：增加、删除元素，将会抛出ConcurrentModificationException 异常，而 Hashtable 则不会。

快速失败（fail—fast）是java集合中的一种机制， 在用迭代器遍历一个集合对象时，
如果遍历过程中对集合对象的内容进行了修改（增加、删除、修改），
则会抛出Concurrent Modification Exception。

保证了不同线程对这个变量进行操作时的可见性，即一个线程修改了某个变量的值，这新值对其他线程来说是立即可见的。（实现可见性）

禁止进行指令重排序。（实现有序性）

volatile 只能保证对单次读/写的原子性。i++ 这种操作不能保证原子性

jdk1.7

ConcurrentHashMap 采用了分段锁技术，其中 Segment 继承于 ReentrantLock。

每当一个线程占用锁访问一个 Segment 时，不会影响到其他的 Segment。

jdk1.8

其中抛弃了原有的 Segment 分段锁，而采用了 CAS + synchronized 来保证并发安全性。

跟HashMap很像，也把之前的HashEntry改成了Node，但是作用不变，把值和next采用了volatile去修饰，保证了可见性，并且也引入了红黑树，在链表大于一定值的时候会转换（默认是8）

ConcurrentHashMap在进行put操作的还是比较复杂的，大致可以分为以下步骤：

根据 key 计算出 hashcode 。

判断是否需要进行初始化。

即为当前 key 定位出的 Node，如果为空表示当前位置可以写入数据，利用 CAS 尝试写入，失败则自旋保证成功。

如果当前位置的 hashcode == MOVED == -1,则需要进行扩容。

如果都不满足，则利用 synchronized 锁写入数据。

如果数量大于 TREEIFY_THRESHOLD 则要转换为红黑树。

CAS 是乐观锁的一种实现方式，是一种轻量级锁，
JUC 中很多工具类的实现就是基于 CAS 的。

线程在读取数据时不进行加锁，在准备写回数据时，
比较原值是否修改，若未被其他线程修改则写回，若已被修改，则重新执行读取流程。

synchronized之前一直都是重量级的锁，但是后来官方是对他进行过升级的，
他现在采用的是锁升级的方式去做的。

针对 synchronized 获取锁的方式，JVM 使用了锁升级的优化方式，
就是先使用偏向锁优先同一线程然后再次获取锁，如果失败，就升级为 CAS 轻量级锁，
如果失败就会短暂自旋，防止线程被系统挂起。最后如果以上都失败就升级为重量级锁

根据计算出来的 hashcode 寻址，如果就在桶上那么直接返回值。

如果是红黑树那就按照树的方式获取值。

就不满足那就按照链表的方式遍历获取值。