容器

fail-fast&fail-safe

fail-fast

• fail-fast 机制，即快速失败机制，是java集合(Collection)中的一种错误检测机制。当在迭代集合的过程中该集合在结构上发生改变的时候，就有可能会发生fail-fast，即抛出 ConcurrentModificationException异常。fail-fast机制并不保证在不同步的修改下一定会抛出异常，它只是尽最大努力去抛出，所以这种机制一般仅用于检测bug。

fail-safe

• fail-safe（安全失败）采用安全失败机制的集合容器，在遍历时不是直接在集合内容上访问的，而是先复制原有集合内容，在拷贝的集合上进行遍历。
• 缺点
  • 基于拷贝内容的优点是避免了Concurrent Modification Exception，但同样地，迭代器并不能访问到修改后的内容，即：迭代器遍历的是开始遍历那一刻拿到的集合拷贝，在遍历期间原集合发生的修改迭代器是不知道的。

Collection

Set

TreeSet

• 基于红黑树实现，支持有序性操作，例如根据一个范围查找元素的操作。但是查找效率不如 HashSet，HashSet 查找的时间复杂度为 O(1)，TreeSet 则为 O(logN)。

HashSet

• 基于哈希表实现，支持快速查找，但不支持有序性操作。并且失去了元素的插入顺序信息，也就是说使用 Iterator 遍历 HashSet 得到的结果是不确定的。

LinkedHashSet

• 继承自HashSet,具有 HashSet 的查找效率，并且内部使用双向链表维护元素的插入顺序。

List

ArrayList

• 基于动态数组实现，支持随机访问。
• 数组默认大小为10，长度不足时，数组长度扩容为原来的1.5倍
• Fail-fast:序列化或者迭代操作时，需要比较操作前后 modCount 是否改变，如果改变了需要抛出 ConcurrentModificationException**(modCount 为ArrayList结构发生变化的次数**)

CopyOnWriteArrayList

• 写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。
• 写操作需要加锁，防止并发写入时导致写入数据丢失。
• 写操作结束之后需要把原始数组指向新的复制数组。
• 缺陷：
  • 内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
  • 数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中
    所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

Vector

• 线程安全的
• 每次扩容容量翻倍

LinkedList

• 基于双向链表实现，只能顺序访问，但是可以快速地在链表中间插入和删除元素。不仅如此，LinkedList 还可以用作栈、队列和双向队列。

Queue

功能	抛异常	返回值
增	add(e)	offer(e)
删	remove()	poll()
瞧	element()	peek()

LinkedList

• 可以用它来实现双向队列。

PriorityQueue

• 基于堆结构实现，可以用它来实现优先队列。

deque

• 双端队列

ArrayDeque

• 可以当作栈来用

blockDque

blackQueue

BlockQueue

ArrayBlockQueue

• 数组实现的有界阻塞队列,环形队列，

PriorityBlockingQueue

• 支持优先级的无界队列

LinkedBlockingQueue

• 链表实现的无界阻塞队列，最大值为MAXVALUE

SynchronousQueue

• 不存储元素的阻塞队列，put一个必须take一个，给线程传递任务

LinkedTransferQueue

Map

HashMap

• 基于哈希表实现，使用拉链法来解决哈希冲突，当链表长度超过8时并且数组长度到64才转变为红黑树(1.8才有的操作)，小于6时重新变成链表，如果长度小于64则不是转变为红黑树，而是扩容
• 1.7 使用头插法进行的，1.8以后使用尾插法,原因多线程下，头插法可能会形成环形链表，但是1.8的HashMap在并发下也可能形成循环的树
• Key做Hash时，为什么使用(h = key.hashCode()) ^ (h >>> 16)，
  • 绝大多数情况桶的数量小于2的16次方。所以始终是hashcode 的低16位（甚至更低）参与运算。要是高16位也参与运算，会让得到的下标更加散列
  • 但是只是用底16位的话，会丢失高位的变化对key的影响，导致冲突加剧，所以混用
  • map长度是2的次幂也是因为上面的操作才这么设定的，为了hash的更均匀
  • 为什么使用^,而不是其他位运算
    • 异或是位运算中最快的操作之一。
    • a ^ b的结果均匀，不会偏向0或1。
• 当链表长度超过8时转变为红黑树，小于6时重新变成链表,为什么是8和6
  • 根据hashmap中的注释，链表长度达到8只有千万分之一的概率出现，链表的平均查找长度为n/2,树的查找复杂度为log(8) = 3,只有到达8的时候，树的查找复杂度低的优势才能体现出来
  • 在6才转化回去时避免频繁的发生树转链表和链表转树
• Hash()为什么使用31作为乘数？
  • 31是一个奇质数，如果选择偶数会导致乘积运算时数据溢出
  • 在二进制中，2 个 5 次方是 32，那么也就是 31 * i == (i << 5) -i。这主要是说乘积运算可以使用位移提升性能，同时目前的 JVM 虚拟机也会自动支持此类的优化。
  • 奇质数中，31的碰撞概率是最小的

扩容

• 相关参数

  • 参数	含义
    capacity	table 的容量大小，默认为 16。需要注意的是 capacity 必须保证为 2 的 n 次方。
    size	键值对数量。
    threshold	size 的临界值，当 size 大于等于 threshold 就必须进行扩容操作。
    loadFactor	装载因子，table 能够使用的比例，threshold = (int)(capacity* loadFactor)。默认0.75

• 每次扩容为原来的2倍
• 当是2次幂时，取模可以用&运算

ConcurrentHashMap

• 1.7

  • 

  • ConcurrentHashMap 和 HashMap 实现上类似，最主要的差别是 ConcurrentHashMap 采用了分段锁（Segment），每个分段锁维护着几个桶（HashEntry），多个线程可以同时访问不同分段锁上的桶，从而使其并发度更高（并发度就是 Segment 的个数）,Segment 继承自 ReentrantLock，Segment 默认初始化个数是16。

  • ConcurrentHashMap 在执行 size 操作时先尝试不加锁，如果连续两次不加锁操作得到的结果一致，那么可以认为这个结果是正确的。

  • 尝试次数使用 RETRIES_BEFORE_LOCK 定义，该值为 2，retries 初始值为 -1，因此尝试次数为 3。如果尝试的次数超过 3 次，就需要对每个 Segment 加锁。

• 1.8

  • 

  • JDK 1.8 采用Node + CAS + Synchronized来保证并发安全进行实现，在 CAS 操作失败时使用内置锁 synchronized。

    并且 JDK 1.8 的实现也在链表过长（长度达到8）时会转换为红黑树

  • 性能提示

    • 高并发写入：CAS减少锁竞争，桶级锁提升并发度。
    • 哈希冲突查询：红黑树降低时间复杂度。
    • 动态扩容：多线程协作加快数据迁移

  • 优化方向	JDK 1.7（分段锁）	JDK 1.8（CAS+Synchronized）
    锁粒度	段级别（粗粒度）	桶级别（细粒度）
    并发度	受限于段数（默认16）	理论上等于桶数（可动态扩容）
    无锁化支持	无	通过CAS实现无锁插入/更新
    哈希冲突处理	链表（O(n)）	链表 + 红黑树（O(log n)）
    扩容效率	单线程按段扩容	多线程协作扩容
    内存占用	较高（每个段独立结构）	较低（去除了段结构）

HashTable

• 与hashMap类似，但是线程安全的，效率很低，已经废弃,不接受null值和null键，初始容量为11，扩容翻倍+1
• 不接受null值和null键，一方面放值的时候没用像HashMap一样对null有特殊处理。另一方面是fail-safe机制，，这种机制会使你此次读到的数据不一定是最新的数据。如果你使用null值，就会使得其无法判断对应的key是不存在还是为空，因为你无法再调用一次contain(key）来对key是否存在进行判断，ConcurrentHashMap同理

TreeMap

• 基于红黑树实现

LinkedHashMap

• 使用双向链表来维护元素的顺序，顺序为插入顺序或者最近最少使用（LRU）顺序。
• accessOrder 如果为false,则列表顺序为插入顺序。如果为true,则列表最后一个为最近访问的元素

WeakHashMap

• WeakHashMap 的 Entry 继承自 WeakReference，被 WeakReference 关联的对象在下一次垃圾回收时会被回收。
  WeakHashMap 主要用来实现缓存，通过使用 WeakHashMap 来引用缓存对象，由 JVM 对这部分缓存进行回收。