Java源码解析HashMap的tableSizeFor函数

2024-04-26 03:00:10

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的指数的值。

总结

以上就是这篇文章的全部内容了，希望本文的内容对大家的学习或者工作具有一定的参考学习价值，谢谢大家对我们的支持。如果你想了解更多相关内容请查看下面相关链接

MapTask工作机制图文详解

MapTask工作机制如图所示. (1)Read阶段:MapTask通过用户编写的RecordReader,从输入InputSplit中解析出一个个key/value. (2)Map阶段:该节点主要是将解析出的key/value交给用户编写map()函数处理,并产生一系列新的key/value. (3)Collect收集阶段:在用户编写map()函数中,当数据处理完成后,一般会调用OutputCollector.collect()输出结果.在该函数内部,它会将生成的key/value分区(调用
Java源码解析TreeMap简介

TreeMap是常用的排序树,本文主要介绍TreeMap中,类的注释中对TreeMap的介绍.代码如下. /** * A Red-Black tree based {@link NavigableMap} implementation. * The map is sorted according to the {@linkplain Comparable natural * ordering} of its keys, or by a {@link Comparator} provided at
MapTask阶段shuffle源码分析

1. 收集阶段在Mapper中,调用context.write(key,value)实际是调用代理NewOutPutCollector的wirte方法 public void write(KEYOUT key, VALUEOUT value ) throws IOException, InterruptedException { output.write(key, value); } 实际调用的是MapOutPutBuffer的collect(),在进行收集前,调用partitioner来计算
MapReduce核心思想图文详解

MapReduce核心编程思想,如图1-1所示. 图1-1 MapReduce核心编程思想 1)分布式的运算程序往往需要分成至少2个阶段. 2)第一个阶段的MapTask并发实例,完全并行运行,互不相干. 3)第二个阶段的ReduceTask并发实例互不相干,但是他们的数据依赖于上一个阶段的所有MapTask并发实例的输出. 4)MapReduce编程模型只能包含一个Map阶段和一个Reduce阶段,如果用户的业务逻辑非常复杂,那就只能多个MapReduce程序,串行运行. 小结:分析WordC
shuffle的关键阶段sort(Map端和Reduce端)源码分析

源码中有这样一段代码 1. Map端排序获取的比较器 public RawComparator getOutputKeyComparator() { // 获取mapreduce.job.output.key.comparator.class,必须是RawComparator类型,如果没设置,是null Class<? extends RawComparator> theClass = getClass( JobContext.KEY_COMPARATOR, null, RawComparat
Java源码解析HashMap的resize函数

HashMap的resize函数,用于对HashMap初始化或者扩容. 首先看一下该函数的注释,如下图.从注释中可以看到,该函数的作用是初始化或者使table的size翻倍.如果table是null,那么就申请空间进行初始化.否则,因为我们在使用2的指数的扩张,在原来table的每个位置的元素,在新的table中,他们要么待在原来的位置,要么移动2的指数的偏移.从这里可以看出,扩容前table每个位置上如果有多个元素,元素之间组成链表时,在扩容后,该链表中的元素,有一部分会待在原地,剩下的元素会
Java源码解析ConcurrentHashMap的初始化

首先看一下代码 private final Node<K,V>[] initTable() { Node<K,V>[] tab; int sc; while ((tab = table) == null || tab.length == 0) { // 第一次检查 if ((sc = sizeCtl) < 0) Thread.yield(); // lost initialization race; just spin else if (U.compareAndSwapInt
Java源码解析HashMap成员变量

本文基于jdk1.8进行分析关于HashMap的简介,可以参考这篇文章https://www.jb51.net/article/154177.htm. 首先看一下HashMap的一些静态常量.第一个是DEFAULT_INITIAL_CAPACITY,默认初始大小,16.从注释中可以了解到,大小必须为2的指数.这里的16,采用的1左移4位实现.而"aka",是as known as的缩写. /** * The default initial capacity - MUST be a p
Java源码解析HashMap的keySet()方法

HashMap的keySet()方法比较简单,作用是获取HashMap中的key的集合.虽然这个方法十分简单,似乎没有什么可供分析的,但真正看了源码,发现自己还是有很多不懂的地方.下面是keySet的代码. public Set<K> keySet() { Set<K> ks = keySet; if (ks == null) { ks = new KeySet(); keySet = ks; } return ks; } 从代码中了解到,第一次调用keySet方法时,keySet
Java源码解析HashMap简介

本文基于jdk1.8进行分析 HashMap是java开发中可以说必然会用到的一个集合.本文就HashMap的源码实现进行分析. 首先看一下源码中类的javadoc注释对HashMap的解释.如下图.HashMap是对Map接口的基于hash表的实现.这个实现提供了map的所有可选操作,并且允许null值(可以多个)和一个null的key(仅限一个).HashMap和HashTable十分相似,除了HashMap是非同步的且允许null元素.这个类不保证map里的顺序,更进一步,随着时间的推移,

Java源码解析HashMap的tableSizeFor函数

相关推荐

随机推荐