ConcurrentMap

public interface ConcurrentMap extends Map

1、 提供其他原子putIfAbsent、remove、replace方法的Map；
2、 内存一致性效果：当存在其他并发collection时，将对象放入ConcurrentMap之前的线程中的操作happen-before随后通过另一线程从ConcurrentMap中访问或移除该元素的操作；

接口方法

/**
 *  如果指定键已经不再与某个值相关联，则将它与给定值关联。
 */
V putIfAbsent(K key, V value);

/**
 *  只有目前将键的条目映射到给定值时，才移除该键的条目。
 */
boolean remove(Object key, Object value);

/**
 *  只有目前将键的条目映射到某一值时，才替换该键的条目。
 */
boolean replace(K key, V oldValue, V newValue);

/**
 *  只有目前将键的条目映射到给定值时，才替换该键的条目。
 */
V replace(K key, V value);

ConcurrentHashMap

public class ConcurrentHashMap extends AbstractMap implements ConcurrentMap, Serializable

1、 支持获取的完全并发和更新的所期望可调整并发的哈希表；
2、 不允许将null用作键或值；
3、 适用于读多写少场景；

成员变量

/* ---------------- Constants -------------- */

/**
 * 默认初始容量
 */
static final int DEFAULT_INITIAL_CAPACITY = 16;

/**
 * 默认装载因子
 */
static final float DEFAULT_LOAD_FACTOR = 0.75f;

/**
 * 默认更新并发线程数
 */
static final int DEFAULT_CONCURRENCY_LEVEL = 16;

/**
 * 最大容量
 */
static final int MAXIMUM_CAPACITY = 1 << 30;

/**
 * SEGMENT最大个数
 */
static final int MAX_SEGMENTS = 1 << 16; // slightly conservative

/**
 * 锁之前重试次数
 */
static final int RETRIES_BEFORE_LOCK = 2;

/* ---------------- Fields -------------- */

/**
 * 段标记
 */
final int segmentMask;

/**
 * 段的偏移量
 */
final int segmentShift;

/**
 * 特殊table-段
 */
final Segment<K,V>[] segments;

transient Set<K> keySet;
transient Set<Map.Entry<K,V>> entrySet;
transient Collection<V> values;

/* ---------------- Small Utilities -------------- */

构造方法

//创建一个带有默认初始容量 (16)、加载因子 (0.75) 和 concurrencyLevel (16) 的新的空映射。
ConcurrentHashMap() 

// 创建一个带有指定初始容量、默认加载因子 (0.75) 和 concurrencyLevel (16) 的新的空映射。          
ConcurrentHashMap(int initialCapacity) 

// 创建一个带有指定初始容量、加载因子和默认 concurrencyLevel (16) 的新的空映射。         
ConcurrentHashMap(int initialCapacity, float loadFactor) 

//创建一个带有指定初始容量、加载因子和并发级别的新的空映射。
ConcurrentHashMap(int initialCapacity, float loadFactor, int concurrencyLevel) 

//构造一个与给定映射具有相同映射关系的新映射。 
ConcurrentHashMap(Map<? extends K,? extends V> m) 
          

常用核心方法

Vput(K key, V value) ：将指定键映射到此表中的指定值。键和值都不可以为 null。返回以前与 key 相关联的值，如果 key 没有映射关系，则返回 null。

public V put(K key, V value) {
    if (value == null)
        throw new NullPointerException();//非空校验
    int hash = hash(key.hashCode());//再哈希
    return segmentFor(hash).put(key, hash, value, false);
}

VputIfAbsent(K key, V value)：如果指定键已经不再与某个值相关联，则将它与给定值关联。返回以前与指定键相关联的值，如果该键没有映射关系，则返回 null。

public V putIfAbsent(K key, V value) {
    if (value == null)
        throw new NullPointerException();
    int hash = hash(key.hashCode());
    return segmentFor(hash).put(key, hash, value, true);
}

final Segment segmentFor(int hash)：根据哈希码计算对应的段segment。

final Segment<K,V> segmentFor(int hash) {
    return segments[(hash >>> segmentShift) & segmentMask];
}

Vput(K key, int hash, V value, boolean onlyIfAbsent)：Segment内部类方法。

static final class Segment<K,V> extends ReentrantLock implements Serializable {
	
	V put(K key, int hash, V value, boolean onlyIfAbsent) {
            lock();//调用父类获取锁方法
            try {
                int c = count;
                if (c++ > threshold) // 判断是否需要扩容
                    rehash();
                HashEntry<K,V>[] tab = table;
                int index = hash & (tab.length - 1);//计算索引
                HashEntry<K,V> first = tab[index];//获取到对应的链表
                HashEntry<K,V> e = first;
                //遍历链表，获取到对应元素
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue;
                if (e != null) {//已存在对应key-value
                    oldValue = e.value;
                    if (!onlyIfAbsent)//判断是否更新value
                        e.value = value;
                }
                else {//key首次put
                    oldValue = null;
                    ++modCount;//修改次数+1
                    tab[index] = new HashEntry<K,V>(key, hash, first, value);
                    count = c; // write-volatile
                }
                return oldValue;
            } finally {
                unlock();//释放锁
            }
        }
}

Vremove(Object key)：从此映射中移除键（及其相应的值）。

public V remove(Object key) {
    int hash = hash(key.hashCode());
    return segmentFor(hash).remove(key, hash, null);
}

boolean remove(Object key, Object value)：只有目前将键的条目映射到给定值时，才移除该键的条目。

public boolean remove(Object key, Object value) {
    int hash = hash(key.hashCode());
    if (value == null)
        return false;
    return segmentFor(hash).remove(key, hash, value) != null;
}

Vremove(Object key, int hash, Object value)：Segment内部类方法。

static final class Segment<K,V> extends ReentrantLock implements Serializable {
	
	 V remove(Object key, int hash, Object value) {
            lock();//获取锁
            try {
                int c = count - 1;
                HashEntry<K,V>[] tab = table;
                int index = hash & (tab.length - 1);
                HashEntry<K,V> first = tab[index];
                HashEntry<K,V> e = first;
                //找对应key-value
                while (e != null && (e.hash != hash || !key.equals(e.key)))
                    e = e.next;

                V oldValue = null;
                if (e != null) {//有对应key-value
                    V v = e.value;
                    if (value == null || value.equals(v)) {
                        oldValue = v;
                        ++modCount;//修改次数+1
                        HashEntry<K,V> newFirst = e.next;
                        //next由final修饰不可变，故移除的节点前所有元素均需要clone。
                        for (HashEntry<K,V> p = first; p != e; p = p.next)
                        newFirst = new HashEntry<K,V>(p.key, p.hash, newFirst, p.value);//                                                 
                        tab[index] = newFirst;
                        count = c; // write-volatile
                    }
                }
                return oldValue;
            } finally {
                unlock();
            }
        }
}

内部类HashEntry

由于key、value、及next均由final声明，故执行remvoe操作后，移除元素的前一个元素对应entry.next值应该变了，但由于final定义，导致不能再改变它，故将它之前的节点全都克隆一次。

 static final class HashEntry<K,V> {
        final K key;
        final int hash;
        volatile V value;
        final HashEntry<K,V> next;
}

Vget(Object key)：返回指定键所映射到的值，如果此映射不包含该键的映射关系，则返回 null。

public V get(Object key) {
    int hash = hash(key.hashCode());
    return segmentFor(hash).get(key, hash);
}

Vget(Object key, int hash) ：Segment内部方法。

V get(Object key, int hash) {
    if (count != 0) { // read-volatile 有key-value
        HashEntry<K,V> e = getFirst(hash);//找到对应的链表，并返回头节点
        //遍历链表,找到对应键值对
        while (e != null) {
            if (e.hash == hash && key.equals(e.key)) {
                V v = e.value;
                if (v != null)
                    return v;
                return readValueUnderLock(e); // recheck
            }
            e = e.next;
        }
    }
    return null;
}

HashEntry<K,V> getFirst(int hash) {
    HashEntry<K,V>[] tab = table;
    return tab[hash & (tab.length - 1)];
}

总结：

1、 ConcurrentHashMap采用分段锁设计(Segment)，默认初始将Map分为16段即Segment[]segments数组长度16，也可理解为写线程并发度为16；
2、 SegmentextendsReentrantLock则每个分段Segment都拥有自己的ReentrantLock，减少锁竞争；
3、 如果并发度设置的过小，会带来严重的锁竞争问题；如果并发度设置的过大，原本位于同一个Segment内的访问会扩散到不同的Segment中，CPUcache命中率会下降，从而引起程序性能下降；
4、 Segment中成员变量：transientvolatileintcount;表示对应Segment中key-value元素个数，当count==0时，get操作直接返回，避免不必要的査找开销；
5、 Segment中有个重要成员变量：volatiletransientConcurrentHashMap.HashEntry[]table每个Segment中key-value都以HashEntry实例存入到该数组中，若有哈希冲突，HashEntry是个链表，以链地址法解决即将哈希地址相同的key，放入到同一个链表中；

putor get or remove主要步骤：

1、 根据key的哈希码再哈希inthash=hash(key.hashCode())；
2、 根据新哈希码找到对应segmentsegmentFor(hash)；
3、 在对应segment中计算HashEntry的索引intindex=hash&(tab.length-1);；
4、 遍历对应HashEntry[]table的table[index]；
5、 匹配HashEntry的哈希码，及key，匹配成功进行对应操作；

jdk1.8新变化：

1、 Segment改为Node，锁住node来实现减小锁粒度；
2、 synchronize替代了ReentrantLock；
3、 利用Unsafe的CAS，实现无锁化的修改值的操作；
4、 Node中next去掉了final修饰，增加了violate修饰，避免了remove后clone问题；
5、 设计了MOVED状态当resize的中过程中线程2还在put数据，线程2会帮助resize；
6、 当链表节点大于等于8时，把链表节点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装；