Java源码解析HashMap的tableSizeFor函数

PHP小丑

今天小编就为大家分享一篇关于Java源码解析HashMap的tableSizeFor函数，小编觉得内容挺不错的，现在分享给大家，具有很好的参考价值，需要的朋友一起跟随小编来看看吧
aka，hashmap的容量大小必须为2的指数，即16，32，64，128这样的值。那么，在构造函数中，如果调用者指定了hashmap的初始大小不是2的指数，那么，hashmap的tablesizefor函数，会计算一个大于或等于给定参数的2的指数的值。先来看一下tablesizefor函数的源码，如下

/**
 * returns a power of two size for the given target capacity.
 **/
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-1，然后一直进行右移操作，最后根据n和maximum_capcity的大小关系，返回一个值。这究竟是如何实现找到一个大于或等于cap的2的指数的值呢？
首先需要解释一下>>>符号。>>>是无符号右移操作，即，右移后，高位补0. 例如二进制的11000101，>>>1后，得到01100010，即不关心符号位，右移后，高位直接补充0.
还有一个符号是|=，例如n |= n>>>1，这个其实可以翻译为n = n | n>>>1，| 是位或操作，即两个数字按位进行或操作，即，某一位上，只有一个数字的该位为1，该位的结果即为1.
说清楚了两个符号的含义，下面我们开始解释算法的过程。
函数一开始，把cap -1 赋值给n。这里我们先按住不说，稍后回头解释。接下来就是对n的四次变换。举个例，对于

01010000
这个值来说，n>>>1即可得到
00101000
两个数字位或后，得到
01111000

可以这么来看这个事情，最开始的n，总有它的最高位为1. 右移1位后，与n进行位或操作，则结果的最高位和次高位都为1了，也就是得到了2个1，而且是高位的2位都为1了。
那么这时再对n进行n>>>2，再和n进行位或操作，即可得到4个1. 依此类推，n |= n>>>4，即可得到8个1。然后n |= n>>>8，即可得到16个1。然后 n |= n>>>16，即可得到32个1. 当然，后面几步得到多少个1，得需要n的初始值足够大才可以。否则，n右移后可能就位0了，那么在进行位或操作，也只是上一步的值而已。
通过上面的分析，可以知道，进行完n的四次右移然后位或操作后，得到的其实是n的所有为都为1的一个值。那么最后，返回的时候，取的n + 1，那么即可得到一个比n大的2的指数的值。
那么回过头来看看第一步 n = cap -1就明白了，这里是为了处理当cap本身即是2的指数时的情况。
因为计算机进行移位和位或操作十分迅速，所以，这个函数的执行效率其实很高。tablesizefor函数就是这样快速找到了一个大于等于cap的2的指数的值。
总结
以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对CodeAE代码之家的支持。如果你想了解更多相关内容请查看下面相关链接
原文链接：https://blog.csdn.net/li_canhui/article/details/85088660