HashMap 的初始容量设置、原因、方法、应用

HashMap 是一个非常重要、必知必会的知识点。

在 Java 面试中，HashMap 经常会被问到，如果面试官想要深挖，大概率就会追问 HashMap 的容量设置。

例如：在实际使用时，我们并没有给 HashMap 设置容量，如果现在要新创建一个 HashMap ，如何设置这个 HashMap 的容量呢，说说你的方法，以及为什么这么操作？

创建一个 HashMap：
Map<String, String> map = new HashMap<String, String>();

本文，我们通过源码、图文结合的方式，一起来深入解析下。

为什么要设置 HashMap 的初始容量

设置一个合适的初始化容量，可以有效地提高性能。

初始容量过小，需要频繁扩容，每次扩容都要重建 hash 表，影响性能。

初始容量设置过大，又会浪费内存。

HashMap 容量分析

HashMap 的底层是数组和链表（ JDK 1.8 优化后，为数组+链表+红黑树）。

在 Java 中，数组和链表都是保存数据比较简单的数据结构。

  • 数组的特点：查询简单，插入删除比较复杂。
  • 链表的特点：查询简单，插入和删除比较容易。

数组和链表相互结合，各自发挥优势。

我们来分析下 HashMap 的源码：

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4; // aka 16
   /**
    * The number of key-value mappings contained in this map.
    */
   transient int size;

  final int capacity() {
       return (table != null) ? table.length :
           (threshold > 0) ? threshold :
           DEFAULT_INITIAL_CAPACITY;
   }

代码示例中，有两个容易混淆的字段：size、capacity 。

  • size ：是指 Map 中的元素个数。
  • capacity ：是指 Map 的容量。

举个例子帮助消化：

我们可以将 HashMap 看作是一个“桶”，容量（capacity）就是这个桶当前最多可以装多少元素，即数组的长度；而元素个数（size），则表示这个桶已经装了多少元素。

HashMap 的所有方法，都没有提供获取对应属性的方法，要如何证实这个操作呢？

可以参考下这两种方法：

  • 通过反射。
  • 通过 Debug ，启动测试类跟踪代码。
public class Test {
    public static void main(String[] args) throws Exception {
        Map<String,Object> result = new HashMap<>();

        result.put("Test","Test");

        Class<?> mapType = result.getClass();
        Method capacity = mapType.getDeclaredMethod("capacity");
        capacity.setAccessible(true);
        System.out.println(capacity.invoke(result));

        System.out.println(result.size());
    }
}

HashMap 默认构造方法中的一段操作：

/**
   * Constructs an empty <tt>HashMap</tt> with the default initial capacity
   * (16) and the default load factor (0.75).
   */
  public HashMap() {
      this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
  }

这段代码中，默认的初始化容量是 16 ，装填因子是 0.75 。

装填因子是什么？容量与哈希冲突又有什么关系呢？

哈希冲突

前面，我们介绍了容量和装填因子，如果说容量标识这个容器中可以装多少个元素的话，那么装填因子就标识这个容器中添加了多少元素之后就会出现冲突。

HashMap的存储结构：

HashMap 的初始容量设置、原因、方法、应用

调用 put 方法，给 Map 中添加元素，可以看到 put() 方法：

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

put() KV 值时，调用了一个 hash() 方法，传入的参数是 key 的值：

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

简单总结下：

  • 这个方法实现了：通过 Key 的 HashCode 判断需要放入到数组中的那个位置。
  • 装填因子主要用来判断，当容器中的容量达到装填因子计算值时，就会产生哈希冲突，这个时候就要使用链表对于冲突元素进行存储。

hash()的实现

上述代码示例中，在 put() 方法调用时，调用了一个 hash() 方法，传入的参数为 key 的值，实现方法：

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

通过获取 key 的 hashCode() 方法，来进行 Hash 值的计算。

这里的 hashCode() 方法，是 Java 中 Object 方法的对象。

即：在 Java 中，所有的对象都有一个 hashCode() 方法。

public native int hashCode();

这个方法 native 标记，调用了本地方法进行生成，而这个本地方法就是被调用执行的 C / C++ 中的代码。

这里，我们只需要关注下面这个计算方式就行了。

因为通过一系列的底层调用之后，反馈到 Java 代码中的，就是一个 int 类型的数据。

(h = key.hashCode()) ^ (h >>> 16)

先来看一下 >>> 运算符。

>>> 表示无符号右移，也叫逻辑右移，即若该数为正，则高位补0，而若该数为负数，则右移后高位同样补0。

按二进制形式，把所有的数字向右移动对应的位数，低位移出（舍弃），高位的空位补零。

对于正数来说，和带符号右移相同；对于负数来说不同，其他结构和 >> 相似。

public static void main(String[] args) {
    int a = -1,count = 0;
    while (a != 0){
        count += a & 1;
        a >>>= 1;
    }
    System.out.println(count);
}

^ 运算符，在 Java 中表示异或，符号两边的数据必须为二进制数。

它的计算方式，则是按照对应位数，位置相同则为 0 ，位置不同则为 1 。

1000^1010 = 0010

也就是说，在通过 hash() 方法计算之后的值，应该是其哈希值与哈希值的无符号右移值，进行了异或操作。

public class Test {
    public static void main(String[] args) throws Exception {
        String  key = "Test";
        System.out.println("Test的Hash值: "+key.hashCode());
        System.out.println("Hash值无符号右移: " + (key.hashCode() >>> 16));
        int h;
        int result = (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
        System.out.println("按照规则计算结果："+result);
    }
}

运行结果：
HashMap 的初始容量设置、原因、方法、应用

通过上面的计算，得出结论：

  • 对于 Hash 值进行 key.hashCode() >>> 16 的操作，就是对 hash 值除以 65536 之后的商。
  • 异或操作，相当于不带进位的二进制加法。也就是说，最终获取到值会落到 1~16 的范围内。
  • 对于超过 65535 的数据，会出现落在这个范围之外的数据。因此，对初始容量的设置、数组最大长度的设置，都离不开 65535 这个数字。

为什么容量是16？

在没有为 HashMap 设置初始大小时，HashMap 会使用如下的构造方法进行 HashMap 的创建。

上面介绍中，我们是通过反射的方式获取 capacity 的值，在这个方法中并没有对 capacity 进行设置。

/**
 * Constructs an empty <tt>HashMap</tt> with the default initial capacity
 * (16) and the default load factor (0.75).
 */
public HashMap() {
    this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted
}

在这个方法注释中，我们也看到了 all other fields defaulted 所有的其他配置都是默认配置。

在 HashMap 源码中，有这样一段代码：

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

会看到注释的意思是：容量大小必须是 2 的 n 次方大小。

问题就来了：

2 的 N 次方有很多，为什么就只选择了16 ？

如果不是 2 的 N 次方数，又会有什么问题？

我们先来看一段代码，这个代码是 Java 提供的、可以创建初始化大小的 HashMap 对象。

public HashMap(int initialCapacity) {
       this(initialCapacity, DEFAULT_LOAD_FACTOR);
   }

这段代码中，调用了一个 this 方法。

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);
  }

这里最大设置的容量大小是 1 << 30 。

在后面的操作中，有 tableSizeFor(initialCapacity) 一个操作，会将设置的大小进行一个新的计算之后，再进行赋值。

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

当传入的大小为 28，会自动计算为 32 。

总结

在运算的过程中，整个的扩容、计算 hash 等操作，都是通过位运算进行的。位运算直接对内存数据进行操作，通过位运算得到的结果，比通过算术运算进行进制转换要更快。因此，如果将 HashMap 的容量设置为 2 的 N 次方，采用位运算计算方式，将极大地提高计算效率。

在上面的代码示例中，我们在计算 hash 之后得到的结果，会在运算之后都落在 1~16 之内。至于为啥要使用 16 作为初始容量，官方并没有明确说明。之所以采用 16 作为初始化的容量 ，可能是因为 16 这个数字更为合适，因为设置的太大浪费内存，而设置的太小扩容操作很消耗资源。

面试题库

2024最全大厂Java面试题解析

2024天猫京东Java面试题解析

2024阿里Java高频面试题解析

2024最新腾讯Java面试题解析

2024最新大厂Spring考题解析

2024最新大厂Java面试题解析

2024大厂MySQL面试题解析

2024大厂Redis面试考题解析

0 条回复 A文章作者 M管理员
    暂无讨论，说说你的看法吧