积土成山，风雨兴焉；积水成渊，蛟龙生焉；积善成德，而神明自得，圣心备焉。故不积跬步，无以至千里，不积小流无以成江海。齐骥一跃，不能十步，驽马十驾，功不在舍。面对悬崖峭壁，一百年也看不出一条裂缝来，但用斧凿，能进一寸进一寸，能进一尺进一尺，不断积累，飞跃必来，突破随之。

目录

在看HashMap底层源码的时候，我们知道HashMap 默认的初始化大小为 16。之后每次扩充，容量变为原来的 2 倍。但创建时如果给定了容量的初始值，那么HashMap 会将其扩充为 2 的幂次方大小。（tableSizeFor()方法中保证的）

// hashmap 源码
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;
}

原理

为了能让 HashMap 存取高效，尽量较少碰撞，也就是要尽量把数据分配均匀。而Hash 值的范围值为 -2147483648 到 2147483647，前后加起来大概 40 亿的映射空间，只要哈希函数映射得比较均匀松散，一般应用是很难出现碰撞的。

但问题是一个 40 亿长度的数组，内存是放不下的。所以这个散列值是不能直接拿来用的。用之前还要先做对数组的长度取模运算（即进行范围限制），得到的余数才是用来要存放的位置，也就是对应的数组下标。但这个下标要怎么算？

正常的话我们肯定会采用取模运算（%）进行一个取模：

n%hash //n表示长度

但是在HashMap中采用的是位运算：

(n - 1) & hash //n表示长度

而使用这种方式的话，n就必须为2的幂次方。

分析

假如 hash=4095 的二进制表示为：1111 1111 1111 ，假如 n=16 的二进制表示为：1 0000

所以 n-1=15 的二进制表示为：0 1111

然后就进行按位与运算：

1111 1111 1111（hash）

0000 0000 1111（n-1）

0000 0000 1111（这就是(n - 1) & hash，即 hash%n ）

这是hash的二进制全为1的情况。

假如 hash=4023 的二进制表示为：1111 1011 0111 ，假如 n=16 的二进制表示为：1 0000

所以 n-1=15 的二进制表示为：0 1111

然后就进行按位与运算：

1111 1011 0111（hash）

0000 0000 1111（n-1）

0000 0000 0111（这就是(n - 1) & hash，即 hash%n ）

总结

因为 n 为2的幂次方，所以n的二进制表示中只有一个1；然后n-1的二进制表示中是除去有效最高位外，右边部分全是1。那么全与其他数进行按位与时，最大即为n-1，否则比n-1小。

2022年5月26日

HashMap在扩容上的优化。

采用2的幂次方作为长度的另外一个原因在于扩容时，key的hash值计算。

在同一个桶中的key，在扩容后，HashMap容量翻倍，再去取模，实际上是需要高一位来参与计算的（即新增的最高位）。

当高位是0时，newBucketIndex = oldBucketIndex，此时元素还是存放在原来的桶中；

当高位是1时，newBucketIndex = oldBucketIndex + oldTable.length，这时元素需要移动到扩容产生的桶中。