当前位置：首页 > news >正文

HashMap 源码中的巧妙小技巧

news 2025/7/10 10:46:36

根据容量计算大于容量的最小的哈希表的大小(table的length)，这里的length需要满足length=2^n，也就是我们需要根据容量算出最小的n的值

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;
}

int n = cap - 1;这里是为了确定在二进制表示的情况下，最高位的1的位置，这里分两种情况来讲
1.cap!=2^n,cap不是2的n次方
这种情况其实减1之后，最高位的1的位置不变例如随便找两个数
69
00000000 00000000 00000000 01000101
69-1
00000000 00000000 00000000 01000100
16196
00000000 00000000 00100000 01000100
16196-1
00000000 00000000 00100000 01000011
4210496
00000000 00100000 00100000 01000000
4210496-1
00000000 00100000 00100000 00111111这几个数字减 1 以后，最高位的1的位置不变2.cap=2^n,cap是2的n次方
这种情况其实减1之后，最高位的1的位置会向右移动一位16
00000000 00000000 00000000 00010000
16-1
00000000 00000000 00000000 00001111
4096
00000000 00000000 00010000 00000000
4096-1
00000000 00000000 00001111 11111111这几个数字减1之后，最高位的1的位置会向右移动一位n |= n >>> 1; 这一步是让从最高位的1开始，往右的前2位变为1
例如：
n = 100000
n >>> 1 就是 10000
n |= n >>> 1 的意思就是 n = n | n >>> 1 = 100000 | 10000 = 110000n |= n >>> 2; 这一步是让从最高位的1开始，往右的前4位变为1
n = 110000
n >>> 2 就是 1100
n |= n >>> 2 的意思就是 n = n | n >>> 2 = 110000 | 1100 = 111100n |= n >>> 4; 这一步是让从最高位的1开始，往右的前8位变为1
n = 111100
n >>> 4 就是 11
n |= n >>> 4 的意思就是 n = n | n >>> 4 = 111100 | 11 = 111111这里再举一个比较大的例子n=10000000000000000000000000000000
n >>> 1 就是 1000000000000000000000000000000
n |= n >>> 1 就是 n = n | n >>> 1 = 10000000000000000000000000000000| 1000000000000000000000000000000= 11000000000000000000000000000000n = 11000000000000000000000000000000
n >>> 2 就是 110000000000000000000000000000
n |= n >>> 2 就是 n = n | n >>> 2 = 11000000000000000000000000000000 | 110000000000000000000000000000 = 11110000000000000000000000000000n = 11110000000000000000000000000000
n >>> 4 就是 1111000000000000000000000000
n |= n >>> 4 就是 n = n | n >>> 4 = 11110000000000000000000000000000 | 1111000000000000000000000000 = 11111111000000000000000000000000n = 11111111000000000000000000000000
n >>> 8 就是 111111110000000000000000
n |= n >>> 8 就是 n = n | n >>> 8 = 11111111000000000000000000000000 | 111111110000000000000000 = 11111111111111110000000000000000n = 11111111111111110000000000000000
n >>> 16 就是 1111111111111111
n |= n >>> 16 就是 n = n | n >>> 16 = 11111111111111110000000000000000 | 1111111111111111 = 11111111111111111111111111111111return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
这里表示如果正常的话返回的值应该是 n + 1
根据我们的经验，如果一个数的二进制表示所有的1都在最右边，那么这个数加 1 以后就是 2^n

计算一个key值的hash值，这里的key的类型是 Object。计算出来的hash值用来参与计算当前键值对在hash表中的位置

static final int hash(Object key) {int h;return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,boolean evict) {Node<K,V>[] tab; Node<K,V> p; int n, i;if ((tab = table) == null || (n = tab.length) == 0)n = (tab = resize()).length;if ((p = tab[i = (n - 1) & hash]) == null)tab[i] = newNode(hash, key, value, null);else {Node<K,V> e; K k;if (p.hash == hash &&((k = p.key) == key || (key != null && key.equals(k))))

以上是put方法的部分代码，我们可以摘取出其中的关键代码

int n , i;
(n = tab.length) == 0 这里执行完，那么 n = tab.length(p = tab[i = (n - 1) & hash]) == null 这里执行完,那么 i = (n - 1) & hash
hash的值就是通过上面的hash()方法计算出的值tab[i] = newNode(hash, key, value, null);
这里可以看出 i 是用来寻找新节点的位置的，看来节点在table中的位置为:
(tab.length - 1) & hash
根据 tableSizeFor() 的实现可以看出，tab.length为2^k , tab.length - 1的值用二进制表示 
低位都为1二进制，高位都是0
那么 (tab.length - 1) & hash 就相当于只取hash的二进制表示的最低的那几位。
如果两个不同的hash值，如果高位不同，低位相同那么算出来的值是相同的，就会增加hash冲突的概率，导致性能受影响。接下来讨论hash()方法的这段代码的巧妙之处

(h = key.hashCode()) ^ (h >>> 16)

h = key.hashCode() 是key的hashCode值
h >>> 16 表示 h 向右移动16位，原来高位的16位移到低位了(h = key.hashCode()) ^ (h >>> 16) 就相当于将 h 的高16位和低16位进行异或运算，
这样h的二进制表示如果高位不同，低位相同，那么最终结果的低位是不同的，
前面put方法分析了寻找键值对在table中的位置时只取hash值的低位来决定键值对的位置，
这样就可以减少hash碰撞的概率

查看全文

http://www.lryc.cn/news/376924.html