解析 hashMap 源码之位运算

shengjk1

发布于 2020-09-09 14:49:21

2920

发布于 2020-09-09 14:49:21

计算索引

tab[i = (n - 1) & hash])

当 n == 2^x 的时候，(n - 1) & hash 与 hash % n 是等价的，但 (n - 1) & hash （位运算 )效率更高，因为 % 是通过加法跟移位来实现的

计算 hash 值

 // 扰动函数
    // 增加 hash 值的任意性，让高位参与到运算中来
    static final int hash(Object key) {
        int h;
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
    }

让高位参与运算，增加 hash 值的随意性

计算 tableSize

/**
     * Returns a power of two size for the given target capacity.
     */
    // 大于等于 cap 的 最小的 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;
    }

什么意思呢？我们假设 cap 分别为 3，127，5，64，*

3    0000 0011
-1   0000 0010
>>>1 0000 0001 
|    0000 0011 
>>>2 0000 0000 
|    0000 0000 
....
结果不变 1

 127   0111 1111 
 -1    0111 1110 
 >>>1  0011 1111 
 |     0111 1111 
 >>>2  0001 1111 
 |     0111 1111 
 ....
 结果不变 128


 5    0000 0101
 -1   0000 0100 
 >>>1 0000 0010 
 |    0000 0110 
 >>>2 0000 0001 
 |    0000 0111 
 >>>3 0000 0000 
 |    0000 0111 
 ....
结果不变 8

//这就是为什么要减一 
64    0100 0000 
-1    0011 1110 
>>>1  0001 1111 
|     0011 1111 
>>>2  0000 1111 
|     0011 1111 
....
结果不变 64


更一般的
     01** ****
-1   01** ****

>>>1 001* ****
|    011* ****
>>>2 0001 1***
|    0111 1***
>>>4 0000 0111 
|    0111 1111 
....
结果不变
      0*** ****
-1    0*** ****
>>>1  00** ****    
|     0*** ****
>>>2  000* ****
|     0*** ****
....
结果不变

其实最终的结果就是返回