java 并发容器一之BoundedConcurrentHashMap(基于JDK1.8)

Wesley13
• 阅读 566

最近开始学习java并发容器,以补充自己在并发方面的知识,从源码上进行。如有不正确之处,还请各位大神批评指正。

前言: 本人个人理解,看一个类的源码要先从构造器入手,然后再看方法。下面看BoundedConcurrentHashMap的注释

 1  先看HashTable的介绍:    This class implements a hash table, which maps keys to values. Any non-<code>null</code> object can be used as a key or as a value.
 2  该类实现了一个哈希表,它将键映射到值。任何非<code> null </ code>对象都可以用作键或值。
 3  To successfully store and retrieve objects from a hashtable To successfully store and retrieve objects from a hashtable, 
 4  从哈希表中成功存储和检索对象从哈希表中成功存储和检索对象
 5  the objects used as keys must implement the <code>hashCode</code> method and the <code>equals</code> method. 
 6  用作键的对象必须实现<code> hashCode </ code>方法和<code> equals </ code>方法
 7  An instance of <code>Hashtable</code> has two parameters that affect its performance: 
 8  <code> Hashtable </ code>的一个实例有两个影响其*性能的参数:初始容量和负载系数<i>initial capacity</i> and <i>load factor</i>
 9  The <i>capacity</i> is the number of <i>buckets</i> in the hash table, and the <i>initial capacity</i> is simply the capacity at the time the hash table is created
10  <i>容量</ i>是哈希表中<i>桶</ i>的数量,<i>初始容量</ i>只是创建哈希表时的容量
11  Note that the hash table is <i>open</i>: in the case of a "hash collision", a single bucket stores multiple entries, which must be searched sequentially. 
12  请注意,哈希表是<i> open </ i>:在“哈希*冲突”的情况下,单个存储桶存储多个条目,必须按顺序搜索
13  The <i>load factor</i> is a measure of how full the hash table is allowed to get before its capacity is automatically increased
14  <i>加载因子</ i>衡量在其容量自动增加之前允许散列*表的填充程度   BoundedConcurrentHashMap类的

一个哈希表,支持检索的完全并发性和可更新的预期并发性。该类遵循与{@link java.util.Hashtable}相同的功能规范,并包含与 Hashtable 的每个方法对应的方法版本。但是,即使所有操作都是线程安全的,但检索操作不需要锁定,并且不支持以阻止所有访问的方式锁定整个表。在依赖于线程安全但不依赖于其同步细节的程序中,此类可与Hashtable完全互操作。检索操作(包括get)通常不会阻塞,因此可能与更新操作重叠(包括 put 和 remove )。检索反映了最近已完成更新操作的结果。对于诸如 putAll 和 clear 之类的聚合操作,并发检索可能反映仅插入或删除某些条目。他们不抛出{@link java.util.ConcurrentModificationException}。但是,迭代器设计为一次只能由一个线程使用。更新操作之间允许的并发性由可选的 concurrencyLevel </ tt>构造函数参数(默认 16 )引导,该参数用作内部大小调整的提示。该表在内部进行分区,以尝试允许指定数量的并发更新而不会发生争用。因为散列表中的放置基本上是随机的,所以实际的并发性会有所不同。理想情况下,您应该选择一个值来容纳与同时修改表一样多的线程。使用比您需要的更高的值会浪费空间和时间,而显着更低的值可能导致线程争用。但是,在一个数量级内过高估计和低估通常不会产生明显的影响。当知道只有一个线程会修改而其他所有线程只能读取时,值为1是合适的。______此外,调整此哈希表或任何其他类型的哈希表是一个相对较慢的操作,因此,在可能的情况下,最好在构造函数中提供预期表大小的估计值。___________该类及其视图和迭代器实现了{@link Map}和{@link Iterator}接口的所有可选</ em>方法。_____________本课程是从Infinispan复制的,最初由Doug Lea在JCP JSR-166专家组成员的协助下编写并发布到公共领域,如http://creativecommons.org/所述。_______________licenses / publicdomain 与{@link java.util.Hashtable}类似,但与{@link HashMap}不同,_________________此类不允许 null用作键或值。________

默认初始容量: DEFAULT_MAXIMUM_CAPACITY = 512; 构造函数中未指定时使用
默认加载因子: DEFAULT_LOAD_FACTOR = 0.75f 构造函数中未指定时使用
默认的并发级别: DEFAULT_CONCURRENCY_LEVEL = 16 构造函数中未指定时使用
最大容量:MAXIMUM_CAPACITY = 1 << 30 当构造函数中指定时使用此参数,指定的值必须是2<= 1 << 30 的幂,以确保条目可使用整数进行索引。
允许的最大段数: MAX_SEGMENTS = 1 << 16 用于绑定*构造函数参数
不理解: RETRIES_BEFORE_LOCK = 2 、
segmentMask: 用于索引到段的掩码值,key的哈希码的高位用于选择段。
segmentShift: 移位值以在段内编制索引(不理解)
Segment<K, V>[] segments: 段。充当了分段锁的角色,这些段,每个段都是一个专门的哈希表。是这个类的内部类,继承了ReentrantLock只是为了简化一些锁定并避免单独构造
也具有keySet,entrySet, values
segmentFor(int hash): 根据传入的hash值来计算出该hash所在的段。
HashEntry: 内部类,用来封装散列映射表中的键值对,如果发生碰撞则采用“分离连接法”处理碰撞,把“碰撞”的 HashEntry 对象链接成一个链表。
由于 HashEntry 的 next 域为 final 型,所以新节点只能在链表的表头处插入

构造器: 其他的构造器也都间接的调用了这个

参数介绍

capacity: 是该map中元素数量的上限容量

concurrencyLevel:估计的并发更新线程数,该实现执行内部大小调整以尝试容纳这么多线程。其他几个构造器调用这个方法时传入的都是默认的 DEFAULT_CONCURRENCY_LEVEL = 16

evictionStrategy:用于从此映射表中驱逐元素的算法(不太明白)

evictionListener:驱逐监听器, 用来通知被驱逐的元素(不太明白)。

public BoundedConcurrentHashMap(int capacity, int concurrencyLevel,Eviction evictionStrategy, EvictionListener<K, V> evictionListener) {
if ( capacity < 0 || concurrencyLevel <= 0 ) { // 不允许最大容量小于0或者并发更新线程数小于等于0,否则就没法玩了
throw new IllegalArgumentException();
}

// 限制并发量不低于元素容量上限的一般并且不大于元传入的并发量

concurrencyLevel = Math.min( capacity / 2, concurrencyLevel ); // concurrencyLevel cannot be > capacity/2
concurrencyLevel = Math.max( concurrencyLevel, 1 ); // concurrencyLevel cannot be less than 1

// 不允许最大容量小于并发数的两倍
if ( capacity < concurrencyLevel * 2 && capacity != 1 ) {
throw new IllegalArgumentException( "Maximum capacity has to be at least twice the concurrencyLevel" );
}

// 不允许驱逐算法和监听为空

if ( evictionStrategy == null || evictionListener == null ) {
throw new IllegalArgumentException();
}

// 限定最大并发更新线程数不大于MAX_SEGMENTS(是1<<16 = 65536,也即是2的16次幂,这样做就保证了最大并发是2的次幂数)

if ( concurrencyLevel > MAX_SEGMENTS ) {
concurrencyLevel = MAX_SEGMENTS;
}

// 用sshift 和 ssize变量来存储最佳匹配参数是2的次幂
int sshift = 0;
int ssize = 1;

  // 从后面看到ssize要用于创建的“分段锁”的数组长度,所以这里不能够比并发线程数小, 否则就会增加“线程”的竞争,导致效率下降。
while ( ssize < concurrencyLevel ) {
++sshift;
ssize <<= 1; // ssize<<=1 也即是 ssize = ssize * 2的1次幂,这里也即是取2的次幂
}
segmentShift = 32 - sshift; // 计算段移位量,用于与hash进行移位运算,找到hash所在的段的位置
segmentMask = ssize - 1;
this.segments = Segment.newArray( ssize ); // 初始化“分段锁”数组的长度。

// 如果capacity(元素的容量上限)比规定的最大容量MAXIMUM_CAPACITY(1<<30)大,那么就去规定的最大容量

if ( capacity > MAXIMUM_CAPACITY ) {
capacity = MAXIMUM_CAPACITY;
}
int c = capacity / ssize; // 取元素的容量上限和“分段锁”数组的长度的余数
int cap = 1;
while ( cap < c ) { // 如果cap小于1那么对cap进行2的次幂运算,否则就把“分段锁”数组的每个元素中的数组初始容量定位1
cap <<= 1;
}

for ( int i = 0; i < this.segments.length; ++i ) {

    // 从Segment构造器中可以看到cap是用来确定“分段锁”数组的具体元素中数组的长度,如果上面“分段锁”数组具体元素容量上限
this.segments[i] = new Segment<K, V>( cap, c, DEFAULT_LOAD_FACTOR, evictionStrategy, evictionListener );
}

// 把Segment构造器放在这里只是配合上面循环中的new Segment容易理解。

  Segment(int cap, int evictCap, float lf, Eviction es, EvictionListener<K, V> listener) {
    loadFactor = lf;
    this.evictCap = evictCap;
    eviction = es.make( this, evictCap, lf );
    evictionListener = listener;
    setTable( HashEntry.<K, V>newArray( cap ) ); // 从这里可以看到cap是用来确定“分段锁”数组的具体元素中数组的长度
  }

  public V put(K key, V value) {
    if ( value == null ) { // 不允许value为null, 这里并没有对key做判断并不代表允许key为null,因为当key为null时在下面的key.hashCode()也会报出空指针异常
      throw new NullPointerException();
    }
    int hash = hash( key.hashCode() ); // 对key的hash码进行再hash确定“分段锁”数组中具体的数组下标

    // segmentFor(hash)是定位“分段锁数组”, Segment是一个内部类。
    return segmentFor( hash ).put( key, hash, value, false );
  }

  V put(K key, int hash, V value, boolean onlyIfAbsent) {
    lock(); // 加锁
    Set<HashEntry<K, V>> evicted = null;
    try {

      // count是此“分段锁”中的元素数
      int c = count;

      // threshold: 是“分段锁”中元素数量的阈值,Eviction.NON是驱逐算法

      // 此判断的意思是当元素数量大于阈值时, 那么表将会被重新hash分配整理
      if ( c++ > threshold && eviction.strategy() == Eviction.NONE ) {
        rehash();
      }
    HashEntry<K, V>[] tab = table;
    int index = hash & tab.length - 1;
    HashEntry<K, V> first = tab[index]; // 拿到数组中的第一个元素,至于为什么这样算出index就是第一个元素,不太理解
    HashEntry<K, V> e = first;

    // 这个while循环的作用是: 查看put进来的key表中是否已经存在,如果存在就是根据key替换value而不是新增。
    while ( e != null && ( e.hash != hash || !key.equals( e.key ) ) ) {
      e = e.next;
    }

    V oldValue;
    if ( e != null ) { // e不为空时说明上面while的另外一个条件e.hash != hash || !key.equals(e.key) 不成立,也即是传入的key在hash表中已经存在,这时候就替换value即可。
      oldValue = e.value; // 记下原来的value值返回。
      if ( !onlyIfAbsent ) {
        e.value = value;
        eviction.onEntryHit( e );
      }
    }
    else { // 否则就是出入的key在hash表中不存在,需要新增

      oldValue = null;

      // modCount是hash表的更新数,用来记录表的更新(可以理解成“乐观锁”,比如size方法中使用是,进入方法时会建立与“分段锁”长度一致的数组来存储每个“分段锁”中hash表修改的次数,当统计计算长度的时候会再次统计一次,然后比较

      // 这两次的值是否一致,如果不一致说明统计数量期间有别的线程进行了数据更新,那么就加上锁重新统计)

      ++modCount;

      // 将加1之后的元素数量重新赋值回去

      count = c; // write-volatile

      if ( eviction.strategy() != Eviction.NONE ) {

        // 当驱逐算法不是NONE时,并且又元素数量又达到了驱逐上限,那么就用eviction本身的驱逐算法对元素进行驱逐,以容纳新的元素

        if ( c > evictCap ) {
        // remove entries;lower count
        evicted = eviction.execute(); // 驱逐元素
        // 重新读取驱逐元素之后的第一个的值
        first = tab[index];
      }
      // 添加一个新的元素放在首位,并将新添加的元素的next指向原来的第一个元素,这样就在链表的开头新增了一个新的节点。
      tab[index] = eviction.createNewEntry( key, hash, first, value );
      //不太理解下面的操作
      Set<HashEntry<K, V>> newlyEvicted = eviction.onEntryMiss( tab[index] ); 
      if ( !newlyEvicted.isEmpty() ) {
        if ( evicted != null ) {
        evicted.addAll( newlyEvicted );
      }
      else {
        evicted = newlyEvicted;
      }
     }
    }
    else { // 如果驱逐算法是NONE构建完链表返回。
      tab[index] = eviction.createNewEntry( key, hash, first, value );
    }
   }

    return oldValue;
  }
  finally {
    unlock(); // 解锁,能够让其他线程访问
    notifyEvictionListener( evicted );
  }
 }

}

点赞
收藏
评论区
推荐文章
blmius blmius
3年前
MySQL:[Err] 1292 - Incorrect datetime value: ‘0000-00-00 00:00:00‘ for column ‘CREATE_TIME‘ at row 1
文章目录问题用navicat导入数据时,报错:原因这是因为当前的MySQL不支持datetime为0的情况。解决修改sql\mode:sql\mode:SQLMode定义了MySQL应支持的SQL语法、数据校验等,这样可以更容易地在不同的环境中使用MySQL。全局s
待兔 待兔
4个月前
手写Java HashMap源码
HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程HashMap的使用教程22
Wesley13 Wesley13
3年前
java基础知识随身记
2018年11月12日20:51:35一、基础知识:1、JVM、JRE和JDK的区别:JVM(JavaVirtualMachine):java虚拟机,用于保证java的跨平台的特性。  java语言是跨平台,jvm不是跨平台的。JRE(JavaRuntimeEnvironment):java的运行环境,包括jvmjava的核心类
Jacquelyn38 Jacquelyn38
3年前
2020年前端实用代码段,为你的工作保驾护航
有空的时候,自己总结了几个代码段,在开发中也经常使用,谢谢。1、使用解构获取json数据let jsonData  id: 1,status: "OK",data: 'a', 'b';let  id, status, data: number   jsonData;console.log(id, status, number )
Wesley13 Wesley13
3年前
Java爬虫之JSoup使用教程
title:Java爬虫之JSoup使用教程date:201812248:00:000800update:201812248:00:000800author:mecover:https://imgblog.csdnimg.cn/20181224144920712(https://www.oschin
Wesley13 Wesley13
3年前
Java日期时间API系列31
  时间戳是指格林威治时间1970年01月01日00时00分00秒起至现在的总毫秒数,是所有时间的基础,其他时间可以通过时间戳转换得到。Java中本来已经有相关获取时间戳的方法,Java8后增加新的类Instant等专用于处理时间戳问题。 1获取时间戳的方法和性能对比1.1获取时间戳方法Java8以前
Stella981 Stella981
3年前
Android So动态加载 优雅实现与原理分析
背景:漫品Android客户端集成适配转换功能(基于目标识别(So库35M)和人脸识别库(5M)),导致apk体积50M左右,为优化客户端体验,决定实现So文件动态加载.!(https://oscimg.oschina.net/oscnet/00d1ff90e4b34869664fef59e3ec3fdd20b.png)点击上方“蓝字”关注我
Wesley13 Wesley13
3年前
mysql设置时区
mysql设置时区mysql\_query("SETtime\_zone'8:00'")ordie('时区设置失败,请联系管理员!');中国在东8区所以加8方法二:selectcount(user\_id)asdevice,CONVERT\_TZ(FROM\_UNIXTIME(reg\_time),'08:00','0
Wesley13 Wesley13
3年前
00:Java简单了解
浅谈Java之概述Java是SUN(StanfordUniversityNetwork),斯坦福大学网络公司)1995年推出的一门高级编程语言。Java是一种面向Internet的编程语言。随着Java技术在web方面的不断成熟,已经成为Web应用程序的首选开发语言。Java是简单易学,完全面向对象,安全可靠,与平台无关的编程语言。
Wesley13 Wesley13
3年前
35岁是技术人的天花板吗?
35岁是技术人的天花板吗?我非常不认同“35岁现象”,人类没有那么脆弱,人类的智力不会说是35岁之后就停止发展,更不是说35岁之后就没有机会了。马云35岁还在教书,任正非35岁还在工厂上班。为什么技术人员到35岁就应该退役了呢?所以35岁根本就不是一个问题,我今年已经37岁了,我发现我才刚刚找到自己的节奏,刚刚上路。