集合两大分支：Collection（包含List和Set）和Map（其下有HashMap-LinkedHashMap，HashTable，TreeMap）

以键值对形式存储数据，大多数以Hash为基本数据结构。

非线程安全：HashMap、LinkedHashMap、TreeMap

线程安全：HashTable、ConcurrentHashMap

---

HashMap：非线程安全

底层基于Hash实现，根据键的Hash值来存储/获取键值对，之前底层用数组+链表，JDK1.8改为数组+链表+红黑树（详见概念篇）。之前采用头插法，并发时扩容（搬迁数组）可能导致形成环形链表。

环形链表具体表现为：链表A-B-C进行尾插法搬迁，线程1记录A的next为B（内部仅维护一个next，所以只能一个一个记录），此时线程2完成搬迁，新链表为C-B-A。

修改了节点指向：C- next -B- next -A- next -Null，导致B的next为A。之后线程1搬完A之后搬迁B，B搬完之后想要搬C，查询B的next，已经被线程2修改为A，此时就去搬A，搬完A后查询next为null，最终的链表逻辑上就是A-B-A-null，在CPU眼里就是A-B-A-B循环。CPU爆炸

而Java8采用尾插法可以保证next不变，不会导致形成环形链表，但多线程下仍有数据覆盖等问题

依旧可以通过Collection.synchrozied关键字粗暴的包装，但是性能方面不如ConCrurrentHashMap。

LinkedHashMap：非线程安全

继承至HashMap，在此基础上使用双向链表维护顺序。

TreeMap：非线程安全

基于红黑树实现的Map，可以对键值对进行排序，但是线程极度不安全，因为多线程插入会破坏红黑树结构。

---

HashTable：线程安全

简单粗暴，在方法上加synchronized关键字

ConcurrentHashMap：线程安全

底层基于HashMap。之前采用分段锁，将Map中的所有数组（桶）分为几大段，对段上锁，比起对整个Map上锁而言锁粒度更细。

而Java8改为了对桶的头节点用Volatile+CAS或synchronized关键字上锁，也就是对单独一个桶上锁。

具体来说:

添加元素时首先会判断容器是否为空：

• 如果为空则使用 volatile 加 CAS （比较并替换） 来初始化。
• 如果容器不为空，则根据存储的元素计算桶是否为空。
• 如果桶为空，则继续利用 volatile配合CAS设置该节点；
• 如果桶不为空(Hash碰撞)，则使用 synchronized锁住头节点，然后，遍历桶中的数据，并替换或新增节点到桶中，最后再判断是否需要转为红黑树。
• tips：[CAS经常配合volatile来保证比较部分的数据的实时性]

不可以存null,大部分并发线程安全的集合都不允许null,因为会导致歧义(null or “null”)

---

Map的遍历方法：forEach、迭代器、Lambda表达式、Stream流等，比较麻烦。

HashMap的put过程：

先计算出Hash值并找到桶的索引。

之后先判断桶内是否为空。

不为空则判断第一个键值对的Hash码和键是否与put的键值对相同（链表O（1））。

不同则遍历链表或红黑树，寻找Hash码和键的equals（）是否相同。

找到则覆盖，否则就新插入。

检查链表长度，是否需要树化。检查是否需要扩容。

HashMap的扩容机制：

HashMap的默认扩容因子是0.75，当需要扩容时，将哈希表翻一倍并且将旧的哈希表搬迁到新的哈希表中。

在Java8之前，需要对所有元素进行Hash计算然后重新分配，性能差。

Java8之后则进行优化：

因为哈希表长度翻倍，根据Hash函数公式而参与运算的二进制会多一位。

所以运算所得的hash值只需要判断新的一位是0还是1就可以了，0则保留原位，1则搬迁，性能优化很大