HashMap

HashMap相信大家都很熟悉了,我们经常用来存放数据的一种容器。HashMap实际上是数组加链表的数据结构。在JDK1.8后又引入了红黑树。今天抽空研究了一下HashMap的源码,感觉还是非常值得学习的,它里面的一些算法思想真是让人佩服。本文就来结合源码学习一下HashMap是如何计算数组初始大小的。

new HashMap

首先回顾一下HashMap的用法。
1.new HashMap时候没有指定大小

HashMap<String,Integer> hashMap = new HashMap<>();

如果没有指定大小,会在put的时候给数组一个默认的大小,这个大小是16。

static final int DEFAULT_INITIAL_CAPACITY = 1 << 4;

这里就不再过多讨论了,后面再去写一篇详解HashMap。
2.指定了HashMap大小

HashMap<String,Integer> hashMap = new HashMap<>(33);

如果我指定了大小是33,那么它里面的数组真的是33吗?
我们看看源码是怎么处理的。

源码分析

首先看一下带一个参数的构造方法。

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

可以看到它又调用了两个参数的构造方法。DEFAULT_LOAD_FACTOR是扩容因子,大小是0.75。它是指如果数组长度达到了最大长度的0.75,数组就会进行扩容。

static final float DEFAULT_LOAD_FACTOR = 0.75f;

接着看构造方法:

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

其实也比较简单,如果传过来的initialCapacity小于0,抛出IllegalArgumentException。我们只需关注tableSizeFor方法,这就是计算数组初始长度的方法,一起看下:

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

看到这是不是内心一句卧槽飘过,这是啥啊。反正我第一次看的时候就是这种感觉。没关系我们一步一步计算一下就知道了。
我们就拿33为例,假设传入的cap等于33.
33的二进制是0010 0001。

第一步:int n = cap - 1;
此时n就等于 0010 0000。

第二步:n |= n >>> 1;
这行代码就等价于 n= n|(n>>>1); >>>是无符号右移。
| 是位运算符,有1则为1。 1 | 1 =1; 1 | 0 = 1;0 | 0 =0;
在这里插入图片描述
经过第一步的计算n现在就是 0011 0000。

第三步:n |= n >>> 2;
n= n|(n>>>2);
此时n=0011 0000
在这里插入图片描述
经过这次计算n就变成了 0011 1100

第四步:n |= n >>> 4;
n= n|(n>>>4);
此时n=0011 1100
在这里插入图片描述
经过这次计算 n = 0011 1111

第五步:n |= n >>> 8;
n= n|(n>>>8);
此时n=0011 1111
这就不用画图了吧,n>>>8 等于0
所以n |= n >>> 8; n不会变还是0011 1111

第六步:n |= n >>> 16;
n= n|(n>>>16);
同理此时n=0011 1111

最后返回

return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;

这里MAXIMUM_CAPACITY是2的30次方

static final int MAXIMUM_CAPACITY = 1 << 30;

所以最终返回的是n+1,也就是 0100 0000。转换成十进制就是64。

总结

所以HashMap是将传入的数转换成比它大的最近的2的n次方的数。有点拗口。
比如:
传入1,返回2。
传入6,返回8。
传入33,返回64。
传入66,返回128。
传入101,返回128。

如果你遇到了这种需求,你会怎么写,可能我会这样写:

    static int myTableSizeFor(int cap){
        int i = 2;
        while ((cap = cap/2)!=0){
            i *= 2;
        }
        return i;
    }

虽然也能实现功能,但是看起来就没人家的厉害。而且计算机中位运算的速度是最快的,性能上也不如人家。总之实在是佩服,怎么想出来的。路漫漫其修远兮,还是要努力学习才行呀。

Logo

权威|前沿|技术|干货|国内首个API全生命周期开发者社区

更多推荐