HashMap中的移位骚操作

基于JDK11

我们都知道，在声明一个HashMap的时候能够指定the initial capacity（初始容量）,如果我们指定了一个初始容量cap,那么就需要根据cap计算出相应的threshold（下次扩容的大小）

Talk is cheep

/** * JDK11 HashMap源码,根据capacity返回2的n次幂(n就是返回值,也是数组的大小) * Returns a power of two size for the given target capacity. */ static final int tableSizeFor(int cap) { int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1); return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1; } /** * Returns the number of zero bits preceding the highest-order * ("leftmost") one-bit in the two's complement binary representation * of the specified {@code int} value. Returns 32 if the * specified value has no one-bits in its two's complement representation, * in other words if it is equal to zero. * * <p>Note that this method is closely related to the logarithm base 2. * For all positive {@code int} values x: * <ul> * <li>floor(log₂(x)) = {@code 31 - numberOfLeadingZeros(x)} * <li>ceil(log₂(x)) = {@code 32 - numberOfLeadingZeros(x - 1)} * </ul> * * @param i the value whose number of leading zeros is to be computed * @return the number of zero bits preceding the highest-order * ("leftmost") one-bit in the two's complement binary representation * of the specified {@code int} value, or 32 if the value * is equal to zero. * @since 1.5 */ @HotSpotIntrinsicCandidate public static int numberOfLeadingZeros(int i) { // HD, Count leading 0's // 处理 i < 0 和 i = 0 的情况,如果 i < 0,二进制第一位为1,所以返回0;如果 i = 0,肯定是用32个0表示 if (i <= 0) return i == 0 ? 32 : 0; // 声明总共可能返回的0的个数 int n = 31; // 如果输入的数大于等于 2^16 ( 1 << 16 ),那么说明左侧连续的0肯定少于等于 (31 - 16) 个 if (i >= 1 << 16) { n -= 16; i >>>= 16; } if (i >= 1 << 8) { n -= 8; i >>>= 8; } if (i >= 1 << 4) { n -= 4; i >>>= 4; } if (i >= 1 << 2) { n -= 2; i >>>= 2; } return n - (i >>> 1); }

移位分析

首先numberOfLeadingZeros计算的是一个int值使用二进制表示时,从左往右连续为0的个数。整个方法的思路是将输入的数不断的进行有条件的右移，右移的过程中将不可能存在的0的个数减去，之所以可能位移16, 8, 4, 2, 1是因为经过这些位移可以将所有int值都进行一次完整的位移（最后直剩下1或0）

public static void main(String[] args) { System.out.println(Integer.numberOfLeadingZeros(2)); System.out.println(Integer.numberOfLeadingZeros(4)); } // 输出 // 30 因为int值在java中使用32位表示,2用二进制表示为10,所以2这个数使用二进制表示的时候的左侧有连续30个0 // 29

tableSizeFor方法中，int n = -1 >>> Integer.numberOfLeadingZeros(cap - 1);的操作其实是先计算出cap-1左侧的0的个数i，然后将-1右移动i位，>>>表示使用0填充移位后的空位,>>运算符会使用符号位的值填充移位后的空位.

计算过程

假如cap = 16cap - 1 = 15 // 0000 0000 0000 0000 0000 0000 0000 1111Integer.numberOfLeadingZeros(cap - 1) = 28-1 // 计算机中的二进制表示：1111 1111 1111 1111 1111 1111 1111 1111（补码）-1 >>> 28 // 0000 0000 0000 0000 0000 0000 1111n = 15最后取n + 1作为桶(数组)的数量，这样是为了在计算Hash值的时候同样可以使用位操作减少冲突，保持数据的分散

我的个人博客有空来坐坐

https://www.wangyanan.online