HashMap中哈希表的长度为什么需要是2的幂次方以及怎么实现

看过HashMap源码的人可能都用印象，就是hashMap的哈希表长度可以由自己指定也可以不指定使用默认长度，但是如果在了解或者发现tableSizeFor方法的话，你就会知道此方法会改变我们的输入长度 (如果我们输入15，他会改为16)，那么他为什么要修改我们设置的长度，以及修改后有什么作用？带着这个疑问我们往下看；

1. HashMap 的长度为什么需要是2的幂次方

为了能让hashMap存取高效，尽量减少碰撞，也就是要尽量把数据分配均匀。
Hash值的取值范围-2147483648到2147483647，总共有40+亿个映射空间，只要哈希函数映射的比较均匀，一般应用很难出现碰撞，但是内存肯定不能一次加载这么长的数组，所以这个散列值是不能拿来直接用的，我们只能创建合理长度的数组作为哈希表，在插入数据之前做取模运算，得到的余数就是将要存放的数据在哈希表中对应的下标。在HashMap中这个下标的取值算法是：(n - 1) & hash n是哈希表的长度。

取模运算中如果除数是2的幂次方则等价于其与除数减一的&操作，就是：hash % length == hash & (length - 1)
采用二进制位操作 & 相对于 % 能够提高运算效率，这也就解释了为啥HashMap的长度需要为2的幂次方

2. HashMap怎么实现的

先看下JDK8的源码:

/**
 * 方法保证了HashMap的哈希表长度总位2的幂次方
 * 返回大于输入参数且最近的2的整数次幂的数
 */
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;
}

我也是看到这个方法后才决定写这篇博文来记录一下我的感想，我已经不知道多少次被源码作者所折服，我甚至觉得这才是代码应该的样子；

结果分析

  n第一次右移一位时，相当于将最高位的1右移一位，再和原来的n取或，就将最高位和次高位都变成1，也就是两个1；

  第二次右移两位时，将最高的两个1向右移了两位，取或后得到四个1；

  依次类推，右移16位再取或就能得到32个1；

你是不是不知道要32个1干嘛？自己体会如下：

2的幂次方	二进制表示	十进制标识
2^0	1	(1-1)+1
2^1	10	(2-1)+1
2^2	100	(4-1)+1
2^3	1000	(8-1)+1
2^4	10000	(16-1)+1
2^5	100000	(32-1)+1

二进制数字如果都是1的话，那么他加一后就是首位为1其他位都是0，这个数字肯定是2的幂次方， 2^n == 1<<n

举例说明：

  10的二进制是1010，减1就是1001

  第一次右移取或： 1001 | 0100 = 1101 ；

  第二次右移取或： 1101 | 0011 = 1111 ；

  第三次右移取或： 1111 | 0000 = 1111 ；

  第四次第五次同理

  最后得到 n = 1111  ，返回值是 n+1 = 2 ^ 4 = 16 ;

自己实验一把

static final int tableSizeFor(int cap) {
    int n = cap - 1;
    n |= n >>> 1;
    System.out.println(Integer.toBinaryString(n));
    n |= n >>> 2;
    System.out.println(Integer.toBinaryString(n));
    n |= n >>> 4;
    System.out.println(Integer.toBinaryString(n));
    n |= n >>> 8;
    System.out.println(Integer.toBinaryString(n));
    n |= n >>> 16;
    System.out.println(Integer.toBinaryString(n));
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

public static void main(String[] args) {
        int a =  65538;
        System.out.println(Integer.toBinaryString(a));
        int i = tableSizeFor(a);
        System.out.println(i);
}

执行结果：

  10000000000000010
  11000000000000001
  11110000000000001
  11111111000000001
  11111111111111111
  11111111111111111
  131072

看到这里是不是也有中被折服的感觉？那就对了，路还长，编码还要继续，且看且学习。。。 ^_