map家族系列(一)——hashmap

​ 日常开发中，HashMap的使用频率不可谓不频繁，key/value结构使用起来非常方便，JDK在提供出来的版本中也对HashMap进行了不断的优化，存储和查找的性能不断得到提升，本文基于JDK1.8对Hash Map的使用过程进行分析，对源码进行解读。

​ 相信大家在使用HashMap时最常用的是直接使用HashMap的构造函数创建对象，下面我们先来看一下HashMap提供出来的几个构造函数。

• 1 2 3 4

  public () { this.loadFactor = DEFAULT_LOAD_FACTOR; // all other fields defaulted }

• 1 2 3 4

  public (int initialCapacity) { // 调用下方构造函数，眼光直接转向下面一个构造函数，此处直接跳过 this(initialCapacity, DEFAULT_LOAD_FACTOR); }

• 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

  // 直接在创建对象的时候对初始容量进行设置，并自行设置一个负载因子 public (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); }

  ​ 这个构造函数中，对入参进行必要的校验之后，开始对需要创建的对象属性进行赋值。可以看到参数校验完成之后，分别对loanFactor和threshold这两个变量进行赋值，对于threshold的赋值，可能多少会有一点疑惑，为什么不是直接用initialCapacity*loadFactor，而是要单独写一个方法来进行赋值呢？

  ​ 带着上面的疑惑，点开了tableSizeFor(initialCapacity)方法，看到了下面的真容：

  1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

  // 这段代码很是简洁，但运算逻辑却需要仔细推敲 static final int tableSizeFor(int cap) { // 上一步调用时传入的initialCapacity - 1 // 此处假设我们初始化传入的数值为10 int n = cap - 1; // n = 9 /* 这一行包含了这几个步骤： * （1）n先无符号右移1位 0***1001 >>> 1 = 0***0100 * （2）n与n右移一位的值进行或运算 0***1001 | 0***0100 = 0***1101 * （3）将计算出来的最新的值赋值给n n = 0***1101 */ n |= n >>> 1; // n = 0***1101 n |= n >>> 2; // n >>> 2 = 0***0011, 0***1101 | 0***0011 = 0***1111 n |= n >>> 4; // n = 0***1111 n |= n >>> 8; // n = 0***1111 n |= n >>> 16; // n = 0***1111 // 传值正常的情况下，最终返回的n大小一定为>=initialCapacity的2的N次方或MAXIMUM_CAPACITY return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; }

  ​ 到此为止，threshold的赋值过程就完成了，构造函数创建对象的时候对threshold赋的初始值为不小于初始容量的2的N次方。但是，为什么不是initialCapacity*loadFactor呢，我们带着这个疑问直接跳转到HashMap的put过程进行探究。

• 1 2 3 4

  public (Map<? extends K, ? extends V> m) { this.loadFactor = DEFAULT_LOAD_FACTOR; putMapEntries(m, false); }

  ​ 直接传入一个已经存在的oldMap对象，创建出一个新的newMap对象，包含oldMap中的所有元素。第一步最熟悉不过了，设置负载因子。第二步，开始把oldMap对象中的元素全部放入到newMap对象中，putMapEntries方法此处画个重点，留个印象，后面我们撸put方法源码的时候会一行一行来拜读。

​ 我们选择了适合自己的构造函数，创建出了我们需要使用的HashMap对象，创建成功之后，我们要向我们创建出来的对象中放入我们需要存储的数据