-
HashMap 的默认大小是 16,这个默认值是可以设置的。如果事先知道具体的例子,可以修改默认初始大小,减少动态扩容的次数,提高性能。修改默认初始大小的值时,比如你设置了 500,那么不会真就使用 500 这个值,而可能会使用 512 这种是 2 的幂的值。
为什么要设置是 2 的幂的值?这个跟下面的 index 的值计算有关,请看第 4 点。
-
最大的装载因子为 0.75,当装载因子超过这个值是就会扩容,每次扩容都会扩容为原来的两倍大小。
那么为什么装载因子是 0.75 呢?经研究显示,负载因子是0.75的时候,空间利用率比较高,而且避免了相当多的 Hash 冲突,使得底层的链表或者是红黑树的高度比较低,提升了空间效率(来自网上)。
为啥是扩容为原来的两倍呢?这个具体请看第 4 点。
-
采用链表法来解决冲突,之后再 JDK1.8 中引入了红黑数,主要链表长度太长(默认超过8)时,链表就转换为红黑树。当少于 6 时,又将红黑树转换为链表,因为红黑树要维护平衡,比起链表性能上的优势并不会特别明显。
那么为什么在少于 6 的时候而不是 8 的时候才将红黑树转换为链表呢?假设设计成大于 8 时链表转换为红黑树,小于 8 的时候又转换为链表。如果一个 hashmap 不停的插入、删除。hashmap 中的个数不停地在 8 徘徊,那么就会频繁的发生链表和红黑树之间转换,效率非常低。因此,6 和 8 之间来一个过渡值可以减缓这种情况造成的影响。
-
散列值的获取分两步走:
// 1. hash 值的计算 static final int hash(Object key) { int hash; return key == null ? 0 : (hash = key.hashCode()) ^ hash >>> 16; } // 2. 插入/查找的时候,计算 key 应该被映射到散列表的什么位置 int index = hash(key) & (capacity - 1)
其中方法 hashcode() 返回的是 Java 对象的 hash_code,这是一个 int 类型的值(32 位)。那么为什么在拿到这个值之后,还需要将自己右移 16 位与自己进行异或呢?因为容量较小的时候,在计算 index 那边,真正用到的其实就只有低几位,假如不融合高低位,那么假设 hashcode() 返回的值都是高位的变动的话,那么很容易造成散列的值都是同一个。但是,假如将高位和低位融合之后,高位的数据变动会最终影响到 index 的变换,所以依然可以保持散列的随机性。
那么在计算 index 的时候,为什么不使用
hash(key) % capacity
呢?这是因为移位运算相比取余运算会更快。那么为什么 hash(key) & (capacity - 1) 也可以呢?这是因为在 B 是 2 的幂情况下: A % B = A & (B - 1)。如果 A 和 B 进行取余,其实相当于把 A 那些不能被 B 整除的部分保留下来。从二进制的方式来看,其实就是把 A 的低位给保留了下来。B-1 相当于一个“低位掩码”,而与的操作结果就是散列值的高位全部置为 0 ,只保留低位,而低位正好是取余之后的值。我们取个例子,A = 24,B =16,那么 A%B=8,从二进制角度来看 A =11000 ,B = 10000。A 中不能被 B 整除的部分其实就是 1000 这个部分。接下去,我们需要将这部分保留下来的话,其实就是使用 01111 这个掩码并跟 A 进行与操作,即可将1000 保留下来,作为 index 的值。而 01111 这个值又等于 B-1。所以 A &(B-1)= A%B。但是这个前提是 B 的容量是 2 的幂,那么如何保证呢?我们可以看到,在设置初始大小的时候,无论你设置了多少,都会被转换为 2 的幂的一个数。之外,扩容的时候也是按照 2 倍进行扩容的。所以 B 的值是 2 的幂是没问题的。
Java HashMap 的那么多为什么
卷死我
- 本文链接: /archives/28
- 版权声明: 本博客所有文章除特别声明外,均采用CC BY-NC-SA 3.0 许可协议。转载请注明出处!