1.hashmap的底层数据结构

众所皆知map的底层结构是类似邻接表的结构,但是进入1.8之后,链表模式再一定情况下又会转换为红黑树
在JDK8中,当链表长度达到8,并且hash桶容量超过64(MIN_TREEIFY_CAPACITY),会转化成红黑树,以提升它的查询、插入效率底层哈希桶的数据结构是数组,所以也会涉及到扩容的问题。
当MyHashMap的容量达到threshold域值时,就会触发扩容。扩容前后,哈希桶的长度一定会是2的次方。

1.1 为什么用红黑树

那么为什么用红黑树呢?之前都是用的链表,之前的文章有提到链表的随机访问效率是很低的,因为需要从head一个个往后面找,那么时间复杂度就是O(n),但是如果是红黑树因为红黑树是平衡二叉树,说白了就是可以索引的,那么时间复杂度只有O(logn),这样效率就可以得到很大的提高
也许有人就想问了,那为什么还搞个链表啊,直接用红黑树不就完了:
1.链表比红黑树简单,构造一个红黑树要比构造链表复杂多了,所以在链表不多的情况下,整体性能上来看,当链表不长的时候红黑树的性能不一定有链表高
2.还有一个节点的添加和删除的时候,需要对红黑树进行旋转,着色等操作,这个就比链表的操作复杂多了
3.所以为链表设置一个阈值用来界定什么时候进行树化,什么时候维持链表,从中间取得一个均衡是很重要的

1.2 为什么阈值是64,链表长度到8

刚刚讲到红黑树查找效率是O(logn)那么8的log是3,而使用链表,我们之前也有提到,源码会进行折半查找(参考之前linkedlist源码分析)那就是8/2 = 4 平均查找长度是4,所以在8的时候是比较合适的因为3比4小
再比如链表长度为6的时候,红黑树会退化为链表同理:6=》log=2~3 和8类似,但是6/2=3也很快,而且红黑树很复杂,所以是用的链表,至于其中的数字7的作用是缓冲一下,避免再长度为7,8徘徊的时候会频繁修改为红黑树和链表
还有为什么是64,参考网上记录是:再低于64的时候容量比较小,hash碰撞的几率比较大,这种时候出现长链表的可能性比较大,这种原因导致的长链表我们应该避免,而是采用扩容的策略避免不必要的树化

接下来我们观察一下hashmap的继承结构,了解一下

【数据结构】8.java源码关于HashMap-LMLPHP

1.3 还有个问题负载因子的作用

0.75f负载因子过高会导致链表过长,查找键值对时间复杂度就会增高,负载因子过低会导致hash桶的个数过多,空间复杂度变高


注意构造函数:

hash桶没有再构造函数中进行初始化,而是再第一次存储键值的时候进行初始化,initialCapacity返回一个大于等于初始化容量大小的最小2的幂次方

 2.hashmap的增长策略

 2.1 插入数据

1.插入数据的时候首先会判断hash桶是否为空,如果为空会进行初始化,这是避免调用构造函数之后没有数据导致,而且再初始化的时候会调用扩容策略这个后面再讲
通过刚刚的学习我们知道hashmap有三种数据存放模式:数组,链表,红黑树
判断是否为空,如果为空,直接数组存放
这里有个细节

hash(key)和(n - 1) & hash 的使用
第一个对key进行hash取值

 2.1.1 为什么要用hash(key),当然hash肯定是必须的,不然object对象怎么定位数组索引但是hashcode不行么?

这里是因为hashcode是32位的数据,用hashcode和n相与的时候,如果n比较小,那么高位的数据基本就没用到(2的16次幂以上的数据),那么就会导致hash碰撞的概率加大
这里hash(key)的操作是吧hashcode右移16位在和原来的hashcode进行异或操作,相当于是吧高位的信息合并到低位上,然后在和n做与运算,这样高位低位的信息全部都有,综合的话hash碰撞的概率相应减低

 2.1.2 (n-1)&hash是什么操作hash%n不行么?

------------------------------------------------------------------------------------------------------------------------------------
说明一下,这两个操作都是取余操作,之前有人说是取模,这里科普一下,取模和取余是不一样的
取模(百度百科):取模运算(“Module Operation”)和取余运算(“Complementation ”)两个概念有重叠的部分但又不完全一致。主要的区别在于对负整数进行除法运算时操作不同。取模主要是用于计算机术语中。取余则更多是数学概念。模运算在数论和程序设计中都有着广泛的应用,从奇偶数的判别到素数的判别,从模幂运算到最大公约数的求法,从孙子问题到凯撒密码问题,无不充斥着模运算的身影。虽然很多数论教材上对模运算都有一定的介绍,但多数都是以纯理论为主,对于模运算在程序设计中的应用涉及不多。
7 mod 4 = 3(商 = 1 或 2,1<2,取商=1)
-7 mod 4 = 1(商 = -1 或 -2,-2<-1,取商=-2)
7 mod -4 = -1(商 = -1或-2,-2<-1,取商=-2)
-7 mod -4 = -3(商 = 1或2,1<2,取商=1)
R = a -c*b
比如-7 mod 4 => -7 = 1 -2 * 4
求模运算和求余运算在第一步不同: 取余运算在取c的值时,向0 方向舍入(fix()函数);而取模运算在计算c的值时,向负无穷方向舍入(floor()函数)。

符号相同时,两者不会冲突。比如,7/3=2.3,产生了两个商2和37=3*2+1或7=3*3+(-2)。因此,7rem3=1,7mod3=1。符号不同时,两者会产生冲突。比如,7/(-3)=-2.3,产生了两个商-2和-37=(-3)*(-2)+1或7=(-3)*(-3)+(-2)。因此,7rem(-3)=1,7mod(-3)=(-2)

------------------------------------------------------------------------------------------------------------------------------------

好的,我们继续讨论(n-1)&hash和hash%n的问题

之前也有说到hashmap的扩容策略是大于等于初始化容量大小的最小2的幂次方,那么也就是说n是2的倍数,转换成2进制也就是最低位是0,再进行-1,那就是奇数
而且进行&操作

这里注意我们的n是2的多次幂,那么就是000100000000类似这样的二进制,减一的结果就是除了最高位其余一下都是1也就是:000011111111111
这个时候和原来的数据hash做&操作,就会把超出这个length范围的数据全部设置为0,也就是这个范围以内的数据不会变

Example:

8 =》 0000 0000 0000 1000
8 - 1 =》 0000 0000 0000 0111
然后不论什么数据与8-1做&操作,那么范围都在 0111之内,也就是7以内包含7范围再0~7,这样懂了吧,比如1000000&(7-1)结果就是0~7
当然出现这种情况有个必要的条件就是长度必须是2的n次幂,这样再二进制数列中,永远只有一个位置是1,其余位置是0,-1之后,这个位置一下的数据全包含再里面&就是截取低位的数据,吧高位去掉,相当于是取余了
因为不论什么数字都是x = a1*2^(n-1) + a2*2^(n-2) + … + a(n-1)*2^(1) + a(n)*2^(0),高位的肯定都是2的y次幂的倍数,所以去掉倍数,剩下的就是余数,不知道我这么说大家有没有理解。。。
大家还可以看看我之前的博客:https://www.cnblogs.com/cutter-point/p/11091727.html

如果不为空那么就要进行链表化或者树化了

 2.1.3 如何链表化

 说白了就是再hash桶的数组上获取这个位置上的node节点,然后循环遍历获取到最后一个节点,然后插入到节点末尾

//链表存放
for (int binCount = 0; ; ++binCount) {
    if ((e = p.next) == null) {
        //链表尾部插入,p的next判断是否为空
        p.next = newNode(hash, key, value, null);
        //当链表的长度大于等于树化阀值,并且hash桶的长度大于等于MIN_TREEIFY_CAPACITY,链表转化为红黑树
//                        if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
//                            treeifyBin(tab, hash);
        break;
    }
    //链表中包含键值对
    if (e.hash == hash &&
            ((k = e.key) == key || (key != null && key.equals(k))))
        break;
    p = e;
}

2.1.4 构造红黑树树化

红黑树的变换规则可以参考我之前的博客:https://www.cnblogs.com/cutter-point/p/10976416.html

我们什么时候会进行树化呢???
就是当我们的链表长度超过或等于8个的时候

【数据结构】8.java源码关于HashMap-LMLPHP

至于如何吧这个链表组建为红黑树,这个以后单独开章节细细探讨。。。。

2.2 扩容策略resize

//数组扩容
public Node<K,V>[] resize() {
    Node<K,V>[] oldTab = table;
    int oldCap = (oldTab == null) ? 0 : oldTab.length;
    int oldThr = threshold;
    int newCap, newThr = 0;
    //如果旧hash桶不为空
    if (oldCap > 0) {
        ////超过hash桶的最大长度,将阀值设为最大值
        if (oldCap >= MAXIMUM_CAPACITY) {
            threshold = Integer.MAX_VALUE;
            return oldTab;
        }
        //新的hash桶的长度2被扩容没有超过最大长度,将新容量阀值扩容为以前的2倍
        //扩大一倍之后,小于最大值,并且大于最小值
        else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
                oldCap >= DEFAULT_INITIAL_CAPACITY)
            //左移1位,也就是扩大2倍
            newThr = oldThr << 1;
    }
    else if (oldThr > 0) //如果旧的容量为空,判断阈值是否大于0,如果是那么就把容量设置为当前阈值
        newCap = oldThr;
    else {               // zero initial threshold signifies using defaults
        newCap = DEFAULT_INITIAL_CAPACITY;
        newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
    }

    //如果阈值还是0,重新计算阈值
    if (newThr == 0) {
        //当HashMap的数据大小>=容量*加载因子时,HashMap会将容量扩容
        float ft = (float)newCap * loadFactor;
        //如果容量还没超MAXIMUM_CAPACITY的loadFactor时候,那么就返回ft,否则就是反馈int的最大值
        newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
                (int)ft : Integer.MAX_VALUE);
    }
    //hash桶的阈值
    threshold = newThr;
    //初始化hash桶
    @SuppressWarnings({"rawtypes","unchecked"})
    Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
    table = newTab;

    if (oldTab != null) {
        //遍历旧数组
        for (int j = 0; j < oldCap; ++j) {
            Node<K,V> e;
            //如果旧的hash桶不为空,需要将旧的hash表里的键值对重新映射到新的hash桶中
            if ((e = oldTab[j]) != null) {
                oldTab[j] = null;
                //只有一个节点,通过索引位置直接映射
                if (e.next == null)
                    newTab[e.hash & (newCap - 1)] = e;  //取余
                    //如果是红黑树,需要进行树拆分然后映射
//                    else if (e instanceof TreeNode)
//                        ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
                else { // preserve order
                    //如果是多个节点的链表,将原链表拆分为两个链表,两个链表的索引位置,一个为原索引,一个为原索引加上旧Hash桶长度的偏移量
                    Node<K,V> loHead = null, loTail = null;
                    Node<K,V> hiHead = null, hiTail = null;
                    Node<K,V> next;
                    do {
                        next = e.next;
//                            在遍历原hash桶时的一个链表时,因为扩容后长度为原hash表的2倍,假设把扩容后的hash表分为两半,分为低位和高位,
//                            如果能把原链表的键值对, 一半放在低位,一半放在高位,这样的索引效率是最高的
                        //这里的方式是e.hash & oldCap,
                        //经过rehash之后,元素的位置要么是在原位置,要么是在原位置再移动2次幂的位置。对应的就是下方的resize的注释
                        //为什么是移动2次幂呢??注意我们计算位置的时候是hash&(length - 1) 那么如果length * 2 相当于左移了一位
                        //也就是截取的就高了一位,如果高了一位的那个二进制正好为1,那么结果也相当于加了2倍
                        //hash & (length * 2 - 1) = length & hash + (length - 1) & hash
                        if ((e.hash & oldCap) == 0) {
                            //如果这个为0,那么就放到lotail链表
                            if (loTail == null)
                                loHead = e;
                            else
                                loTail.next = e;
                            loTail = e;
                        }
                        else {
                            //如果length & hash 不为0,说明扩容之后位置不一样了
                            if (hiTail == null)
                                hiHead = e;
                            else
                                hiTail.next = e;
                            hiTail = e;
                        }
                    } while ((e = next) != null);
                    if (loTail != null) {
                        loTail.next = null;
                        //而这个loTail链表就放在原来的位置上
                        newTab[j] = loHead;
                    }
                    if (hiTail != null) {
                        hiTail.next = null;
                        //因为扩容了2倍,那么新位置就可以是原来的位置,右移一倍原始容量的大小
                        newTab[j + oldCap] = hiHead;
                    }
                }
            }
        }
    }
    return newTab;
}

总结就是扩容的时候吧数组大小扩大一倍,相当于左移1位,并且要重新计算hash散列值,找对应的位置填充
链表也要进行拆分,链表的拆分主要就体现在:
如果原来hash索引的位置就是这里,那么还是连接再原来的节点上,如果取余到对应的位置的节点,数组扩大一倍,我们原来的计算方式是hash&(n - 1)
那么如果我们大小扩大一倍结果就是:hash&(2n - 1)=hash&n + hash&(n-1)因为n是2的n次幂,除了对应的位置为1其余位置都为0
那么这里就可以转换为hash&(2n - 1)=hash&n + hash&(n-1) => n + hash&(n-1) => oldIndex + oldCap 也就是旧索引位置加上旧的容量大小

 3.hashmap查找数据

查找对于红黑树部分我们略过:
至于其他部分,也就是跟之前大同小异了,还是hash取位置,然后取余获取对应的索引下标
首先检查是不是第一个,如果是那就直接返回了
如果不是循环遍历链表找到对应的key为止

final Node<K,V> getNode(int hash, Object key) {
    Node<K,V>[] tab; Node<K,V> first, e; int n; K k;
    //注意这一步中(n - 1) & hash 的值 等同于 hash(k)%table.length
    if ((tab = table) != null && (n = tab.length) > 0 &&
            //这里是计算相当于是取余的索引位置(n - 1) & hash 等价于hash % n
            //而且由于hashmap中的length再tableSizeFor的时候,就把长度设置为2的n次幂了,那么n-1之后的值,就是最高位全都是0,下面位数全是1
            //这个也就是取hash的低位的值
            (first = tab[(n - 1) & hash]) != null) {
        if (first.hash == hash && // always check first node
                ((k = first.key) == key || (key != null && key.equals(k))))
            return first;
        if ((e = first.next) != null) {
            //暂时不考虑红黑树
//                if (first instanceof TreeNode)
//                    return ((TreeNode<K,V>)first).getTreeNode(hash, key);
            do {
                if (e.hash == hash &&
                        ((k = e.key) == key || (key != null && key.equals(k))))
                    return e;
            } while ((e = e.next) != null);
        }
    }
    return null;
}

 4.hashmap删除数据

4.1 树形退化
红黑树,我们就略过吧,这里篇幅有限不做探讨。。。。

 5.关于hashmap的特殊操作

这里可以讲讲hashmap的特殊地方了
1.hashmap是允许null键和值的,而hashtable就不允许了


参考:
https://juejin.im/post/5a7719456fb9a0633e51ae14
https://blog.csdn.net/xingfei_work/article/details/79637878
https://juejin.im/post/5bed97616fb9a049b77fefbf
https://www.zhihu.com/question/30526656
https://juejin.im/post/5cb09c85e51d456e3428c0cf

08-23 02:58