日常工作、面试中常遇到的HashMap源码

马士兵 2021-03-12

136

戳蓝字“马士兵”关注我们哦！

细读源码是《马士兵教育》旗下赏析源码的栏目。我们赏析源码的目的不是为了炫技，而是为了去理解作者的设计思想，并取其精华，去其糟粕，从而写出更加优秀的代码。另一方面，也可以给面试加分。代码好的坏的评价，不可避免地会代入个人的主观色彩，大家和而不同。

由于HashMap在日常工作或者的面试中，

遇到的频率非常高，

所以今天就赏析一下HashMap的源码。

本文将从以下三个部分进行讲解：

1、赏析代码中实现优秀，精妙，值得我们借鉴的地方；

2、分析代码实现不好的地方及其原因，以及如何通过重构来解决问题；

3、哪些HashMap的小技巧，可以来提高程序的执行效率；

一.代码中设计好的地方

1.使用2的N次幂作为table数组的长度

使用2的N次幂作为table数组的长度，可以使用与位运算(&)替换取余运算(%)，这样大大提高运算效率，具体而言，当capacity = 2的N次幂时，下面的恒等式总是成立：

hash % capacity == hash & (capacity - 1)。

2.hash值的处理

HashMap不是直接使用hashCode % capacity作为table的索引，而且对hashCode做了下面的处理，代码如下：

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

这个方法的功能就是将hashCode的高16位和低16位进行异或，得到的结果作为最后hash值，然后再对apacity取余操作求索引位置。为什么要这么做呢？方法的注释上详细阐述了作者意图，这里简单翻译一下。这么做的目的是为了减少hash冲突发生的概率，并且只使用了一次移位运算和异或运算，就达到目的，这样对性能的损失几乎忽略不计。

举一个异常典型场景：

当HashMap使用Float类型作为key的时候，key的值为0到1024的所有整数，对这1025个数，求hashCode值，结果的最低14位全部都是0，对capacity 2048取余，得到的结果全部都是0。下面的代码可以验证这点：

public static void main(String[] args) {        for (int i = 0; i < 1024; i++) {            Float f = (float) i;            System.out.println(f.hashCode() % 2048);        }}

上面代码最后输出结果全部都是0。对于Float类型0到1024的1025个整数，如果直接使用hashCode % capacity求在table中的索引，导致的结果就是所有的元素都会定位在table[0]的位置，产生严重的冲突，最后不得不使用链表+红黑色解决冲突，最后导致HashMap在此情况下的性能大幅下降，使用了上面的hash方法处理后，就能很好的避免这个问题的发生。

3.tableSizeFor实现

HashMap的构造函数，可以指定table数组的初始化容量，指定容量的目的是为了避免在添加元素的时候进行的频繁扩容（再hash），影响性能。

初始化容量capacity可以是任意非负整数，而table数组的长度必须是2的N次幂，所以就需要一个tableSizeFor方法，来计算一个最小的大于等于初始化容量capacity的数，并且该数是2的N次幂。

一种非常朴素的实现方法是，不断的乘以2，直到大于等于capacity，代码如下：

static final int tableSizeFor(int cap) {        if (cap <= 1) {            return 1;        }        if (cap >= MAXIMUM_CAPACITY) {            return MAXIMUM_CAPACITY;        }        int ret = 2;        while (ret < cap) {            ret = ret << 1;        }        return ret;    }

但是JDK1.8的实现，给了一种更优的实现方法，采用了二分的思想，代码如下：

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

举个例子，当cap = 17时候，tableSizeFor执行过程如下：

执行n = cap - 1;

n = 17 - 1 = 16 = 10000;

执行n |= n >>> 1;

n = 10000 | 01000 = 11000，将最高的2位设置为1；

执行n |= n >>> 2;

n = 11000 | 00110 = 11110，将最高的4位设置为1；

执行n |= n >>> 4;

n = 11110 | 00001 = 11111，将最高的8位设置为1；

执行n |= n >>> 8;

n = 11111 | 00000 = 11111，将最高的16位设置为1；

执行n |= n >>> 16;

n = 11111 | 00000 = 11111，将最高的32位设置为1；

到此n从最高位往下都是1，n一定等于2的N次幂 - 1，最后 + 1，一定等于2的N次幂。

对比两个方法时间复杂度，朴素的实现方法的时间复杂度是O(log2n)，JKD1.8实现的时间复杂度是O(1)，5次移位运算+5次或运算+1次加法运算，一共11次运算。所以当n > 2048的时候，JDK实现更优。n < 2048的时候，朴素的实现方法更优。

4.扩容resize细节的处理

JKD1.8对resize的过程进行了优化，我们摘取部分代码进行分析，代码如下：

final Node[] resize() {              NodeloHead = null, loTail = null;        NodehiHead = null, hiTail = null;        Nodenext;        e = table[j];        do {            next = e.next;            if ((e.hash & oldCap) == 0) {                if (loTail == null)                    loHead = e;                else                    loTail.next = e;                loTail = e;            } else {                if (hiTail == null)                    hiHead = e;                else                    hiTail.next = e;                hiTail = e;            }        } while ((e = next) != null);        if (loTail != null) {            loTail.next = null;            newTab[j] = loHead;        }        if (hiTail != null) {            hiTail.next = null;            newTab[j + oldCap] = hiHead;        }}

因为HashMap中的table.length是2的N次幂，并且扩容是双倍扩容，table中的某一个node节点是链表时，链表里面的node的hash值对扩容前后的容量oldCapacity和newCapacity取余，其结果要么完全相同，要么只有最高的一位不相同，其余的低位完全相同。

举例说明：

扩容前后分别使用hash % capacity结果只有最高一位不相同，其他低位相同的情况：

oldCapacity = 8，newCapacity = 16，hash = 9

扩容前：(8 - 1) & 9 = 0111 & 1001 = 0001

扩容后：(16 - 1) & 9 = 1111 & 1001 = 1001

0001和1001只有最高位不同，其他低位完全相同。

扩容前后分别使用hash % capacity结果完全相同的情况：

oldCapacity = 8，newCapacity = 16，hash = 5

扩容前：(8 - 1) & 9 = 0111 & 0101 = 0101

扩容后：(16 - 1) & 9 = 1111 & 0101 = 0101

上面的代码的功能就是table的某node一条链表，直接拆分为两条链表，low链表和high链表。判断条件就是看e.hash & oldCap 是否为0，如果为0，表示扩容前后node的位置不变，把其放在low链表；如果不为0，表示扩容前后node的位置要发生变化，把其放在high链表，变化的位置只有最高位，进行加oldCap就可以得到其位置。

最后newTab[j] = low链表头， newTab[j + oldCap] = high链表头即可。

改进前后对比：

1.改进后执行效率更高，没有再hash的过程；

2.解决了并发访问HashMap出现死循环问题。

二.代码中需要改进的地方

1.在if，while，for语句里面使用赋值语句

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                   boolean evict) {          Node[] tab;          Nodep;          int n, i;          if ((tab = table) == null || (n = tab.length) == 0)              n = (tab = resize()).length;           }

(tab = table) == null和(n = tab.length) == 0都是先赋值，然后再做判断，导致了一行代码里面，有4个动作（2个赋值动作，2个判断动作），读起来不是那么容易理解。

通常情况下，我们更习惯去读一行源代码里面只有一个动作的代码。如何解决上面的问题，我们可以对这部分代码进行重构，重构结果如下：

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,                    boolean evict) {          Node[] tab = table;          int n = tab == null ? 0 : tab.length;          if (n == 0) {              tab = resize();              n = tab.length;          }}

重构以后，代码就清晰多了，赋值语句是赋值语句，判断语句是判断语句，读起来更轻松。

2.对象的字段在对象的不同的生命周期代表完全不同的含义

HashMap中有一个非常重要的字段threshold（The next size value at which to resize (capacity * load factor).），存储HashMap下一次进行扩容的阈值，但是在HashMap构造函数执行完的时候，threshold的业务含义是capacity（table数组的长度）。

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

其中this.threshold = tableSizeFor(initialCapacity)，threshold存储的是capacity（table数组的长度），而不是下次扩容的阈值。我们先尝试分析一下作者为什么要这么做，原因如下：

A.HashMap中的table数组使用的延迟加载的策略，当构造函数执行完成，尚未向其中添加元素的时候，table数组还是null，其自身无法存储初始化长度，所以需要一个额外的字段来存储初始化容量；

B.HashMap为了节省空间，并没有定义一个capacity字段来存储table数组的长度，而是在构造函数里面借用了threshold这个字段，暂存一下table数组的初始化长度；

C.HashMap中添加元素的时候，需要先对table进行初始化，初始化后capacity就可以用table.length来表示，threshold就恢复原有的业务含义。

一般情况下，我们在程序执行时间，使用空间和可读性，可维护性做选择的时候，一般选择可读性，除非是特殊的场景。而HashMap明显是选择了节省空间这一策略，也降低了代码的可读性和可维护性。

3.一个的方法包含了过多的职责，而且方法过长

final Node[] resize() {          Node[] oldTab = table;          int oldCap = (oldTab == null) ? 0 : oldTab.length;          int oldThr = threshold;          int newCap, newThr = 0;          if (oldCap > 0) {              if (oldCap >= MAXIMUM_CAPACITY) {                  threshold = Integer.MAX_VALUE;                  return oldTab;              } else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&                      oldCap >= DEFAULT_INITIAL_CAPACITY)                  newThr = oldThr << 1; // double threshold          } else if (oldThr > 0) // initial capacity was placed in threshold              newCap = oldThr;          else {               // zero initial threshold signifies using defaults              newCap = DEFAULT_INITIAL_CAPACITY;              newThr = (int) (DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);          }          if (newThr == 0) {              float ft = (float) newCap * loadFactor;              newThr = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?                      (int) ft : Integer.MAX_VALUE);          }          threshold = newThr;          @SuppressWarnings({"rawtypes", "unchecked"})          Node[] newTab = (Node[]) new Node[newCap];          table = newTab;          if (oldTab != null) {              //……              //……          }          return newTab;}

resize从方法名看，是要进行扩容，但是方法实际包含了初始化和扩容两部分功能。同样可以使用重构的方式，来消除不优雅的地方，步骤如下：

A.方法重命名，将resize的方法名重命名为initOrResize，表达方法的实际含义；

B.方法拆分为两个独立的方法，doInit和doResize，分别来做初始化和扩容；

重构后的结果：

final Node[] initOrResize() {
          if (table == null) {
              return doInit();
          }
          return doResize();
      }


 private Node[] doInit() {
          int initCapacity = threshold == 0 ? DEFAULT_INITIAL_CAPACITY : threshold;
          float ft = (float) initCapacity * loadFactor;
          threshold = (initCapacity < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                  (int) ft : Integer.MAX_VALUE);
          table = (Node[]) new Node[initCapacity];
          return table;
 }


private Node[] doResize() {
          if (table.length >= MAXIMUM_CAPACITY) {
              threshold = Integer.MAX_VALUE;
              return table;
          }
          Node[] oldTab = table;
          int oldCap = oldTab.length;
          int newCap = oldCap << 1;
          if (newCap < MAXIMUM_CAPACITY && oldCap >= DEFAULT_INITIAL_CAPACITY) {
              threshold = threshold << 1; // double threshold
          } else {
              float ft = (float) newCap * loadFactor;
              threshold = (newCap < MAXIMUM_CAPACITY && ft < (float) MAXIMUM_CAPACITY ?
                      (int) ft : Integer.MAX_VALUE);
          }
          Node[] newTab = (Node[]) new Node[newCap];
          table = newTab;
          //……
          //……
          return newTab;
}

三.使用HashMap的小技巧

1.HashMap构造时指定的初始容量

下面代码展示了，在插入完全相同的数据的条件下，HashMap指定初始化容量和使用默认初始化容量的下的性能差异，代码如下：

public class HashMapCapacityTest {
    private static final int SIZE = 10000000;
    private static final float DEFAULT_LOAD_FACTOR = 0.75f;


    public static void main(String[] args) {
        long totalA = 0, totalB = 0;
        for (int i = 0; i < 1000; i++) {
            totalA += testHashMapUseDefaultCapacity();
            totalB += testHashMapAssignedCapacity();
            System.out.println(totalA + " " + totalB + " " + (totalA * 1.0  totalB));
        }
    }


    private static long testHashMapUseDefaultCapacity() {
        long start = System.currentTimeMillis();
        Map map = new HashMap();
        for (int i = 0; i < SIZE; i++) {
            map.put(i, i);
        }
        return System.currentTimeMillis() - start;
    }


    private static long testHashMapAssignedCapacity() {
        long start = System.currentTimeMillis();
        int capacity = (int) (SIZE  DEFAULT_LOAD_FACTOR);
        Map map = new HashMap(capacity);
        for (int i = 0; i < SIZE; i++) {
            map.put(i, i);
        }
        return System.currentTimeMillis() - start;
    }
}

上面的代码在运行稳定条件后，testHashMapAssignedCapacity的性能相比testHashMapUseDefaultCapacity提高了50%。

2.避免使用containsKey后，再使用get，进行两次hash查找

public class HashMapGetTest {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("1", 1);
        System.out.println(getIntValueFromMap(map, "2"));
    }


    private static int getIntValueFromMap(Mapmap, String key) {
        return map.get(key);
    }
}

因为上面的代码，会出NullPointerException。为了避免这种情况，有的同学会在map的get之前先调用一个containsKey方法，确保key存在的情况，再调用get方法，调整后代码如下：

public class HashMapGetTest {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("1", 1);
        System.out.println(getIntValueFromMap(map, "2"));
    }


    private static int getIntValueFromMap(Mapmap, String key) {
        if (map.containsKey(key)) {
            return map.get(key);
        }
        return 0;
    }
}

上面的代码，在key存在的情况下，进行了两次hash查找，这样就损失了一半的性能，再次调整代码如下：

public class HashMapGetTest {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("1", 1);
        System.out.println(getIntValueFromMap(map, "2"));
    }


    private static int getIntValueFromMap(Mapmap, String key) {
        Integer value = map.get(key);
        if (value == null) {
            return 0;
        }
        return value.intValue();
    }
}

调整后性能问题得到解决，但是当value == null的时候，就无法区分因为key不存在，还是key存在但是value是null的情况。

最后，如果大家在面试的时候，按照上面的思路去回答HashMap的原理，来个三板斧，一定会让面试官对你产生不一样的看法。

第一版斧，HashMap的优点，好在哪里；

第二版斧，HashMap的缺点，如何改进；

第三版斧，HashMap使用小技巧。

欢迎大家的持续关注，会定期更新哒～

长按“识别二维码”点关注

具体问题具体分析，这是永恒的办法，不要老想着造永动机。

看都看完了，还不点这里试试

面试

文章转载自马士兵，如果涉嫌侵权，请发送邮件至：contact@modb.pro进行举报，并提供相关证据，一经查实，墨天轮将立刻删除相关内容。

日常工作、面试中常遇到的HashMap源码

评论