结合下文对ConcurrentHashMap的分析，可以得知ConcurrentHashMap的数据结构如下，其实就是可以简单的认为，ConcurrentHashMap就是HashMap[] 数组，就是一个数组，数组元素是一个一个的HashMap。
为了更好的理解ConcurrentHashMap，最好首先阅读如下几篇文章： 1）HashMap源码分析 http://blog.csdn.net/prestigeding/article/details/52861420 2）使用Unsafe根据内存地址与偏移量访问数组元素方法：http://blog.csdn.net/prestigeding/article/details/52980801 3）ReentrantLock锁分析：http://blog.csdn.net/prestigeding/article/details/53084883 2、在讲解ConcurrentHashMap之前，先罗列出ConcurrentMap接口
/**2.1 ConcurrentHashMap构造方法与数据结构分析
* A {@link java.util.Map} providing additional atomic
* <tt>putIfAbsent</tt>, <tt>remove</tt>, and <tt>replace</tt> methods.
*
* <p>Memory consistency effects: As with other concurrent
* collections, actions in a thread prior to placing an object into a
* {@code ConcurrentMap} as a key or value
* <a href="package-summary.html#MemoryVisibility"><i>happen-before</i></a>
* actions subsequent to the access or removal of that object from
* the {@code ConcurrentMap} in another thread.
*
* <p>This interface is a member of the
* <a href="{@docRoot}/../technotes/guides/collections/index.html">
* Java Collections Framework</a>.
*
* @since 1.5
* @author Doug Lea
* @param <K> the type of keys maintained by this map
* @param <V> the type of mapped values
*/
public interface ConcurrentMap<K, V> extends Map<K, V> {
/**
* If the specified key is not already associated
* with a value, associate it with the given value.
* This is equivalent to
* <pre>
* if (!map.containsKey(key))
* return map.put(key, value);
* else
* return map.get(key);</pre>
* except that the action is performed atomically.
*
* @param key key with which the specified value is to be associated
* @param value value to be associated with the specified key
* @return the previous value associated with the specified key, or
* <tt>null</tt> if there was no mapping for the key.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with the key,
* if the implementation supports null values.)
* @throws UnsupportedOperationException if the <tt>put</tt> operation
* is not supported by this map
* @throws ClassCastException if the class of the specified key or value
* prevents it from being stored in this map
* @throws NullPointerException if the specified key or value is null,
* and this map does not permit null keys or values
* @throws IllegalArgumentException if some property of the specified key
* or value prevents it from being stored in this map
*
*/
V putIfAbsent(K key, V value);
/**
* Removes the entry for a key only if currently mapped to a given value.
* This is equivalent to
* <pre>
* if (map.containsKey(key) && map.get(key).equals(value)) {
* map.remove(key);
* return true;
* } else return false;</pre>
* except that the action is performed atomically.
*
* @param key key with which the specified value is associated
* @param value value expected to be associated with the specified key
* @return <tt>true</tt> if the value was removed
* @throws UnsupportedOperationException if the <tt>remove</tt> operation
* is not supported by this map
* @throws ClassCastException if the key or value is of an inappropriate
* type for this map
* (<a href="../Collection.html#optional-restrictions">optional</a>)
* @throws NullPointerException if the specified key or value is null,
* and this map does not permit null keys or values
* (<a href="../Collection.html#optional-restrictions">optional</a>)
*/
boolean remove(Object key, Object value);
/**
* Replaces the entry for a key only if currently mapped to a given value.
* This is equivalent to
* <pre>
* if (map.containsKey(key) && map.get(key).equals(oldValue)) {
* map.put(key, newValue);
* return true;
* } else return false;</pre>
* except that the action is performed atomically.
*
* @param key key with which the specified value is associated
* @param oldValue value expected to be associated with the specified key
* @param newValue value to be associated with the specified key
* @return <tt>true</tt> if the value was replaced
* @throws UnsupportedOperationException if the <tt>put</tt> operation
* is not supported by this map
* @throws ClassCastException if the class of a specified key or value
* prevents it from being stored in this map
* @throws NullPointerException if a specified key or value is null,
* and this map does not permit null keys or values
* @throws IllegalArgumentException if some property of a specified key
* or value prevents it from being stored in this map
*/
boolean replace(K key, V oldValue, V newValue);
/**
* Replaces the entry for a key only if currently mapped to some value.
* This is equivalent to
* <pre>
* if (map.containsKey(key)) {
* return map.put(key, value);
* } else return null;</pre>
* except that the action is performed atomically.
*
* @param key key with which the specified value is associated
* @param value value to be associated with the specified key
* @return the previous value associated with the specified key, or
* <tt>null</tt> if there was no mapping for the key.
* (A <tt>null</tt> return can also indicate that the map
* previously associated <tt>null</tt> with the key,
* if the implementation supports null values.)
* @throws UnsupportedOperationException if the <tt>put</tt> operation
* is not supported by this map
* @throws ClassCastException if the class of the specified key or value
* prevents it from being stored in this map
* @throws NullPointerException if the specified key or value is null,
* and this map does not permit null keys or values
* @throws IllegalArgumentException if some property of the specified key
* or value prevents it from being stored in this map
*/
V replace(K key, V value);
}
/**代码@1 concurrencyLevel，含义，并发级别，并发度，在键不冲突的情况下，最多允许多少个线程同时访问数据不需要阻塞（理想情况下），我们应该知道，ConcurrentHashMap的基本实现原理就是引入Segment数据结构，将锁的粒度细化到Segment,也就是说，如果多个线程，同时操作多个key,如果这些key，分布在不同的Segment,那这些线程的操作互不影响，当然不需要加锁，提高性能。所以concurrencyLevel，就是要求告诉ConcurrentHashMap,我需要这么过个线程同时访问你而不产生锁冲突。代码@2，ssize，该变量的值等于ConcurrentHashMap中segment的长度，也就是 Segment[]的长度。该值取决于concurrencyLevel,其实就是小于concurrencyLevel的最大的2的幂，，比如concurrencyLevel=16,那 ssize=16,如果 concurrencyLevel=12,ssize=8，因为ssize的长度为2的幂。变量shift的值，看出来了没，其实就是 ssize 2 ^ shift,其实就是表示ssize需要的二进制位。segmentMask、segmentShift ，这两个属性在该表达式中使用：(h >>> segmentShift) & segmentMask)，很明显，就是用来算Segment[]数组中的下标来的。意图segmentShift = 32 - sshift，也就是利用hash的高位与代表（ssize-1）来定位下标。// 如果默认，初始容量16,那么ssize=16, sshift=4 定位端 hash 无符号向右移多少28位，（总共32位），那就是使原本32-29位参与运算（高位）
* Creates a new, empty map with the specified initial
* capacity, load factor and concurrency level.
*
* @param initialCapacity the initial capacity. The implementation
* performs internal sizing to accommodate this many elements.
* @param loadFactor the load factor threshold, used to control resizing.
* Resizing may be performed when the average number of elements per
* bin exceeds this threshold.
* @param concurrencyLevel the estimated number of concurrently
* updating threads. The implementation performs internal sizing
* to try to accommodate this many threads.
* @throws IllegalArgumentException if the initial capacity is
* negative or the load factor or concurrencyLevel are
* nonpositive.
*/
@SuppressWarnings("unchecked")
public ConcurrentHashMap(int initialCapacity,
float loadFactor, int concurrencyLevel) { //@1
if (!(loadFactor > 0) || initialCapacity < 0 || concurrencyLevel <= 0)
throw new IllegalArgumentException();
if (concurrencyLevel > MAX_SEGMENTS)
concurrencyLevel = MAX_SEGMENTS;
// Find power-of-two sizes best matching arguments
int sshift = 0; //@2 start
int ssize = 1;
while (ssize < concurrencyLevel) {
++sshift;
ssize <<= 1;
}
this.segmentShift = 32 - sshift;
this.segmentMask = ssize - 1; //@2 end
if (initialCapacity > MAXIMUM_CAPACITY)
initialCapacity = MAXIMUM_CAPACITY;
int c = initialCapacity / ssize;
if (c * ssize < initialCapacity)
++c;
int cap = MIN_SEGMENT_TABLE_CAPACITY; // 每个 segment 内部容里
while (cap < c)
cap <<= 1;
// create segments and segments[0]
Segment<K,V> s0 =
new Segment<K,V>(loadFactor, (int)(cap * loadFactor),
(HashEntry<K,V>[])new HashEntry[cap]);
Segment<K,V>[] ss = (Segment<K,V>[])new Segment[ssize];
UNSAFE.putOrderedObject(ss, SBASE, s0); // ordered write of segments[0]
this.segments = ss;
}
变量cap,就是每个Segment中HashEntity[]的长度，大于【初始容量/segment长度】的最小2的幂。分析到这里，ConcurrentHashMap就构建成功了，我们先重点关注一下Segment的数据结构。Segment段的内部数据结构如下：1）类的声明：static final class Segment<K,V> extends ReentrantLock implements Serializable2）数据结构：transient volatile HashEntry<K,V>[] table; // 内部键值对transient int count; // 元素数量transient int modCount; // 结构发生变化的次数transient int threshold; // 扩容时的阔值final float loadFactor; // 扩容因子，主要影响threshold，影响什么时候扩容对上述结构，是否似曾相识，对了，就是它，HashMap；每个Segment其实就是一个HashMap;还有一个很关键点：Segment继承自ReentrantLock,也就是Segment本身就是一把锁。
2.2 public V put(K key, V value) 源码分析
public V put(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException(); // @1
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask; //@2
if ((s = (Segment<K,V>)UNSAFE.getObject // nonvolatile; recheck in ensureSegment
(segments, (j << SSHIFT) + SBASE)) == null) // in ensureSegment @3
s = ensureSegment(j); //@4
return s.put(key, hash, value, false); //@5
}
代码@1，表明 ConcurrentHashMap不支持value为空的键值对。代码@2，计算该key对应的Segment的位置（数组下标），并发包中获取数组元素的方式，采用的是UNSAFE直接操作内存的方式，而不是典型的 Segment[] a = new Segment[16], 第j个元素的值为 a[j]。如果需要详细了解UNSAFE操作数组元素的原理，请查看 另一篇博客(AtomicIntegerArray 源码分析)比如一个Integer[]中，每个int是32位，占4个字节，那数组中第3个位置的开始字节是多少呢？=(3-1) << 2,也就是说SHIFT的值为元素中长度的幂。怎么获取每个元素在数组中长度（字节为单位）= UNSAFE.arrayIndexScale,而 UNSAFE.arrayBaseOffset,返回的是，第一个数据元素相对于对象起始地址的便宜量，该部分的详解，请参考我的技术博客【http://blog.csdn.net/prestigeding/article/details/52980801】代码@3，就是获取j下标的segment对象。相当于 if( (s == segments[j])== null )代码@4，我们将目光移到 ensureSegment方法中：/**该方法，主要是确保segment槽的k位置的Segment不为空，如果为空，初始化。代码@5，代码@4初始化k位置的segment后，将键值对加入到segment,接下重点看一下Segment的put方法：
* Returns the segment for the given index, creating it and
* recording in segment table (via CAS) if not already present.
*
* @param k the index
* @return the segment
*/
@SuppressWarnings("unchecked")
private Segment<K,V> ensureSegment(int k) {
final Segment<K,V>[] ss = this.segments;
long u = (k << SSHIFT) + SBASE; // raw offset
Segment<K,V> seg;
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u)) == null) {
Segment<K,V> proto = ss[0]; // use segment 0 as prototype
int cap = proto.table.length;
float lf = proto.loadFactor;
int threshold = (int)(cap * lf);
HashEntry<K,V>[] tab = (HashEntry<K,V>[])new HashEntry[cap];
if ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) { // recheck
Segment<K,V> s = new Segment<K,V>(lf, threshold, tab);
while ((seg = (Segment<K,V>)UNSAFE.getObjectVolatile(ss, u))
== null) {
if (UNSAFE.compareAndSwapObject(ss, u, null, seg = s))
break;
}
}
}
return seg;
}
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value); // @1
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index); // @2
for (HashEntry<K,V> e = first;;) { // @3
if (e != null) { // @4
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) { //@5
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else { //@6
if (node != null)
node.setNext(first);
else
node = new HashEntry<K,V>(hash, key, value, first);
int c = count + 1;
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
rehash(node);
else
setEntryAt(tab, index, node);
++modCount;
count = c;
oldValue = null;
break;
}
}
} finally {
unlock();
}
return oldValue;
}
该方法，实现思路其实和HashMap一样，就是要在Segment的HashEntity[] table的指定位置加入新的Node,如果在位置k的位置不为空，此时，说明该位置发生了hash冲突，这是需要先遍历整个链，看是否有相等的key,如果key相等，则替换该值，如果没有，则将新加入的节点的next指针指向 table[k],然后将node加入到k位置。但是，由于ConcurrentHashMap是支持多个线程同时访问的，对于单个Segment的操作，需要加锁。代码@1，首先尝试获取锁，如果成功获取锁，则继续添加元素，如果获取锁失败，后面重点分析。代码@2，获取该key所对应的table[]中的下标。根据该元素是否为空，有两种操作，如果为空，说明没有发生冲突，也就是走代码@6分支，就是将新创建的节点的节点放入table[k]处，当然，此时需要判断是否需要进行rehash操作（ConcurrentHashMap的是否需要rehash,就是判断阔值）。代码@4，就是循环判断table[k]的链条中，是否有key与待操作key相等，如果相等，直接替换就好。由于@3开始，其实就是整个put方法，会在锁保护中。上述过程，应该很好理解，所以，现在重点关注两个方法，一是scanAndLockForPut，二是rehash(比较好奇，是否与HashMap相同，应该是一样的吧，呵呵)。/**在没有成功获取锁的情况下，先不急于阻塞，而是乐观的估计获取锁的线程操作的key与当前操作的key没关系，那我该干嘛就干嘛，自旋尝试获取锁（尝试MAX_SCAN_RETRIES，如果未成功获取锁）尝试超过最大尝试次数，为了性能考虑，该线程阻塞，参加代码@2。@3，每隔一次，检查一下 Segment HashEntity[] table 处k的位置的元素是否发生变化，如果发生变化，则重试次数设置为-1，继续尝试获取锁。该方法如果在阻塞在lock()方法，时，一旦获取锁，则进入到final V put(K key, int hash, V value, boolean onlyIfAbsent) 方法中，进行常规的put方法（与HashMap操作类似。）接下来重点看一下代码@7，如果当前segment中容量大于阔值，并小于允许的最大长度时，需要进行rehash,下面分析一下rehash源码：
* Scans for a node containing given key while trying to
* acquire lock, creating and returning one if not found. Upon
* return, guarantees that lock is held. UNlike in most
* methods, calls to method equals are not screened: Since
* traversal speed doesn't matter, we might as well help warm
* up the associated code and accesses as well.
*
* @return a new node if key not found, else null
*/
private HashEntry<K,V> scanAndLockForPut(K key, int hash, V value) {
HashEntry<K,V> first = entryForHash(this, hash);
HashEntry<K,V> e = first;
HashEntry<K,V> node = null;
int retries = -1; // negative while locating node
while (!tryLock()) {
HashEntry<K,V> f; // to recheck first below
if (retries < 0) {
if (e == null) {
if (node == null) // speculatively create node
node = new HashEntry<K,V>(hash, key, value, null);
retries = 0;
}
else if (key.equals(e.key))
retries = 0;
else
e = e.next;
}
else if (++retries > MAX_SCAN_RETRIES) {
lock();
break;
}
else if ((retries & 1) == 0 &&
(f = entryForHash(this, hash)) != first) {
e = first = f; // re-traverse if entry changed
retries = -1;
}
}
return node;
}
/**在理解了HashMap的rehash方法后，再来看该方法，应该能很好的理解，故不做重复讲解了。
* Doubles size of table and repacks entries, also adding the
* given node to new table
*/
@SuppressWarnings("unchecked")
private void rehash(HashEntry<K,V> node) {
/*
* Reclassify nodes in each list to new table. Because we
* are using power-of-two expansion, the elements from
* each bin must either stay at same index, or move with a
* power of two offset. We eliminate unnecessary node
* creation by catching cases where old nodes can be
* reused because their next fields won't change.
* Statistically, at the default threshold, only about
* one-sixth of them need cloning when a table
* doubles. The nodes they replace will be garbage
* collectable as soon as they are no longer referenced by
* any reader thread that may be in the midst of
* concurrently traversing table. Entry accesses use plain
* array indexing because they are followed by volatile
* table write.
*/
HashEntry<K,V>[] oldTable = table;
int oldCapacity = oldTable.length;
int newCapacity = oldCapacity << 1;
threshold = (int)(newCapacity * loadFactor);
HashEntry<K,V>[] newTable =
(HashEntry<K,V>[]) new HashEntry[newCapacity];
int sizeMask = newCapacity - 1;
for (int i = 0; i < oldCapacity ; i++) {
HashEntry<K,V> e = oldTable[i];
if (e != null) {
HashEntry<K,V> next = e.next;
int idx = e.hash & sizeMask;
if (next == null) // Single node on list
newTable[idx] = e;
else { // Reuse consecutive sequence at same slot
HashEntry<K,V> lastRun = e;
int lastIdx = idx;
for (HashEntry<K,V> last = next;
last != null;
last = last.next) {
int k = last.hash & sizeMask;
if (k != lastIdx) {
lastIdx = k;
lastRun = last;
}
}
newTable[lastIdx] = lastRun;
// Clone remaining nodes
for (HashEntry<K,V> p = e; p != lastRun; p = p.next) {
V v = p.value;
int h = p.hash;
int k = h & sizeMask;
HashEntry<K,V> n = newTable[k];
newTable[k] = new HashEntry<K,V>(h, p.key, v, n);
}
}
}
}
int nodeIndex = node.hash & sizeMask; // add the new node
node.setNext(newTable[nodeIndex]);
newTable[nodeIndex] = node;
table = newTable;
}
2.2.2、public V putIfAbsent(K key, V value) 该方法的语义是，如果存在key，则直接返回key关联的value,如果key不存在，则加入该键值对，并返回null；该步骤是原子操作。
public V putIfAbsent(K key, V value) {
Segment<K,V> s;
if (value == null)
throw new NullPointerException();
int hash = hash(key);
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
s = ensureSegment(j);
return s.put(key, hash, value, true);
}
该方法与put方法的实现基本相同，唯一不同的是，对已经存在key时，put方法是直接覆盖旧值，而putIfAbsent是，返回旧值。
2.2.3、 public void putAll(Map m)
public void putAll(Map<? extends K, ? extends V> m) {
for (Map.Entry<? extends K, ? extends V> e : m.entrySet())
put(e.getKey(), e.getValue());
}
直接将传人的Map类型的参数，遍历，调用put方法。看过了put函数，我们将目标转向到get方法中，瞧一瞧get相关方法的实现：2.2.4 public V get(Object key)源码分析：/**从上文中可以看到，get方法并没有加锁，只是根据key的hash，然后算出Segment槽的位置，不是直接根据下标去获取Segment，也不是直接根据下标去Segment 的 HashEntity[] tab中去获取元素，而是使用了 UNSAFE.getObjectVolatile方法，直接操作内存，并使用volatile方式获取，最大程度保证可见性。有人或许有疑问，为什么get方法不加读锁，阻止其他写入请求呢？其实这样做意义并不大，ConcurrentHashMap的是一个容器，数据存储，提供基本的 put,get操作，对单一一个get请求加锁，没什么意义，因为get方法并不会改变ConcurrentHashMap的内部结构，在当前线程获取到key中的值，然后其他线程删除了该key,这在业务场景上本身就是正常不过的操作。所以get方法并不需要加锁。
* Returns the value to which the specified key is mapped,
* or {@code null} if this map contains no mapping for the key.
*
* <p>More formally, if this map contains a mapping from a key
* {@code k} to a value {@code v} such that {@code key.equals(k)},
* then this method returns {@code v}; otherwise it returns
* {@code null}. (There can be at most one such mapping.)
*
* @throws NullPointerException if the specified key is null
*/
public V get(Object key) {
Segment<K,V> s; // manually integrate access methods to reduce overhead
HashEntry<K,V>[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return e.value;
}
}
return null;
}
2.3 浏览源码，发现无论是replace方法，还是remove方法等操作内部等都和HashMap相似，因为Segment就是一个带锁的HashMap。所以，接下来，我们可以这样思考，put,replace,remove这些方法比HashMap效率高，因为提供了并发度，那这些获取全局的属性的方法呢，比如keys,size等这些方法，性能又是如何呢？我们将目光转向size，keys等遍历方法。2.3.1 public int size方法
/**该方法的核心实现原理：从上文的解读，我想大家应该已经了解每一个Segment就是一个HashMap,HashMap中有两个变量，modCount，表示数据结构发生变化次数，比如put一个未在HashMap中包含的key,比如remove,比如clear方法，每调用一次上述方法，modCount就加1，也就是影响size属性的操作，都会将modeCount加一；另一个变量size，记录HashMap中键值对的个数。那ConcurrentHashMap的size方法，如果结构没有发生改变，只需将各个Segment的size相加，就可以得到ConcurrentHashMap的size,然并卯，在相加的过程其他线程如果有改变Segment内部的结构的话，导致size不准确，该方法的实现办法，是先乐观的尝试计算相加的过程最多三次，最少两次，如果前后两次的modCount一样，就说明在计算size的过程中，其他线程并没有改变ConcurrentHashMap的结构没有变化，则可以直接将size返回，结束该方法的调用，如果有变化，则需要依次对所有Segment申请加锁操作，只有获取全部锁后，然后对每个segment的size相加，然后是否锁，并返回size值。代码@1,如果重试次数达到 (RETRIES_BEFORE_LOCK +１ ,默认为2)次数后，说明需要加锁才能计算。代码@2，对Segment相加计算size代码@3，就是实现，判断连续两次计算出的modCount相等，说明该size值正确，否则，继续尝试，获取去请求锁。2.3.2 public boolean isEmpty() 方法源码解读
* Returns the number of key-value mappings in this map. If the
* map contains more than <tt>Integer.MAX_VALUE</tt> elements, returns
* <tt>Integer.MAX_VALUE</tt>.
*
* @return the number of key-value mappings in this map
*/
public int size() {
// Try a few times to get accurate count. On failure due to
// continuous async changes in table, resort to locking.
final Segment<K,V>[] segments = this.segments;
int size;
boolean overflow; // true if size overflows 32 bits
long sum; // sum of modCounts
long last = 0L; // previous sum
int retries = -1; // first iteration isn't retry
try {
for (;;) {
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
sum = 0L;
size = 0;
overflow = false;
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
sum += seg.modCount;
int c = seg.count;
if (c < 0 || (size += c) < 0)
overflow = true;
}
}
if (sum == last)
break;
last = sum;
}
} finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
return overflow ? Integer.MAX_VALUE : size;
}
/**该方法的核心实现原理：就是遍历有所有的segment，一旦发现有存在size不等于0的segment，则返回false；如果发现所有的segment的size为0，则再次遍历，如果两次遍历时 modCount一样，则返回true,否则返回false。大家再看看如下方法：2.3.3 public boolean containsKey(Object key)
* Returns <tt>true</tt> if this map contains no key-value mappings.
*
* @return <tt>true</tt> if this map contains no key-value mappings
*/
public boolean isEmpty() {
/*
* Sum per-segment modCounts to avoid mis-reporting when
* elements are concurrently added and removed in one segment
* while checking another, in which case the table was never
* actually empty at any point. (The sum ensures accuracy up
* through at least 1<<31 per-segment modifications before
* recheck.) Methods size() and containsValue() use similar
* constructions for stability checks.
*/
long sum = 0L;
final Segment<K,V>[] segments = this.segments;
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
if (seg.count != 0)
return false;
sum += seg.modCount;
}
}
if (sum != 0L) { // recheck unless no modifications
for (int j = 0; j < segments.length; ++j) {
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null) {
if (seg.count != 0)
return false;
sum -= seg.modCount;
}
}
if (sum != 0L)
return false;
}
return true;
}
/**2.3.4 public boolean containsValue(Object value)
* Tests if the specified object is a key in this table.
*
* @param key possible key
* @return <tt>true</tt> if and only if the specified object
* is a key in this table, as determined by the
* <tt>equals</tt> method; <tt>false</tt> otherwise.
* @throws NullPointerException if the specified key is null
*/
@SuppressWarnings("unchecked")
public boolean containsKey(Object key) {
Segment<K,V> s; // same as get() except no need for volatile value read
HashEntry<K,V>[] tab;
int h = hash(key);
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
for (HashEntry<K,V> e = (HashEntry<K,V>) UNSAFE.getObjectVolatile
(tab, ((long)(((tab.length - 1) & h)) << TSHIFT) + TBASE);
e != null; e = e.next) {
K k;
if ((k = e.key) == key || (e.hash == h && key.equals(k)))
return true;
}
}
return false;
}
/**2.3.5 public Set<Map.Entry<K,V>> entrySet(); 遍历元素方法。
* Returns <tt>true</tt> if this map maps one or more keys to the
* specified value. Note: This method requires a full internal
* traversal of the hash table, and so is much slower than
* method <tt>containsKey</tt>.
*
* @param value value whose presence in this map is to be tested
* @return <tt>true</tt> if this map maps one or more keys to the
* specified value
* @throws NullPointerException if the specified value is null
*/
public boolean containsValue(Object value) {
// Same idea as size()
if (value == null)
throw new NullPointerException();
final Segment<K,V>[] segments = this.segments;
boolean found = false;
long last = 0;
int retries = -1;
try {
outer: for (;;) {
if (retries++ == RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
ensureSegment(j).lock(); // force creation
}
long hashSum = 0L;
int sum = 0;
for (int j = 0; j < segments.length; ++j) {
HashEntry<K,V>[] tab;
Segment<K,V> seg = segmentAt(segments, j);
if (seg != null && (tab = seg.table) != null) {
for (int i = 0 ; i < tab.length; i++) {
HashEntry<K,V> e;
for (e = entryAt(tab, i); e != null; e = e.next) {
V v = e.value;
if (v != null && value.equals(v)) {
found = true;
break outer;
}
}
}
sum += seg.modCount;
}
}
if (retries > 0 && sum == last)
break;
last = sum;
}
} finally {
if (retries > RETRIES_BEFORE_LOCK) {
for (int j = 0; j < segments.length; ++j)
segmentAt(segments, j).unlock();
}
}
return found;
}
public Set<Map.Entry<K,V>> entrySet() {
Set<Map.Entry<K,V>> es = entrySet;
return (es != null) ? es : (entrySet = new EntrySet());
}
final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return new EntryIterator();
}
public boolean contains(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
V v = ConcurrentHashMap.this.get(e.getKey());
return v != null && v.equals(e.getValue());
}
public boolean remove(Object o) {
if (!(o instanceof Map.Entry))
return false;
Map.Entry<?,?> e = (Map.Entry<?,?>)o;
return ConcurrentHashMap.this.remove(e.getKey(), e.getValue());
}
public int size() {
return ConcurrentHashMap.this.size();
}
public boolean isEmpty() {
return ConcurrentHashMap.this.isEmpty();
}
public void clear() {
ConcurrentHashMap.this.clear();
}
}
final class EntryIterator
extends HashIterator
implements Iterator<Entry<K,V>>
{
public Map.Entry<K,V> next() {
HashEntry<K,V> e = super.nextEntry();
return new WriteThroughEntry(e.key, e.value);
}
}
abstract class HashIterator {
int nextSegmentIndex;
int nextTableIndex;
HashEntry<K,V>[] currentTable;
HashEntry<K, V> nextEntry;
HashEntry<K, V> lastReturned;
HashIterator() {
nextSegmentIndex = segments.length - 1;
nextTableIndex = -1;
advance();
}
/**
* Set nextEntry to first node of next non-empty table
* (in backwards order, to simplify checks).
*/
final void advance() { // @1
for (;;) {
if (nextTableIndex >= 0) {
if ((nextEntry = entryAt(currentTable,
nextTableIndex--)) != null)
break;
}
else if (nextSegmentIndex >= 0) {
Segment<K,V> seg = segmentAt(segments, nextSegmentIndex--);
if (seg != null && (currentTable = seg.table) != null)
nextTableIndex = currentTable.length - 1;
}
else
break;
}
}
final HashEntry<K,V> nextEntry() { // @2
HashEntry<K,V> e = nextEntry;
if (e == null)
throw new NoSuchElementException();
lastReturned = e; // cannot assign until after null check
if ((nextEntry = e.next) == null)
advance();
return e;
}
public final boolean hasNext() { return nextEntry != null; }
public final boolean hasMoreElements() { return nextEntry != null; }
public final void remove() {
if (lastReturned == null)
throw new IllegalStateException();
ConcurrentHashMap.this.remove(lastReturned.key);
lastReturned = null;
}
}
final class WriteThroughEntry
extends AbstractMap.SimpleEntry<K,V>
{
WriteThroughEntry(K k, V v) {
super(k,v);
}
/**
* Set our entry's value and write through to the map. The
* value to return is somewhat arbitrary here. Since a
* WriteThroughEntry does not necessarily track asynchronous
* changes, the most recent "previous" value could be
* different from what we return (or could even have been
* removed in which case the put will re-establish). We do not
* and cannot guarantee more.
*/
public V setValue(V value) {
if (value == null) throw new NullPointerException();
V v = super.setValue(value);
ConcurrentHashMap.this.put(getKey(), value);
return v;
}
}
上述代码主要关注两点：第一是遍历元素的方法；第二是调用该迭代器的size,isEmpty等方法。代码@1，advance，该方法主要是从segments[]数组中的最后一个元素开始，找出segment中HashEntity[] table数组中最后一个元素开始遍历，找到一个不为空nextEntity,这里返回的nextEntity,就是 table[]数组中的元素，不包括链表中的HashEntity，链表中的HashEntity遍历在代码@2 nextEntry 方法中，实现真的挺优雅的。第二个特点是，调用迭代器的size、contains，isEmpty等方法，都是对ConcurrentHashMap对应方法的调用。最后，通过上述的分析，我想对ConcurrentHashMap做一个简单的总结：1、结合上述源码分析，我们可以清楚的认为，一个Segment就是一个与HashMap相同的结构，当然每个Segment就是一把锁，该类的核心思想，就是通过对key的第一次hash,定位的不是以前的HashEntity,而是一个Segemnt,然后对该key限定在该Segment中执行，，这样可以同时允许多个线程向ConcurrentHashMap同时添加元素（当然，要分散到不同的Segment类，故提供了并发度。）2、ConcurrentHashMap是一个并发容器，所谓的并发容器并不是说在使用过程中一定不需要加锁，并发容器能提 供的保证是多个线程同时访问该容器，同时调用会改变内部结构的方法时，比如put方法时，不会破坏内部结构 以至于不能提供服务或提供错误服务（数据视图）。怎么理解并不是一定不要加锁这句话，我举一个例子，比如我们用ConcurrentHashMap来存储数据，完成如下操作1、第一步，设置一个key 为"status":1,然后经过复杂的逻辑处理，由存入一个金额 key为amount,值为10； 伪代码如下 ConcurrentHashMap a = new ConcurrentHashMap(); 逻辑代码 void eval(参数 ...) { a.put("status",1); //经过计算 a.put("amount": 10); //付款 if( a.get("status")==1 ) { //执行付款操作 } } 从上面的代码，如果多个线程执行eval方法，肯定会有问题。所以，还是需要加锁，说白了，ConcurrentHashMap只对单个方法负责，比如对 put 方法负责，只是对调用一次put方法，保证该操作，不会受到其他线程的影响。 3、ConcurrentHash采取如下方法从Segment[] segments,HashEntity[] table,数组中获取元素，其准确实施性依次增强 1） segment[下标],table[下标] 2） 使用UNSAFE根据便宜量直接操作内存方式，使用(voliate方式) 3） 重试一定次数后，加锁。