Java HashMap 的那么多为什么

1. HashMap 的默认大小是 16，这个默认值是可以设置的。如果事先知道具体的例子，可以修改默认初始大小，减少动态扩容的次数，提高性能。修改默认初始大小的值时，比如你设置了 500，那么不会真就使用 500 这个值，而可能会使用 512 这种是 2 的幂的值。



为什么要设置是 2 的幂的值？这个跟下面的 index 的值计算有关，请看第 4 点。

1. 最大的装载因子为 0.75，当装载因子超过这个值是就会扩容，每次扩容都会扩容为原来的两倍大小。



那么为什么装载因子是 0.75 呢？经研究显示，负载因子是0.75的时候，空间利用率比较高，而且避免了相当多的 Hash 冲突，使得底层的链表或者是红黑树的高度比较低，提升了空间效率（来自网上）。



为啥是扩容为原来的两倍呢？这个具体请看第 4 点。

1. 采用链表法来解决冲突，之后再 JDK1.8 中引入了红黑数，主要链表长度太长（默认超过8）时，链表就转换为红黑树。当少于 6 时，又将红黑树转换为链表，因为红黑树要维护平衡，比起链表性能上的优势并不会特别明显。



那么为什么在少于 6 的时候而不是 8 的时候才将红黑树转换为链表呢？假设设计成大于 8 时链表转换为红黑树，小于 8 的时候又转换为链表。如果一个 hashmap 不停的插入、删除。hashmap 中的个数不停地在 8 徘徊，那么就会频繁的发生链表和红黑树之间转换，效率非常低。因此，6 和 8 之间来一个过渡值可以减缓这种情况造成的影响。

1. 散列值的获取分两步走：

// 1. hash 值的计算
static final int hash(Object key) {
    int hash;
    return key == null ? 0 : (hash = key.hashCode()) ^ hash >>> 16;
}

// 2. 插入/查找的时候，计算 key 应该被映射到散列表的什么位置
int index = hash(key) & (capacity - 1)

其中方法 hashcode() 返回的是 Java 对象的 hash_code，这是一个 int 类型的值（32 位）。那么为什么在拿到这个值之后，还需要将自己右移 16 位与自己进行异或呢？因为容量较小的时候，在计算 index 那边，真正用到的其实就只有低几位，假如不融合高低位，那么假设 hashcode() 返回的值都是高位的变动的话，那么很容易造成散列的值都是同一个。但是，假如将高位和低位融合之后，高位的数据变动会最终影响到 index 的变换，所以依然可以保持散列的随机性。



那么在计算 index 的时候，为什么不使用 hash(key) % capacity 呢？这是因为移位运算相比取余运算会更快。那么为什么 hash(key) & (capacity - 1) 也可以呢？这是因为在 B 是 2 的幂情况下： A % B = A & (B - 1)。如果 A 和 B 进行取余，其实相当于把 A 那些不能被 B 整除的部分保留下来。从二进制的方式来看，其实就是把 A 的低位给保留了下来。B-1 相当于一个“低位掩码”，而与的操作结果就是散列值的高位全部置为 0 ，只保留低位，而低位正好是取余之后的值。我们取个例子，A = 24，B =16，那么 A%B=8，从二进制角度来看 A =11000 ，B = 10000。A 中不能被 B 整除的部分其实就是 1000 这个部分。接下去，我们需要将这部分保留下来的话，其实就是使用 01111 这个掩码并跟 A 进行与操作，即可将1000 保留下来，作为 index 的值。而 01111 这个值又等于 B-1。所以 A &（B-1）= A%B。但是这个前提是 B 的容量是 2 的幂，那么如何保证呢？我们可以看到，在设置初始大小的时候，无论你设置了多少，都会被转换为 2 的幂的一个数。之外，扩容的时候也是按照 2 倍进行扩容的。所以 B 的值是 2 的幂是没问题的。