手撕HashMap | tableSizeFor初始化容量与jdk7、jdk8的对比_jdk7和jdk8 初始化容量时机

转载本文章请标明作者和出处
本文出自《爱喝纯净水的南荣牧歌》

加油，程序猿！！！

最近我们发现HashMap是大厂面试官的最爱之一，面试的提问频率可以说超过60%，那怎么办，盘他！！！

首先我们去new一个HashMap的时候，可以在构造函数中指定它的初始容量（阿里的代码检查器也要求我们最好指明）；

我们打开HashMap的这个构造函数看一下；

    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
2
3
4
5
6
7
8
9
10
11
12

前面都是给负载因子赋值的操作，最后我发现调用了一个tableSizeFor(int)方法；追上去，看一下；

    /**
     * Returns a power of two size for the given target capacity.
     */
    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;
    }
1
2
3
4
5
6
7
8
9
10
11
12

通过注释我们可以发现，这是要给出一个2的整数幂的一个操作，其实也就是给出第一个比cap大的2的整数幂；

那么这几行代码是则呢么办到的呢？

先不管开始的减一和最后的加一操作，那几个位运算和或等于又代表着什么呢？

假设，我们给定的cap值为9；那么n=9-1等于8；
如下为8的二进制表达；

那么我们把8无符号右移一位，得到；

这两个数，我们做一下|=操作（当前位上有1就是1，全为0才是0），得到；

再把这个数，无符号右移两位得到；

上面两个数再做|=，得到；

最后的
n |= n >>> 4;
n |= n >>> 8;
n |= n >>> 16;
得出的还是这个结果，然后再加1等于16，恰好是离9最近的2的整数幂；

• 那为什么要一直无符号右移16位呢？

  因为int类型刚好为32位，最后的右移16位，刚好能覆盖整个int类型；

• 那么为什么要先减去1最后再加上1呢？

  因为如果cap等于8的话，直接操作的话结果会是16不会是8，就是如果传入一个正好为2的整数幂的数，不会返回这个数本身；

---

如果面试官在问你HashMap的时候你可以对比说一下jdk7和jdk8的区别的话，相信面试官一定会眼前一亮；

jdk8相较于jdk7做了比较大的升级；具体可以分为一下几点；

• 扰动函数，在jdk8中位移了一次，而在jdk7中位移了4次；
• jdk8采用的实现哈希表的方式是数组加链表加红黑树，而jdk7则是数组加链表的方式；
• jdk7发生哈希碰撞之后插入节点的方式是头插法，而在jdk8中采用了尾插法；
• 扩容的时候1.7需要对原数组中的元素进行重新hash定位在新数组的位置，1.8采用更简单的判断逻辑，位置不变或索引+旧容量大小；
• jdk7再向链表中添加节点的时候是先判断是否需要转红黑树再插入节点，而jdk8中是先插入节点，再判断是否需要转红黑树；

喜欢的朋友可以加我的个人微信，我们一起进步