HashMap的容量初始值要如何设置?

x33g5p2x  于2021-10-31 转载在 Java  
字(3.2k)|赞(0)|评价(0)|浏览(221)

HashMap的容量初始值要如何设置?

Java中的集合框架是每一个java程序员使用很多的,其中hashMap的使用也是很多的,我之前也写过一篇对hashMap源码进行比较详细分析的博客:链接,读者可以参考学习。然后有看过阿里编程规范的应该知道,规范里指出在使用hashMap时候是可以指定一个初始化的容量的,然后具体原因是什么?

ok,我们还是找到崇山版的编程规范,这是最新的文档,在阿里的《阿里编程规范崇山版》/#(六) 集合处理 /# 17里找到阿里规范对hashMap初始化容量的建议:
【推荐】集合初始化时,指定集合初始值大小。
说明:HashMap 使用 HashMap(int initialCapacity) 初始化,如果暂时无法确定集合大小,那么指定默
认值(16)即可。
正例:initialCapacity = (需要存储的元素个数 / 负载因子) + 1。注意负载因子(即 loader factor)默认
为 0.75,如果暂时无法确定初始值大小,请设置为 16(即默认值)。
反例: HashMap 需要放置 1024 个元素,由于没有设置容量初始大小,随着元素增加而被迫不断扩容,
resize()方法总共会调用 8 次,反复重建哈希表和数据迁移。当放置的集合元素个数达千万级时会影响程序
性能。

从上面信息可以知道几个知识点:

  • HashMap默认的初始化容量是16,也就是不指定的情况,就是16
  • 规范里建议我们设置 initialCapacity = (需要存储的元素个数 / 负载因子) + 1
  • 规范里指出没有指定容量的情况,可能会进行扩容resize,需要重建hash表,比较耗性能

ok,从规范里知道,不指定的情况可能会导致hashMap的扩容问题,什么情况会进行扩容?从HashMap源码里知道大于 initialCapacity /* 负载因子(默认0.75f)的时候就会进行扩容

下面给出一个例子,在指定了容量,性能就会好?

import java.lang.reflect.InvocationTargetException;
import java.lang.reflect.Method;
import java.util.HashMap;
import java.util.Map;

public class HashMapExample{

    public static void main(String[] args) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException{
        Map<String, Object> map = new HashMap<>(4);
        map.put("name" , "tom");
        printHashMapInfo(map);
        map.put("address" , "hangzhou");
        printHashMapInfo(map);
        map.put("tel" , "15522299988");
        printHashMapInfo(map);
        map.put("email", "22999888@qq.com");
        printHashMapInfo(map);
    }

    protected  static void printHashMapInfo(Map<String , Object> map) throws NoSuchMethodException, InvocationTargetException, IllegalAccessException {
        Class<?> mapCls = map.getClass();
        Method capacityMethod = mapCls.getDeclaredMethod("capacity");
        capacityMethod.setAccessible(true);
        System.out.println(String.format("capacity:%s , size :%d" , capacityMethod.invoke(map) , map.size()));

    }
}

在新增到4的时候,进行了扩容,为什么?因为hashMap里达到阈值,容量/*0.75之后,就会进行扩容resize,然后容量从4变成了8

capacity:4 , size :1
capacity:4 , size :2
capacity:4 , size :3
capacity:8 , size :4

然后我们对初始容量进行修改,比如改为6,按照阿里的规范initialCapacity = (需要存储的元素个数 / 负载因子) + 1,再次打印:

capacity:8 , size :1
capacity:8 , size :2
capacity:8 , size :3
capacity:8 , size :4

这次打印处理的结果,可以看出没有进行扩容了,所以这个容量指定不能随便指定

ok,跟到这里,读者是否会有一个疑问?我们刚才传入的初始容量,明明是6,然后打印时候,怎么打印出8了?其实这个是hashMap源码对我们传入的数据进行重新计算,重新找出最近的一个2的n次方的值,比如传入6,距离最近的值就是2的3次方8

具体的源码,可以在hashMap源码里找到

/** * 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;
    }

ok,然后又有一个问题了,hashMap的开发者为什么要将初始容量转变为2的n次方?

这个问题,还是要先看一下源码,比较关键的put逻辑里,可以找到如下代码,hashMap里有计算数组下标的代码逻辑(n-1) & hash

resize扩容的源码:

既然是计算hashMap里数组的下标,所以就不需要特别大,我们可能会想到用取余计算 hash % n,没错,hashMap源码的作者也是考虑到这个,因为在n,也即容量为2的n次方的时候 hash & (n-1) = hash % n,然后为什么不用取余的方法,因为效率没有与运算高,与运算直接是二进制的运算,直接对内存数据进行计算,取余的还是用十进制数据计算,所以效率没有与运算高

然后为什么要使用n-1?,举个例子,默认hashMap初始容量是16,n-1就是15,二进制是1111,然后试试其它的数据,其实发现n为2的n次方的情况,n-1其实都是1111…,然后为什么?因为都是1的情况,和hashcode进行与计算,数据是比较均匀的,比较少有hash冲突的情况

1111和其它二进制数据进行与运算,顺便计算,没有发现相同的数据

找其它非1111…的数据进行与计算,发现,里面都要3个数据是1001,所以这种情况就会出现hash冲突

ok,归纳一下,设置为2的n次方的原因:

  • hash & (n-1) 和 hash % n 在2的n次方的情况,会相等,而且与运算效率更高,所以计算数组下标使用hash & (n-1)
  • n-1,在n为2的n次方的情况,结果都是1111…,所以进行与运算,hash冲突的情况是很少的

本博客需要有一定的hashMap源码阅读经验,所以读者可以阅读我之前博客,链接,然后再来学习这篇博客

相关文章

微信公众号

最新文章

更多