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

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