JDK1.8
什么是HashMap？
基于哈希表的 Map 接口的实现。此实现提供所有可选的映射操作，并允许使用 null 值和 null 键。（除了不同步和允许使用 null 之外，HashMap 类与 Hashtable 大致相同。）此类不保证映射的顺序，特别是它不保证该顺序恒久不变。另外，HashMap是非线程安全的，也就是说在多线程的环境下，可能会存在问题，而Hashtable是线程安全的。
数据结构
数组+链表+红黑树
红黑树虽然本质上是一棵二叉查找树，但它在二叉查找树的基础上增加了着色和相关的性质使得红黑树相对平衡，从而保证了红黑树的查找、插入、删除的时间复杂度最坏为O(log n)。
java7和java8在实现HashMap上有所区别，当然java8的效率要更好一些，主要是java8的HashMap在java7的基础上增加了红黑树这种数据结构，使得在桶里面查找数据的复杂度从O(n)降到O(logn)，当然还有一些其他的优化，比如resize的优化等。
key-value数据结构：
static class Node<K,V> implements Map.Entry<K,V> {
final int hash; // 确定Node的位置
final K key;
V value;
Node<K,V> next;
// 省略构造函数和getter和setter
}
HashMap类：
transient Node<K,V>[] table;
transient是Java语言的关键字，用来表示一个域不是该对象串行化的一部分。当一个对象被串行化的时候，transient型变量的值不包括在串行化的表示中，然而非transient型的变量是被包括进去的。
HashMap为什么线程不安全？
put操作时可能出现数据覆盖问题，造成数据不一致- 初始化时可能进行多次初始化
解决思路
- 在put方法上加上
synchronized，也就是HashTable的实现思路。
提出ConcurrentHashMap
因为HashTable效率的问题，提出了ConcurrentHashMap，它和HashMap很像，不一样的地方体现在：
- key或value不能为空
- table数组有
volatile关键字 synchronized只加在数组元素，锁的范围比HashTable缩小了，不影响其它数组元素的操作
PUT过程分析
sizeCtl：记录数组的大小默认值16，记录扩展标准12，负数表示要进行扩容
fh：f.hash，是当前数组头结点的hash值
-
对数据进行初始化，通过
CAS无锁化的方式，保证线程的安全性。保证只有一个线程操作共享变量。将sizeCtl改成-1，其它线程判断这个值是否小于0，小于0则Thread.yield()。 -
根据hash计算下标位置，判断当前位置的值是否为空，
U.getObjectVolatile(tab, ((long)i<<ASHIFT) + ABASE)拿到内存中的最新值，为空时直接通过CAS方式存放元素。 -
判断是否正在扩容，在扩容的话就帮助其它线程进行扩容。
- 下标位置相同时，通过
synchronized同步代码块方式加锁- key值相同，直接覆盖
- key值不相同，放到链表最后
- key值不相同，当前头节点是红黑树，插入到红黑树
- 当链表长度超过8时，
- 数组长度大于64则转成红黑树
- 数组长度小于64则数组进行
扩容，扩大1倍n<<1
-
返回老的值
- 通过CAS方式判断sizeCtl和sc的值是否相等，如果相等，则对sizeCtl进行更改，改成负数，再进行扩容
resize- 数组大小扩大，扩容之后的数组：nextTable
- 将老的数据的元素搬到新的数组中
- CAS的思想很简单：三个参数，一个当前内存值V、旧的预期值A、即将更新的值B，当且仅当预期值A和内存值V相同时，将内存值修改为B并返回true，否则什么都不做，并返回false。
- Thread.yield()让出当前的时间片，不往下执行。
- 15 & hash 等价于 hash % 16