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

最近开始学习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}。但是,迭代器设计为一次只能由一个线程使用。更新操作之间允许的并发性由可选的<tt> concurrencyLevel </ tt>构造函数参数(默认 16 )引导,该参数用作内部大小调整的提示。该表在内部进行分区,以尝试允许指定数量的并发更新而不会发生争用。因为散列表中的放置基本上是随机的,所以实际的并发性会有所不同。理想情况下,您应该选择一个值来容纳与同时修改表一样多的线程。使用比您需要的更高的值会浪费空间和时间,而显着更低的值可能导致线程争用。但是,在一个数量级内过高估计和低估通常不会产生明显的影响。当知道只有一个线程会修改而其他所有线程只能读取时,值为1是合适的。此外,调整此哈希表或任何其他类型的哈希表是一个相对较慢的操作,因此,在可能的情况下,最好在构造函数中提供预期表大小的估计值。该类及其视图和迭代器实现了{@link Map}和{@link Iterator}接口的所有<em>可选</ 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 );
  }
 }

}


上一篇:AHK(1)之运行程序或打开文档


下一篇:c++学习笔记—二叉树基本操作的实现