【Java入门提高篇】Day23 Java容器类详解(六)HashMap源码分析(中)

  上一篇中对HashMap中的基本内容做了详细的介绍,解析了其中的get和put方法,想必大家对于HashMap也有了更好的认识,本篇将从了算法的角度,来分析HashMap中的那些函数。

HashCode

  先来说说HashMap中HashCode的算法,在上一篇里,我们看到了HashMap中的put方法是这样的:

    public V put(K key, V value) {
        return putVal(hash(key), key, value, false, true);
    }

  那这个hash函数又是什么呢?让我们来看看它的真面目:

    /**
     * 将高位与低位进行与运算来计算哈希值。因为在hashmap中使用2的整数幂来作为掩码,所以只在当前掩码之上的位上发生
     * 变化的散列总是会发生冲突。(在已知的例子中,Float键的集合在小表中保持连续的整数)因此,我们应用一个位运算
     * 来向下转移高位的影响。 这是在综合考虑了运算速度,效用和质量之后的权衡。因为许多常见的散列集合已经合理分布
     * (所以不能从扩散中受益),并且因为我们使用树来处理bin中发生的大量碰撞的情况,所以我们尽可能以代价最低的方式
     * 对一些位移进行异或运算以减少系统损失, 以及合并由于hashmap容量边界而不会被用于散列运算的最高位的影响。
     *
     * todo 扰动函数
     */
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

  可以看出,这里并不是简单的使用了key的hashCode,而是将它的高16位与低16位做了一个异或操作。(“>>>”是无符号右移的意思,即右移的时候左边空出的部分用0填充)这是一个扰动函数,具体效果后面会说明。接下来再看看之前的putval方法:

 1     final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
 2                    boolean evict) {
 3         Node<K,V>[] tab; Node<K,V> p; int n, i;
 4         //如果当前table未初始化,则先重新调整大小至初始容量
 5         if ((tab = table) == null || (n = tab.length) == 0)
 6             n = (tab = resize()).length;
 7         //(n-1)& hash 这个地方即根据hash求序号,想了解更多散列相关内容可以查看下一篇
 8         if ((p = tab[i = (n - 1) & hash]) == null)
 9             //不存在,则新建节点
10             tab[i] = newNode(hash, key, value, null);
11         else {
12             Node<K,V> e; K k;
13             //先找到对应的node
14             if (p.hash == hash &&
15                     ((k = p.key) == key || (key != null && key.equals(k))))
16                 e = p;
17             else if (p instanceof TreeNode)
18                 //如果是树节点,则调用相应的putVal方法,这部分放在第三篇内容里
19                 //todo putTreeVal
20                 e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
21             else {
22                 //如果是链表则之间遍历查找
23                 for (int binCount = 0; ; ++binCount) {
24                     if ((e = p.next) == null) {
25                         //如果没有找到则在该链表新建一个节点挂在最后
26                         p.next = newNode(hash, key, value, null);
27                         if (binCount >= TREEIFY_THRESHOLD - 1) // -1 for 1st
28                             //如果链表长度达到树化的最大长度,则进行树化,该函数内容也放在第三篇
29                             //todo treeifyBin
30                             treeifyBin(tab, hash);
31                         break;
32                     }
33                     if (e.hash == hash &&
34                             ((k = e.key) == key || (key != null && key.equals(k))))
35                         break;
36                     p = e;
37                 }
38             }
39             //如果已存在该key的映射,则将值进行替换
40             if (e != null) { // existing mapping for key
41                 V oldValue = e.value;
42                 if (!onlyIfAbsent || oldValue == null)
43                     e.value = value;
44                 afterNodeAccess(e);
45                 return oldValue;
46             }
47         }
48         //修改次数加一
49         ++modCount;
50         if (++size > threshold)
51             resize();
52         afterNodeInsertion(evict);
53         return null;
54     }

  注意看第八行的代码:

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

  (n - 1) & hash 即通过key的hash值来取对应的数组下标,并非是对table的size进行取余操作。

  那么,为什么要这样做呢?首先,扰动函数的目的就是为了扩大高位的影响,使得计算出来的数值包含了高 16 位和第 16 位的特性,让 hash 值更加深不可测

来降低碰撞的概率。从hash方法的注释中,我们也可以找到答案,一般的散列,其实都是做取余处理,但是HashMap中的table大小是2的整数次幂,也就是说,肯定不是质数,那么在取余的时候,偶数的映射范围势必就要小了一半,这样效果显然就差很多,而且,除法和取余其实是很慢的操作,所以在JDK8中,使用了一种很巧妙的方式来进行散列。首先,table的大小size设置成了2的整数次幂,这样使用size-1就变成了掩码,下面是我找的一张图,能很好的解释这个过程:

  n是table的大小,默认是16,二进制即为10000,n - 1 对应的二进制则为1111,这样再与hash值做“与”操作时,就变成了掩码,除了最后四位全部被置为0,而最后四位的范围肯定会落在(0~n-1)之间,正好是数组的大小范围,散列函数的妙处就在于此了。

简直不能更稳,一波操作猛如虎。

  那么我们继续上一篇的栗子,我们来一步一步分析一下,小明和小李的hash值的映射过程:

  小明的hash值是756692,转换为二进制为10111000101111010100,table的大小是32,n-1=31,对应的二进制为:11111,做“与”运算之后,得到的结果是10100,即为20。

  小李的hash值是757012,转换为二进制为10111000110100010100,与11111做与运算后,得到的结果也是10100,即20,于是就与小明发生了冲突,但还是要先来后到,于是小李就挂在了小明后面。

  散列函数看完了,我们接下来再看看扩容函数。

扩容函数

  扩容函数其实之前也已经见过了,就在上面的putVal方法里,往上面翻一翻,第六行可以看到resize函数,这就是扩容函数,让我们来看看它的庐山真面目:

 1     /**
 2      * 初始化或将table的大小进行扩容。 如果table为null,则按照字段threshold中的初始容量目标进行分配。
 3      * 否则,因为我们使用2次幂进行扩容,所以在新表中,来自每个bin中的元素必须保持在相同的索引处,或者以原偏移量的2次幂进行移动。
 4      */
 5     final Node<K,V>[] resize() {
 6         Node<K,V>[] oldTab = table;
 7         int oldCap = (oldTab == null) ? 0 : oldTab.length;
 8         int oldThr = threshold;
 9         int newCap, newThr = 0;
10         if (oldCap > 0) {
11             if (oldCap >= MAXIMUM_CAPACITY) {
12                 threshold = Integer.MAX_VALUE;
13                 return oldTab;
14             }
15             //新的容量扩展成原来的两倍
16             else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
17                     oldCap >= DEFAULT_INITIAL_CAPACITY)
18                 //阈值也调整为原来的两倍
19                 newThr = oldThr << 1; // double threshold
20         }
21         else if (oldThr > 0) // initial capacity was placed in threshold
22             newCap = oldThr;
23         else {               // zero initial threshold signifies using defaults
24             newCap = DEFAULT_INITIAL_CAPACITY;
25             newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
26         }
27         if (newThr == 0) {
28             float ft = (float)newCap * loadFactor;
29             newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
30                     (int)ft : Integer.MAX_VALUE);
31         }
32         threshold = newThr;
33         @SuppressWarnings({"rawtypes","unchecked"})
34         Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
35         table = newTab;
36         //将旧数组中的node重新散列到新数组中
37         if (oldTab != null) {
38             for (int j = 0; j < oldCap; ++j) {
39                 Node<K,V> e;
40                 if ((e = oldTab[j]) != null) {
41                     oldTab[j] = null;
42                     if (e.next == null)
43                         newTab[e.hash & (newCap - 1)] = e;
44                     else if (e instanceof TreeNode)
45                         ((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
46                     else { // preserve order
47                         Node<K,V> loHead = null, loTail = null;
48                         Node<K,V> hiHead = null, hiTail = null;
49                         Node<K,V> next;
50                         do {
51                             next = e.next;
52                             if ((e.hash & oldCap) == 0) {
53                                 if (loTail == null)
54                                     loHead = e;
55                                 else
56                                     loTail.next = e;
57                                 loTail = e;
58                             }
59                             else {
60                                 if (hiTail == null)
61                                     hiHead = e;
62                                 else
63                                     hiTail.next = e;
64                                 hiTail = e;
65                             }
66                         } while ((e = next) != null);
67                         if (loTail != null) {
68                             loTail.next = null;
69                             newTab[j] = loHead;
70                         }
71                         if (hiTail != null) {
72                             hiTail.next = null;
73                             newTab[j + oldCap] = hiHead;
74                         }
75                     }
76                 }
77             }
78         }
79         return newTab;
80     }

  这里可以看到,如果原来的table还未被初始化的话,调用该函数后就会被扩容到默认大小(16),上一篇中也已经说过,HashMap也是使用了懒加载的方式,在构造函数中并没有初始化table,而是在延迟到了第一次插入元素之后。

  当使用put插入元素的时候,如果发现目前的bins占用程度已经超过了Load Factor所设置的比例,那么就会发生resize,简单来说就是把原来的容量和阈值都调整为原来的2倍,之后重新计算index,把节点再放到新的bin中。因为index值的计算与table数组的大小有关,所以扩容后,元素的位置有可能会调整:

  以上图为例,如果对应的hash值第五位是0,那么做与操作后,得到的序号不会变,那么它的位置就不会改变,相反,如果是1,那么它的新序号就会变成原来的序号+16,。

  好像也不是很多嘛,嗯,算法部分就先介绍到这里了,之后的一篇再来说说HashMap中的EntrySet,KeySet和values(如果时间够的话顺便把迭代器也说一说)。

  好了,本篇就此愉快的结束了,最后祝大家端午节快乐!如果觉得内容还不错的话记得动动小手点关注哦,你的支持就是我最大的动力!

原创声明,本文系作者授权云+社区发表,未经许可,不得转载。

如有侵权,请联系 yunjia_community@tencent.com 删除。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏数据魔术师

运筹学教学 | 十分钟教你求解分配问题(assignment problem)

biu~ biu~ biu~ 我们的运筹学教学推文又出新文拉 还是熟悉的配方,熟悉的味道 今天向大家推出的是 运筹学教学--第六弹 分配问题(Assignmen...

4388
来自专栏木可大大

二进制那些事

理清字符集和字符编码关系中介绍到计算机内部由集成电路决定了计算机的信息只能用二进制数处理。本期将介绍二进制那些事。 移位运算 移位运算指的是将二进制数值的各数位...

3288
来自专栏海天一树

2015年第二十一届全国青少年信息学奥林匹克联赛初赛普及组C++详细答案

https://wenku.baidu.com/view/76e5f672284ac850ad0242f3.html?from=search

782
来自专栏刘君君

JDK8的HashMap源码学习笔记

2528
来自专栏算法修养

HDU 1233 还是畅通工程(Kruskal)

还是畅通工程 Time Limit: 4000/2000 MS (Java/Others)    Memory Limit: 65536/32768 K (J...

2465
来自专栏java一日一条

Java TreeMap 源码解析

可以看到,相比HashMap来说,TreeMap多继承了一个接口NavigableMap,也就是这个接口,决定了TreeMap与HashMap的不同:

451
来自专栏智能计算时代

Analyze tweets in under 30 minutes using Node-RED

I created a Node-RED app in Bluemix which searches for a specified keyword, user...

2736
来自专栏深度学习与计算机视觉

算法-两个栈实现队列

题目: 用两个栈实现一个队列。队列的声明如下,请实现它的两个函数appendTail和deleteHead,分别完成在队列尾部插入结点和在队列头部删除结点的...

19410
来自专栏我是业余自学C/C++的

栈(stack)是一种特殊的线性表,其插入(也称入栈或压栈)和删除(也称出栈或弹栈)操作都在表的同一端进行。这一端被称为栈顶(top)另一端称为栈底端(bott...

581
来自专栏菩提树下的杨过

javascript:查找“跳号”号码

业务背景: 航空货运系统中,“货运代理商”会定期从“航空公司”领取一定数量的纸质运单(每张纸上有一个单号),这些单号都是连续的(即:每次可以理解为领取一个“号段...

1748

扫码关注云+社区