HashMap
结构
<font color="#c41230">数组+链表/红黑树</font>
<font color="#c41230">初始数量默认为16</font>
<font color="#c41230">装载因子默认为0.75</font>
源码解读
```
table变量<br>
HashMap的底层数据结构，是Node类的实体数组，用于保存key-value对
<font color="#c41230">capacity</font><br>
并不是一个成员变量，但却是一个必须要知道的概念，表示容量
threshold变量<br>
临界值，当超出该值时，表示table表示该扩容了<br>threshod = capacity * loadFactor<br>
loadFactor变量<br>
装载因子, 默认为0.75
put
1. key的hash值 -> 数组table的位置i
2. 判断table是否初始化
否 -> resize扩容
3. 判断table[i]是否已有元素
否 -> 直接插入
4. 判断table[i]是否为TreeNode
是 -> 红黑树插入
否 -> 链表遍历插入
链表深度>8 -> 转换为红黑树
5. size是否大于临界值threshold -> resize扩容
resize扩容
<font color="#c41230">1. newsize = oldsize*2, 容量为2的幂次方</font>
2. 扩容针对整个Map，每次扩容时，原来数组中的元素依次<font color="#c41230">重新计算存放位置( index = hash & (tab.length – 1) )</font>
优化: 若知道HashMap的K-V个数size, 初始化时可以 <font color="#0076b3">new HashMap(</font><font color="#c41230">size/loadFactor >> 1</font><font color="#0076b3">)</font>
Hashtable
结构
<font color="#c41230">数组+链表</font>
<font color="#c41230">初始数量默认为11</font>
<font color="#c41230">装载因子默认为0.75</font>
rehash扩容
<font color="#c41230">1. newsize = oldsize*2+1</font>
2. 扩容针对整个Map，每次扩容时，原来数组中的元素依次<font color="#c41230">重新计算存放位置( index = (hash & 0x7FFFFFFF) % tab.length )</font>
锁
<font color="#c41230">synchronized</font>
LinkedHashMap
基于<font color="#c41230">HashMap</font>实现
双向链表
维护链表节点--<font color="#c41230">重写newNode</font>
ConcurrentHashMap
结构
<font color="#c41230">分段的数组+链表</font>
扩容
段内扩容, 不会对整个Map进行扩容
锁
<font color="#c41230">分段锁</font>
1. Hashtable的synchronized是针对整张Hash表的，ConcurrentHashMap允许多个修改操作并发进行
2. 有些方法需要跨段，比如size()和containsValue()，它们可能需要锁定整个表而而不仅仅是某个段，这需要按顺序锁定所有段，操作完毕后，又按顺序释放所有段的锁
TreeMap
结构
<font color="#c41230">红黑树</font>
容量方面没有限制
