Map体系

HashMap、HashTable、ConcurrentHashMap

HashMap(Java 8以前)：

数组+链表

数组长度默认16

存储规则：hash(key.hashCode())%len

HashMap（Java 8及以后）：

数组+链表+红黑树

通过常量TREEIFY_THRESHOLD决定是否将链表转化为红黑树

使用LazyLoad原则，首次使用时才会初始化数组

HashMap：如何有效减少碰撞

扰动函数：促使元素位置均匀分布，减少碰撞几率。
使用final对象，并采用合适的equals()和hashCode()方法。

Hash函数

高16位与低16位做异或，让结果更均匀，同时数组长度总是二的倍数，方便取下标，直接多取一位就行了。

HashMap：扩容问题

多线程条件下，调整大小会存在条件竞争，容易造成死锁
reHashing是一个比较耗时的过程（将原来的内容重新移到新的hash值对应的桶中）
HashMap在JDK1.8之后引入了红黑树的概念，表示若桶中链表元素超过8时（并且数组的大小是64），会自动转化成红黑树；若桶中元素小于等于6时，树结构还原成链表形式。
- 链表长度达到8个元素的概率为0.00000006，几乎是不可能事件.

获得线程安全的HashMap：

public static void main(String[] args) {
    Map hashMap = new HashMap();
    Map safeHashMap = Collections.synchronizedMap(hashMap);
}

操作safeHashMap即是线程安全的。原理是对public方法加synchronized锁

原理和HashTable类似，故也效率较低

HashTable

早期java类库提供的哈希表的实现
线程安全：涉及到修改hashTable的方法都使用了synchronized修饰-
串形化的方式运行，性能较差
基本上不再使用

如何优化HashTable？

通过锁细粒度化，将整锁拆解成多个锁进行优化。

ConccurentHashMap

出自J.U.C包

不允许插入null键（HashMap允许）

早期的ConccurentHashMap：通过分段锁Segment实现

将锁一段一段的存储，为每一段分配一个锁segment，不同的segment访问互不影响。

默认分为16个段，理论上将多线程能力提升了16倍。

实现原理就是把原数组逻辑上拆成多个子数组，每个子数组配置一把锁。

当前的ConccurentHashMap：CAS+synchronized使锁细化

取消了segment分段锁，而采用CAS+synchronized使锁细化。

对数组元素的插入使用CAS，需要不断的做失败重试，直到成功为止

如果发生hash碰撞，就会锁住链表或者红黑树的头节点，

ConcurrentHashMap总结

Java8及以后比起之前的segment，锁拆得更细
- 首先使用无锁操作CAS插入头节点，失败则循环重试
- 若头节点已存在，则尝试获取头节点的同步锁，再进行操作

ConcurrentHashMap别的需要注意的点

size()和mappingCount()方法的异同，两者计算是否准确？
多线程环境下如何进行扩容？