老猿说说-HashMap

1. 概述

HashMap 底层的数据结构主要是:数组 + 链表 + 红黑树。其中当链表的长度大于等于 8 时，
链表会转化成红黑树，当红黑树的大小小于等于 6 时，红黑树会转化成链表

HashMap是数组结构，数组的元素可能是单个 Node，也可能是个链表，也可能是个红黑树，
比如数组下标索引为 2 的位置就是一个链表，下标索引为 9 的位置对应的就是红黑树，具体细节我们下文再说

1.1 类注释

从HashMap的类注释中，我们可以得到如下信息：

允许null值，不同于HashTable,是线程不安全的；
load factor(影响因子）默认值是0.75,是均衡了时间和空间损耗算出来的值，较高的值
会减少空间开销（扩容减少，数组大小增长速度变慢）,但增加了查找成本（hash冲突增
加，链表长度变长）,不扩容的条件：数组容量>需要的数组大小/load factor
如果有很多数据需要储存到HashMap中，建议HashMap的容量一开始就设置成足够的大
小，这样可以防止在其过程中不断的扩容，影响性能；
HashMap是非线程安全的，我们可以自己在外部加锁，或者通过
Collections#synchronizedMap来实现线程安全，Collections#synchronizedMap的实现
是在每个方法上加上了synchronized锁；
在迭代过程中，如果HashMap的结构被修改，会快速失败。

1.2 常见属性

//初始容量为16
static final int DEFAULT_INITIAL_CAPACITY=1<<4;
//最大容量
static final int MAXIMUM_CAPACITY =1<<30;
//负载因子默认值
static final float DEFAULT_LOAD_FACTOR=0.75f;
/桶上的链表长度大于等于8时，链表转化成红黑树
static final int TREEIFY_THRESHOLD=8
/桶上的红黑树大小小于等于6时，红黑树转化成链表
static final int UNTREEIFY_THRESHOLD=6;
//HashMap 树最小容量,最少4倍TREEIFY_THRESHOLD，防止经常扩容缩容的开销
static final int MIN_TREEIFY_CAPACITY = 64;

2. 新增

新增 key，value 大概的步骤如下:

空数组有无初始化，没有的话初始化;
如果通过 key 的 hash 能够直接找到值，跳转到 6，否则到 3;
如果 hash 冲突，两种解决方案:链表 or 红黑树;
如果是链表，递归循环，把新元素追加到队尾;
如果是红黑树，调用红黑树新增的方法;
通过 2、4、5 将新元素追加成功，再根据 onlyIfAbsent 判断是否需要覆盖;
判断是否需要扩容，需要扩容进行扩容，结束。

//入参hash:通过hash算法计算出来的值。
//入参onlylfAbsent:false表示即使key已经存在了，仍然会用新值覆盖原来的值，默认为false
final V putVal(int hash, K key, V value, boolean onlylfAbsent,boolean evict){
    //n表示数组的长度，i为数组索引下标，p为i下标位置的Node值
    Node<K,V>[]tab;Node<K,V>p;int n,i;
    //如果数组为空，使用resize方法初始化
    if((tab=table)==nullll(n=tab.length)==0)
        n=(tab=resize().length;
    //如果当前索引位置是空的，直接生成新的节点在当前索引位置上
    if((p=tab[i=(n-1)&hash])==null)
        tab[i]=newNode(hash,key,value,null);
    //如果当前索引位置有值的处理方法，即我们常说的如何解决hash冲突
    }else {
        //e当前节点的临时变量
        Node<K,V>e;Kk;
        //如果key的hash和值都相等，直接把当前下标位置的Node值赋值给临时变量
        if(p.hash==hash&&
        ((k=p.key)==keyll(key!=null&&key.equals(k))))
            e=p;
        //如果是红黑树，使用红黑树的方式新增
        else if (p instanceof TreeNode)
            e=((TreeNode<K,V>)p).putTreeVal(this,tab,hash,key,value);
        //是个链表，把新节点放到链表的尾端
        else{
            for (int binCount = 0; ; ++binCount) {
                //p.next==null表明p是链表的尾节点
                if((e=p.next)==null){
                    //把新节点放到链表的尾部
                    p.next=newNode(hash,key,value,null);
                    //当链表的长度大于等于8时，链表转红黑树
                    if(binCount>=TREEIFY_THRESHOLD-1)
                    treeifyBin(tab,hash);
                    break;
                }
                //链表遍历过程中，发现有元素和新增的元素相等，结束循环
                if(e.hash==hash&&
                ((k=e.key)==keyll(key!=null&key.equals(k))))
                    break;
                //更改循环的当前元素，使p在遍历过程中，一直往后移动。
                p=e;
            }
        }
        //说明新节点的新增位置已经找到了
        if(e!=null){
            V oldValue = e.value
            //当onlylfAbsent为false时，才会覆盖值
            if(!onlylfAbsentlloldValue==null)
                e.value = value ;
            afterNodeAccess(e);
            //返回老值
            return oldValue
        }
    }
    //记录HashMap的数据结构发生了变化
    ++modCount;
    //如果HashMap的实际大小大于扩容的门槛，开始扩容
    if(++size>threshold)
        resize();
    afterNodelnsertion(evict);
    return null;
}

新增的流程上面应该已经表示很清楚了，接下来我们来看看链表和红黑树新增的细节：

2.1 链表的新增

链表的新增比较简单，就是把当前节点追加到链表的尾部，和LinkedList的追加实现一样的。

当链表长度大于等于8时，此时的链表就会转化成红黑树，转化的方法是：treeifyBin,此方法
有一个判断，当链表长度大于等于8,并且整个数组大小大于64时，才会转成红黑树，当数组
大小小于64时，只会触发扩容，不会转化成红黑树，转化成红黑树的过程也比较简单

可能面试的时候，有人问你为什么是8,这个答案在源码中注释有说，中文翻译过来大概的意思是：

链表查询的时间复杂度是O(n),红黑树的查询复杂度是O(log(n))。在链表数据不多的时候，
使用链表进行遍历也比较快，只有当链表数据比较多的时候，才会转化成红黑树，但红黑树需要
的占用空间是链表的2倍，考虑到转化时间和空间损耗，所以我们需要定义出转化的边界值。

在考虑设计8这个值的时候，我们参考了泊松分布概率函数，由泊松分布中得出结论，链表各
个长度的命中概率为：

0:    0.60653066
1:    0.30326533
2:    0.07581633
3:    0.01263606
4:    0.00157952
5:    0.00015795
6:    0.00001316
7:    0.00000094
8:    0.00000006

意思是，当链表的长度是8的时候，出现的概率是0.00000006,不到千万分之一，所以说正常
情况下，链表的长度不可能到达8,而一旦到达8时，肯定是hash算法出了问题，所以在这
种情况下，为了让HashMap仍然有较高的查询性能，所以让链表转化成红黑树，我们正常写
代码，使用HashMap时，几乎不会碰到链表转化成红黑树的情况，毕竟概念只有千万分之一

2.2 红黑树新增节点过程

首先判断新增的节点在红黑树上是不是已经存在，判断手段有如下两种：
1.1. 如果节点没有实现Comparable接口，使用equals进行判断；
1.2. 如果节点自己实现了Comparable接口，使用compareTo进行判断。
新增的节点如果已经在红黑树上，直接返回；不在的话，判断新增节点是在当前节点的左边
还是右边，左边值小，右边值大；
自旋递归1和2步，直到当前节点的左边或者右边的节点为空时，停止自旋，当前节点即为
我们新增节点的父节点；
把新增节点放到当前节点的左边或右边为空的地方，并于当前节点建立父子节点关系；
进行着色和旋转，结束。

//入参h:key的hash值
final TreeNode<K,V> putTreeVal(HashMap<K,V> map, Node<K,V> tab,int h,K k,V v){
    Class<?>kc=null;
    boolean searched = false
    //找到根节点
    TreeNode<K,V>root=(parent!=null)?root():this;
    //自旋
    for(TreeNode<K,V>p=root;;){
        int dir, ph; K pk;
        //p hash值大于h,说明p在h的右边
        if((ph=p.hash)&gt;h)
            dir=-1;
        //p hash值小于h,说明p在h的左边
        else if (ph < h)
            dir = 1;
        //要放进去key在当前树中已经存在了（equals来判断）
        else if ((pk=p.key)==kll(k!=null&&kequals(pk))
            return p;
        //自己实现的Comparable的话，不能用hashcode比较了，需要用compareTo
        else if ((kc== null &&
        //得到key的Class类型，如果key没有实现Comparable就是null
                        (kc = comparableClassFor(k)) == null) ||
                         (dir = compareComparables(kc, k, pk)) == 0) {
            if(!searched){
                TreeNode<K,V> q, ch;
                searched = true;
                if (((ch = p.left) != null &&
                     (q = ch.find(h, k, kc)) != null) ||
                    ((ch = p.right) != null &&
                     (q = ch.find(h, k, kc)) != null))
                return q;
            }
            dir = tieBreakOrder(k, pk);
        }
        TreeNode<K,V> xp = p;
        //找到和当前hashcode值相近的节点（当前节点的左右子节点其中一个为空即可）
        if((p=(dir<=0)?p.left:p.right)==null){
            Node<K,V>xpn=xp.next
            //生成新的节点
            TreeNode<K,V>x=map.newTreeNode(h,k,v,xpn);
            //把新节点放在当前子节点为空的位置上
            if(dir<=0)
                xp.left=X;
            else
                xp.right
            //当前节点和新节点建立父子，前后关系
            xp.next = X;
            x.parent=x.prev=xp;
            if(xpn!=null)
                ((TreeNode<K,V>)xpn).prev=X;
            //balancelnsertion对红黑树进行着色或旋转，以达到更多的查找效率，着色或旋转的几种场
            //着色：新节点总是为红色；如果新节点的父亲是黑色，则不需要重新着色；如果父亲是红色
            //旋转：父亲是红色，叔叔是黑色时，进行旋转
            //如果当前节点是父亲的右节点，则进行左旋
            //如果当前节点是父亲的左节点，则进行右旋
            //moveRootToFront方法是把算出来的root放到根节点上
            moveRootToFront(tab,balancelnsertion(root,x);
            return null;
        }
    }
}

红黑树的新增，要求大家对红黑树的数据结构有一定的了解。面试的时候，一般只会问到新增节
点到红黑树上大概是什么样的一个过程，着色和旋转的细节不会问，因为很难说清楚，但我们要
清楚着色指的是给红黑树的节点着上红色或黑色，旋转是为了让红黑树更加平衡，提高查询的效
率，总的来说都是为了满足红黑树的5个原则：

节点是红色或黑色
根是黑色
所有叶子都是黑色
从任一节点到其每个叶子的所有简单路径都包含相同数目的黑色节点
从每个叶子到根的所有路径上不能有两个连续的红色节点

3 查找

HashMap的查找主要分为以下三步：

初始判断，hash定位到具体的数组下标的元素，判断第一个节点的key是否匹配，匹配则返回值，若不匹配则步骤2
判断当前节点有无next节点，有的话判断是链表类型，还是红黑树类型。
分别走链表和红黑树不同类型的查找方法。
链表查找的关键代码是：

 final Node<K,V> getNode(int hash, Object key) {
        Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
        //初始判断
        if ((tab = table) != null && (n = tab.length) > 0 &&
            //hash定位到数组下标元素
            (first = tab[(n - 1) & hash]) != null) {
            //看到第一个节点key是否匹配，匹配则返回值
            if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
                return first;
             //判断有无next节点
            if ((e = first.next) != null) {
                if (first instanceof TreeNode)
                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
                //采用自旋方式从链表中查找key,e初始为为链表的头节点
                do {
                    //如果当前节点hash等于key的hash,并且equals相等，当前节点就是我们要找的节点
                    //当hash冲突时，同一个hash值上是一个链表的时候，我们是通过equals方法来比较key是己
                    if(e.hash==hash&&
                    ((k=e.key)==keyll(key!=null&&key.equals(k))))
                        return e;
                    //否则，把当前节点的下一个节点拿出来继续寻找
                } while ((e = e.next) != null)
            }
        }
        return null;
    }

红黑树查找的代码很多，我们大概说下思路，实际步骤比较复杂，可以去github上面去查看源

从根节点递归查找；
根据hashcode,比较查找节点，左边节点，右边节点之间的大小，根本红黑树左小右大的特性进行判断；
判断查找节点在第2步有无定位节点位置，有的话返回，没有的话重复2,3两步；
一直自旋到定位到节点位置为止如果红黑树比较平衡的话，每次查找的次数就是树的深度。

总结

HashMap的内容虽然较多，但大多数api都只是对数组+链表+红黑树这种数据结构进行封
装而已，本小节我们从新增和查找两个角度进行了源码的深入分析，分析了是如何对数组、链表
和红黑树进行操作的