ArrayList

简介

底层是数组队列，与Java中的数组相比，它的容量可以动态增长。

继承于AbstractList, 实现了List，RandomAccess，Cloneable，java.io.Serializeable接口

可以存储任何类型的对象，包括null值，但是不建议向ArrayList添加null值

扩容机制

（JDK8）以无参数构造方法创建ArrayList时，实际上初始化赋值的是一个空数组。当真正对数组进行添加元素操作时，才真正分配容量。即向数组中添加第一个元素时，数组容量扩为10。

扩容 grow()函数
先将新容量扩大为原来的1.5倍
判断新容量是否大于最小需要容量
如果小于，最小需要容量就作为新容量
判断新容量是否大于MAX_ARRAY_SIZE
如果大于，进入hugeCapacity()函数，比较最小需要容量和MAX_ARRAY_SIZE，如果最小需要容量大于MAX_ARRAY_SIZE，新容量为Integer.MAX_VALUE，否则，新容量为MAX_ARRAY_SIZE，即为Integer.MAX_VALUE-8

LinkedList

简介

基于双向链表实现，项目中一般不会用到，需要用到LinkedList的场景几乎都可以用ArrayList代替。

LinkedList继承了AbstractSequentialList，而AbstractSequentialList又继承于AbstractList。实现了List，Deque，Cloneable，Serializable接口

HashMap

简介

基于哈希表的Map接口实现，非线程安全

可以存储null的key和value，但null作为键只能有一个，null作为值可以多个

JDK1.8之前，数组加链表，数组是主体，链表是为了解决哈希冲突存在的

通过key的hashCode经过扰动函数（HashMap的hash方法，防止一些实现比较差的hashCode（）方法，减少碰撞）处理后得到hash值，通过(n-1)&hash判断当前元素存放的位置（n指的是数组的长度），如果当前元素存在元素，就判断该元素与要存入元素的hash值以及key是否相同，如果相同，直接覆盖，如果不同就通过拉链法解决。

JDK1.8之后，当链表长度大于等于阈值（默认为8）（将链表转为红黑树前会判断，如果当前数组的长度小于64，那么会选择先进行数组扩容，而不是转换为红黑树）时，将链表转化为红黑树，以减少搜索时间。

HashMap默认的初始化大小为16，之后每次扩充，容量变为原来的2倍。并且，HashMap总是使用2的幂作为哈希表的大小。

  • loadFactor负载因子
    负载因子控制数组存放数据的疏密程度，0.75f是官方给出的比较好的临界值。太大导致查找元素效率低，太小导致数组的利用率低

  • threshold
    threshold=capacity * loadFactor，当size > threshold，考虑数组的扩增

扩容：

超过最大值就不再扩容，直接返回table

没超过最大值，扩充为原来的两倍，threshold也是两倍

ConcurrentHashMap

JDK1.7

由很多个Segment组合，每个Segment类似于HashMap结构，HashMap内部可以进行扩容，但是Segment的个数一旦初始化就不变化。（Segment默认16，可以认为ConcurrentHashMap默认支持16个线程并发）

使用分段锁，每个Segment上同时只有一个线程可以操作。

JDK1.8

Node数组+链表/红黑树，当冲突链表达到一定长度时，链表会转换成红黑树

使用Synchronized锁加CAS的机制

CopyOnWriteArrayList

JDK1.5引入了Java.util.concurrent(JUC)包，其中提供了很多线程安全且并发性能良好的容器，其中唯一的线程安全List实现就是CopyOnWriteArrayList。

写时复制。CopyOnWriteArrayList中的读取操作完全无需加锁，写入操作也不会阻塞读操作，只有写写才会互斥。

当需要修改（add，set，remove等操作）CopyOnWriteArrayList的内容时，不会直接修改原数组，而是会先创建底层数组的副本，对副本数组进行修改，修改完之后再将修改后的数组赋值回去。

适合读多写少的并发场景。