专栏首页earthchen的专栏HashMap和concurrentHashMap的初始化

HashMap和concurrentHashMap的初始化

HashMap和concurrentHashMap的初始化时的区别

初始化的区别

主要分析下传入指定容量时,最后真正初始化的容量到底是多少?

HashMap的构造函数

当不指定负载因子时,负载因子为0.75

/**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and the default load factor (0.75).
     *
     * @param  initialCapacity the initial capacity.
     * @throws IllegalArgumentException if the initial capacity is negative.
     */
    public HashMap(int initialCapacity) {
        this(initialCapacity, DEFAULT_LOAD_FACTOR);
    }
    
/**
     * Constructs an empty <tt>HashMap</tt> with the specified initial
     * capacity and load factor.
     *
     * @param  initialCapacity the initial capacity
     * @param  loadFactor      the load factor
     * @throws IllegalArgumentException if the initial capacity is negative
     *         or the load factor is nonpositive
     */
    public HashMap(int initialCapacity, float loadFactor) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal initial capacity: " +
                                               initialCapacity);
        if (initialCapacity > MAXIMUM_CAPACITY)
            initialCapacity = MAXIMUM_CAPACITY;
        if (loadFactor <= 0 || Float.isNaN(loadFactor))
            throw new IllegalArgumentException("Illegal load factor: " +
                                               loadFactor);
        this.loadFactor = loadFactor;
        this.threshold = tableSizeFor(initialCapacity);
    }

最终调用的都是这个HashMap(int initialCapacity, float loadFactor)方法

其中计算容量的方法为

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

都是位运算,可能不太看得懂,但是我们通过注释可以知道这么一系列位移操作算法最后是为了得到一个power of two size的值。(也就是第一个大于指定容量的值)

ConcurrentHashMap

同样的,我们不去看负载因子0.75,并发级别16这些,只关注指定容量

/**
     * Creates a new, empty map with an initial table size
     * accommodating the specified number of elements without the need
     * to dynamically resize.
     *
     * @param initialCapacity The implementation performs internal
     * sizing to accommodate this many elements.
     * @throws IllegalArgumentException if the initial capacity of
     * elements is negative
     */
    public ConcurrentHashMap(int initialCapacity) {
        if (initialCapacity < 0)
            throw new IllegalArgumentException();
        int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                   MAXIMUM_CAPACITY :
                   tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));
        this.sizeCtl = cap;
    }

主要的部分就是

int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?
                  MAXIMUM_CAPACITY :
                  tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));

sizeCtl=大于(1.5倍initialCapacity+1)的最小的2的幂次

这算出来的也就是容量,但是sizeCtl变量还有其他的含义

sizeCtl的含义

  • 用来控制表初始化和扩容的,默认值为0,当在初始化的时候指定了大小,这会将这个大小保存在sizeCtl中,大小为数组的0.75
  • 当为负的时候,说明表正在初始化或扩张,
  • -1表示初始化
  • -(1+n) n:表示活动的扩张线程

ConcurrentHashMap源码解析

数组长度要求为2^n的原因

在存入元素的时候下标的计算方式为

index = hashcode % table.length

但是a % (2^n) 等价于 a & (2^n - 1)

同时位运算比取模运算具有更高的效率,所以作者就将取模运算改为了位运算

然后计算方式就变为了

index = hashcode & (n - 1)

其中n为数组长度为2的整数次幂 HashMap为了存取高效,要尽量较少碰撞,就是要尽量把数据分配均匀,每个链表长度大致相同,这个实现就在把数据存到哪个链表中的算法; 这个算法实际就是取模,hash%length,计算机中直接求余效率不如位移运算,源码中做了优化hash&(length-1), hash%length==hash&(length-1)的前提是length是2的n次方;

为什么这样能均匀分布减少碰撞呢?2的n次方实际就是1后面n个0,2的n次方-1 实际就是n个1;

例如长度为9时候,3&(9-1)=0 2&(9-1)=0 ,都在0上,碰撞了;

例如长度为8时候,3&(8-1)=3 2&(8-1)=2 ,不同位置上,不碰撞;

其实就是按位“与”的时候,每一位都能 &1 ,也就是和1111……1111111进行与运算

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 10分钟掌握ConcurrentHashMap 3分钟清楚和HashMap、Hashtable的区别

    ConcurrentHashMap顾名思义就是同步的HashMap,也就是线程安全的HashMap,所以本篇介绍的ConcurrentHashMap和HashM...

    猿天地
  • 10分钟掌握ConcurrentHashMap 3分钟清楚和HashMap、Hashtable的区别

    ConcurrentHashMap顾名思义就是同步的HashMap,也就是线程安全的HashMap,所以本篇介绍的ConcurrentHashMap和HashM...

    Java技术江湖
  • 还不懂 ConcurrentHashMap ?这份源码分析了解一下

    上一篇文章介绍了 HashMap 源码,反响不错,也有很多同学发表了自己的观点,这次又来了,这次是 ConcurrentHashMap 了,作为线程安全的Has...

    未读代码
  • 详解HashMap、HashTable

    之前的文章《HashMap源码详解》中我们已经结合Java1.8中HashMap的源码对数据结构、数据存取、数据写入、扩容等操作进行了详细的梳理。

    用户1880875
  • JDK1.7ConcurrentHashMap源码解析

    我们都知道HashMap在多线程情况下,在put的时候,插入的元素超过了容量(由负载因子决定)的范围就会触发扩容操作,就是rehash,这个会重新将原数组的内容...

    黑洞代码
  • 这几道Java集合框架面试题在面试中几乎必问

    本文会同步更新在我开源的Java学习指南仓库 Java-Guide (一份涵盖大部分Java程序员所需要掌握的核心知识,正在一步一步慢慢完善,期待您的参与)中,...

    用户2164320
  • Java ConcurrentHashMap 最佳实践

    相对于HashMap,ConcurrentHashMap提供了内部实现的并发支持。使得开发者在多线程应用中访问ConcurrentHashMap时,不必使用sy...

    用户7886150
  • 并发容器和框架之ConcurrentHashMap

    了解HashMap的人都知道HashMap是线程不安全的(多线程下的put方法达到一定大小,引发rehash,导致闭链,最终占满CPU),同时线程安全的Hash...

    MindMrWang
  • 突击并发编程JUC系列-并发容器ConcurrentHashMap

    本节让我们一起研究一下该容器是如何在保证线程安全的同时又能保证高效的操作。ConcurrentHashMap是线程安全且高效的HashMap。

    山间木匠
  • 这几道Java集合框架面试题在面试中几乎必问

    双向链表也叫双链表,是链表的一种,它的每个数据结点中都有两个指针,分别指向直接后继和直接前驱。所以,从双向链表中的任意一个结点开始,都可以很方便地访问它的前驱结...

    Java技术江湖
  • 持续3分钟 - Java -11

    HashMap 根据键的 hashCode 值存储数据,大多数情况下可以直接定位到它的值,因而具有很快的访问速度,但遍历顺序却是不确定的。

    子乾建建-Jeff
  • ConcurrentHashMap(JDK8)

    ConcurrentHashMap是HashMap的升级版,HashMap是线程不安全的,而ConcurrentHashMap是线程安全。而其他功能和实现原理和...

    chenchenchen
  • ConcurrentHashMap源码学习

    既然有了HashMap为什么还会出现ConcurrentHashMap?同时ConcurrentHashMap具有什么优势?ConcurrentHashMap与...

    路行的亚洲
  • Java的ConcurrentHashMap

    ConcurrentHashMap是Java中的一个线程安全且高效的HashMap实现。

    用户3467126
  • HashMap, ConcurrentHashMap 原理及源码,一次性讲清楚!

    网上关于 HashMap 和 ConcurrentHashMap 的文章确实不少,不过缺斤少两的文章比较多,所以才想自己也写一篇,把细节说清楚说透,尤其像 Ja...

    Java技术栈
  • Java7和8 中的 HashMap 和 ConcurrentHashMap 全解析

    转自https://www.javadoop.com/post/hashmap#toc7

    Java技术江湖
  • 面试必备:HashMap、Hashtable、ConcurrentHashMap的原理与区别

    HashMap和Hashtable都是用hash算法来决定其元素的存储,因此HashMap和Hashtable的hash表包含如下属性:

    猿人谷
  • ConcurrentHashMap 原理解析(JDK1.8)

    java404
  • 速读原著-深入分析 ConcurrentHashMap

    因为多线程环境下,使用 HashMap 进行 put 操作会引起死循环,导致 CPU 利用率接近 100%, 所以在并发情况下不能使用 HashMap,如以下代...

    cwl_java

扫码关注云+社区

领取腾讯云代金券