JDK1.8中的HashMap核心源码解析
继承类：AbstractMap
继承接口：Map，Cloneable，Serializable
主要性质：
- 默认初始table使用的是Map.Entry<K,V>[]实现数组 + 链表 结构进行存储
- 转换临界值:TREEIFY_THRESHOLD = 8;链表长度 >= 8时进行转换,转换成红黑树结构
- table默认初始容量为16;DEFAULT_INITIAL_CAPACITY = 1 << 4，即2的4次方，便于后续的扩容操作
- table最大容量为2的30次方;MAXIMUM_CAPACITY = 1 << 30
- table默认的负载因子DEFAULT_LOAD_FACTOR = 0.75,只有元素总量达到总容量的75%才会进行扩容
- 扩容每次扩容为原有容量的2倍,保证了容量n为2的x次方
- 允许键、值均为null
主要方法解析
- put(key,value)方法：
- 如果定位到的数组位置没有元素 就直接插入
- 如果定位到的数组位置有元素就和要插入的key比较
- 如果key相同就直接覆盖
- 如果key不相同，就判断p是否是一个树节点
- 如果是就调用e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value)将元素添加进入
- 如果不是就遍历链表插入
- 插入后判断是否达到转换红黑树的临界值8，若达到则进行红黑树的转换
- get(key)方法:
- 根据key的hashCode计算对应的hash(int类型)
- 然后通过(n - 1) & hash 得到元素存放的位置
- 调用getNode(hash,key):
- 先根据hash的模运算得到索引再比较key
- 满足(k = e.key) == key || (key != null && key.equals(k))条件则返回当前节点e：
- 先比较key是否地址相等（即同一对象），相等则直接返回e
- 若对象不为同一对象（地址不等）则进行内容比较（equals方法），若内容相同，也返回e
- 返回对应节点
- 最后判断得到的节点是否为空，若不为空则返回e.value
具体Put()流程
put方法：
public V put(K key, V value) {
return putVal(hash(key), key, value, false, true);
}
//onlyIfAbsent，if true，则表示只要当前节点的value != null则不会改变当前节点的value值
final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
boolean evict) {
Node<K,V>[] tab; Node<K,V> p; int n, i;
//判断当前的table是否为空,若为空或长度为0,进行扩容初始化,并将其扩容后的长度赋值给n
if ((tab = table) == null || (n = tab.length) == 0)
//resize()中对table进行了初始化操作
n = (tab = resize()).length;
//判断数组当前索引没有元素,则直接添加新节点
if ((p = tab[i = (n - 1) & hash]) == null)//当n为2的次方数时(扩容时必须已经考虑到这个条件),满足(n - 1) & hash 等价于 hash % n,这里采用&运算性能更高
tab[i] = newNode(hash, key, value, null);
else {
//若当索引处有节点元素
Node<K,V> e; K k;
//1.如果key相等
if (p.hash == hash &&
((k = p.key) == key || (key != null && key.equals(k))))
//直接覆盖
e = p;
//2.key不相等的情况,判断当前节点是否是TreeNode,即是红黑树的情况
else if (p instanceof TreeNode)
e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
//3.key不相等,在链表后添加新节点,即链表的情况
else {
//遍历链表结构
for (int binCount = 0; ; ++binCount) {
//链表结构中没有对应的key
if ((e = p.next) == null) {
//添加新的节点
p.next = newNode(hash, key, value, null);
if (binCount >= TREEIFY_THRESHOLD - 1) //这里binCount是从0开始计数，所以需要与TREEIFY_THRESHOLD - 1 = 8 - 1 = 7进行比较
//将当前链表结构转换成对应的树结构
treeifyBin(tab, hash);
break;
}
//树中有对应的key的节点,跳出遍历
if (e.hash == hash &&//判断是否产生hash碰撞，产生碰撞后比较其key值是否真正相等
((k = e.key) == key || (key != null && key.equals(k))))
//相等则跳出循环，当前e即为对应key的节点
break;
//即 p = p.next
p = e;
}
}
//若e不为空则说明存在当前key的节点
if (e != null) { // existing mapping for key
V oldValue = e.value;
if (!onlyIfAbsent || oldValue == null)
//将新value赋值给节点e
e.value = value;
afterNodeAccess(e);
//返回当前key对应的旧的value
return oldValue;
}
}
++modCount;
if (++size > threshold)
resize();
afterNodeInsertion(evict);
return null;
}流程图：
之前看了很多博客上的流程图，我只想说 like a piece of shit，大部分人都是进行copy，根本没完善细节也没有结合源码进行理解和思考。建议可以对照该图和其他博客的图示进行对比，找出不同的地方，以及理解为什么不一样。
get流程：
public V get(Object key) {
Node<K,V> e;
//找到对应key的节点并返回value
return (e = getNode(hash(key), key)) == null ? null : e.value;
}
final Node<K,V> getNode(int hash, Object key) {
Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
//当table的长度大于0且根据hash的摸计算得到对应的索引元素不为空
if ((tab = table) != null && (n = tab.length) > 0 &&
(first = tab[(n - 1) & hash]) != null) {
//线对第一个节点进行判断,当一个节点的hash相等,key内存地址相等,key对象的内容相等
if (first.hash == hash && // always check first node
((k = first.key) == key || (key != null && key.equals(k))))
//满足条件后返回对应的节点
return first;
//第一个节点的条件不满足的情况下,进行遍历链表结构或树结构查找是否有对应的值
if ((e = first.next) != null) {
//判断当前节点是否为TreeNode,当Map中的某个链表存储的长度过长会自动转换为树结构
if (first instanceof TreeNode)
//遍历树结构取出对应的值
return ((TreeNode<K,V>)first).getTreeNode(hash, key);
//链表结构,一直遍历直到节点为null
do {
//若当前节点满足条件就进行返回该节点
if (e.hash == hash &&
((k = e.key) == key || (key != null && key.equals(k))))
return e;
} while ((e = e.next) != null);
}
}
return null;
}内部hash函数的实现？
static final int hash(Object key) {
int h;
//根据key的hashcode计算对应的hash值
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位异或
// >>>:无符号右移，忽略符号位，空位都以0补齐
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//相对于取模运算而言,运算效率高速度快
}
- 计算int hash = 对key的hashCode做hash操作（高16bit不变，低16bit和高16bit做了一个异或）
- 计算先table下标 = (n - 1) & hash
HashMap的求余%和&运算转换问题
1.为什么计算hash时使用移位和异或进行计算？
首先看看代码：
static final int hash(Object key) {
int h;
//根据key的hashcode计算对应的hash值
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位异或
// >>>:无符号右移，忽略符号位，空位都以0补齐
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);//相对于取模运算而言,运算效率高速度快
}
答：
- 首先hashCode为int类型，占用了4个字节，一共32位
- 右移16位的原因是当table的length过小时，保证高16位和低16位都参与运算
- 同时移位异或提高计算效率高
2.为什么使用table默认长度是16 = 2^4？
答：只有n = 2^x 才能满足 hash % n == (n - 1) & hash
面试考点
1.put，get原理及流程？
- put参考上述流程
- get比较简单，容易理解，结合源码理解。
2.内部数据结构？ 数组 + 链表 + 红黑树
3.扩展会问解决hash冲突的方法有哪些？
- 开放地址法
- 链地址法（HashMap实现）
- 再哈希法
4.自定义对象作为key存在什么问题？
因为每次hash时是根据对象的hashCode进行hash函数的操作，如果自定义对象作为key必须重写Object的hashCode()方法和equals()方法。这样才能保证每次相等的对象得到的hash值是一样的，防止键值改变。所以通常使用String和Integer类型作为键，因为他们内部都已经重写了hashCode()和equals()方法。
举个反例：如果不重写hashcode方法，则put时调用Object的hashcode方法，每次获取的是根据内存地址获取的。当两个不同对象具备相同值时，得到不同的hashcode，存放到不同的table下标中，所以达不到同key值进行覆盖的效果。同样在取时根据new出来的相同值的对象则取到的可能是null或其他值，无法获取之前同key值的value。
5.高并发可能出现的安全性问题？
- 数据丢失
- resize()导致链表死循环
注：jdk1.7会出现扩容导致的链表死循环问题，但是jdk1.8已经解决了该问题。
该问题可以参考博客：https://www.jianshu.com/p/6be00db9ddbb