|
对ConcurrentReferenceHashMap进行代码分析并对主要部分加注释
package com.zzd.boot.autoconfigure.util;
import java.lang.ref.ReferenceQueue;
import java.lang.ref.SoftReference;
import java.lang.ref.WeakReference;
import java.lang.reflect.Array;
import java.util.*;
import java.util.concurrent.ConcurrentMap;
import java.util.concurrent.locks.ReentrantLock;
public class ConcurrentReferenceHashMap<K, V> extends AbstractMap<K, V> implements ConcurrentMap<K, V> {
private static final int DEFAULT_INITIAL_CAPACITY = 16;
private static final float DEFAULT_LOAD_FACTOR = 0.75F;
private static final int DEFAULT_CONCURRENCY_LEVEL = 16;
private static final ReferenceType DEFAULT_REFERENCE_TYPE;
private static final int MAXIMUM_CONCURRENCY_LEVEL = 65536;
private static final int MAXIMUM_SEGMENT_SIZE = 1073741824;
private final Segment[] segments;
private final float loadFactor;
private final ConcurrentReferenceHashMap.ReferenceType referenceType;
private final int shift;
private Set<Map.Entry<K, V>> entrySet;
public ConcurrentReferenceHashMap() {
this(16, 0.75F, 16, DEFAULT_REFERENCE_TYPE);
}
public ConcurrentReferenceHashMap(int initialCapacity) {
this(initialCapacity, 0.75F, 16, DEFAULT_REFERENCE_TYPE);
}
public ConcurrentReferenceHashMap(int initialCapacity, float loadFactor) {
this(initialCapacity, loadFactor, 16, DEFAULT_REFERENCE_TYPE);
}
public ConcurrentReferenceHashMap(int initialCapacity, int concurrencyLevel) {
this(initialCapacity, 0.75F, concurrencyLevel, DEFAULT_REFERENCE_TYPE);
}
public ConcurrentReferenceHashMap(int initialCapacity, ReferenceType referenceType) {
this(initialCapacity, 0.75F, 16, referenceType);
}
public ConcurrentReferenceHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) {
this(initialCapacity, loadFactor, concurrencyLevel, DEFAULT_REFERENCE_TYPE);
}
public ConcurrentReferenceHashMap(int initialCapacity, float loadFactor, int concurrencyLevel, ReferenceType referenceType) {
Assert.isTrue(initialCapacity >= 0, "Initial capacity must not be negative");
Assert.isTrue(loadFactor > 0.0F, "Load factor must be positive");
Assert.isTrue(concurrencyLevel > 0, "Concurrency level must be positive");
Assert.notNull(referenceType, "Reference type must not be null");
this.loadFactor = loadFactor;
//计算最小值需要位移的次数
this.shift = calculateShift(concurrencyLevel, 65536);
//最小需要位移的位数再向右位移一位即*2
int size = 1 << this.shift;
this.referenceType = referenceType;
int roundedUpSegmentCapacity = (int)(((long)(initialCapacity + size) - 1L) / (long)size);
//创建数组，数组的个数为需要位移的次数，最大值为65536需要右移的次数为16
this.segments = (Segment[])((Segment[]) Array.newInstance(Segment.class, size));
for(int i = 0; i < this.segments.length; ++i) {
//初始化数组，roundedUpSegmentCapacity这个为每个数组初始的容量
this.segments[i] = new Segment(roundedUpSegmentCapacity);
}
}
protected final float getLoadFactor() {
return this.loadFactor;
}
//返回分段数组的长度
protected final int getSegmentsSize() {
return this.segments.length;
}
//获取分段数组的第index段数据
protected final ConcurrentReferenceHashMap<K, V>.Segment getSegment(int index) {
return this.segments[index];
}
//创建ReferenceManager对象
protected ReferenceManager createReferenceManager() {
return new ReferenceManager();
}
protected int getHash(Object o) {
//使用native方法获取hash值
int hash = o == null ? 0 : o.hashCode();
//暂不知道为什么需要去对hash值进行处理
hash += hash << 15 ^ -12931;
hash ^= hash >>> 10;
hash += hash << 3;
hash ^= hash >>> 6;
hash += (hash << 2) + (hash << 14);
hash ^= hash >>> 16;
return hash;
}
@Override
public V get(Object key) {
Reference<K, V> reference = this.getReference(key, Restructure.WHEN_NECESSARY);
Entry<K, V> entry = reference != null ? reference.get() : null;
return entry != null ? entry.getValue() : null;
}
@Override
public boolean containsKey(Object key) {
Reference<K, V> reference = this.getReference(key, Restructure.WHEN_NECESSARY);
Entry<K, V> entry = reference != null ? reference.get() : null;
return entry != null && ObjectUtils.nullSafeEquals(entry.getKey(), key);
}
//通过key获取对应的value（1、获取hash值，2、获取此hash在第几个Segment，3、获取对应的Reference，4、遍历Reference获取key对应的value值）
protected final Reference<K, V> getReference(Object key, Restructure restructure) {
int hash = this.getHash(key);
return this.getSegmentForHash(hash) //返回第k个Segment（段）
.getReference(key, hash, restructure); //获取对应的值
}
@Override
public V put(K key, V value) {
return this.put(key, value, true);
}
@Override
public V putIfAbsent(K key, V value) {
return this.put(key, value, false);
}
//每次put值的时候都新建线程来实现
private V put(K key, final V value, final boolean overwriteExisting) {
return this.doTask(key, new Task<V>(new TaskOption[]{TaskOption.RESTRUCTURE_BEFORE, TaskOption.RESIZE}) {
@Override
protected V execute(Reference<K, V> reference, Entry<K, V> entry, Entries entries) {
if (entry != null) {
V previousValue = entry.getValue();
if (overwriteExisting) {
entry.setValue(value);
}
return previousValue;
} else {
entries.add(value);
return null;
}
}
});
}
/*
创建新线程--删除key对应的值并返回其value
*/
@Override
public V remove(Object key) {
return this.doTask(key, new Task<V>(new TaskOption[]{TaskOption.RESTRUCTURE_AFTER, TaskOption.SKIP_IF_EMPTY}) {
@Override
protected V execute(Reference<K, V> reference, Entry<K, V> entry) {
if (entry != null) {
reference.release();
return entry.value;
} else {
return null;
}
}
});
}
/*
创建新线程 -- 执行删除 根据key和value值进行删除，当key的value值与输入的value值一致时删除并返回true否则返回false
*/
@Override
public boolean remove(Object key, final Object value) {
return (Boolean)this.doTask(key, new Task<Boolean>(new TaskOption[]{TaskOption.RESTRUCTURE_AFTER, TaskOption.SKIP_IF_EMPTY}) {
@Override
protected Boolean execute(Reference<K, V> reference, Entry<K, V> entry) {
if (entry != null && ObjectUtils.nullSafeEquals(entry.getValue(), value)) {
reference.release();
return true;
} else {
return false;
}
}
});
}
/*
根据key和value将结果替换为新值，并返回替换成功失败的结果
*/
@Override
public boolean replace(K key, final V oldValue, final V newValue) {
return (Boolean)this.doTask(key, new Task<Boolean>(new TaskOption[]{TaskOption.RESTRUCTURE_BEFORE, TaskOption.SKIP_IF_EMPTY}) {
@Override
protected Boolean execute(Reference<K, V> reference, Entry<K, V> entry) {
if (entry != null && ObjectUtils.nullSafeEquals(entry.getValue(), oldValue)) {
entry.setValue(newValue);
return true;
} else {
return false;
}
}
});
}
/*
根据key替换value值，并返回旧值（被替换的值）
*/
@Override
public V replace(K key, final V value) {
return this.doTask(key, new ConcurrentReferenceHashMap<K, V>.Task<V>(new TaskOption[]{TaskOption.RESTRUCTURE_BEFORE, TaskOption.SKIP_IF_EMPTY}) {
@Override
protected V execute(Reference<K, V> reference, Entry<K, V> entry) {
if (entry != null) {
V previousValue = entry.getValue();
entry.setValue(value);
return previousValue;
} else {
return null;
}
}
});
}
/*
遍历每一个segment并对每一个segment进行clear处理
*/
@Override
public void clear() {
Segment[] var1 = this.segments;
int var2 = var1.length;
for(int var3 = 0; var3 < var2; ++var3) {
Segment segment = var1[var3];
segment.clear();
}
}
public void purgeUnreferencedEntries() {
Segment[] var1 = this.segments;
int var2 = var1.length;
for(int var3 = 0; var3 < var2; ++var3) {
ConcurrentReferenceHashMap<K, V>.Segment segment = var1[var3];
segment.restructureIfNecessary(false);
}
}
@Override
public int size() {
int size = 0;
Segment[] var2 = this.segments;
int var3 = var2.length;
for(int var4 = 0; var4 < var3; ++var4) {
ConcurrentReferenceHashMap<K, V>.Segment segment = var2[var4];
size += segment.getCount();
}
return size;
}
@Override
public Set<java.util.Map.Entry<K, V>> entrySet() {
if (this.entrySet == null) {
this.entrySet = new EntrySet();
}
return this.entrySet;
}
//TODO：看到了此处
private <T> T doTask(Object key, Task<T> task) {
int hash = this.getHash(key);
return this.getSegmentForHash(hash) //获取此hash值在的Segment的id
.doTask(hash, key, task); //根据传入的task对象执行相应的增加和删除操作
}
//获取此hash值在的Segment的id
private Segment getSegmentForHash(int hash) {
return this.segments[hash >>> 32 - this.shift & this.segments.length - 1];
}
//计算最小值需要位移的次数 minimumValue初始值为16
protected static int calculateShift(int minimumValue, int maximumValue) {
int shift = 0;
for(int value = 1; value < minimumValue && value < maximumValue; ++shift) {
value <<= 1;
}
return shift;
}
static {
DEFAULT_REFERENCE_TYPE = ReferenceType.SOFT;
}
private static final class WeakEntryReference<K, V> extends WeakReference<Entry<K, V>> implements Reference<K, V> {
private final int hash;
private final Reference<K, V> nextReference;
public WeakEntryReference(Entry<K, V> entry, int hash, Reference<K, V> next, ReferenceQueue<Entry<K, V>> queue) {
super(entry, queue);
this.hash = hash;
this.nextReference = next;
}
@Override
public int getHash() {
return this.hash;
}
@Override
public Reference<K, V> getNext() {
return this.nextReference;
}
@Override
public void release() {
this.enqueue();
this.clear();
}
}
private static final class SoftEntryReference<K, V> extends SoftReference<Entry<K, V>> implements Reference<K, V> {
private final int hash;
private final Reference<K, V> nextReference;
public SoftEntryReference(Entry<K, V> entry, int hash, Reference<K, V> next, ReferenceQueue<Entry<K, V>> queue) {
super(entry, queue);
this.hash = hash;
this.nextReference = next;
}
@Override
public int getHash() {
return this.hash;
}
@Override
public Reference<K, V> getNext() {
return this.nextReference;
}
@Override
public void release() {
this.enqueue();
this.clear();
}
}
protected class ReferenceManager {
private final ReferenceQueue<Entry<K, V>> queue = new ReferenceQueue();
protected ReferenceManager() {
}
public Reference<K, V> createReference(Entry<K, V> entry, int hash, Reference<K, V> next) {
return (Reference)(ConcurrentReferenceHashMap.this.referenceType == ReferenceType.WEAK ? new WeakEntryReference(entry, hash, next, this.queue) : new SoftEntryReference(entry, hash, next, this.queue));
}
public Reference<K, V> pollForPurge() {
return (Reference)this.queue.poll(); //移除并返回第一个值
}
}
protected static enum Restructure {
WHEN_NECESSARY,
NEVER;
private Restructure() {
}
}
private class EntryIterator implements Iterator<Map.Entry<K, V>> {
private int segmentIndex;
private int referenceIndex;
private Reference<K, V>[] references;
private Reference<K, V> reference;
private Entry<K, V> next;
private Entry<K, V> last;
public EntryIterator() {
this.moveToNextSegment();
}
@Override
public boolean hasNext() {
this.getNextIfNecessary();
return this.next != null;
}
@Override
public Entry<K, V> next() {
this.getNextIfNecessary();
if (this.next == null) {
throw new NoSuchElementException();
} else {
this.last = this.next;
this.next = null;
return this.last;
}
}
private void getNextIfNecessary() {
while(this.next == null) {
this.moveToNextReference();
if (this.reference == null) {
return;
}
this.next = this.reference.get();
}
}
private void moveToNextReference() {
if (this.reference != null) {
this.reference = this.reference.getNext();
}
while(this.reference == null && this.references != null) {
if (this.referenceIndex >= this.references.length) {
this.moveToNextSegment();
this.referenceIndex = 0;
} else {
this.reference = this.references[this.referenceIndex];
++this.referenceIndex;
}
}
}
private void moveToNextSegment() {
this.reference = null;
this.references = null;
if (this.segmentIndex < ConcurrentReferenceHashMap.this.segments.length) {
this.references = ConcurrentReferenceHashMap.this.segments[this.segmentIndex].references;
++this.segmentIndex;
}
}
@Override
public void remove() {
Assert.state(this.last != null, "No element to remove");
ConcurrentReferenceHashMap.this.remove(this.last.getKey());
}
}
private class EntrySet extends AbstractSet<Map.Entry<K, V>> {
private EntrySet() {
}
@Override
public Iterator<java.util.Map.Entry<K, V>> iterator() {
return ConcurrentReferenceHashMap.this.new EntryIterator();
}
@Override
public boolean contains(Object o) {
if (o != null && o instanceof java.util.Map.Entry) {
java.util.Map.Entry<?, ?> entry = (java.util.Map.Entry)o;
Reference<K, V> reference = ConcurrentReferenceHashMap.this.getReference(entry.getKey(), Restructure.NEVER);
Entry<K, V> other = reference != null ? reference.get() : null;
if (other != null) {
return ObjectUtils.nullSafeEquals(entry.getValue(), other.getValue());
}
}
return false;
}
@Override
public boolean remove(Object o) {
if (o instanceof java.util.Map.Entry) {
java.util.Map.Entry<?, ?> entry = (java.util.Map.Entry)o;
return ConcurrentReferenceHashMap.this.remove(entry.getKey(), entry.getValue());
} else {
return false;
}
}
@Override
public int size() {
return ConcurrentReferenceHashMap.this.size();
}
@Override
public void clear() {
ConcurrentReferenceHashMap.this.clear();
}
}
private abstract class Entries {
private Entries() {
}
public abstract void add(V var1);
}
private static enum TaskOption {
RESTRUCTURE_BEFORE,
RESTRUCTURE_AFTER,
SKIP_IF_EMPTY,
RESIZE;
private TaskOption() {
}
}
private abstract class Task<T> {
private final EnumSet<TaskOption> options;
public Task(TaskOption... options) {
this.options = options.length == 0 ? EnumSet.noneOf(TaskOption.class) : EnumSet.of(options[0], options);
}
public boolean hasOption(TaskOption option) {
return this.options.contains(option);
}
protected T execute(Reference<K, V> reference, Entry<K, V> entry, Entries entries) {
return this.execute(reference, entry);
}
protected T execute(Reference<K, V> reference, Entry<K, V> entry) {
return null;
}
}
protected static final class Entry<K, V> implements java.util.Map.Entry<K, V> {
private final K key;
private volatile V value;
public Entry(K key, V value) {
this.key = key;
this.value = value;
}
@Override
public K getKey() {
return this.key;
}
@Override
public V getValue() {
return this.value;
}
@Override
public V setValue(V value) {
V previous = this.value;
this.value = value;
return previous;
}
@Override
public String toString() {
return this.key + "=" + this.value;
}
@Override
public final boolean equals(Object other) {
if (this == other) {
return true;
} else if (!(other instanceof java.util.Map.Entry)) {
return false;
} else {
java.util.Map.Entry otherEntry = (java.util.Map.Entry)other;
return ObjectUtils.nullSafeEquals(this.getKey(), otherEntry.getKey()) && ObjectUtils.nullSafeEquals(this.getValue(), otherEntry.getValue());
}
}
@Override
public final int hashCode() {
return ObjectUtils.nullSafeHashCode(this.key) ^ ObjectUtils.nullSafeHashCode(this.value);
}
}
protected interface Reference<K, V> {
Entry<K, V> get();
int getHash();
Reference<K, V> getNext();
void release();
}
protected final class Segment extends ReentrantLock {
private final ReferenceManager referenceManager = ConcurrentReferenceHashMap.this.createReferenceManager();
private final int initialSize;
private volatile Reference<K, V>[] references;
private volatile int count = 0;
private int resizeThreshold;
public Segment(int initialCapacity) {
this.initialSize = 1 << calculateShift(initialCapacity, 1073741824);
this.setReferences(this.createReferenceArray(this.initialSize));
}
//获取对应key的value值（通过hash获取key在references中的位置）
public Reference<K, V> getReference(Object key, int hash, Restructure restructure) {
if (restructure == Restructure.WHEN_NECESSARY) {
this.restructureIfNecessary(false);
}
if (this.count == 0) {
return null;
} else {
Reference<K, V>[] references = this.references;
int index = this.getIndex(hash, references);
Reference<K, V> head = references[index];
return this.findInChain(head, key, hash);
}
}
public <T> T doTask(final int hash, final Object key, Task<T> task) {
boolean resize = task.hasOption(TaskOption.RESIZE);
if (task.hasOption(TaskOption.RESTRUCTURE_BEFORE)) {
//对当前的Segment进行扩容处理
this.restructureIfNecessary(resize);
}
if (task.hasOption(TaskOption.SKIP_IF_EMPTY) && this.count == 0) {
return (T) task.execute((Reference)null, (Entry)null, (Entries)null); //返回null
} else {
//锁住当前Segment对象
this.lock();
Object var10;
try {
final int index = this.getIndex(hash, this.references); //获取key对应的index值
final Reference<K, V> head = this.references[index]; //获取Reference对象
Reference<K, V> reference = this.findInChain(head, key, hash); //同一个hash可能会保存多个值，此时就需要遍历所有的值，直到key与其值一致
Entry<K, V> entry = reference != null ? reference.get() : null;
Entries entries = new Entries() {
@Override
public void add(V value) {
Entry<K, V> newEntry = new Entry(key, value);
Reference<K, V> newReference = Segment.this.referenceManager.createReference(newEntry, hash, head); //创建一个Reference对象
Segment.this.references[index] = newReference; //将结果直接赋值到对应数组的index上
Segment.this.count++; //数据量加一
}
};
var10 = task.execute(reference, entry, entries); //返回执行后的结果
} finally {
this.unlock(); //解锁
if (task.hasOption(TaskOption.RESTRUCTURE_AFTER)) {
//在加锁的过程中count值有变化，需要对是否需要重新扩容处理
this.restructureIfNecessary(resize);
}
}
return (T) var10;
}
}
public void clear() {
if (this.count != 0) {
this.lock();
try {
this.setReferences(this.createReferenceArray(this.initialSize));
this.count = 0;
} finally {
this.unlock();
}
}
}
//判断是否需要扩容
protected final void restructureIfNecessary(boolean allowResize) {
boolean needsResize = this.count > 0 && this.count >= this.resizeThreshold;
Reference<K, V> reference = this.referenceManager.pollForPurge(); //移除并返回第一个值
if (reference != null || needsResize && allowResize) {
//加锁，进行扩容
this.lock();
try {
int countAfterRestructure = this.count;
Set<Reference<K, V>> toPurge = Collections.emptySet(); //新建空Set
if (reference != null) {
for(toPurge = new HashSet(); reference != null; reference = this.referenceManager.pollForPurge()) {
((Set)toPurge).add(reference); //将所有的this.referenceManager.pollForPurge()的reference放入新建的Set中
}
}
countAfterRestructure -= ((Set)toPurge).size();
needsResize = countAfterRestructure > 0 && countAfterRestructure >= this.resizeThreshold; //计算是否需要扩容
boolean resizing = false;
int restructureSize = this.references.length;
if (allowResize && needsResize && restructureSize < 1073741824) { //1073741824 为int的最大值
restructureSize <<= 1;
resizing = true;
}
Reference<K, V>[] restructured = resizing ? this.createReferenceArray(restructureSize) : this.references;
for(int i = 0; i < this.references.length; ++i) {
reference = this.references[i];
if (!resizing) {
restructured[i] = null;
}
for(; reference != null; reference = reference.getNext()) {
if (!((Set)toPurge).contains(reference) && reference.get() != null) {
int index = this.getIndex(reference.getHash(), restructured);
restructured[index] = this.referenceManager.createReference(reference.get(), reference.getHash(), restructured[index]);//根据值新建一个Reference<K, V>对象，并放到对应的数组中
}
}
}
if (resizing) {
this.setReferences(restructured);
}
//把扩容后的容量赋值到count中
this.count = Math.max(countAfterRestructure, 0);
} finally {
//解锁
this.unlock();
}
}
}
//同一个hash可能会保存多个值，此时就需要遍历所有的值，直到key与其值一致
private Reference<K, V> findInChain(Reference<K, V> reference, Object key, int hash) {
for(; reference != null; reference = reference.getNext()) {
if (reference.getHash() == hash) {
Entry<K, V> entry = reference.get();
if (entry != null) {
K entryKey = entry.getKey();
if (entryKey == key || entryKey.equals(key)) {
return reference;
}
}
}
}
return null;
}
//根据传入的size创建数组
private Reference<K, V>[] createReferenceArray(int size) {
return (Reference[])((Reference[])Array.newInstance(Reference.class, size));
}
//获取当前此hash在对应的那个位置Segment
private int getIndex(int hash, Reference<K, V>[] references) {
return hash & references.length - 1;
}
//把数组放到Segment中，并设置此Segment需要重新扩容或缩容的值
private void setReferences(Reference<K, V>[] references) {
this.references = references;
this.resizeThreshold = (int)((float)references.length * ConcurrentReferenceHashMap.this.getLoadFactor());
}
public final int getSize() {
return this.references.length;
}
public final int getCount() {
return this.count;
}
}
public static enum ReferenceType {
SOFT,
WEAK;
private ReferenceType() {
}
}
}
欢迎评论，交流
|