🚩LinkedHashMap（底层是(数组+链表/红黑树)+环形双向链表，继承自HashMap)
LinkedHashMap是key键有序的HashMap的一种实现。它除了使用哈希表这个数据结构，使用环形双向链表来保证key的顺序。
HashMap是无序的，也就是说，迭代HashMap所得到的元素顺序并不是它们最初放置到HashMap的顺序。HashMap的这一缺点往往会造成诸多不便，因为在有些场景中，我们确需要用到一个可以保持插入顺序的Map。庆幸的是，JDK为我们解决了这个问题，它为HashMap提供了一个子类 —— LinkedHashMap。虽然LinkedHashMap增加了时间和空间上的开销，但是它通过维护一个额外的双向链表保证了迭代顺序。特别地，该迭代顺序可以是插入顺序，也可以是访问顺序。因此，根据链表中元素的顺序可以将LinkedHashMap分为：保持插入顺序的LinkedHashMap 和 保持访问顺序（LRU，get后调整链表序，最新获取的放在最后)的LinkedHashMap，其中LinkedHashMap的默认实现是按插入顺序排序的。
特点：
一般来说，如果需要使用的Map中的key无序，选择HashMap；如果要求key有序，则选择TreeMap。
但是选择TreeMap就会有性能问题，因为TreeMap的get操作的时间复杂度是O(log(n))的，相比于HashMap的O(1)还是差不少的，LinkedHashMap的出现就是为了平衡这些因素，使得能够以O(1)时间复杂度增加查找元素，又能够保证key的有序性
实现原理：
将所有Entry节点链入一个双向链表的HashMap。在LinkedHashMap中，所有put进来的Entry都保存在哈希表中，但由于它又额外定义了一个以head为头结点的双向链表，因此对于每次put进来Entry，除了将其保存到哈希表上外，还会将其插入到双向链表的尾部。
LinkedHashMap#Entry
static class Entry<K,V> extends HashMap.Node<K,V> {Entry<K,V> before, after;Entry(int hash, K key, V value, Node<K,V> next) {super(hash, key, value, next);}}
成员变量
/*** The head (eldest) of the doubly linked list.*/transient LinkedHashMap.Entry<K,V> head;/*** The tail (youngest) of the doubly linked list.*/transient LinkedHashMap.Entry<K,V> tail;/*** The iteration ordering method for this linked hash map: <tt>true</tt>* for access-order, <tt>false</tt> for insertion-order.** @serial*/final boolean accessOrder;
构造方法
public LinkedHashMap(int initialCapacity, float loadFactor) {super(initialCapacity, loadFactor);accessOrder = false;}/*** Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance* with the specified initial capacity and a default load factor (0.75).** @param initialCapacity the initial capacity* @throws IllegalArgumentException if the initial capacity is negative*/public LinkedHashMap(int initialCapacity) {super(initialCapacity);accessOrder = false;}/*** Constructs an empty insertion-ordered <tt>LinkedHashMap</tt> instance* with the default initial capacity (16) and load factor (0.75).*/public LinkedHashMap() {super();accessOrder = false;}
/*** Constructs an empty <tt>LinkedHashMap</tt> instance with the* specified initial capacity, load factor and ordering mode.** @param initialCapacity the initial capacity* @param loadFactorthe load factor* @param accessOrderthe ordering mode - <tt>true</tt> for* access-order, <tt>false</tt> for insertion-order* @throws IllegalArgumentException if the initial capacity is negative* or the load factor is nonpositive*/public LinkedHashMap(int initialCapacity,float loadFactor,boolean accessOrder) {super(initialCapacity, loadFactor);this.accessOrder = accessOrder;}
put
同HashMap，但重写了afterNodeInsertion。- void afterNodeInsertion(boolean evict) { // possibly remove eldestLinkedHashMap.Entry<K,V> first;if (evict && (first = head) != null && removeEldestEntry(first)) {K key = first.key;removeNode(hash(key), key, null, false, true);}}//可以自行重写该方法protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {return false;}public class LRUHashMap<K, V> extends LinkedHashMap<K, V>{private final int MAX_CACHE_SIZE;public BaseLRUCache(int cacheSize) {super(cacheSize, 0.75f, true);MAX_CACHE_SIZE = cacheSize;}@Overrideprotected boolean removeEldestEntry(Map.Entry eldest) {return size() > MAX_CACHE_SIZE;}}
get
public V get(Object key) {Node<K,V> e;if ((e = getNode(hash(key), key)) == null)return null;if (accessOrder)afterNodeAccess(e);return e.value;}void afterNodeAccess(Node<K,V> e) { // move node to lastLinkedHashMap.Entry<K,V> last;if (accessOrder && (last = tail) != e) {LinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.after = null;if (b == null)head = a;elseb.after = a;if (a != null)a.before = b;elselast = b;if (last == null)head = p;else {p.before = last;last.after = p;}tail = p;++modCount;}}
remove
同HashMap，但重写了afterNodeRemoval。void afterNodeRemoval(Node<K,V> e) { // unlinkLinkedHashMap.Entry<K,V> p =(LinkedHashMap.Entry<K,V>)e, b = p.before, a = p.after;p.before = p.after = null;if (b == null)head = a;elseb.after = a;if (a == null)tail = b;elsea.before = b;}
遍历（迭代环形双向链表)
entrySet
public Set<Map.Entry<K,V>> entrySet() {Set<Map.Entry<K,V>> es;return (es = entrySet) == null ? (entrySet = new LinkedEntrySet()) : es;}
它使用的是该迭代器：
abstract class LinkedHashIterator {LinkedHashMap.Entry<K,V> next;LinkedHashMap.Entry<K,V> current;int expectedModCount;LinkedHashIterator() {next = head;expectedModCount = modCount;current = null;}public final boolean hasNext() {return next != null;}final LinkedHashMap.Entry<K,V> nextNode() {LinkedHashMap.Entry<K,V> e = next;if (modCount != expectedModCount)throw new ConcurrentModificationException();if (e == null)throw new NoSuchElementException();current = e;next = e.after;return e;}public final void remove() {Node<K,V> p = current;if (p == null)throw new IllegalStateException();if (modCount != expectedModCount)throw new ConcurrentModificationException();current = null;K key = p.key;removeNode(hash(key), key, null, false, false);expectedModCount = modCount;}} final class LinkedEntryIterator extends LinkedHashIteratorimplements Iterator<Map.Entry<K,V>> {public final Map.Entry<K,V> next() { return nextNode(); }}
🚩TreeMap（底层是红黑树)
支持排序的Map实现。
基于红黑树实现，无容量限制。
是非线程安全的。
TreeMap是根据key进行排序的，它的排序和定位需要依赖比较器或覆写Comparable接口，也因此不需要key覆写hashCode方法和equals方法，就可以排除掉重复的key，而HashMap的key则需要通过覆写hashCode方法和equals方法来确保没有重复的key
TreeMap的查询、插入、删除效率均没有HashMap高，一般只有要对key排序时才使用TreeMap。
TreeMap的key不能为null，而HashMap的key可以为null。
TreeMap#Entry
static final class Entry<K,V> implements Map.Entry<K,V> {K key;V value;Entry<K,V> left;Entry<K,V> right;Entry<K,V> parent;boolean color = BLACK;/*** Make a new cell with given key, value, and parent, and with* {@code null} child links, and BLACK color.*/Entry(K key, V value, Entry<K,V> parent) {this.key = key;this.value = value;this.parent = parent;}/*** Returns the key.** @return the key*/public K getKey() {return key;}/*** Returns the value associated with the key.** @return the value associated with the key*/public V getValue() {return value;}/*** Replaces the value currently associated with the key with the given* value.** @return the value associated with the key before this method was* called*/public V setValue(V value) {V oldValue = this.value;this.value = value;return oldValue;}public boolean equals(Object o) {if (!(o instanceof Map.Entry))return false;Map.Entry<?,?> e = (Map.Entry<?,?>)o;return valEquals(key,e.getKey()) && valEquals(value,e.getValue());}public int hashCode() {int keyHash = (key==null ? 0 : key.hashCode());int valueHash = (value==null ? 0 : value.hashCode());return keyHash ^ valueHash;}public String toString() {return key + "=" + value;}}
成员变量
private final Comparator<? super K> comparator;private transient Entry<K,V> root;/*** The number of entries in the tree*/private transient int size = 0;/*** The number of structural modifications to the tree.*/private transient int modCount = 0;
构造方法
public TreeMap() {comparator = null;}
public TreeMap(Comparator<? super K> comparator) {parator = comparator;}
put
public V put(K key, V value) {Entry<K,V> t = root;if (t == null) {compare(key, key); // type (and possibly null) checkroot = new Entry<>(key, value, null);size = 1;modCount++;return null;}int cmp;Entry<K,V> parent;// split comparator and comparable pathsComparator<? super K> cpr = comparator;if (cpr != null) {do {parent = t;cmp = pare(key, t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}else {if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;do {parent = t;cmp = pareTo(t.key);if (cmp < 0)t = t.left;else if (cmp > 0)t = t.right;elsereturn t.setValue(value);} while (t != null);}Entry<K,V> e = new Entry<>(key, value, parent);if (cmp < 0)parent.left = e;elseparent.right = e;fixAfterInsertion(e);size++;modCount++;return null;}
get
public V get(Object key) {Entry<K,V> p = getEntry(key);return (p==null ? null : p.value);}final Entry<K,V> getEntry(Object key) {// Offload comparator-based version for sake of performanceif (comparator != null)return getEntryUsingComparator(key);if (key == null)throw new NullPointerException();@SuppressWarnings("unchecked")Comparable<? super K> k = (Comparable<? super K>) key;Entry<K,V> p = root;while (p != null) {int cmp = pareTo(p.key);if (cmp < 0)p = p.left;else if (cmp > 0)p = p.right;elsereturn p;}return null;}final Entry<K,V> getEntryUsingComparator(Object key) {@SuppressWarnings("unchecked")K k = (K) key;Comparator<? super K> cpr = comparator;if (cpr != null) {Entry<K,V> p = root;while (p != null) {int cmp = pare(k, p.key);if (cmp < 0)p = p.left;else if (cmp > 0)p = p.right;elsereturn p;}}return null;}
remove
public V remove(Object key) {Entry<K,V> p = getEntry(key);if (p == null)return null;V oldValue = p.value;deleteEntry(p);return oldValue;} private void deleteEntry(Entry<K,V> p) {modCount++;size--;// If strictly internal, copy successor's element to p and then make p// point to successor.if (p.left != null && p.right != null) {Entry<K,V> s = successor(p);p.key = s.key;p.value = s.value;p = s;} // p has 2 children// Start fixup at replacement node, if it exists.Entry<K,V> replacement = (p.left != null ? p.left : p.right);if (replacement != null) {// Link replacement to parentreplacement.parent = p.parent;if (p.parent == null)root = replacement;else if (p == p.parent.left)p.parent.left = replacement;elsep.parent.right = replacement;// Null out links so they are OK to use by fixAfterDeletion.p.left = p.right = p.parent = null;// Fix replacementif (p.color == BLACK)fixAfterDeletion(replacement);} else if (p.parent == null) { // return if we are the only node.root = null;} else { // No children. Use self as phantom replacement and unlink.if (p.color == BLACK)fixAfterDeletion(p);if (p.parent != null) {if (p == p.parent.left)p.parent.left = null;else if (p == p.parent.right)p.parent.right = null;p.parent = null;}}}
containsKey
public boolean containsKey(Object key) {return getEntry(key) != null;}
containsValue
public boolean containsValue(Object value) {for (Entry<K,V> e = getFirstEntry(); e != null; e = successor(e))if (valEquals(value, e.value))return true;return false;}final Entry<K,V> getFirstEntry() {Entry<K,V> p = root;if (p != null)while (p.left != null)p = p.left;return p;}static <K,V> TreeMap.Entry<K,V> successor(Entry<K,V> t) {if (t == null)return null;else if (t.right != null) {Entry<K,V> p = t.right;while (p.left != null)p = p.left;return p;} else {Entry<K,V> p = t.parent;Entry<K,V> ch = t;while (p != null && ch == p.right) {ch = p;p = p.parent;}return p;}}static final boolean valEquals(Object o1, Object o2) {return (o1==null ? o2==null : o1.equals(o2));}
遍历
public Set<Map.Entry<K,V>> entrySet() {EntrySet es = entrySet;return (es != null) ? es : (entrySet = new EntrySet());} class EntrySet extends AbstractSet<Map.Entry<K,V>> {public Iterator<Map.Entry<K,V>> iterator() {return new EntryIterator(getFirstEntry());} }abstract class PrivateEntryIterator<T> implements Iterator<T> {Entry<K,V> next;Entry<K,V> lastReturned;int expectedModCount;PrivateEntryIterator(Entry<K,V> first) {expectedModCount = modCount;lastReturned = null;next = first;}public final boolean hasNext() {return next != null;}final Entry<K,V> nextEntry() {Entry<K,V> e = next;if (e == null)throw new NoSuchElementException();if (modCount != expectedModCount)throw new ConcurrentModificationException();next = successor(e);lastReturned = e;return e;}final Entry<K,V> prevEntry() {Entry<K,V> e = next;if (e == null)throw new NoSuchElementException();if (modCount != expectedModCount)throw new ConcurrentModificationException();next = predecessor(e);lastReturned = e;return e;}public void remove() {if (lastReturned == null)throw new IllegalStateException();if (modCount != expectedModCount)throw new ConcurrentModificationException();// deleted entries are replaced by their successorsif (lastReturned.left != null && lastReturned.right != null)next = lastReturned;deleteEntry(lastReturned);expectedModCount = modCount;lastReturned = null;}} final class EntryIterator extends PrivateEntryIterator<Map.Entry<K,V>> {EntryIterator(Entry<K,V> first) {super(first);}public Map.Entry<K,V> next() {return nextEntry();}}
🚩ConcurrentHashMap（底层是数组+链表/红黑树，基于CAS+synchronized)
JDK1.7前：分段锁
基于currentLevel划分出了多个Segment来对key-value进行存储，从而避免每次put操作都得锁住整个数组。在默认的情况下，最佳情况下可以允许16个线程并发无阻塞地操作集合对象，尽可能地减少并发时的阻塞现象。
put、remove会加锁。get和containsKey不会加锁。
计算size：在不加锁的情况下遍历所有的段，读取其count以及modCount，这两个属性都是volatile类型的，并进行统计，再遍历一次所有的段，比较modCount是否有改变。如有改变，则再尝试两次机上动作。
如执行了三次上述动作，仍然有问题，则遍历所有段，分别进行加锁，然后进行计算，计算完毕后释放所有锁，从而完成计算动作。
JDK1.8后：CAS+synchronized
bin是桶 bucket的意思
ConcurrentHashMap是延迟初始化的，只有在插入数据时，整个HashMap才被初始化为2的次方大小个桶（bin)，每个bin包含哈希值相同的一系列Node（一般含有0或1个Node)。每个bin的第一个Node作为这个bin的锁，Hash值为零或者负的将被忽略；
每个bin的第一个Node插入用到CAS原理，这是在ConcurrentHashMap中最常发生的操作，其余的插入、删除、替换操作对bin中的第一个Node加锁，进行操作
ConcurrentHashMap的size()函数一般比较少用，同时为了提高增删查改的效率，容器并未在内部保存一个size值，而且采用每次调用size()函数时累加各个bin中Node的个数计算得到，而且这一过程不加锁，即得到的size值不一定是最新的。
ConcurrentHashMap#Node
Node是最核心的内部类，它包装了key-value键值对，所有插入ConcurrentHashMap的数据都包装在这里面。它与HashMap中的定义很相似，但是但是有一些差别：它对value和next属性设置了volatile属性；’它不允许调用setValue方法直接改变Node的value域；它增加了find方法辅助map.get()方法。
static class Node<K,V> implements Map.Entry<K,V> {final int hash;final K key;volatile V val; // value和next是volatile的volatile Node<K,V> next;Node(int hash, K key, V val, Node<K,V> next) {this.hash = hash;this.key = key;this.val = val;this.next = next;}public final K getKey() { return key; }public final V getValue(){ return val; }public final int hashCode() { return key.hashCode() ^ val.hashCode(); }public final String toString(){ return key + "=" + val; }public final V setValue(V value) {throw new UnsupportedOperationException();}public final boolean equals(Object o) {Object k, v, u; Map.Entry<?,?> e;return ((o instanceof Map.Entry) &&(k = (e = (Map.Entry<?,?>)o).getKey()) != null &&(v = e.getValue()) != null &&(k == key || k.equals(key)) &&(v == (u = val) || v.equals(u)));}/*** Virtualized support for map.get(); overridden in subclasses.*/Node<K,V> find(int h, Object k) {Node<K,V> e = this;if (k != null) {do {K ek;if (e.hash == h &&((ek = e.key) == k || (ek != null && k.equals(ek))))return e;} while ((e = e.next) != null);}return null;}}
ConcurrentHashMap#TreeNode
当链表长度过长的时候，会转换为TreeNode。但是与HashMap不相同的是，它并不是直接转换为红黑树，而是把这些结点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装。而且TreeNode在ConcurrentHashMap继承自Node类，而并非HashMap中的继承自LinkedHashMap.Entry<K,V>类，也就是说TreeNode带有next指针，这样做的目的是方便基于TreeBin的访问。static final class TreeNode<K,V> extends Node<K,V> {TreeNode<K,V> parent; // red-black tree linksTreeNode<K,V> left;TreeNode<K,V> right;TreeNode<K,V> prev; // needed to unlink next upon deletionboolean red;TreeNode(int hash, K key, V val, Node<K,V> next,TreeNode<K,V> parent) {super(hash, key, val, next);this.parent = parent;}Node<K,V> find(int h, Object k) {return findTreeNode(h, k, null);}/*** Returns the TreeNode (or null if not found) for the given key* starting at given root.*/final TreeNode<K,V> findTreeNode(int h, Object k, Class<?> kc) {if (k != null) {TreeNode<K,V> p = this;do {int ph, dir; K pk; TreeNode<K,V> q;TreeNode<K,V> pl = p.left, pr = p.right;if ((ph = p.hash) > h)p = pl;else if (ph < h)p = pr;else if ((pk = p.key) == k || (pk != null && k.equals(pk)))return p;else if (pl == null)p = pr;else if (pr == null)p = pl;else if ((kc != null ||(kc = comparableClassFor(k)) != null) &&(dir = compareComparables(kc, k, pk)) != 0)p = (dir < 0) ? pl : pr;else if ((q = pr.findTreeNode(h, k, kc)) != null)return q;elsep = pl;} while (p != null);}return null;}}
ConcurrentHashMap#TreeBin
这个类并不负责包装用户的key、value信息，而是包装的很多TreeNode节点。它代替了TreeNode的根节点，也就是说在实际的ConcurrentHashMap“数组”中，存放的是TreeBin对象，而不是TreeNode对象，这是与HashMap的区别。另外这个类还带有了读写锁。可以看到在构造TreeBin节点时，仅仅指定了它的hash值为TREEBIN常量，这也就是个标识位；同时也看到我们熟悉的红黑树构造方法。/*** TreeNodes used at the heads of bins. TreeBins do not hold user* keys or values, but instead point to list of TreeNodes and* their root. They also maintain a parasitic read-write lock* forcing writers (who hold bin lock) to wait for readers (who do* not) to complete before tree restructuring operations.*/static final class TreeBin<K,V> extends Node<K,V> {TreeNode<K,V> root;volatile TreeNode<K,V> first;volatile Thread waiter;volatile int lockState;// values for lockStatestatic final int WRITER = 1; // set while holding write lockstatic final int WAITER = 2; // set when waiting for write lockstatic final int READER = 4; // increment value for setting read lock/*** Tie-breaking utility for ordering insertions when equal* hashCodes and non-comparable. We don't require a total* order, just a consistent insertion rule to maintain* equivalence across rebalancings. Tie-breaking further than* necessary simplifies testing a bit.*/static int tieBreakOrder(Object a, Object b) {int d;if (a == null || b == null ||(d = a.getClass().getName().compareTo(b.getClass().getName())) == 0)d = (System.identityHashCode(a) <= System.identityHashCode(b) ?-1 : 1);return d;}/*** Creates bin with initial set of nodes headed by b.*/TreeBin(TreeNode<K,V> b) {super(TREEBIN, null, null, null);this.first = b;TreeNode<K,V> r = null;for (TreeNode<K,V> x = b, next; x != null; x = next) {next = (TreeNode<K,V>)x.next;x.left = x.right = null;if (r == null) {x.parent = null;x.red = false;r = x;}else {K k = x.key;int h = x.hash;Class<?> kc = null;for (TreeNode<K,V> p = r;;) {int dir, ph;K pk = p.key;if ((ph = p.hash) > h)dir = -1;else if (ph < h)dir = 1;else if ((kc == null &&(kc = comparableClassFor(k)) == null) ||(dir = compareComparables(kc, k, pk)) == 0)dir = tieBreakOrder(k, pk);TreeNode<K,V> xp = p;if ((p = (dir <= 0) ? p.left : p.right) == null) {x.parent = xp;if (dir <= 0)xp.left = x;elsexp.right = x;r = balanceInsertion(r, x);break;}}}}this.root = r;assert checkInvariants(root);}}
ConcurrentHashMap#ForwardingNode
/*** A node inserted at head of bins during transfer operations.*/static final class ForwardingNode<K,V> extends Node<K,V> {final Node<K,V>[] nextTable;ForwardingNode(Node<K,V>[] tab) {super(MOVED, null, null, null);this.nextTable = tab;}Node<K,V> find(int h, Object k) {// loop to avoid arbitrarily deep recursion on forwarding nodesouter: for (Node<K,V>[] tab = nextTable;;) {Node<K,V> e; int n;if (k == null || tab == null || (n = tab.length) == 0 ||(e = tabAt(tab, (n - 1) & h)) == null)return null;for (;;) {int eh; K ek;if ((eh = e.hash) == h &&((ek = e.key) == k || (ek != null && k.equals(ek))))return e;if (eh < 0) {if (e instanceof ForwardingNode) {tab = ((ForwardingNode<K,V>)e).nextTable;continue outer;}elsereturn e.find(h, k);}if ((e = e.next) == null)return null;}}}}
ConcurrentHashMap#ReservationNode
/*** A place-holder node used in computeIfAbsent and compute*/static final class ReservationNode<K,V> extends Node<K,V> {ReservationNode() {super(RESERVED, null, null, null);}Node<K,V> find(int h, Object k) {return null;}}
节点类型
hash值大于等于0，则是链表节点，Node
hash值为-1 MOVED，则是forwarding nodes，存储nextTable的引用。只有table发生扩容的时候，ForwardingNode才会发挥作用，作为一个占位符放在table中表示当前节点为null或则已经被移动。
hash值为-2 TREEBIN，则是红黑树根，TreeBin类型
hash值为-3 RESERVED，则是reservation nodes，
static final int MOVED = -1; // hash for forwarding nodes
static final int TREEBIN = -2; // hash for roots of trees
static final int RESERVED = -3; // hash for transient reservations
成员变量
/*** The largest possible table capacity. This value must be* exactly 1<<30 to stay within Java array allocation and indexing* bounds for power of two table sizes, and is further required* because the top two bits of 32bit hash fields are used for* control purposes.*/private static final int MAXIMUM_CAPACITY = 1 << 30;/*** The default initial table capacity. Must be a power of 2* (i.e., at least 1) and at most MAXIMUM_CAPACITY.*/private static final int DEFAULT_CAPACITY = 16;/*** The largest possible (non-power of two) array size.* Needed by toArray and related methods.*/static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;/*** The default concurrency level for this table. Unused but* defined for compatibility with previous versions of this class.*/private static final int DEFAULT_CONCURRENCY_LEVEL = 16;/*** The load factor for this table. Overrides of this value in* constructors affect only the initial table capacity. The* actual floating point value isn't normally used -- it is* simpler to use expressions such as {@code n - (n >>> 2)} for* the associated resizing threshold.*/private static final float LOAD_FACTOR = 0.75f;/*** The bin count threshold for using a tree rather than list for a* bin. Bins are converted to trees when adding an element to a* bin with at least this many nodes. The value must be greater* than 2, and should be at least 8 to mesh with assumptions in* tree removal about conversion back to plain bins upon* shrinkage.*/static final int TREEIFY_THRESHOLD = 8;/*** The bin count threshold for untreeifying a (split) bin during a* resize operation. Should be less than TREEIFY_THRESHOLD, and at* most 6 to mesh with shrinkage detection under removal.*/static final int UNTREEIFY_THRESHOLD = 6;/*** The smallest table capacity for which bins may be treeified.* (Otherwise the table is resized if too many nodes in a bin.)* The value should be at least 4 * TREEIFY_THRESHOLD to avoid* conflicts between resizing and treeification thresholds.*/static final int MIN_TREEIFY_CAPACITY = 64;/*** Minimum number of rebinnings per transfer step. Ranges are* subdivided to allow multiple resizer threads. This value* serves as a lower bound to avoid resizers encountering* excessive memory contention. The value should be at least* DEFAULT_CAPACITY.*/private static final int MIN_TRANSFER_STRIDE = 16;/*** The number of bits used for generation stamp in sizeCtl.* Must be at least 6 for 32bit arrays.*/private static int RESIZE_STAMP_BITS = 16;/*** The maximum number of threads that can help resize.* Must fit in 32 - RESIZE_STAMP_BITS bits.*/private static final int MAX_RESIZERS = (1 << (32 - RESIZE_STAMP_BITS)) - 1;/*** The bit shift for recording size stamp in sizeCtl.*/private static final int RESIZE_STAMP_SHIFT = 32 - RESIZE_STAMP_BITS;/** Encodings for Node hash fields. See above for explanation.*/static final int MOVED= -1; // hash for forwarding nodesstatic final int TREEBIN = -2; // hash for roots of treesstatic final int RESERVED = -3; // hash for transient reservationsstatic final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash/** Number of CPUS, to place bounds on some sizings */static final int NCPU = Runtime.getRuntime().availableProcessors();
/*** The array of bins. Lazily initialized upon first insertion.* Size is always a power of two. Accessed directly by iterators.*/transient volatile Node<K,V>[] table;/*** The next table to use; non-null only while resizing.*/private transient volatile Node<K,V>[] nextTable;/*** Base counter value, used mainly when there is no contention,* but also as a fallback during table initialization* races. Updated via CAS.*/private transient volatile long baseCount;/*** Table initialization and resizing control. When negative, the* table is being initialized or resized: -1 for initialization,* else -(1 + the number of active resizing threads). Otherwise,* when table is null, holds the initial table size to use upon* creation, or 0 for default. After initialization, holds the* next element count value upon which to resize the table.
负数代表正在进行初始化或扩容操作-1代表正在初始化-N 表示有N-1个线程正在进行扩容操作
正数或0代表hash表还没有被初始化，这个数值表示初始化或下一次进行扩容的大小，这一点类似于扩容阈值的概念。还后面可以看到，它的值始终是当前ConcurrentHashMap容量的0.75倍，这与loadfactor是对应的。*/private transient volatile int sizeCtl;/*** The next table index (plus one) to split while resizing.*/private transient volatile int transferIndex;/*** Spinlock (locked via CAS) used when resizing and/or creating CounterCells.*/private transient volatile int cellsBusy;/*** Table of counter cells. When non-null, size is a power of 2.*/private transient volatile CounterCell[] counterCells;// viewsprivate transient KeySetView<K,V> keySet;private transient ValuesView<K,V> values;private transient EntrySetView<K,V> entrySet;
构造方法
public ConcurrentHashMap() {}/*** Creates a new, empty map with an initial table size* accommodating the specified number of elements without the need* to dynamically resize.** @param initialCapacity The implementation performs internal* sizing to accommodate this many elements.* @throws IllegalArgumentException if the initial capacity of* elements is negative*/public ConcurrentHashMap(int initialCapacity) {if (initialCapacity < 0)throw new IllegalArgumentException();int cap = ((initialCapacity >= (MAXIMUM_CAPACITY >>> 1)) ?MAXIMUM_CAPACITY :tableSizeFor(initialCapacity + (initialCapacity >>> 1) + 1));this.sizeCtl = cap;}/*** Creates a new map with the same mappings as the given map.** @param m the map*/public ConcurrentHashMap(Map<? extends K, ? extends V> m) {this.sizeCtl = DEFAULT_CAPACITY;putAll(m);}/*** Creates a new, empty map with an initial table size based on* the given number of elements ({@code initialCapacity}) and* initial table density ({@code loadFactor}).** @param initialCapacity the initial capacity. The implementation* performs internal sizing to accommodate this many elements,* given the specified load factor.* @param loadFactor the load factor (table density) for* establishing the initial table size* @throws IllegalArgumentException if the initial capacity of* elements is negative or the load factor is nonpositive** @since 1.6*/public ConcurrentHashMap(int initialCapacity, float loadFactor) {this(initialCapacity, loadFactor, 1);}/*** Creates a new, empty map with an initial table size based on* the given number of elements ({@code initialCapacity}), table* density ({@code loadFactor}), and number of concurrently* updating threads ({@code concurrencyLevel}).** @param initialCapacity the initial capacity. The implementation* performs internal sizing to accommodate this many elements,* given the specified load factor.* @param loadFactor the load factor (table density) for* establishing the initial table size* @param concurrencyLevel the estimated number of concurrently* updating threads. The implementation may use this value as* a sizing hint.* @throws IllegalArgumentException if the initial capacity is* negative or the load factor or concurrencyLevel are* nonpositive*/public ConcurrentHashMap(int initialCapacity,float loadFactor, int concurrencyLevel) {if (!(loadFactor > 0.0f) || initialCapacity < 0 || concurrencyLevel <= 0)throw new IllegalArgumentException();if (initialCapacity < concurrencyLevel) // Use at least as many binsinitialCapacity = concurrencyLevel; // as estimated threadslong size = (long)(1.0 + (long)initialCapacity / loadFactor);int cap = (size >= (long)MAXIMUM_CAPACITY) ?MAXIMUM_CAPACITY : tableSizeFor((int)size);this.sizeCtl = cap;}
CAS
private static final sun.misc.Unsafe U;
Unsafe类的几个CAS方法，可以原子性地修改对象的某个属性值
/*** Atomically update Java variable to <tt>x</tt> if it is currently* holding <tt>expected</tt>.* @return <tt>true</tt> if successful*/public final native boolean compareAndSwapObject(Object o, long offset,Object expected,Object x);/*** Atomically update Java variable to <tt>x</tt> if it is currently* holding <tt>expected</tt>.* @return <tt>true</tt> if successful*/public final native boolean compareAndSwapInt(Object o, long offset,int expected,int x);/*** Atomically update Java variable to <tt>x</tt> if it is currently* holding <tt>expected</tt>.* @return <tt>true</tt> if successful*/public final native boolean compareAndSwapLong(Object o, long offset,long expected,long x);
/*** Fetches a reference value from a given Java variable, with volatile* load semantics. Otherwise identical to {@link #getObject(Object, long)}*/public native Object getObjectVolatile(Object o, long offset);/*** Stores a reference value into a given Java variable, with* volatile store semantics. Otherwise identical to {@link #putObject(Object, long, Object)}*/public native void putObjectVolatile(Object o, long offset, Object x);
Unsafe.getObjectVolatile可以直接获取指定内存的数据，保证了每次拿到数据都是最新的。
三个核心方法
ConcurrentHashMap定义了三个原子操作，用于对指定位置的节点进行操作。正是这些原子操作保证了ConcurrentHashMap的线程安全。static final <K,V> Node<K,V> tabAt(Node<K,V>[] tab, int i) {return (Node<K,V>)U.getObjectVolatile(tab, ((long)i << ASHIFT) + ABASE);}static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,Node<K,V> c, Node<K,V> v) {return pareAndSwapObject(tab, ((long)i << ASHIFT) + ABASE, c, v);}static final <K,V> void setTabAt(Node<K,V>[] tab, int i, Node<K,V> v) {U.putObjectVolatile(tab, ((long)i << ASHIFT) + ABASE, v);}
初始化
对于ConcurrentHashMap来说，调用它的构造方法仅仅是设置了一些参数而已。而整个table的初始化是在向ConcurrentHashMap中插入元素的时候发生的。如调用put、computeIfAbsent、compute、merge等方法的时候，调用时机是检查table==null。初始化方法主要应用了关键属性sizeCtl 如果这个值<0，表示其他线程正在进行初始化，就放弃这个操作。在这也可以看出ConcurrentHashMap的初始化只能由一个线程完成。如果获得了初始化权限，就用CAS方法将sizeCtl置为-1，防止其他线程进入。初始化数组后，将sizeCtl的值改为0.75*n。private final Node<K,V>[] initTable() {Node<K,V>[] tab; int sc;while ((tab = table) == null || tab.length == 0) {if ((sc = sizeCtl) < 0)Thread.yield(); // lost initialization race; just spin// 利用CAS方法把sizectl的值置为-1 表示本线程正在进行初始化 else if (pareAndSwapInt(this, SIZECTL, sc, -1)) {try {if ((tab = table) == null || tab.length == 0) {int n = (sc > 0) ? sc : DEFAULT_CAPACITY;@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];table = tab = nt;// 相当于0.75*n 设置一个扩容的阈值 sc = n - (n >>> 2);}} finally {sizeCtl = sc;}break;}}return tab;}
spread（hash)
h是某个对象的hashCode返回值static final int spread(int h) {return (h ^ (h >>> 16)) & HASH_BITS;}
static final int HASH_BITS = 0x7fffffff; // usable bits of normal node hash
类似于Hashtable+HashMap的hash实现，Hashtable中也是和一个魔法值取与，保证结果一定为正数；HashMap中也是将hashCode与其移动低n位的结果再取异或，保证了对象的hashCode的高16位的变化能反应到低16位中，
size相关
成员变量
@sun.misc.Contended static final class CounterCell {volatile long value;CounterCell(long x) { value = x; }}/*** Base counter value, used mainly when there is no contention,* but also as a fallback during table initialization* races. Updated via CAS.*/private transient volatile long baseCount;/*** Spinlock (locked via CAS) used when resizing and/or creating CounterCells.*/private transient volatile int cellsBusy;/*** Table of counter cells. When non-null, size is a power of 2.*/private transient volatile CounterCell[] counterCells;
每个CounterCell都对应一个bucket，CounterCell中的long值就是对应bucket的binCount。计算总大小就是将所有bucket的binCount求和，而每个binCount都存储在CounterCell#value中，每当put或者remove时都会更新节点所在bucket对应的CounterCell#value。
size()
没有直接返回baseCount 而是统计一次这个值，而这个值其实也是一个大概的数值，因此可能在统计的时候有其他线程正在执行插入或删除操作。public int size() {long n = sumCount();return ((n < 0L) ? 0 :(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :(int)n);}
在baseCount基础上再加上所有counterCell的值求和。而在addCount时，会先尝试CAS更新baseCount，如果有冲突，则再尝试CAS更新随机的一个counterCell中的value，这样求和就是正确的size了。
final long sumCount() {CounterCell[] as = counterCells; CounterCell a;long sum = baseCount;if (as != null) {for (int i = 0; i < as.length; ++i) {if ((a = as[i]) != null)// 所有counter的值求和 sum += a.value;}}return sum;}
put（若bucket第一个结点插入则使用CAS，否则加锁)
public V put(K key, V value) {return putVal(key, value, false);}
整体流程就是首先定义不允许key或value为null的情况放入 。对于每一个放入的值，首先利用spread方法对key的hashcode进行一次hash计算，由此来确定这个值在table中的位置。
- 如果这个位置是空的，那么直接放入，而且不需要加锁操作。
- 如果这个位置存在结点，说明发生了hash碰撞，首先判断这个节点的类型。
- 如果是MOVED节点，则表示正在扩容，帮助进行扩容
- 如果是链表节点(hash >=0),则得到的结点就是hash值相同的节点组成的链表的头节点。需要依次向后遍历确定这个新加入的值所在位置。如果遇到hash值与key值都与新加入节点是一致的情况，则只需要更新value值即可。否则依次向后遍历，直到链表尾插入这个结点。 如果加入这个节点以后链表长度大于8，就把这个链表转换成红黑树。
- 如果这个节点的类型已经是树节点的话，直接调用树节点的插入方法进行插入新的值。
- addCount 增加计数值
/** Implementation for put and putIfAbsent */final V putVal(K key, V value, boolean onlyIfAbsent) {if (key == null || value == null) throw new NullPointerException();int hash = spread(key.hashCode());int binCount = 0;// 死循环，只有插入成功时才会跳出for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;if (tab == null || (n = tab.length) == 0)// table为空则初始化（延迟初始化)tab = initTable();else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) {// hash to index后正好为空，则CAS放入；如果失败那么进入下次循环继续尝试if (casTabAt(tab, i, null,new Node<K,V>(hash, key, value, null)))break; // no lock when adding to empty bin}// 如果index处非空，且hash为MOVED（表示该节点是ForwardingNode)，则表示有其它线程正在扩容，则一起进行扩容操作。 else if ((fh = f.hash) == MOVED)tab = helpTransfer(tab, f);// 如果index处非空，且为链表节点或树节点else {V oldVal = null;// 对某个bucket上执行添加操作仅需要锁住第一个Node即可（可以保证不会多线程同时对某个bucket进行写入)synchronized (f) {if (tabAt(tab, i) == f) {// 1) 如果是链表节点，那么插入到链表中if (fh >= 0) {// binCount是该bucket中元素个数binCount = 1;for (Node<K,V> e = f;; ++binCount) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {oldVal = e.val;if (!onlyIfAbsent)e.val = value;break;}Node<K,V> pred = e;if ((e = e.next) == null) {pred.next = new Node<K,V>(hash, key,value, null);break;}}}// 2)如果是红黑树树根，那么插入到红黑树中else if (f instanceof TreeBin) {Node<K,V> p;binCount = 2;if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key,value)) != null) {oldVal = p.val;if (!onlyIfAbsent)p.val = value;}}}}// 插入节点/释放锁之后，如果大小合适调整为红黑树，那么将链表转为红黑树if (binCount != 0) {if (binCount >= TREEIFY_THRESHOLD)treeifyBin(tab, i);if (oldVal != null)return oldVal;break;}}}// 将当前ConcurrentHashMap的元素数量+1 ，如果超过阈值，那么进行扩容 addCount(1L, binCount);return null;}
treeifyBin（有锁，数组较小则扩容，较大则转为红黑树)
private final void treeifyBin(Node<K,V>[] tab, int index) {Node<K,V> b; int n, sc;if (tab != null) {// 如果数组长度n小于阈值MIN_TREEIFY_CAPACITY，默认是64，则会调用tryPresize方法把数组长度扩大到原来的两倍，并触发transfer方法，重新调整节点的位置if ((n = tab.length) < MIN_TREEIFY_CAPACITY)tryPresize(n << 1);else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {synchronized (b) {if (tabAt(tab, index) == b) {TreeNode<K,V> hd = null, tl = null;for (Node<K,V> e = b; e != null; e = e.next) {TreeNode<K,V> p =new TreeNode<K,V>(e.hash, e.key, e.val,null, null);if ((p.prev = tl) == null)hd = p;elsetl.next = p;tl = p;}setTabAt(tab, index, new TreeBin<K,V>(hd));}}}}}
tryPreSize
/*** Tries to presize table to accommodate the given number of elements.** @param size number of elements (doesn't need to be perfectly accurate)*/private final void tryPresize(int size) {int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :tableSizeFor(size + (size >>> 1) + 1);int sc;while ((sc = sizeCtl) >= 0) {Node<K,V>[] tab = table; int n;if (tab == null || (n = tab.length) == 0) {n = (sc > c) ? sc : c;if (pareAndSwapInt(this, SIZECTL, sc, -1)) {try {if (table == tab) {@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];table = nt;sc = n - (n >>> 2);}} finally {sizeCtl = sc;}}}else if (c <= sc || n >= MAXIMUM_CAPACITY)break;else if (tab == table) {int rs = resizeStamp(n);if (sc < 0) {Node<K,V>[] nt;if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||transferIndex <= 0)break;if (pareAndSwapInt(this, SIZECTL, sc, sc + 1))transfer(tab, nt);}else if (pareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))transfer(tab, null);}}}
扩容
tryPresize
tryPresize在putAll以及treeifyBin中调用
private final void tryPresize(int size) {// c是扩容之后预计表的大小int c = (size >= (MAXIMUM_CAPACITY >>> 1)) ? MAXIMUM_CAPACITY :tableSizeFor(size + (size >>> 1) + 1);int sc;// 没有正在初始化或扩容while ((sc = sizeCtl) >= 0) {Node<K,V>[] tab = table; int n;if (tab == null || (n = tab.length) == 0) {n = (sc > c) ? sc : c;// 期间没有其他线程对表操作，则CAS将SIZECTL状态置为-1，表示正在进行初始化if (pareAndSwapInt(this, SIZECTL, sc, -1)) {try {if (table == tab) {@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n];table = nt;// 即0.75*nsc = n - (n >>> 2);}} finally {sizeCtl = sc;}}}// 若欲扩容值不大于原阈值，或现有容量>=最值，则do nothingelse if (c <= sc || n >= MAXIMUM_CAPACITY)break;// table不为空，且在此期间其他线程未修改tableelse if (tab == table) {int rs = resizeStamp(n);if (sc < 0) {Node<K,V>[] nt;if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||transferIndex <= 0)break;if (pareAndSwapInt(this, SIZECTL, sc, sc + 1))// 协助扩容transfer(tab, nt);}else if (pareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))// 发起扩容transfer(tab, null);}}}
addCount
x=1，check=bucketCount
private final void addCount(long x, int check) {// 计数值加x// 利用CAS方法更新baseCount的值 CounterCell[] as; long b, s;if ((as = counterCells) != null ||!pareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x)) {// 如果CAS更新baseCount失败或者counterCells不为空，那么尝试CAS更新当前线程的hashCode对应的bucket的valueCounterCell a; long v; int m;boolean uncontended = true;- if (as == null || (m = as.length - 1) < 0 ||(a = as[ThreadLocalRandom.getProbe() & m]) == null ||!(uncontended =pareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {// 如果两次CAS都失败了，那么调用fullAddCount方法fullAddCount(x, uncontended);return;}if (check <= 1)return;s = sumCount();}// 以上与扩容无关，如果check值大于等于0 则需要检查是否需要进行扩容操作 if (check >= 0) {Node<K,V>[] tab, nt; int n, sc;while (s >= (long)(sc = sizeCtl) && (tab = table) != null &&(n = tab.length) < MAXIMUM_CAPACITY) {int rs = resizeStamp(n);// 如果sizeCtl是小于0的，说明有其他线程正在执行扩容操作，nextTable一定不为空if (sc < 0) {if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || (nt = nextTable) == null ||transferIndex <= 0)break;// 协助扩容if (pareAndSwapInt(this, SIZECTL, sc, sc + 1))transfer(tab, nt);}// 当前线程是唯一的或是第一个发起扩容的线程 此时nextTable=null else if (pareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))// 发起扩容transfer(tab, null);s = sumCount();}}}private final void fullAddCount(long x, boolean wasUncontended) {int h;if ((h = ThreadLocalRandom.getProbe()) == 0) {ThreadLocalRandom.localInit();// force initializationh = ThreadLocalRandom.getProbe();wasUncontended = true;}boolean collide = false;// True if last slot nonemptyfor (;;) {CounterCell[] as; CounterCell a; int n; long v;if ((as = counterCells) != null && (n = as.length) > 0) {if ((a = as[(n - 1) & h]) == null) {if (cellsBusy == 0) { // Try to attach new CellCounterCell r = new CounterCell(x); // Optimistic createif (cellsBusy == 0 &&pareAndSwapInt(this, CELLSBUSY, 0, 1)) {boolean created = false;try {// Recheck under lockCounterCell[] rs; int m, j;if ((rs = counterCells) != null &&(m = rs.length) > 0 &&rs[j = (m - 1) & h] == null) {rs[j] = r;created = true;}} finally {cellsBusy = 0;}if (created)break;continue; // Slot is now non-empty}}collide = false;}else if (!wasUncontended) // CAS already known to failwasUncontended = true;// Continue after rehashelse if (pareAndSwapLong(a, CELLVALUE, v = a.value, v + x))break;else if (counterCells != as || n >= NCPU)collide = false; // At max size or staleelse if (!collide)collide = true;else if (cellsBusy == 0 &&pareAndSwapInt(this, CELLSBUSY, 0, 1)) {try {if (counterCells == as) {// Expand table unless staleCounterCell[] rs = new CounterCell[n << 1];for (int i = 0; i < n; ++i)rs[i] = as[i];counterCells = rs;}} finally {cellsBusy = 0;}collide = false;continue; // Retry with expanded table}h = ThreadLocalRandom.advanceProbe(h);}else if (cellsBusy == 0 && counterCells == as &&pareAndSwapInt(this, CELLSBUSY, 0, 1)) {boolean init = false;try { // Initialize tableif (counterCells == as) {CounterCell[] rs = new CounterCell[2];rs[h & 1] = new CounterCell(x);counterCells = rs;init = true;}} finally {cellsBusy = 0;}if (init)break;}else if (pareAndSwapLong(this, BASECOUNT, v = baseCount, v + x))break;// Fall back on using base}}
transfer
当table容量不足的时候，即table的元素数量达到容量阈值sizeCtl，需要对table进行扩容。 整个扩容分为两部分：
1)构建一个nextTable，大小为table的两倍。2)把table的数据复制到nextTable中。
这两个过程在单线程下实现很简单，但是ConcurrentHashMap是支持并发插入的，扩容操作自然也会有并发的出现，这种情况下，第二步可以支持节点的并发复制，这样性能自然提升不少，但实现的复杂度也上升了一个台阶。
先看第一步，构建nextTable，毫无疑问，这个过程只能有单个线程进行nextTable的初始化。
通过pareAndSwapInt修改sizeCtl值，保证只有一个线程能够初始化nextTable，扩容后的数组长度为原来的两倍。
节点从table移动到nextTable，大体思想是遍历、复制的过程。
1)首先根据运算得到需要遍历的次数i，然后利用tabAt方法获得i位置的元素f，初始化一个ForwardingNode实例fwd。2)如果f==null，则在table中的i位置放入fwd，这个过程是采用
pareAndSwapObjectf方法实现的，很巧妙的实现了节点的并发移动。
3)如果f是链表的头节点，就构造一个反序链表，把他们分别放在nextTable的i和i+n的位置上，移动完成，采用Unsafe.putObjectVolatile方法给table原位置赋值fwd。4)如果f是TreeBin节点，也做一个反序处理，并判断是否需要untreeify，把处理的结果分别放在nextTable的i和i+n的位置上，移动完成，同样采用Unsafe.putObjectVolatile方法给table原位置赋值fwd。5)遍历过所有的节点以后就完成了复制工作，把table指向nextTable，并更新sizeCtl为新数组大小的0.75倍 ，扩容完成。
在多线程环境下，ConcurrentHashMap用两点来保证正确性：ForwardingNode和synchronized。当一个线程遍历到的节点如果是ForwardingNode，则继续往后遍历，如果不是，则将该节点加锁，防止其他线程进入，完成后设置ForwardingNode节点，以便要其他线程可以看到该节点已经处理过了，如此交叉进行，高效而又安全。
/*** Moves and/or copies the nodes in each bin to new table. See* above for explanation.*/private final void transfer(Node<K,V>[] tab, Node<K,V>[] nextTab) {int n = tab.length, stride;if ((stride = (NCPU > 1) ? (n >>> 3) / NCPU : n) < MIN_TRANSFER_STRIDE)stride = MIN_TRANSFER_STRIDE; // subdivide range// 扩容第一步，创建两倍长的数组nextTable，单线程执行// initiating只能有一个线程进行构造nextTable，如果别的线程进入发现不为空就不用构造nextTable了if (nextTab == null) { // initiatingtry {@SuppressWarnings("unchecked")Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];nextTab = nt;} catch (Throwable ex) {// try to cope with OOMEsizeCtl = Integer.MAX_VALUE;return;}nextTable = nextTab;// 原先扩容大小transferIndex = n;}// 扩容第二步，把table的数据复制到nextTable中，多线程可以同时进行int nextn = nextTab.length;// 构造一个ForwardingNode用于多线程之间的共同扩容情况ForwardingNode<K,V> fwd = new ForwardingNode<K,V>(nextTab);boolean advance = true;boolean finishing = false; // to ensure sweep before committing nextTab// 遍历每个节点for (int i = 0, bound = 0;;) {Node<K,V> f; int fh;while (advance) {int nextIndex, nextBound;if (--i >= bound || finishing)advance = false;else if ((nextIndex = transferIndex) <= 0) {i = -1;advance = false;}else if (pareAndSwapInt(this, TRANSFERINDEX, nextIndex,nextBound = (nextIndex > stride ?nextIndex - stride : 0))) {bound = nextBound;i = nextIndex - 1;advance = false;}}// 得到一个i，i指向table中某一个尚未拷贝的bucket，下面的代码是对i对应的bucket进行拷贝，拷贝完后将bucket赋值为fwd（ForwadingNode)//**************************************************************//if (i < 0 || i >= n || i + n >= nextn) {int sc;// 如果原table已经复制结束if (finishing) {nextTable = null;table = nextTab;// 修改扩容后的阀值，应该是现在容量的0.75倍sizeCtl = (n << 1) - (n >>> 1);return;}// 采用CAS算法更新SizeCtl，减一，表示有一个新的线程参与到扩容操作if (pareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT)return;finishing = advance = true;i = n; // recheck before commit}}// CAS算法获取某一个数组的节点，为空就设为ForwordingNodeelse if ((f = tabAt(tab, i)) == null)advance = casTabAt(tab, i, null, fwd);// 如果这个节点的hash值是MOVED，就表示这个节点是ForwordingNode节点，就表示这个节点已经被处理过了，直接跳过else if ((fh = f.hash) == MOVED)advance = true; // already processedelse {synchronized (f) {if (tabAt(tab, i) == f) {Node<K,V> ln, hn;if (fh >= 0) {//如果这个节点的确是链表节点，则拆分为两个子链表，存储到nextTable相应的两个位置int runBit = fh & n;Node<K,V> lastRun = f;for (Node<K,V> p = f.next; p != null; p = p.next) {int b = p.hash & n;if (b != runBit) {runBit = b;lastRun = p;}}if (runBit == 0) {ln = lastRun;hn = null;}else {hn = lastRun;ln = null;}for (Node<K,V> p = f; p != lastRun; p = p.next) {int ph = p.hash; K pk = p.key; V pv = p.val;if ((ph & n) == 0)ln = new Node<K,V>(ph, pk, pv, ln);elsehn = new Node<K,V>(ph, pk, pv, hn);}// CAS存储在nextTable的i位置上setTabAt(nextTab, i, ln);// CAS存储在nextTable的i+n位置上setTabAt(nextTab, i + n, hn);// CAS在原table的i处设置forwordingNode节点，表示这个这个节点已经处理完毕setTabAt(tab, i, fwd);advance = true;}// 如果这个节点是红黑树，则拆分为两颗子树，保存到nextTable相应的两个位置else if (f instanceof TreeBin) {TreeBin<K,V> t = (TreeBin<K,V>)f;TreeNode<K,V> lo = null, loTail = null;TreeNode<K,V> hi = null, hiTail = null;int lc = 0, hc = 0;for (Node<K,V> e = t.first; e != null; e = e.next) {int h = e.hash;TreeNode<K,V> p = new TreeNode<K,V>(h, e.key, e.val, null, null);if ((h & n) == 0) {if ((p.prev = loTail) == null)lo = p;elseloTail.next = p;loTail = p;++lc;}else {if ((p.prev = hiTail) == null)hi = p;elsehiTail.next = p;hiTail = p;++hc;}}// 如果拆分后的树的节点数量已经少于6个就需要重新转化为链表ln = (lc <= UNTREEIFY_THRESHOLD) ? untreeify(lo) :(hc != 0) ? new TreeBin<K,V>(lo) : t;hn = (hc <= UNTREEIFY_THRESHOLD) ? untreeify(hi) :(lc != 0) ? new TreeBin<K,V>(hi) : t;// CAS存储在nextTable的i位置上setTabAt(nextTab, i, ln);// CAS存储在nextTable的i+n位置上setTabAt(nextTab, i + n, hn);// CAS在原table的i处设置forwordingNode节点，表示这个这个节点已经处理完毕setTabAt(tab, i, fwd);advance = true;}}}}}}
helpTransfer
final Node<K,V>[] helpTransfer(Node<K,V>[] tab, Node<K,V> f) {Node<K,V>[] nextTab; int sc;if (tab != null && (f instanceof ForwardingNode) &&(nextTab = ((ForwardingNode<K,V>)f).nextTable) != null) {int rs = resizeStamp(tab.length);while (nextTab == nextTable && table == tab &&(sc = sizeCtl) < 0) {if ((sc >>> RESIZE_STAMP_SHIFT) != rs || sc == rs + 1 ||sc == rs + MAX_RESIZERS || transferIndex <= 0)break;if (pareAndSwapInt(this, SIZECTL, sc, sc + 1)) {// 调用扩容方法transfer(tab, nextTab);break;}}return nextTab;}return table;}
get（无锁)
public V get(Object key) {Node<K,V>[] tab; Node<K,V> e, p; int n, eh; K ek;int h = spread(key.hashCode());if ((tab = table) != null && (n = tab.length) > 0 &&(e = tabAt(tab, (n - 1) & h)) != null) {if ((eh = e.hash) == h) {// bucket中第一个结点就是我们要找的，直接返回if ((ek = e.key) == key || (ek != null && key.equals(ek)))return e.val;}else if (eh < 0)// bucket中第一个结点是红黑树根，则调用find方法去找return (p = e.find(h, key)) != null ? p.val : null;// bucket中第一个结点是链表，则遍历链表查找while ((e = e.next) != null) {if (e.hash == h &&((ek = e.key) == key || (ek != null && key.equals(ek))))return e.val;}}return null;}
untreeify（无锁)
static <K,V> Node<K,V> untreeify(Node<K,V> b) {Node<K,V> hd = null, tl = null;for (Node<K,V> q = b; q != null; q = q.next) {Node<K,V> p = new Node<K,V>(q.hash, q.key, q.val, null);if (tl == null)hd = p;elsetl.next = p;tl = p;}return hd;}
remove（有锁)
public boolean remove(Object key, Object value) {if (key == null)throw new NullPointerException();return value != null && replaceNode(key, null, value) != null;} /*** Implementation for the four public remove/replace methods:* Replaces node value with v, conditional upon match of cv if* non-null. If resulting value is null, delete.*/final V replaceNode(Object key, V value, Object cv) {int hash = spread(key.hashCode());for (Node<K,V>[] tab = table;;) {Node<K,V> f; int n, i, fh;if (tab == null || (n = tab.length) == 0 ||(f = tabAt(tab, i = (n - 1) & hash)) == null)break;else if ((fh = f.hash) == MOVED)// 如果已经被移动，那么就帮助进行扩容tab = helpTransfer(tab, f);else {V oldVal = null;boolean validated = false;synchronized (f) {if (tabAt(tab, i) == f) {// 如果是链表，则删除链表中的节点if (fh >= 0) {validated = true;for (Node<K,V> e = f, pred = null;;) {K ek;if (e.hash == hash &&((ek = e.key) == key ||(ek != null && key.equals(ek)))) {V ev = e.val;if (cv == null || cv == ev ||(ev != null && cv.equals(ev))) {oldVal = ev;if (value != null)e.val = value;else if (pred != null)pred.next = e.next;elsesetTabAt(tab, i, e.next);}break;}pred = e;if ((e = e.next) == null)break;}}// 如果是红黑树，则从红黑树中删除结点else if (f instanceof TreeBin) {validated = true;TreeBin<K,V> t = (TreeBin<K,V>)f;TreeNode<K,V> r, p;if ((r = t.root) != null &&(p = r.findTreeNode(hash, key, null)) != null) {V pv = p.val;if (cv == null || cv == pv ||(pv != null && cv.equals(pv))) {oldVal = pv;if (value != null)p.val = value;else if (t.removeTreeNode(p))setTabAt(tab, i, untreeify(t.first));}}}}}if (validated) {if (oldVal != null) {if (value == null)addCount(-1L, -1);return oldVal;}break;}}}return null;}
containsKey
public boolean containsKey(Object key) {return get(key) != null;}
containsValue
public boolean containsValue(Object value) {if (value == null)throw new NullPointerException();Node<K,V>[] t;if ((t = table) != null) {Traverser<K,V> it = new Traverser<K,V>(t, t.length, 0, t.length);for (Node<K,V> p; (p = it.advance()) != null; ) {V v;if ((v = p.val) == value || (v != null && value.equals(v)))return true;}}return false;} static class Traverser<K,V> {Node<K,V>[] tab; // current table; updated if resizedNode<K,V> next; // the next entry to useTableStack<K,V> stack, spare; // to save/restore on ForwardingNodesint index; // index of bin to use nextint baseIndex;// current index of initial tableint baseLimit;// index bound for initial tablefinal int baseSize;// initial table sizeTraverser(Node<K,V>[] tab, int size, int index, int limit) {this.tab = tab;this.baseSize = size;this.baseIndex = this.index = index;this.baseLimit = limit;this.next = null;}/*** Advances if possible, returning next valid node, or null if none.*/final Node<K,V> advance() {Node<K,V> e;if ((e = next) != null)e = e.next;for (;;) {Node<K,V>[] t; int i, n; // must use locals in checksif (e != null)return next = e;if (baseIndex >= baseLimit || (t = tab) == null ||(n = t.length) <= (i = index) || i < 0)return next = null;if ((e = tabAt(t, i)) != null && e.hash < 0) {if (e instanceof ForwardingNode) {tab = ((ForwardingNode<K,V>)e).nextTable;e = null;pushState(t, i, n);continue;}else if (e instanceof TreeBin)e = ((TreeBin<K,V>)e).first;elsee = null;}if (stack != null)recoverState(n);else if ((index = i + baseSize) >= n)index = ++baseIndex; // visit upper slots if present}}/*** Saves traversal state upon encountering a forwarding node.*/private void pushState(Node<K,V>[] t, int i, int n) {TableStack<K,V> s = spare; // reuse if possibleif (s != null)spare = s.next;elses = new TableStack<K,V>();s.tab = t;s.length = n;s.index = i;s.next = stack;stack = s;}/*** Possibly pops traversal state.** @param n length of current table*/private void recoverState(int n) {TableStack<K,V> s; int len;while ((s = stack) != null && (index += (len = s.length)) >= n) {n = len;index = s.index;tab = s.tab;s.tab = null;TableStack<K,V> next = s.next;s.next = spare; // save for reusestack = next;spare = s;}if (s == null && (index += baseSize) >= n)index = ++baseIndex;}}
遍历
public Set<Map.Entry<K,V>> entrySet() {EntrySetView<K,V> es;return (es = entrySet) != null ? es : (entrySet = new EntrySetView<K,V>(this));} public Iterator<Map.Entry<K,V>> iterator() {ConcurrentHashMap<K,V> m = map;Node<K,V>[] t;int f = (t = m.table) == null ? 0 : t.length;return new EntryIterator<K,V>(t, f, 0, f, m);} static class BaseIterator<K,V> extends Traverser<K,V> {final ConcurrentHashMap<K,V> map;Node<K,V> lastReturned;BaseIterator(Node<K,V>[] tab, int size, int index, int limit,ConcurrentHashMap<K,V> map) {super(tab, size, index, limit);this.map = map;advance();}public final boolean hasNext() { return next != null; }public final boolean hasMoreElements() { return next != null; }public final void remove() {Node<K,V> p;if ((p = lastReturned) == null)throw new IllegalStateException();lastReturned = null;map.replaceNode(p.key, null, null);}} static final class EntryIterator<K,V> extends BaseIterator<K,V>implements Iterator<Map.Entry<K,V>> {EntryIterator(Node<K,V>[] tab, int index, int size, int limit,ConcurrentHashMap<K,V> map) {super(tab, index, size, limit, map);}public final Map.Entry<K,V> next() {Node<K,V> p;if ((p = next) == null)throw new NoSuchElementException();K k = p.key;V v = p.val;lastReturned = p;advance();return new MapEntry<K,V>(k, v, map);}}
1.7 分段锁实现
采用 Segment + HashEntry的方式进行实现put
当执行 put方法插入数据时，根据key的hash值，在 Segment数组中找到相应的位置，如果相应位置的 Segment还未初始化，则通过CAS进行赋值，接着执行 Segment对象的 put方法通过加锁机制插入数据，实现如下：场景：线程A和线程B同时执行相同 Segment对象的 put方法1、线程A执行 tryLock()方法成功获取锁，则把 HashEntry对象插入到相应的位置；2、线程B获取锁失败，则执行 scanAndLockForPut()方法，在 scanAndLockForPut方法中，会通过重复执行 tryLock()方法尝试获取锁，在多处理器环境下，重复次数为64，单处理器重复次数为1，当执行 tryLock()方法的次数超过上限时，则执行 lock()方法挂起线程B；3、当线程A执行完插入操作时，会通过 unlock()方法释放锁，接着唤醒线程B继续执行；size
因为 ConcurrentHashMap是可以并发插入数据的，所以在准确计算元素时存在一定的难度，一般的思路是统计每个 Segment对象中的元素个数，然后进行累加，但是这种方式计算出来的结果并不一样的准确的，因为在计算后面几个 Segment的元素个数时，已经计算过的 Segment同时可能有数据的插入或则删除。先采用不加锁的方式，连续计算元素的个数，最多计算3次： 1、如果前后两次计算结果相同，则说明计算出来的元素个数是准确的； 2、如果前后两次计算结果都不同，则给每个 Segment进行加锁，再计算一次元素的个数；ConcurrentSkipListMap
ConcurrentSkipListMap有几个ConcurrentHashMap 不能比拟的优点：
1、ConcurrentSkipListMap 的key是有序的。
2、ConcurrentSkipListMap 支持更高的并发。ConcurrentSkipListMap 的存取时间是log（N)，和线程数几乎无关。也就是说在数据量一定的情况下，并发的线程越多，ConcurrentSkipListMap越能体现出他的优势。
SkipList 跳表：
跳表是平衡树的一种替代的数据结构，但是和红黑树不相同的是，跳表对于树的平衡的实现是基于一种随机化的算法的，这样也就是说跳表的插入和删除的工作是比较简单的。
下面来研究一下跳表的核心思想：
先从链表开始，如果是一个简单的链表，那么我们知道在链表中查找一个元素I的话，需要将整个链表遍历一次。
如果是说链表是排序的，并且节点中还存储了指向前面第二个节点的指针的话，那么在查找一个节点时，仅仅需要遍历N/2个节点即可。
这基本上就是跳表的核心思想，其实也是一种通过“空间来换取时间”的一个算法，通过在每个节点中增加了向前的指针，从而提升查找的效率。
