哈希表（如 HashMap）中的高效的位运算技巧

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
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>=MAXMUM_CAPACITY ? MAXMUM_CAPACITY : n+1);

}

它的作用就是把我们传入的初始容量值 变成离他最近的而且是2的整数次方的值
17  –> 32
16  –>16
31  –>32
33  –>64

帮助理解：
二进制 10000000010 对应的十进制是 1026，假设这就是 cap-1 的值（即 n = 1026），执行过程如下：

  1. 初始 n = 10000000010（二进制）

  2. n |= n >>> 1
    右移 1 位得到 01000000001，按位或后结果为 11000000011

  3. n |= n >>> 2
    右移 2 位得到 00110000000，按位或后结果为 11110000011

  4. n |= n >>> 4
    右移 4 位得到 00001111000，按位或后结果为 11111111011

  5. n |= n >>> 8
    右移 8 位得到 00000000111，按位或后结果为 11111111111

  6. n |= n >>> 16
    右移 16 位后结果为 0，按位或后值不变

  7. 最终结果是二进制 11111111111（十进制 2047），这是大于等于 1026 的最小的 2 的幂次方减 1（2¹¹-1）。

  • 注意：cap - 1 这一步的核心作用就是处理原始容量本身已经是 2 的幂次方的情况，确保最终计算结果正确。

根据哈希值 计算元素在桶中的索引

1
2
3
4
5
6
7
8
9
//h 就是哈希值 (经过扰动函数之后的)
//length 哈希桶的长度

public int indexFor(int h,int length){

	//return h%length
	return h&(length-1);//这个写法 相当于把h%length 前提是 length为2的整数次方

}