最近开始学习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 );
}
}
}