Java集合—HashMap之hash优化算法

HashMap 底层是 数组 + 链表 + 红黑树

数组我们很熟悉,支持随机访问,所以在最优情况下,即 HashMap 没有出现 hash 冲突,没有形成链表或红黑树结构,此时数据都存在数组中,get 方法的查询时间复杂度为 O(1) 。

链表查询时间复杂度 O(n) ,红黑树 O( )。底层的数据结构和对应的时间复杂度是我们研究的基础。

再来看看 HashMap 继承或实现了哪些类和接口。

public class HashMap<K,V> extends AbstractMap<K,V>
    implements Map<K,V>, Cloneable, Serializable {
复制代码

如代码所示,HashMap 实现了 Cloneable、Serializable,说明支持克隆和序列化。

**备注:**所有关于 HashMap 的分析都是基于 JDK1.8 。

2. 源码解析

先来看看常用的基本属性。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
static final float DEFAULT_LOAD_FACTOR = 0.75f;
int threshold;
static final int TREEIFY_THRESHOLD = 8;
static final int UNTREEIFY_THRESHOLD = 6;
transient Node<K,V>[] table;
transient int size;
复制代码

默认 bucket 数组长度为16,默认负载因子 0.75 ,默认 threshold = 16 * 0.75 = 12 。当数组长度达到 12 时开始扩容。(这都不知道的同学建议去面壁思过)

TREEIFY_THRESHOLD 是指链表长度达到 8 以后转化为红黑树,UNTREEIFY_THRESHOLD 则相反。

size 是 HashMap 中元素的总个数,要和 table 的 length 区分开。

我们着重来看一下 Node ,因为数据都存储在 Node 中。

static class Node<K,V> implements Map.Entry<K,V> {
    final int hash;
    final K key;
    V value;
    Node<K,V> next;
复制代码
  • hash: 根据存储元素的 key 的 hash 值
  • next:因为是数组,肯定要存储下一个节点

2.1 构造函数

思考一个问题:HashMap 是在什么时候给 bucket 数组分配内存的?是 new HashMap() 的时候吗?带着问题我们来看看HashMap 的四种构造函数。

2.1.1 HashMap()

public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}
复制代码

可以看到,无参构造函数只是把 DEFAULT_LOAD_FACTOR 的值(默认 0.75)赋值给 loadFactor,loadFactor 是给 HashTable 用的,所以可以理解为啥正事都没干。

2.1.2 HashMap(int initialCapacity)

一般我们实际使用过程中都是用的这个,在新建一个 HashMap 的时候先预估存储的元素的个数,假设个数为 n ,然后用 n 除以 0.75 ,假设算出的值是 m ,initialCapacity 取不小于 m 的 2 的幂次方对应的值。

举个例子:我现假设要往 HashMap 中存入 17 个值,17 / 0.75 = 22.67 。取不小于 22.67 的最近的 2 的幂次方,最终 initialCapacity 取 32(2的5次方) 。即 new HashMap(32) 。

为什么 initialCapacity 要取 2 的幂次方呢?之后我们讲 put 方法的时候会讲到。

如果我脑残,非要 new HashMap(17) ,会发生什么呢?

来,上源码:

public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}
复制代码

此时,传入的 initialCapacity 是 17,loadFactor 是 0.75 。

第 2~9 行代码都是判断 initialCapacity 的合法性,是否小于 0 ,是否大于最大数组长度等等。

第 11 行代码才是重点,我们来看看 tableSizeFor 方法:

/**
 * Returns a power of two size for the given target capacity.
 */
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}
复制代码

注释,power of two 是二次方的意思。翻译一下就是,根据传进来的数返回一个合适的二次方的结果。 最终的结果就是传入 17,算出来的返回值是 32 ,最后 threshold 等于 32 。 此时 threshold 是临时保存初始化容量 initialCapacity 的值,在后面会有用到。

2.1.3 HashMap(int initialCapacity, float loadFactor)

这个和 2.2.2 的区别是它可以自定义负载因子,但是一般我们都不改负载因子,默认使用 0.75 就行。下面来说说为什么是负载因子是 0.75 。

我们应该很容易理解负载因子应该在 0.5~1.0 之间。

如果小于 0.5,假设取 0.3 。初始化数组长度 16,threshold = 16*0.3 = 4.8 ,也就是数组长度大于 5 的时候进行扩容,扩容到 32 ;以此类推,数组长度 10 的时候,扩容到 64 。越往后,未使用的空间会越来越大,纯属浪费。

如果大于 1,假设取 1.5 。初始化数组长度 16,threshold = 16*1.5 = 24 。大家有没有发现一个问题,一个长度为 16 的数组要存储 24 条数据。那形成链表的几率就是百分之百了。会严重影响到查询的效率。

那为什么在 0.5~1.0 之间选择了 0.75 呢?0.6 行不行,0.8 行不行?

看看源码注释里面的一段话:

* <p>As a general rule, the default load factor (.75) offers a good
* tradeoff between time and space costs.  Higher values decrease the
* space overhead but increase the lookup cost (reflected in most of
* the operations of the <tt>HashMap</tt> class, including
* <tt>get</tt> and <tt>put</tt>).  The expected number of entries in
* the map and its load factor should be taken into account when
* setting its initial capacity, so as to minimize the number of
* rehash operations.  If the initial capacity is greater than the
* maximum number of entries divided by the load factor, no rehash
* operations will ever occur.
复制代码

翻译一下,默认的负载因子 0.75 在时间和空间消耗上提供了一个平衡。较高的值会降低空间使用但是会增加查找消耗(会影响 put 和 get 方法)。map 期望的 entries 数量和负载因子在初始化的时候就要考虑到,这样可以降低 rehash 的次数。如果初始化的数组长度大于 map 存储数据的最大值除以负载因子,将不会有 rehash 发生。

其实官方的说法跟我上面实际使用中的取值方法一样,0.75 是官方认为最优的平衡时间和空间的值。至于 0.75 是怎么推算出来的,这是个数学问题。有兴趣的同学可以自行研究。

**小结:**负载因子默认使用 0.75 就行了,不要自以为是的瞎改。

2.1.4 HashMap(Map<? extends K, ? extends V> m)

比较少用,有兴趣的同学自行研究,不是很重要。

2.1.5 总结

回到我们最初的问题,在构造函数中并没有发现初始化 bucket 数组的操作。所以并不是在这个阶段给数组分配内存的。除此之外,我也讲了推荐的构造函数使用方法。

2.2 hash优化算法

看完了构造方法,我们来看看 put 方法,这也是 HashMap 最重要最复杂的方法。

在详细讲解 put 方法之前,我们先约定好几个变量的定义,以免后面发生混乱。

  • h : 这个表示直接通过 Object 类的 hashCode 方法算出来的值
  • hash : 这个表示优化之后的 hash 值
  • index :这个是数组的角标

来,上源码:

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

我们先看一下 hash(key) 这个方法,然后再看 putVal 方法。

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

h = key.hashCode()) ^ (h >>> 16) 这个就是最核心的 hash 优化算法了。

key.hashCode() 就是调用的 Object 类的 hashCode 方法,算出一个 h 值,int 类型(4 个字节,32 位)。

h ^ (h >>> 16) 这个是干嘛用的呢?我们来举个例子。以我的名字为 key(原谅我臭不要脸),我们得出 “赵小发” 的 hashCode 是 35552727 。转化为二进制是 0000 0010 0001 1110 0111 1101 1101 0111 。

那 h >>> 16 就是把二进制右移 16 位,然后高位空出来的 16 位用 0 补充。

得到的结果是: 0000 0000 0000 0000 0000 0010 0001 1110 。

然后进行 异或算法 (异或算法的结果是相同为 0,不同为 1 )。h ^ (h >>> 16) 算出来的结果如下:

我们通过 hash 方法算出来的就是 0000 0000 0001 1110 0111 1111 1100 1001 。

然后我们进入 putVal 方法 :

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
               boolean evict) {
    Node<K,V>[] tab; Node<K,V> p; int n, i;
    if ((tab = table) == null || (n = tab.length) == 0)
        n = (tab = resize()).length;
    if ((p = tab[i = (n - 1) & hash]) == null)
        tab[i] = newNode(hash, key, value, null);
    else {
        // 省略
        }
    }
   // 省略
}
复制代码

我们这一讲主要是讲 hash 优化算法,所以就不将完整代码截出来了。

onlyIfAbsent、evict 并不是核心的属性,可以忽略。

很明显,第一次 put 的时候是满足第 4 行代码的判断的,此时会执行第 5 行代码。

此时,resize 方法做的事情主要就是第一次给数组分配内存,可以看一下我 debug 的截图。

Java集合—HashMap之hash优化算法

在 resize 方法中, Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap]; 这行代码才是初始化数组,分配内存的操作。所以,这也回答了上面构造函数中的那个问题,HashMap 是在执行 put 方法时给 bucket 数组分配内存的。

resize 方法执行完毕后,table 的 length 是 16 ,即第 5 行代码 n = (tab = resize()).length 的值为 16 。

然后执行第 6 行代码,这个非常非常非常重要。

(n – 1) & hash 这行代码是将数组长度和之前算出来的 hash 值进行与运算,如下所示:

算出来的值 1001 ,二进制是 9 。然后将 9 赋值给 i ,而 i 就是数组的 index 角标。也就是说,key 为“赵小发”的这条数据会被存储在数组的 index 为 9 的那个 Node 里。来,截个图看一下:

Java集合—HashMap之hash优化算法

思考:(n – 1) & hash 本质是啥?

我们之前通过 h ^ (h >>> 16) 算出来了一个 hash 值,但是这个 hash 值太大了,我们最终是要算出一个 index,而这个 index 必须在 0~(n – 1) 之间。那最先想到的应该就是取模算法了,对 n 取模,即 hash / n ,余数就是对应的 index 位置。那为什么不用取模算法呢?原因是性能没有位运算高。

那 (n – 1) & hash 为什么能保证算出来的值在 0~(n – 1) 之间呢?

因为此时 n -1 = 15 ,15 的二进制是 0000 0000 0000 0000 0000 0000 0000 1111 ,前面的 28 位全部是0 。在进行与运算时,无论 hash 的值是多少,进行与运算之后前面的 28 位肯定也是 0 。而结果的后 4 位完全由 hash 的后 4 位决定,并且结果一定小于等于 15 。此时就可以把结果赋值给数组的 index 了。

同样的,如果 n 是 32 ,那么 n – 1 = 31 ,31 的二进制是 0000 0000 0000 0000 0000 0000 0001 1111 。hash 的值无论是多少,(n – 1) & hash 运算后前 27 位都是 0 ,后 5 位完全由 hash 的后 5 位决定,并且结果一定小于等于 31 。

这里对二进制稍微敏感的同学很容易反应过来。

这也充分说明了 HashMap 的数组长度为什么必须是 2 的幂次方。因为只有 2 的幂次方在减 1 之后,它的二进制低位全部为1。

再思考:为什么要用 h ^ (h >>> 16) ?

直接通过 Object 类的 hashCode 算法算出一个 h 值,直接拿来和 (n – 1) 做与运算,不是更简单吗?为什么要多此一举 h ^ (h >>> 16) 。

还是以“赵小发”为 key 来举例,h 值是 0000 0010 0001 1110 0111 1101 1101 0111 。如果这个时候直接拿来和 (n – 1) 做与运算,就是下面这样子。

最终的计算结果由 h 值的后 4 位(0111)决定。那 h 值的前面的 28 位岂不是完全没有参与运算?下面我举几个例子:

0000 0010 0001 1110 0111 1101 1101 0111 ("赵小发")

1000 0010 0001 1110 0111 1101 1101 0111 ("赵大发")

000 1 0010 0001 1110 0111 1101 1101 0111 ("赵二狗")

如上面我加粗的例子来看,高位不同,但是完全不影响和 (n – 1) 做与运算的结果,凭啥?凭啥我赵小发算出来和赵二狗在同一个 index 上面。高 28 位完全不起作用。所以我们要想着,让高位也要参与运算,这样可以减少 hash 冲突。所以要拿 h 和 (h >>> 16) 做运算,让 h 的高 16 位和 h 进行计算,计算的结果再和 (n – 1) 做与运算,最终算出数组的 index 。

再再思考:为什么 h 和 (h >>> 16) 做的是异或运算?

原因是异或运算能更好的保留各部分的特征,与运算结果会向 1 靠拢,或运算结果会向 0 靠拢 。

**总结:**hash 优化算法包含两部分。一是通过 hashCode 值的高16 位参与运算来减少冲突,二是通过与运算而不是取模运算提高性能。

下一篇文章,我们详细梳理下 put 方法的流程, Java集合—HashMap之梳理put方法逻辑 。

原文 

https://juejin.im/post/5e2054d0e51d454d3046aaed

本站部分文章源于互联网,本着传播知识、有益学习和研究的目的进行的转载,为网友免费提供。如有著作权人或出版方提出异议,本站将立即删除。如果您对文章转载有任何疑问请告之我们,以便我们及时纠正。

PS:推荐一个微信公众号: askHarries 或者qq群:474807195,里面会分享一些资深架构师录制的视频录像:有Spring,MyBatis,Netty源码分析,高并发、高性能、分布式、微服务架构的原理,JVM性能优化这些成为架构师必备的知识体系。还能领取免费的学习资源,目前受益良多

转载请注明原文出处:Harries Blog™ » Java集合—HashMap之hash优化算法

赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址