HashMap的这些巧夺天工的设计，你能想到吗？

HashMap作为程序员最常用的数据结构，包含了设计者的许多精巧构思，看完源码让人直呼我怎么没想到，快来一块学习一下。

1. 有没有一种数据结构，增删改查都快？

我们都知道数组的查询比较快，因为地址是连续的，可以通过下标直接找到元素。不过增删较慢，每次在数组中间增删一个元素，都涉及数组拷贝。 HashMap设计高明之处，是用hashCode代替数组下标访问，不再要求元素存储必须连续，增删的时候也就不需要数组拷贝。 使用链表解决hash冲突，使用阈值默认75%控制容量，避免元素过多、hash冲突过多，退化成链表存储，影响查询性能。HashMap通常情况下，增删改查的效率都是O(1)

2. 如果快速找到HashMap数组下标？

计算机中与运算的性能要高于求余，HashMap直接用hashCode逻辑与(length-1)，得到数组下标。

static int indexFor(int h, int length) {
    return h & (length-1);
}

测试一下，hashCode分别是10（二级制是1010）和17（二级制是100001），HashMap的length是16，(length-1)的二进制就是1111，进行与运算。

这也是要求HashMap的容量必须是2的幂次方的原因。

3. 怎么计算大于当前数值的最小2的幂次方？

如果HashMap的初始容量时10，由于HashMap要求容量必须是2的幂次方，怎么计算出大于10的最小的2的幂次方16呢？

// number是初始化容量10，计算出capacity=16
int capacity = highestOneBit((number - 1) << 1);

public static int highestOneBit(int i) {
    i |= (i >>  1);
    i |= (i >>  2);
    i |= (i >>  4);
    i |= (i >>  8);
    i |= (i >> 16);
    return i - (i >>> 1);
}

初看这段源码是不是懵逼了，图解一下就清晰了。

>> 代表二进制右移，>> 1 表示右移一位，>> 2 表示右移两位
>>> 代表无符号右移

number = 10， 先计算 i = (number-1) << 1 number - 1 = 9 ，9的二进制是1001，左移一位变成 0001 0010, 然后执行 highestOneBit() 方法 最后得到的结果应该是16，如图所示

最后得到 0001 1111, 然后执行 i - (i >>> 1), 0001 1111 转换成十进制是31， i >>> 1 得到 1111，转换成十进制是15 31 - 15 = 16