HashMap源码中值得学习的一些东西

简介：

HashMap是我们在Java中用来保存key-value值使用频率较高的一个工具，其本身是对数据结构哈希表的一个具体实现，本文主要是以源码为主来解决我们下面提出的问题

1、HashMap是如何将一个对象的hashCode转换为数组中的索引？
　　2、当发生冲突时，HashMap是如何解决冲突的？
　　3、HashMap在什么情况下会扩容？怎么扩容？
　　4、HashMap的线程安全问题

一、HashMap是如何将一个对象的hashCode转换为数组中的索引？

首先我们看一下是如何获取hashcode的

 static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
  }

这段代码主要做了如下几下事情：
1、如果key值为null则将key值设置为0
2、根据object中的native方法获取到一个int型的hashcode
3、hashcode的二进制位移动16位
4、将本身的hashcode与位移后的hashcode进行了一个^运算，得出结果

步骤3和步骤四是将已经获取到的hashcode进行了一个高低位的干扰运算。
我们知道int类型是取值范围是-2147483648到2147483648，加起来大概40亿的映射空间。
直接用来当作索引的话hashmap的默认容量就需要40Y个了，但是我们知道hashmap的初始空间为16。
所以需要将得到的hashcode映射为数组中的索引，我们看下面代码：

    tab[i = (n - 1) & hash]

这个就是将hashcode转化为索引的方法，n为数组的长度。
& 运算后就是高位值全部归零，只使用低位值来保证得到的索引是不超过当前数组的长度的。
（这里也就说明了为什么扩容是扩2次幂，因为这样数组的长度减1之后得到的二进制位尾数都是1）

但是这样问题就来了，两个完全不一样的hashcode，但是低位相同就会发生冲突，所以就有了步骤三和步骤四。

我们看一下下面的计算过程：

h:              1111 1111 1111 1111 1111 0000 1110 1010
h >>> 16:       0000 0000 0000 0000 1111 1111 1111 1111
h ^ (h >>> 16): 1111 1111 1111 1111 0000 1111 0001 0101

这样将高低位都参与到运算中就避免了低位相同导致出现冲突的情况。

二、当发生冲突时，HashMap是如何解决冲突的？

首先我们看一下添加元素进哈希表的putVal方法一个流程图

Untitled Diagram.png

然后我们分析一下源码:

1、判断当前hash表的容量是否为空，为空则进行扩容

if ((tab = table) == null || (n = tab.length) == 0)
     n = (tab = resize()).length;

2、根据得到的索引判断该位置是否有元素，没有则保存

if ((p = tab[i = (n - 1) & hash]) == null)
     tab[i] = newNode(hash, key, value, null);

3、判断当前的key值和发生冲突位置的key值是否相等，相等稍后直接覆盖

 if ((p = tab[i = (n - 1) & hash]) == null)
            tab[i] = newNode(hash, key, value, null);

        if (e != null) { // existing mapping for key
                V oldValue = e.value;
                if (!onlyIfAbsent || oldValue == null)
                    e.value = value;
                afterNodeAccess(e);
                return oldValue;
            }

4、判断当前的元素是否为红黑树中的一个节点，是在添加到树中

else if (p instanceof TreeNode)
        e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);

5、遍历该链表上的元素，将当前元素保存到最后一位

else {
       for (int binCount = 0; ; ++binCount) {
             if ((e = p.next) == null) {
               p.next = newNode(hash, key, value, null);

6、当链表的长度超过8时，将链表转为红黑树

if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
    treeifyBin(tab, hash);

上面步骤就是将元素添加到哈希表中的过程，其中3-4-5-6是就是解决冲突的方法。
红黑树是在JDK1.8引入进来了，为了解决链表过长导致的效率慢的问题

三、HashMap在什么情况下会扩容？怎么扩容？

首先是在put方法刚开始时，哈希表未初始化时则进行扩容，其次就是在添加完成后

if (++size > threshold)
     resize();

当前的数组长度已经大于threshold（数组长度*0.75）则进行扩容。

为什么不是当长度超过数组长度进行扩容呢？

我们知道，当数组所剩余的长度比我们的元素数量少很多时，
就会发生大量的元素冲突（也未必能填满数组），导致哈希表的效率变慢，
所以我们需要提前对数组进行扩容。默认的0.75的在效率和内存空间上的一个平衡点。

接下来我们看一下扩容里面的一段代码：

else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
         oldCap >= DEFAULT_INITIAL_CAPACITY)
         newThr = oldThr << 1; // double threshold

新数组的长度其实就是旧数组的长度*2,上面也解释了为什么是2。

四、HashMap的线程安全问题

HashMap本身是线程不安全的，在多线程环境下会导致丢失数据，在JDK1.8之前扩容操作还会死循环，CPU飙升100%。

JDK1.7中出现死循环的原因主要是链表在转移数据的过程中，多线程环境下出现环形链表导致的，在JDK1.8中已经使用双链表解决了。

但是在多线程环境下还是不要使用，也不用加同步（锁全部对象导致效率差），直接使用ConcurrentHashMap来解决

参考资料：

https://www.zhihu.com/question/20733617 @胖胖
美团点评技术团队Java8重新认识HashMap https://zhuanlan.zhihu.com/p/21673805