前往小程序,Get更优阅读体验!
立即前往
首页
学习
活动
专区
工具
TVP
发布
社区首页 >专栏 >HashMap和concurrentHashMap的初始化

HashMap和concurrentHashMap的初始化

作者头像
earthchen
发布2020-09-24 15:58:39
1.4K0
发布2020-09-24 15:58:39
举报
文章被收录于专栏:earthchen的专栏

HashMap和concurrentHashMap的初始化时的区别

初始化的区别

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

HashMap的构造函数

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

代码语言:javascript
复制
/**
     * 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)方法

其中计算容量的方法为

代码语言:javascript
复制
/**
     * 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这些,只关注指定容量

代码语言:javascript
复制
/**
     * 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;
    }

主要的部分就是

代码语言:javascript
复制
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的原因

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

代码语言:javascript
复制
index = hashcode % table.length

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

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

然后计算方式就变为了

代码语言:javascript
复制
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进行与运算

本文参与 腾讯云自媒体同步曝光计划,分享自作者个人站点/博客。
原始发表:2018-11-01,,如有侵权请联系 cloudcommunity@tencent.com 删除

本文分享自 作者个人站点/博客 前往查看

如有侵权,请联系 cloudcommunity@tencent.com 删除。

本文参与 腾讯云自媒体同步曝光计划  ,欢迎热爱写作的你一起参与!

评论
登录后参与评论
0 条评论
热度
最新
推荐阅读
目录
  • 初始化的区别
    • HashMap的构造函数
      • ConcurrentHashMap
        • 数组长度要求为2^n的原因
        领券
        问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档