HashMap容量解析

短命女 2022-04-16 01:55 300阅读 0赞

HashMap中有一个有参的构造方法，传递的参数是map初始化的容量。那么给定的参数，HashMap就一定给分配参数对应的容量吗？比如，我传7进去，HashMap就会给分配7个空间吗 ？

答案是：否

因为 HashMap分配的容量可能大于入参，可能小于入参，可能等于入参。为什么会这样？一点点看

### HashMap的构造方法 ###

HashMap有四个构造方法

*  public HashMap() 默认构造方法，默认初始容量为16，加载因子为0.75f
 *  public HashMap(int initialCapacity) 指定初始容量的构造方法，加载因子为默认的0.75f
 *  public HashMap(int initialCapacity, float loadFactor) 指定初始容量和默认加载因子的初始方法
 *  public HashMap(Map<? extends K, ? extends V> m) 以子map为入参，构造新的hashmap

上面有提到HashMap中两个非常关键的变量，容量和加载因子

容量：capacity  HashMap分配的空间个数大小，如果不指定，则默认为16，即HashMap无参构造方法构造出来的map的容量大小。

/**
         * The default initial capacity - MUST be a power of two.
         */
        static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16

装载因子：load factor 用来表示HashMap中元素的填满的程度，loadFactor的默认值为0.75f。

/**
         * The load factor used when none specified in constructor.
         */
        static final float DEFAULT_LOAD_FACTOR = 0.75f;

如果一个map的size大于临界值时，HashMap会自动扩容，将当前容量扩一倍出来，并重新计算每个对象的位置并存放。

加载因子，是hashmap在扩容时需要的，表示Hsah表中元素的填满的程度。待hashmap中存放的对象数量大于等于map容量\*加载因子时，hashmap会自动扩容，将map的容量扩大一倍，并将之前的对象重新进行hash寻址，并存放到新的地址中。

加载因子越大，填满的元素越多，空间利用率越高，但是冲突的机会增大；加载因子越小，填满的元素越少，冲突的机会越小，但空间浪费增多。hash值冲突时，会将对象在同一位置存放链表，增加了数据结构的复杂性。冲突的机会越大，则查找的成本越高；冲突的机会越小，查找的成本越小，换言之，查找时间就越小，更快一些。   
必须在 "冲突率"与"空间利用率"之间寻找一种平衡与折衷， Java默认的容量设置为16，默认的加载因子设置为0.75。

临界值：threshold 当实际K-V个数超过threshold时，HashMap会将容量扩容，threshold＝容量\*加载因子。

对象数量：size hashmap中实际存放的对象数量。

### 容量初始化 ###

上面四个构造方法，看源码，会发现，第一个和第二个构造方法，都会跟到第三个构造方法。这里重点看下第三个构造方法。

/**
         * 构造一个hashmap，在指定初始化容量和装载因子的情况下
         *
         * @param  initialCapacity 初始化容量
         * @param  loadFactor      装载因子
         * @throws IllegalArgumentException 容量或装载因子非法时抛异常
         */
        public HashMap(int initialCapacity, float loadFactor) {
            // 如果容量小于0，则抛非法容量异常
            if (initialCapacity < 0)
                throw new IllegalArgumentException("Illegal initial capacity: " +
                                                   initialCapacity);
    
            // 如果容量大于最大容量，则将hashmap容量设置为最大容量，即 1 << 30 
            if (initialCapacity > MAXIMUM_CAPACITY)
                initialCapacity = MAXIMUM_CAPACITY;
    
            // 如果装载因子小于等于0 或 装载因子非数字，抛非法异常
            if (loadFactor <= 0 || Float.isNaN(loadFactor))
                throw new IllegalArgumentException("Illegal load factor: " +
                                                   loadFactor);
    
            // 将装载因子赋给方法
            this.loadFactor = loadFactor;
            
            // 根据初始化容量参数构建存放对象的table大小，并设置临界值threshold
            // 此处有疑点，为何将容量直接设置为临界值，临界值 = 容量 * 装载因子 的啊，有知道的朋友解答下
            this.threshold = tableSizeFor(initialCapacity);
        }

上面的方法中，基本可以看到，如果传入的容量大于HashMap可承载最大容量时，容量会被设置为最大容量。

最后的一个方法 tableSizeFor(initialCapacity)来看下

/**
         * 根据传参的容量数字，返回一个2的整数次幂的容量大小
         */
        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;
        }

上面方法，求大于等于入参的最小的2的整数次幂。

### HashMap初始容量测试 ###

测试方法如下

/**
    	 * 容量测试
    	 * @param initCapacity 入参容量
    	 * @return 实际容量
    	 * @throws Exception
    	 */
    	public static int capacityTest(int initCapacity) throws Exception {
    		
    		Map<String, String> map = new HashMap<String, String>(initCapacity);
    		
    		// 通过反射获取容量变量capacity,并调用map对象
    		Method capacity = map.getClass().getDeclaredMethod("capacity");
    		capacity.setAccessible(true);
    		Integer realCapacity = (Integer) capacity.invoke(map);
    		System.out.println("入参容量为" + initCapacity + "时，实际容量为" + realCapacity);
    		return realCapacity;
    	}

在main方法中进行测试

capacityTest(1);
    		capacityTest(2);
    		capacityTest(3);
    		capacityTest(4);
    		capacityTest(7);
    		capacityTest(21);
    		capacityTest(1500000000);

可以得到如下结果  
入参容量为1时，实际容量为1  
入参容量为2时，实际容量为2  
入参容量为3时，实际容量为4  
入参容量为4时，实际容量为4  
入参容量为7时，实际容量为8  
入参容量为21时，实际容量为32  
入参容量为1500000000时，实际容量为1073741824  // 超过最大容量，系统默认为最大容量

如果将给定参数和最终容量换算给2进制的话，则容易理解一些

<table style="width:491px;"> 
 <tbody> 
  <tr> 
   <td style="width:121px;">入参十进制数值</td> 
   <td style="width:123px;">容量十进制表示</td> 
   <td style="width:124px;">入参二进制表示</td> 
   <td style="width:120px;">容量二进制表示</td> 
  </tr> 
  <tr> 
   <td style="width:121px;">1</td> 
   <td style="width:123px;">1</td> 
   <td style="width:124px;">1</td> 
   <td style="width:120px;">1</td> 
  </tr> 
  <tr> 
   <td style="width:121px;">2</td> 
   <td style="width:123px;">10</td> 
   <td style="width:124px;">10</td> 
   <td style="width:120px;">10</td> 
  </tr> 
  <tr> 
   <td style="width:121px;">3</td> 
   <td style="width:123px;">4</td> 
   <td style="width:124px;">11</td> 
   <td style="width:120px;">100</td> 
  </tr> 
  <tr> 
   <td style="width:121px;">4</td> 
   <td style="width:123px;">4</td> 
   <td style="width:124px;">100</td> 
   <td style="width:120px;">100</td> 
  </tr> 
  <tr> 
   <td style="width:121px;">7</td> 
   <td style="width:123px;">8</td> 
   <td style="width:124px;">111</td> 
   <td style="width:120px;">1000</td> 
  </tr> 
  <tr> 
   <td style="width:121px;">21</td> 
   <td style="width:123px;">32</td> 
   <td style="width:124px;">10101</td> 
   <td style="width:120px;">100000</td> 
  </tr> 
 </tbody> 
</table>

可以发现大致规律：如果入参除了最高位是1，其余位都是0时，则容量就是入参自己；如果除了最高位之外，其余位还有1，则容量为左移一位，并将其余位全部置0；超过最大容量时，系统默认为最大容量。

### HashMap扩容测试 ###

/**
    	 * 临界值测试
    	 * @throws Exception
    	 */
    	public static void thresholdTest() throws Exception {
    		
    		Map<String, String> map = new HashMap<String, String>();
    		
    		// 获取map扩容时临界阈值  阈值 = 容量 * 加载因子
    		// 默认容量 为16，加载因子 默认为0.75
    	    Field threshold = map.getClass().getDeclaredField("threshold");
    	    Field size = map.getClass().getDeclaredField("size");
    	    Method capacity = map.getClass().getDeclaredMethod("capacity");
    	    
    	    threshold.setAccessible(true);
    	    size.setAccessible(true);
    	    capacity.setAccessible(true);
    	    
    	    // 未存放对象时，各项值测试
    	    System.out.println("start:临界值" + threshold.get(map));
    	    System.out.println("start:size" + size.get(map));
    	    System.out.println("start:容量" + capacity.invoke(map));
    	    
    	    // 临界值、容量测试
    		for (int i=1; i<26; i++) {
    			map.put(String.valueOf(i), i + "**");
    			if (i == 11 || i == 12 || i == 13 || i == 23 || i == 24 || i == 25) {
    				System.out.println("第" + i + "个对象, size为" + size.get(map) + ", 临界值为" + threshold.get(map) + ", 容量为" + capacity.invoke(map));
    			}
    		}
    	}

可以得到

start:临界值0  
start:size0  
start:容量16  
第11个对象, size为11, 临界值为12, 容量为16  
第12个对象, size为12, 临界值为12, 容量为16  
第13个对象, size为13, 临界值为24, 容量为32  
第23个对象, size为23, 临界值为24, 容量为32  
第24个对象, size为24, 临界值为24, 容量为32  
第25个对象, size为25, 临界值为48, 容量为64

可以看到，

容量为16时，当放第12个对象时，容量依然为16，此时 size = 临界值 = 容量 \*  装载因子；

当放第13个对象时，容量扩为32，临界值同步升级为24 = 32 \* 0.75；

容量为32时，当放第25个对象时，size > 临界值24，继续扩容，容量由32升级为64，临界值跟着升级为48。

上面在start处，给的临界值为0，作何解释

找到HashMap中putVal方法，可以看到，初始化后，并未实际分配容量，只是计算出了容量的数值。待第一次put对象进去的生活，Java虚拟机才会实际的分配map的容量空间出来。

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;

以上是最近几天看HashMap的一点总结，因本人水平有限，如果文中有错误或措辞不严谨之处，欢迎批评提出。谢谢。

PS：JDK1.8.0\_181