【Java面试进阶】关于HashMap容量初始化的几个问题

谁践踏了优雅 2022-09-12 15:55 177阅读 0赞

### 关于HashMap容量初始化的几个问题 ###

*  size和capacity
 *  loadFactor和threshold
 *  为什么要设置HashMap的初始化容量呢？
 *  HashMap中容量的初始化
 *  HashMap中初始容量的合理值
 *  总结

首先，HashMap中定义了如下变量：  
![HashMap中的变量][HashMap]  
其中，我们主要关注：`size`、`loadFactor`、`threshold`、`DEFAULT_LOAD_FACTOR`和`DEFAULT_INITIAL_CAPACITY`.

HashMap类中有一下主要成员变量：

*  transient int size:
    
     *  记录了Map中KV对的个数
 *  loadFactor
    
     *  装载印子，用来衡量HashMap满的程度。loadFactor的默认值是0.75f。
 *  int threshold：
    
     *  临界值，当实际KV个数超过threshold时，HashMap会将容量扩容，threshold=容量\*加载因子
 *  除了以上这些重要成员变量外，HashMap中还有一个和它们密切相关的概念：capacity
    
     *  容量：如果不指定，默认容量是16，即1<<4

那么问题来了：size和capacity之间有啥关系？为什么要定义这两个变量，loadFactor和threshold又是干什么的？

# size和capacity #

HashMap中的size和capacity之间的区别其实解释起来也挺简单的。我们知道，HashMap就像一个“桶”，那么**capacity就是这个桶“当前”最多可以装多少元素，而size表示这个桶已经装了多少元素**。示例代码：

public class TestMap {
        
        public static void main(String[] args) throws NoSuchFieldException, NoSuchMethodException, InvocationTargetException, IllegalAccessException {
        
            Map<String, String> map = new HashMap<>();
            map.put("Hello","Wolrd");
    
            Class<?> mapType = map.getClass();
            Method capacity = mapType.getDeclaredMethod("capacity");
            capacity.setAccessible(true);
            System.out.println("capacity:"+capacity.invoke(map));
    
            Field size = mapType.getDeclaredField("size");
            size.setAccessible(true);
            System.out.println("size : "+size.get(map));
        }
    }

执行结果如下（注意，在执行时添加VM参数：`--illegal-access=permit`）：  
![执行结果][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6ZWw5YiA6Z-t6I-c_size_20_color_FFFFFF_t_70_g_se_x_16]  
默认情况下，**一个HashMap的容量（capacity）是16，设计成16的好处主要是可以使用按位与替代取模来提升hash的效率**。

HashMap是具有扩容机制的。**在一个HashMap第一次初始化的时候，默认情况下他的容量是16，当达到扩容条件的时候，就需要进行扩容了，会从16扩容成32**。

HashMap的重载的构造函数中，有一个是支持传入initialCapacity的，那么我们尝试着设置一下，看结果如何：

public class TestMap {
        
        public static void main(String[] args) throws NoSuchFieldException, NoSuchMethodException, InvocationTargetException, IllegalAccessException {
        
            Map<String, String> map = new HashMap<>(1);
    
            Class<?> mapType = map.getClass();
            Method capacity = mapType.getDeclaredMethod("capacity");
            capacity.setAccessible(true);
            System.out.println("capacity : " + capacity.invoke(map));
    
            Map<String, String> map7 = new HashMap<>(7);
    
            Class<?> mapType7 = map7.getClass();
            Method capacity7 = mapType7.getDeclaredMethod("capacity");
            capacity7.setAccessible(true);
            System.out.println("capacity : " + capacity7.invoke(map7));
    
    
            Map<String, String> map9 = new HashMap<>(9);
    
            Class<?> mapType9 = map9.getClass();
            Method capacity9 = mapType9.getDeclaredMethod("capacity");
            capacity9.setAccessible(true);
            System.out.println("capacity : " + capacity9.invoke(map9));
        }
    }

执行结果：  
![执行结果][watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6ZWw5YiA6Z-t6I-c_size_20_color_FFFFFF_t_70_g_se_x_16 1]  
也就是说，默认情况下HashMap的容量是16，但是，如果用户通过构造函数指定了一个数字作为容量，那么Hash会选择大于等于该数字的第一个2的幂作为容量。(1->1、7->8、9->16)

建议：**在初始化HashMap的时候，应该尽量指定其大小。尤其是当你已知map中存放的元素个数时**。

# loadFactor和threshold #

HashMap有扩容机制，就是当达到扩容条件时会进行扩容，从16扩容到32、64、128…那么，这个扩容条件指的是什么呢？

其实，**HashMap的扩容条件就是当HashMap中的元素个数（size）超过临界值（threshold）时就会自动扩容**。

在HashMap中， t h r e s h o l d = l o a d F a c t o r ∗ c a p a c i t y threshold = loadFactor \* capacity threshold=loadFactor∗capacity。

loadFactor是装载因子，表示HashMap满的程度，默认值为0.75f，设置成0.75有一个好处，那就是0.75正好是3/4，而capacity又是2的幂。所以，两个数的乘积都是整数。对于一个默认的HashMap来说，默认情况下，当其size大于12(16\*0.75)时就会触发扩容。

public class TestMap {
        
        public static void main(String[] args) throws NoSuchFieldException, NoSuchMethodException, InvocationTargetException, IllegalAccessException {
        
            Map<String, String> map = new HashMap<>();
            map.put("Hello_1", "World_1");
            map.put("Hello_2", "World_2");
            map.put("Hello_3", "World_3");
            map.put("Hello_4", "World_4");
            map.put("Hello_5", "World_5");
            map.put("Hello_6", "World_6");
            map.put("Hello_7", "World_7");
            map.put("Hello_8", "World_8");
            map.put("Hello_9", "World_9");
            map.put("Hello_10", "World_10");
            map.put("Hello_11", "World_11");
            map.put("Hello_12", "World_12");
            Class<?> mapType = map.getClass();
    
            Method capacity = mapType.getDeclaredMethod("capacity");
            capacity.setAccessible(true);
            System.out.println("capacity : " + capacity.invoke(map));
    
            Field size = mapType.getDeclaredField("size");
            size.setAccessible(true);
            System.out.println("size : "+size.get(map));
    
            Field threshold = mapType.getDeclaredField("threshold");
            threshold.setAccessible(true);
            System.out.println("threshold : " + threshold.get(map));
    
            Field loadFactor = mapType.getDeclaredField("loadFactor");
            loadFactor.setAccessible(true);
            System.out.println("loadFactor : " + loadFactor.get(map));
    
            map.put("Hello_13", "World_13");
            Method capacity2 = mapType.getDeclaredMethod("capacity");
            capacity2.setAccessible(true);
            System.out.println("capacity : " + capacity2.invoke(map));
    
            Field size2 = mapType.getDeclaredField("size");
            size2.setAccessible(true);
            System.out.println("size : "+size2.get(map));
    
            Field threshold2 = mapType.getDeclaredField("threshold");
            threshold2.setAccessible(true);
            System.out.println("threshold : " + threshold2.get(map));
    
            Field loadFactor2 = mapType.getDeclaredField("loadFactor");
            loadFactor2.setAccessible(true);
            System.out.println("loadFactor : " + loadFactor2.get(map));
        }
    }

执行结果：  
![执行结果3][3]当HashMap中的元素个数达到13的时候，capacity就从16扩容到32了。

另外，HashMap中还提供了一个支持传入initialCapacity,loadFactor两个参数的方法，来初始化容量和装载因子。不过，一般不建议修改loadFactor的值。

# 为什么要设置HashMap的初始化容量呢？ #

首先测试在不指定初始化容量和指定初始化容量的情况下性能如何，代码如下：

public class TestMap {
        
        public static void main(String[] args) throws NoSuchFieldException, NoSuchMethodException, InvocationTargetException, IllegalAccessException {
        
            int aHundredMillion = 10000000;
    
            Map<Integer, Integer> map = new HashMap<>();
            long s1 = System.currentTimeMillis();
            for (int i = 0; i < aHundredMillion; i++) {
        
                map.put(i, i);
            }
            long s2 = System.currentTimeMillis();
            System.out.println("未初始化容量，耗时 ： " + (s2 - s1));
    
            Map<Integer, Integer> map1 = new HashMap<>(aHundredMillion / 2);
            long s5 = System.currentTimeMillis();
            for (int i = 0; i < aHundredMillion; i++) {
        
                map1.put(i, i);
            }
            long s6 = System.currentTimeMillis();
            System.out.println("初始化容量5000000，耗时 ： " + (s6 - s5));
    
            Map<Integer, Integer> map2 = new HashMap<>(aHundredMillion);
            long s3 = System.currentTimeMillis();
            for (int i = 0; i < aHundredMillion; i++) {
        
                map2.put(i, i);
            }
            long s4 = System.currentTimeMillis();
            System.out.println("初始化容量为10000000，耗时 ： " + (s4 - s3));
        }
    }

执行结果：  
![执行结果1][1]  
从结果中，我们可以知道，在已知HashMap中将要存放的KV个数的时候，设置一个合理的初始化容量可以有效的提高性能。如果我们没有设置初始容量大小，随着元素的不断增加，HashMap会发生多次扩容，而HashMap中的扩容机制决定了每次扩容都需要重建hash表，是非常影响性能的。

我们还发现，同样是设置初始化容量，设置的数值不同也会影响性能，那么当我们已知HashMap中即将存放的KV个数的时候，容量设置成多少为好呢？

# HashMap中容量的初始化 #

默认情况下，当我们设置HashMap的初始化容量时，实际上HashMap会采用第一个大于该数值的2的幂作为初始化容量。当我们通过HashMap(int initialCapacity)设置初始容量的时候，HashMap并不一定会直接采用我们传入的数值，而是经过计算，得到一个新值，目的是提高hash的效率。(1->1、3->4、7->8、9->16)

*  在Jdk 1.7和Jdk 1.8中，HashMap初始化这个容量的时机不同。jdk1.8中，在调用HashMap的构造函数定义HashMap的时候，就会进行容量的设定。而在Jdk 1.7中，要等到第一次put操作时才进行这一操作。

不管是Jdk 1.7还是Jdk 1.8，计算初始化容量的算法其实是如出一辙的，主要代码如下：

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;

# HashMap中初始容量的合理值 #

当我们使用HashMap(int initialCapacity)来初始化容量的时候，jdk会默认帮我们计算一个相对合理的值当做初始容量。那么，是不是我们只需要把已知的HashMap中即将存放的元素个数直接传给initialCapacity就可以了呢？

initiaCapacity = (需要存储的元素个数 / 负载因子) + 1。注意负载因子（即loaderfactor）默认为0.75,如果暂时无法确定初始值大小，请设置为16（即默认值）。

# 总结 #

*  创建一个HashMap的时候，如果我们已知这个Map中即将存放的元素个数，给HashMap设置初始容量可以在一定程度上提升效率。
 *  为了最大程度的避免扩容带来的性能消耗，我们建议可以把默认容量的数字设置成expectedSize / 0.75F + 1.0F 。在日常开发中，可以使用`Map<String, String> map = Maps.newHashMapWithExpectedSize(10);`，来创建一个HashMap，计算的过程guava会帮我们完成。

[HashMap]: /images/20220828/b4f7e65d13eb4898b39a3e7d7fb1ee8b.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6ZWw5YiA6Z-t6I-c_size_20_color_FFFFFF_t_70_g_se_x_16]: /images/20220828/1bd51e2884434305898338b5248205b1.png
[watermark_type_ZHJvaWRzYW5zZmFsbGJhY2s_shadow_50_text_Q1NETiBA6ZWw5YiA6Z-t6I-c_size_20_color_FFFFFF_t_70_g_se_x_16 1]: /images/20220828/876553c03a5b41fc95410709534c97aa.png
[3]: /images/20220828/1e9ccc7ae67c4f9ab8edf7fec5fe9aa8.png
[1]: /images/20220828/cb23f0bbbdec470ca0c88ac11e306bc4.png