从今天开始，我的博客更新将围绕着老铁每天面试的问题开始，哈哈，直接进入昨天老铁问倒我的第二个问题：hashLinkedMap，但是顺便加上了几个常问的进行总结：
hashmap:
java1.7 hashMap 底层实现是数组+链表
java1.8 对上面进行优化 数组+链表+红黑树
2.hashmap 是怎么保存数据的。
Node结构:
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
V value;
Node<K,V> next;
Node(int hash, K key, V value, Node<K,V> next) {
this.hash = hash;
this.key = key;
this.value = value;
this.next = next;
}
当我们像hashMap 中放入数据时，其实就是一个
Enity{
private String key;
private String vaue;
}
在存之前会把这个Entity 转成Node :
根据Entity 的key通过hash算出一个值当成Node 的 hash
复制完成后，还需要通过Entity 对象的hash 算出 该 Entiry对象 具体应该放在 hashMap 的那个位置。计算如下 Hash&(lenth-1) 得到的值就是hashMap 对应具体的位置。（length是当前hashMap 的长度）。
map.put(k,v)实现原理
第一步首先将k,v封装到Node对象当中（节点）。第二步它的底层会调用K的hashCode()方法得出hash值。第三步通过哈希表函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上。如果说下标对应的位置上有链表。此时，就会拿着k和链表上每个节点的k进行equal。如果所有的equals方法返回都是false，那么这个新的节点将被添加到链表的末尾。如其中有一个equals返回了true，那么这个节点的value将会被覆盖。
HashMap集合的key，会先后调用两个方法，hashCode and equals方法，这这两个方法都需要重写。
map.get(k)实现原理
先调用k的hashCode()方法得出哈希值，并通过哈希算法转换成数组的下标。第二步：通过上一步哈希算法转换成数组的下标之后，在通过数组下标快速定位到某个位置上。重点理解如果这个位置上什么都没有，则返回null。如果这个位置上有单向链表，那么它就会拿着参数K和单向链表上的每一个节点的K进行equals，如果所有equals方法都返回false，则get方法返回null。如果其中一个节点的K和参数K进行equals返回true，那么此时该节点的value就是我们要找的value了，get方法最终返回这个要找的value。
解决hash 冲突
就是不同的元素通过 Hash&(lenth-1) 公式算出的位置相同，现在就启动了链表（单项链表），挂在了当前位置的下面，而链表的元素怎么关联呢，就用到了Node 的next ，next的值就是该链表下一个元素在内存中的地址。
jdk1.7 就是这样处理的，而到了 1.8 以后，就引用了红黑树，1.8以后这个链表只让挂7个元素，超过七个就会转成一个红黑树进行处理（最多是64，超多64 就会重新拆分）。
当红黑树下挂的节点小于等于6的时候，系统会把红黑树转成链表。 Node 在jdk1.8之前是插入链表头部的，在jdk1.8中是插入链表的尾部的。
hashMap 扩容：
hashMap 会根据 当前的hashMap 的存储量达到 160.75=12 的时候，就是扩容 162=32 依次类推下去。2倍扩容。
JDK1.7下的resize()方法是这样的：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
transfer(newTable, initHashSeedAsNeeded(newCapacity));
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
代码中可以看到，如果原有table长度已经达到了上限，就不再扩容了。
如果还未达到上限，则创建一个新的table，并调用transfer方法：
/**
* Transfers all entries from current table to newTable.
*/
void transfer(Entry[] newTable, boolean rehash) {
int newCapacity = newTable.length;
for (Entry<K,V> e : table) {
while(null != e) {
Entry<K,V> next = e.next; //注释1
if (rehash) {
e.hash = null == e.key ? 0 : hash(e.key);
}
int i = indexFor(e.hash, newCapacity); //注释2
e.next = newTable[i]; //注释3
newTable[i] = e; //注释4
e = next; //注释5
}
}
}
transfer方法的作用是把原table的Node放到新的table中，使用的是头插法，也就是说，新table中链表的顺序和旧列表中是相反的，在HashMap线程不安全的情况下，这种头插法可能会导致环状节点。
jdk1.8:
final Node<K,V>[] resize() {
Node<K,V>[] oldTab = table;
int oldCap = (oldTab == null) ? 0 : oldTab.length;
int oldThr = threshold;
int newCap, newThr = 0;
if (oldCap > 0) {
if (oldCap >= MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return oldTab;
}
else if ((newCap = oldCap << 1) < MAXIMUM_CAPACITY &&
oldCap >= DEFAULT_INITIAL_CAPACITY) //注释1
newThr = oldThr << 1; // double threshold
}
else if (oldThr > 0) // initial capacity was placed in threshold
newCap = oldThr;
else { // zero initial threshold signifies using defaults
newCap = DEFAULT_INITIAL_CAPACITY;
newThr = (int)(DEFAULT_LOAD_FACTOR * DEFAULT_INITIAL_CAPACITY);
}
if (newThr == 0) {
float ft = (float)newCap * loadFactor;
newThr = (newCap < MAXIMUM_CAPACITY && ft < (float)MAXIMUM_CAPACITY ?
(int)ft : Integer.MAX_VALUE);
}
threshold = newThr;
@SuppressWarnings({"rawtypes","unchecked"})
Node<K,V>[] newTab = (Node<K,V>[])new Node[newCap];
table = newTab;
if (oldTab != null) {
for (int j = 0; j < oldCap; ++j) { //注释2
Node<K,V> e;
if ((e = oldTab[j]) != null) {
oldTab[j] = null;
if (e.next == null) //注释3
newTab[e.hash & (newCap - 1)] = e;
else if (e instanceof TreeNode)
((TreeNode<K,V>)e).split(this, newTab, j, oldCap);
else { // preserve order
Node<K,V> loHead = null, loTail = null;
Node<K,V> hiHead = null, hiTail = null;
Node<K,V> next;
do {
next = e.next;
if ((e.hash & oldCap) == 0) { //注释4
if (loTail == null) //注释5
loHead = e;
else
loTail.next = e; //注释6
loTail = e; //注释7
}
else {
if (hiTail == null)
hiHead = e;
else
hiTail.next = e;
hiTail = e;
}
} while ((e = next) != null);
if (loTail != null) { /注释8
loTail.next = null;
newTab[j] = loHead;
}
if (hiTail != null) {
hiTail.next = null;
newTab[j + oldCap] = hiHead;
}
}
}
}
}
return newTab;
}
代码解析：
1，在resize()方法中，定义了oldCap参数，记录了原table的长度，定义了newCap参数，记录新table长度，newCap是oldCap长度的2倍（注释1），同时扩展点也乘2。
2，注释2是循环原table，把原table中的每个链表中的每个元素放入新table。
3，注释3，e.next==null，指的是链表中只有一个元素，所以直接把e放入新table，其中的e.hash & (newCap - 1)就是计算e在新table中的位置，和JDK1.7中的indexFor()方法是一回事。
4，注释// preserve order，这个注释是源码自带的，这里定义了4个变量：loHead，loTail，hiHead，hiTail，看起来可能有点眼晕，其实这里体现了JDK1.8对于计算节点在table中下标的新思路：
正常情况下，计算节点在table中的下标的方法是：hash&(oldTable.length-1)，扩容之后，table长度翻倍，计算table下标的方法是hash&(newTable.length-1)，也就是hash&(oldTable.length*2-1)，于是我们有了这样的结论：这新旧两次计算下标的结果，要不然就相同，要不然就是新下标等于旧下标加上旧数组的长度。
举个例子，假设table原长度是16，扩容后长度32，那么一个hash值在扩容前后的table下标是这么计算的：
hash值的每个二进制位用abcde来表示，那么，hash和新旧table按位与的结果，最后4位显然是相同的，唯一可能出现的区别就在第5位，也就是hash值的b所在的那一位，如果b所在的那一位是0，那么新table按位与的结果和旧table的结果就相同，反之如果b所在的那一位是1，则新table按位与的结果就比旧table的结果多了10000（二进制），而这个二进制10000就是旧table的长度16。
换言之，hash值的新散列下标是不是需要加上旧table长度，只需要看看hash值第5位是不是1就行了，位运算的方法就是hash值和10000（也就是旧table长度）来按位与，其结果只可能是10000或者00000。
所以，注释4处的e.hash & oldCap，就是用于计算位置b到底是0还是1用的，只要其结果是0，则新散列下标就等于原散列下标，否则新散列坐标要在原散列坐标的基础上加上原table长度。
hashLinkedMap
先看个类图：
本质上，HashMap和双向链表合二为一即是LinkedHashMap。所谓LinkedHashMap，其落脚点在HashMap，因此更准确地说，它是一个将所有Entry节点链入一个双向链表双向链表的HashMap。
HashMap是无序的，当我们希望有顺序地去存储key-value时，就需要使用LinkedHashMap了。
由于LinkedHashMap是HashMap的子类，所以LinkedHashMap自然会拥有HashMap的所有特性。比如，LinkedHashMap也最多只允许一条Entry的键为Null(多条会覆盖)，但允许多条Entry的值为Null。
put方法
LinkedHashMap没有重写put方法，所以还是调用HashMap得到put方法，如下：
public V put(K key, V value) {
// 对key为null的处理
if (key == null)
return putForNullKey(value);
// 计算hash
int hash = hash(key);
// 得到在table中的index
int i = indexFor(hash, table.length);
// 遍历table[index]，是否key已经存在，存在则替换，并返回旧值
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
e.recordAccess(this);
return oldValue;
}
}
modCount++;
// 如果key之前在table中不存在，则调用addEntry，LinkedHashMap重写了该方法
addEntry(hash, key, value, i);
return null;
}
我们看看LinkedHashMap的addEntry方法：
void addEntry(int hash, K key, V value, int bucketIndex) {
// 调用父类的addEntry，增加一个Entry到HashMap中
super.addEntry(hash, key, value, bucketIndex);
// removeEldestEntry方法默认返回false，不用考虑
Entry<K,V> eldest = header.after;
if (removeEldestEntry(eldest)) {
removeEntryForKey(eldest.key);
}
}
HashMap的addEntry方法中，createEntry方法，LinkedHashMap进行了重写。
void createEntry(int hash, K key, V value, int bucketIndex) {
HashMap.Entry<K,V> old = table[bucketIndex];
// e就是新创建了Entry，会加入到table[bucketIndex]的表头
Entry<K,V> e = new Entry<>(hash, key, value, old);
table[bucketIndex] = e;
// 把新创建的Entry，加入到双向链表中
e.addBefore(header);
size++;
}
从这里就可以看出，当put元素时，不但要把它加入到HashMap中去，还要加入到双向链表中，所以可以看出LinkedHashMap就是HashMap+双向链表，
LinkedHashMap中添加数据的过程，红色部分是双向链表，黑色部分是HashMap结构，header是一个Entry类型的双向链表表头，本身不存储数据。
首先是只加入一个元素Entry1，假设index为0：
当再加入一个元素Entry2，假设index为15：
当再加入一个元素Entry3, 假设index也是0：
扩容
在HashMap的put方法中，如果发现前元素个数超过了扩容阀值时，会调用resize方法，如下：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
// 把旧table的数据迁移到新table
transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
LinkedHashMap重写了transfer方法，数据的迁移，它的实现如下：
void resize(int newCapacity) {
Entry[] oldTable = table;
int oldCapacity = oldTable.length;
if (oldCapacity == MAXIMUM_CAPACITY) {
threshold = Integer.MAX_VALUE;
return;
}
Entry[] newTable = new Entry[newCapacity];
boolean oldAltHashing = useAltHashing;
useAltHashing |= sun.misc.VM.isBooted() &&
(newCapacity >= Holder.ALTERNATIVE_HASHING_THRESHOLD);
boolean rehash = oldAltHashing ^ useAltHashing;
// 把旧table的数据迁移到新table
transfer(newTable, rehash);
table = newTable;
threshold = (int)Math.min(newCapacity * loadFactor, MAXIMUM_CAPACITY + 1);
}
可以看出，LinkedHashMap扩容时，数据的再散列和HashMap是不一样的。
HashMap是先遍历旧table，再遍历旧table中每个元素的单向链表，取得Entry以后，重新计算hash值，然后存放到新table的对应位置。
LinkedHashMap是遍历的双向链表，取得每一个Entry，然后重新计算hash值，然后存放到新table的对应位置。
从遍历的效率来说，遍历双向链表的效率要高于遍历table，因为遍历双向链表是N次（N为元素个数）；而遍历table是N+table的空余个数（N为元素个数）。
双向链表的重排序
前面分析的，主要是当前LinkedHashMap中不存在当前key时，新增Entry的情况。当key如果已经存在时，则进行更新Entry的value。就是HashMap的put方法中的如下代码：
for (Entry<K,V> e = table[i]; e != null; e = e.next) {
Object k;
if (e.hash == hash && ((k = e.key) == key || key.equals(k))) {
V oldValue = e.value;
e.value = value;
// 重排序
e.recordAccess(this);
return oldValue;
}
}
主要看e.recordAccess(this)，这个方法跟访问顺序有关，而HashMap是无序的，所以在HashMap.Entry的recordAccess方法是空实现，但是LinkedHashMap是有序的,LinkedHashMap.Entry对recordAccess方法进行了重写。
void recordAccess(HashMap<K,V> m) {
LinkedHashMap<K,V> lm = (LinkedHashMap<K,V>)m;
// 如果LinkedHashMap的accessOrder为true，则进行重排序
// 比如前面提到LruCache中使用到的LinkedHashMap的accessOrder属性就为true
if (lm.accessOrder) {
lm.modCount++;
// 把更新的Entry从双向链表中移除
remove();
// 再把更新的Entry加入到双向链表的表尾
addBefore(lm.header);
}
}
在LinkedHashMap中，只有accessOrder为true，即是访问顺序模式，才会put时对更新的Entry进行重新排序，而如果是插入顺序模式时，不会重新排序，这里的排序跟在HashMap中存储没有关系，只是指在双向链表中的顺序。
举个栗子：开始时，HashMap中有Entry1、Entry2、Entry3，并设置LinkedHashMap为访问顺序，则更新Entry1时，会先把Entry1从双向链表中删除，然后再把Entry1加入到双向链表的表尾，而Entry1在HashMap结构中的存储位置没有变化，对比图如下所示：
get方法
public V get(Object key) {
// 调用genEntry得到Entry
Entry<K,V> e = (Entry<K,V>)getEntry(key);
if (e == null)
return null;
// 如果LinkedHashMap是访问顺序的，则get时，也需要重新排序
e.recordAccess(this);
return e.value;
}
先是调用了getEntry方法，通过key得到Entry，而LinkedHashMap并没有重写getEntry方法，所以调用的是HashMap的getEntry方法，在上一篇文章中我们分析过HashMap的getEntry方法：首先通过key算出hash值，然后根据hash值算出在table中存储的index，然后遍历table[index]的单向链表去对比key，如果找到了就返回Entry。
后面调用了LinkedHashMap.Entry的recordAccess方法，上面分析过put过程中这个方法，其实就是在访问顺序的LinkedHashMap进行了get操作以后，重新排序，把get的Entry移动到双向链表的表尾。
遍历方式取数据
来看看HashMap使用遍历方式取数据的过程：
很明显，这样取出来的Entry顺序肯定跟插入顺序不同了，既然LinkedHashMap是有序的，那么它是怎么实现的呢？
先看看LinkedHashMap取遍历方式获取数据的代码：
Map<String, String> linkedHashMap = new LinkedHashMap<>();
linkedHashMap.put("name1", "josan1");
linkedHashMap.put("name2", "josan2");
linkedHashMap.put("name3", "josan3");
// LinkedHashMap没有重写该方法，调用的HashMap中的entrySet方法
Set<Entry<String, String>> set = linkedHashMap.entrySet();
Iterator<Entry<String, String>> iterator = set.iterator();
while(iterator.hasNext()) {
Entry entry = iterator.next();
String key = (String) entry.getKey();
String value = (String) entry.getValue();
System.out.println("key:" + key + ",value:" + value);
}
LinkedHashMap没有重写entrySet方法，我们先来看HashMap中的entrySet，如下：
public Set<Map.Entry<K,V>> entrySet() {
return entrySet0();
}
private Set<Map.Entry<K,V>> entrySet0() {
Set<Map.Entry<K,V>> es = entrySet;
return es != null ? es : (entrySet = new EntrySet());
}
private final class EntrySet extends AbstractSet<Map.Entry<K,V>> {
public Iterator<Map.Entry<K,V>> iterator() {
return newEntryIterator();
}
// 无关代码
......
}
可以看到，HashMap的entrySet方法，其实就是返回了一个EntrySet对象。
我们得到EntrySet会调用它的iterator方法去得到迭代器Iterator，从上面的代码也可以看到，iterator方法中直接调用了newEntryIterator方法并返回，而LinkedHashMap重写了该方法
Iterator<Map.Entry<K,V>> newEntryIterator() {
return new EntryIterator();
}
LinkedHashMap中，Iterator<Entry<String, String>> iterator = set.iterator()，这段代码会返回一个继承LinkedHashIterator的Iterator，它有着跟HashIterator不一样的遍历规则。
该iterator遍历的是双向链表，所以不会存在HashMap中需要寻找下一条单向链表的情况，从头结点Entry header的下一个节点开始，只要把当前返回的Entry的after作为下一个应该返回的节点即可。直到到达双向链表的尾部时，after为双向链表的表头节点Entry header，这时候hasNext就会返回false，表示没有下一个元素了。LinkedHashMap的遍历取值如下图所示：
LinkedHashMap在Android中的应用
在Android中使用图片时，一般会用LruCacha做图片的内存缓存，它里面就是使用LinkedHashMap来实现存储的。
public class LruCache<K, V> {
private final LinkedHashMap<K, V> map;
public LruCache(int maxSize) {
if (maxSize <= 0) {
throw new IllegalArgumentException("maxSize <= 0");
}
this.maxSize = maxSize;
// 注意第三个参数，是accessOrder，这里为true，后面会讲到
this.map = new LinkedHashMap<K, V>(0, 0.75f, true);
}
前面提到了，accessOrder为true，表示LinkedHashMap为访问顺序，当对已存在LinkedHashMap中的Entry进行get和put操作时，会把Entry移动到双向链表的表尾（其实是先删除，再插入）。
我们拿LruCache的put方法举例：
public final V put(K key, V value) {
if (key == null || value == null) {
throw new NullPointerException("key == null || value == null");
}
V previous;
// 对map进行操作之前，先进行同步操作
synchronized (this) {
putCount++;
size += safeSizeOf(key, value);
previous = map.put(key, value);
if (previous != null) {
size -= safeSizeOf(key, previous);
}
}
if (previous != null) {
entryRemoved(false, key, previous, value);
}
// 整理内存，看是否需要移除LinkedHashMap中的元素
trimToSize(maxSize);
return previous;
}
之前提到了，HashMap是线程不安全的，LinkedHashMap同样是线程不安全的。所以在对调用LinkedHashMap的put方法时，先使用synchronized 进行了同步操作。
我们最关心的是倒数第一行代码，其中maxSize为我们给LruCache设置的最大缓存大小。我们看看该方法
/**
* Remove the eldest entries until the total of remaining entries is at or
* below the requested size.
*
* @param maxSize the maximum size of the cache before returning. May be -1
* to evict even 0-sized elements.
*/
public void trimToSize(int maxSize) {
// while死循环，直到满足当前缓存大小小于或等于最大可缓存大小
while (true) {
K key;
V value;
// 线程不安全，需要同步
synchronized (this) {
if (size < 0 || (map.isEmpty() && size != 0)) {
throw new IllegalStateException(getClass().getName()
+ ".sizeOf() is reporting inconsistent results!");
}
// 如果当前缓存的大小，已经小于等于最大可缓存大小，则直接返回
// 不需要再移除LinkedHashMap中的数据
if (size <= maxSize || map.isEmpty()) {
break;
}
// 得到的就是双向链表表头header的下一个Entry
Map.Entry<K, V> toEvict = map.entrySet().iterator().next();
key = toEvict.getKey();
value = toEvict.getValue();
// 移除当前取出的Entry
map.remove(key);
// 从新计算当前的缓存大小
size -= safeSizeOf(key, value);
evictionCount++;
}
entryRemoved(true, key, value, null);
}
}
前面的重排序我们知道，对LinkedHashMap的put和get操作，都会让被操作的Entry移动到双向链表的表尾，而移除是从map.entrySet().iterator().next()开始的，也就是双向链表的表头的header的after开始的，这也就符合了LRU算法的需求。
TreeMap
TreeMap的底层是一颗红黑树
红黑树简介
红黑树又称红-黑二叉树，它首先是一颗二叉树，它具体二叉树所有的特性。同时红黑树更是一颗自平衡的排序二叉树。
我们知道一颗基本的二叉树他们都需要满足一个基本性质--即树中的任何节点的值大于它的左子节点，且小于它的右子节点。按照这个基本性质使得树的检索效率大大提高。我们知道在生成二叉树的过程是非常容易失衡的，最坏的情况就是一边倒（只有右/左子树），这样势必会导致二叉树的检索效率大大降低（O(n)），所以为了维持二叉树的平衡，大牛们提出了各种实现的算法，如：AVL，SBT，伸展树，TREAP ，红黑树等等。
平衡二叉树必须具备如下特性：它是一棵空树或它的左右两个子树的高度差的绝对值不超过1，并且左右两个子树都是一棵平衡二叉树。也就是说该二叉树的任何一个等等子节点，其左右子树的高度都相近。
红黑树顾名思义就是节点是红色或者黑色的平衡二叉树，它通过颜色的约束来维持着二叉树的平衡。对于一棵有效的红黑树二叉树而言我们必须增加如下规则：
1、每个节点都只能是红色或者黑色
2、根节点是黑色
3、每个叶节点（NIL节点，空节点）是黑色的。
4、如果一个结点是红的，则它两个子节点都是黑的。也就是说在一条路径上不能出现相邻的两个红色结点。
5、从任一节点到其每个叶子的所有路径都包含相同数目的黑色节点。
这些约束强制了红黑树的关键性质: 从根到叶子的最长的可能路径不多于最短的可能路径的两倍长。结果是这棵树大致上是平衡的。因为操作比如插入、删除和查找某个值的最坏情况时间都要求与树的高度成比例，这个在高度上的理论上限允许红黑树在最坏情况下都是高效的，而不同于普通的二叉查找树。所以红黑树它是复杂而高效的，其检索效率O(log n)。下图为一颗典型的红黑二叉树。
TreeMap继承AbstractMap，实现NavigableMap、Cloneable、Serializable三个接口。其中AbstractMap表明TreeMap为一个Map即支持key-value的集合， NavigableMap（更多）则意味着它支持一系列的导航方法，具备针对给定搜索目标返回最接近匹配项的导航方法 。
继承体系: Map -> SortMap -> NavigbleMap
// 既然叫做SortMap, 要排序的话，当然需要一个比较器了
Comparator<? super K> comparator();
SortedMap<K,V> subMap(K fromKey, K toKey);
// 源码注释: 返回比Map中key比参数toKey小的所有kv对
SortedMap<K,V> headMap(K toKey);
// 源码注释：返回比Map中key比参数fromKey大或相等的所有kv对
SortedMap<K,V> tailMap(K fromKey);
K firstKey();
K lastKey()
接着就是 NavigableMap 定义的接口
// 返回Map中比传入参数key小的kv对中，key最大的一个kv对
Map.Entry<K,V> lowerEntry(K key);
K lowerKey(K key);
// 返回Map中比传入参数key小或相等的kv对中，key最大的一个kv对
Map.Entry<K,V> floorEntry(K key);
K floorKey(K key);
// 返回Map中比传入参数key大或相等的kv对中，key最小的一个kv对
Map.Entry<K,V> ceilingEntry(K key);
K ceilingKey(K key);
// 返回Map中比传入参数key大的kv对中，key最小的一个kv对
Map.Entry<K,V> higherEntry(K key);
K higherKey(K key);
Map.Entry<K,V> firstEntry();
Map.Entry<K,V> lastEntry();
Map.Entry<K,V> pollFirstEntry();
NavigableMap<K,V> descendingMap();
NavigableSet<K> navigableKeySet();
NavigableSet<K> descendingKeySet();
put方法：
public V put(K key, V value) {
Entry<K,V> t = root;
/**
* 如果根节点都为null，还没建立起来红黑树，我们先new Entry并赋值给root把红黑树建立起来，这个时候红
* 黑树中已经有一个节点了，同时修改操作+1。
*/
if (t == null) {
compare(key, key);
root = new Entry<>(key, value, null);
size = 1;
modCount++;
return null;
}
/**
* 如果节点不为null,定义一个cmp，这个变量用来进行二分查找时的比较；定义parent，是new Entry时必须
* 要的参数
*/
int cmp;
Entry<K,V> parent;
// cpr表示有无自己定义的排序规则，分两种情况遍历执行
Comparator<? super K> cpr = comparator;
if (cpr != null) {
/**
* 从root节点开始遍历，通过二分查找逐步向下找
* 第一次循环：从根节点开始，这个时候parent就是根节点，然后通过自定义的排序算法
* cpr.compare(key, t.key)比较传入的key和根节点的key值，如果传入的key<root.key，那么
* 继续在root的左子树中找，从root的左孩子节点（root.left）开始：如果传入的key>root.key,
* 那么继续在root的右子树中找，从root的右孩子节点（root.right）开始;如果恰好key==root.key，
* 那么直接根据root节点的value值即可。
* 后面的循环规则一样，当遍历到的当前节点作为起始节点，逐步往下找
*
* 需要注意的是：这里并没有对key是否为null进行判断，建议自己的实现Comparator时应该要考虑在内
*/
do {
parent = t;
cmp = cpr.compare(key, t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
else {
//从这里看出，当默认排序时，key值是不能为null的
if (key == null)
throw new NullPointerException();
@SuppressWarnings("unchecked")
Comparable<? super K> k = (Comparable<? super K>) key;
//这里的实现逻辑和上面一样，都是通过二分查找，就不再多说了
do {
parent = t;
cmp = k.compareTo(t.key);
if (cmp < 0)
t = t.left;
else if (cmp > 0)
t = t.right;
else
return t.setValue(value);
} while (t != null);
}
/**
* 能执行到这里，说明前面并没有找到相同的key,节点已经遍历到最后了，我们只需要new一个Entry放到
* parent下面即可，但放到左子节点上还是右子节点上，就需要按照红黑树的规则来。
*/
Entry<K,V> e = new Entry<>(key, value, parent);
if (cmp < 0)
parent.left = e;
else
parent.right = e;
/**
* 节点加进去了，并不算完，我们在前面红黑树原理章节提到过，一般情况下加入节点都会对红黑树的结构造成
* 破坏，我们需要通过一些操作来进行自动平衡处置，如【变色】【左旋】【右旋】
*/
fixAfterInsertion(e);
size++;
modCount++;
return null;
}
对于新节点的插入有如下三个关键地方：
1、插入新节点总是红色节点 。
2、如果插入节点的父节点是黑色, 能维持性质 。
3、如果插入节点的父节点是红色, 破坏了性质. 故插入算法就是通过重新着色或旋转, 来维持性质 。
左旋：
CurrentHashMap
在JDK1.7中ConcurrentHashMap采用了数组+Segment+分段锁的方式实现。
1.Segment(分段锁)
ConcurrentHashMap中的分段锁称为Segment，它即类似于HashMap的结构，即内部拥有一个Entry数组，数组中的每个元素又是一个链表,同时又是一个ReentrantLock（Segment继承了ReentrantLock）。
2.内部结构
ConcurrentHashMap使用分段锁技术，将数据分成一段一段的存储，然后给每一段数据配一把锁，当一个线程占用锁访问其中一个段数据的时候，其他段的数据也能被其他线程访问，能够实现真正的并发访问。如下图是ConcurrentHashMap的内部结构图：
从上面的结构我们可以了解到，ConcurrentHashMap定位一个元素的过程需要进行两次Hash操作。
第一次Hash定位到Segment，第二次Hash定位到元素所在的链表的头部。
3.该结构的优劣势
坏处
这一种结构的带来的副作用是Hash的过程要比普通的HashMap要长
好处
写操作的时候可以只对元素所在的Segment进行加锁即可，不会影响到其他的Segment，这样，在最理想的情况下，ConcurrentHashMap可以最高同时支持Segment数量大小的写操作（刚好这些写操作都非常平均地分布在所有的Segment上）。
put添加操作
public V put(K key, V value) {
Segment<K,V> s;
//计算hash key值
int hash = hash(key);
//通过hash key值计算出存入Segment的位置
int j = (hash >>> segmentShift) & segmentMask;
if ((s = (Segment<K,V>)UNSAFE.getObject
(segments, (j << SSHIFT) + SBASE)) == null)
//初始化Segment
s = ensureSegment(j);
//添加
return s.put(key, hash, value, false);
}
Segment:
final V put(K key, int hash, V value, boolean onlyIfAbsent) {
//segment操作加锁，使用尝试获取锁方式。如果获取失败，进入scanAndLockForPut方法
HashEntry<K,V> node = tryLock() ? null :
scanAndLockForPut(key, hash, value);
V oldValue;
try {
HashEntry<K,V>[] tab = table;
int index = (tab.length - 1) & hash;
HashEntry<K,V> first = entryAt(tab, index);
for (HashEntry<K,V> e = first;;) {
if (e != null) {
K k;
if ((k = e.key) == key ||
(e.hash == hash && key.equals(k))) {
oldValue = e.value;
if (!onlyIfAbsent) {
e.value = value;
++modCount;
}
break;
}
e = e.next;
}
else {
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;
}
上面几个方法，ConcurrentHashMap在进行put操作时，先通过key找到承载的Segment对象位置，然后竞争操作Segment的独占锁，以确保操作线程。获取锁方式很简单，就是tryLock()，如果获取锁失败，执行scanAndLockForPut方法
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; // 迭代次数
while (!tryLock()) {
HashEntry<K,V> f;
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;
}
scanAndLockForPut 实现也比较简单，循环调用tryLock，多次获取，如果循环次数retries 次数大于事先设置定好的MAX_SCAN_RETRIES，就执行lock() 方法，此方法会阻塞等待，一直到成功拿到Segment锁为止。
扩容问题
ConcurrentHashMap的扩容跟HashMap有点不同， ConcurrentHashMap的Segment槽是固定的16个，不变的
final Segment<K,V>[] segments;
而ConcurrentHashMap的扩容讲的是Segment中的HashEntry数组扩容。当HashEntry达到某个临界点后，会扩容2为之前的2倍， 原理跟HashMap扩容类似。
现在我们，在看会put方法中一个if分支
```java
if (c > threshold && tab.length < MAXIMUM_CAPACITY)
//扩容， 这是后续做解释
rehash(node);
else
rehash方法就是HashEntry扩展逻辑。当线程执行到rehash方法时，表示当前线程已经获取到到当前Segment的锁对象，这就表示rehash方法的执行是线程安全，不会存在并发问题。
ConcurrentHashMap的remove方法跟put方法操作一样，先获取segement对象后再操作，这里就不重复了。
get操作：
public V get(Object key) {
Segment<K,V> s;
HashEntry<K,V>[] tab;
//1:计算key的hash值
int h = hash(key);
//2:确定在segment的位置，得到HashEntry数组
long u = (((h >>> segmentShift) & segmentMask) << SSHIFT) + SBASE;
if ((s = (Segment<K,V>)UNSAFE.getObjectVolatile(segments, u)) != null &&
(tab = s.table) != null) {
//3:得到数据链表，迭代，查找key对应的value值
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;
}
细心的朋友会发现get方法并没有获取锁的操作，这时就得讨论下执行get操作线程安全问题。
1：一线程执行put，另一个线程执行get
ConcurrentHashMap约定新添的节点是在链表的表头， 所以如果先执行get，后执行put， get操作已经遍历到链表中间了， 不会影响put的安全执行。如果先执行put，这时候，就必须保证刚刚插入的表头节点能被读取，ConcurrentHashMap使用的UNSAFE.putOrderedObject赋值方式保证。
2：一个线程执行put，并在扩容操作期间， 另一个线程执行get
ConcurrentHashMap扩容是新创建了HashEntry数组，然后进行迁移数据，最后面将 newTable赋值给oldTable。如果 get 先执行，那么就是在oldTable 上做查询操作，不发送线程安全问题；而如果put 先执行，那么 put 操作的可见性保证就是 oldTable使用了 volatile 关键字即可。
3:一线程执行remove，另一个线程执行get
ConcurrentHashMap的删除分2种情况， 1>删除节点在链表表头。那操作节点就是HashEntry数组元素了，虽然HashEntry[] table 使用了volatile修饰， 但是， volatile并保证数据内部元素的操作可见性，所以只能使用UNSAFE 来操作元素。2>删除节点中标中间， 那么好办， 只需要保证节点中的next属性是volatile修饰即可
总结：get方法之所以不需要加锁，原因比较简单，get为只读操作，不会改动map数据结构，所以在操作过程中，只需要保证涉及读取数据的属性为线程可见即可，也即使用volatile修饰。
JDK1.8版本的CurrentHashMap的实现原理
jdk8版本的ConcurrentHashMap相对于jdk7版本，发送了很大改动，jdk8直接抛弃了Segment的设计，采用了较为轻捷的Node + CAS + Synchronized设计，保证线程安全。
看上图ConcurrentHashMap的大体结构，一个node数组，默认为16，可以自动扩展，扩展速度为0.75
private static finalint DEFAULT_CONCURRENCY_LEVEL = 16;
private static final float LOAD_FACTOR = 0.75f;
每一个节点，挂载一个链表，当链表挂载数据大于8时，链表自动转换成红黑树
ConcurrentHashMap
public class ConcurrentHashMap<K,V> extends AbstractMap<K,V>
implements ConcurrentMap<K,V>, Serializable {
transient volatile Node<K,V>[] table;
}
static class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
}
static final class TreeNode<K,V> extends Node<K,V> {
TreeNode<K,V> parent; // red-black tree links
TreeNode<K,V> left;
TreeNode<K,V> right;
TreeNode<K,V> prev; // needed to unlink next upon deletion
boolean red;
}
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;
}
Node
ConcurrentHashMap核心内部类，它包装了key-value键值对，所有插入ConcurrentHashMap的数据都包装在这里面。
TreeNode
树节点类，当数据链表长度大于8时，会转换为TreeNode。注意，此时的TreeNode并不是红黑树对象，它并不是直接转换为红黑树，而是把这些结点包装成TreeNode放在TreeBin对象中，由TreeBin完成对红黑树的包装。
TreeBin
TreeNode节点的包装对象，可以认为是红黑树对象。它代替了TreeNode的根节点，ConcurrentHashMap的node“数组”中，存放就是TreeBin对象，而不是TreeNode对象。
在ConcurrentHashMap中使用了unSafe方法，通过直接操作内存的方式来保证并发处理的安全性，使用的是硬件的安全机制。
/*
* 用来返回节点数组的指定位置的节点的原子操作
*/
@SuppressWarnings("unchecked")
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);
}
/*
* cas原子操作，在指定位置设定值
*/
static final <K,V> boolean casTabAt(Node<K,V>[] tab, int i,
Node<K,V> c, Node<K,V> v) {
return U.compareAndSwapObject(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);
}
来看下jdk8版本ConcurrentHashMap 的put操作
/*
* 当添加一对键值对的时候，首先会去判断保存这些键值对的数组是不是初始化了，
* 如果没有的话就初始化数组
* 然后通过计算hash值来确定放在数组的哪个位置
* 如果这个位置为空则直接添加，如果不为空的话，则取出这个节点来
* 如果取出来的节点的hash值是MOVED(-1)的话，则表示当前正在对这个数组进行扩容，复制到新的数组，则当前线程也去帮助复制
* 最后一种情况就是，如果这个节点，不为空，也不在扩容，则通过synchronized来加锁，进行添加操作
* 然后判断当前取出的节点位置存放的是链表还是树
* 如果是链表的话，则遍历整个链表，直到取出来的节点的key来个要放的key进行比较，如果key相等，并且key的hash值也相等的话，
* 则说明是同一个key，则覆盖掉value，否则的话则添加到链表的末尾
* 如果是树的话，则调用putTreeVal方法把这个元素添加到树中去
* 最后在添加完成之后，会判断在该节点处共有多少个节点（注意是添加前的个数），如果达到8个以上了的话，
* 则调用treeifyBin方法来尝试将处的链表转为树，或者扩容数组
*/
final V putVal(K key, V value, boolean onlyIfAbsent) {
if (key == null || value == null) throw new NullPointerException();//K,V都不能为空，否则的话跑出异常
int hash = spread(key.hashCode()); //取得key的hash值
int binCount = 0; //用来计算在这个节点总共有多少个元素，用来控制扩容或者转移为树
for (Node<K,V>[] tab = table;;) { //
Node<K,V> f; int n, i, fh;
if (tab == null || (n = tab.length) == 0)
tab = initTable(); //第一次put的时候table没有初始化，则初始化table
else if ((f = tabAt(tab, i = (n - 1) & hash)) == null) { //通过哈希计算出一个表中的位置因为n是数组的长度，所以(n-1)&hash肯定不会出现数组越界
if (casTabAt(tab, i, null, //如果这个位置没有元素的话，则通过cas的方式尝试添加，注意这个时候是没有加锁的
new Node<K,V>(hash, key, value, null))) //创建一个Node添加到数组中区，null表示的是下一个节点为空
break; // no lock when adding to empty bin
}
/*
* 如果检测到某个节点的hash值是MOVED，则表示正在进行数组扩张的数据复制阶段，
* 则当前线程也会参与去复制，通过允许多线程复制的功能，一次来减少数组的复制所带来的性能损失
*/
else if ((fh = f.hash) == MOVED)
tab = helpTransfer(tab, f);
else {
/*
* 如果在这个位置有元素的话，就采用synchronized的方式加锁，
* 如果是链表的话(hash大于0)，就对这个链表的所有元素进行遍历，
* 如果找到了key和key的hash值都一样的节点，则把它的值替换到
* 如果没找到的话，则添加在链表的最后面
* 否则，是树的话，则调用putTreeVal方法添加到树中去
*
* 在添加完之后，会对该节点上关联的的数目进行判断，
* 如果在8个以上的话，则会调用treeifyBin方法，来尝试转化为树，或者是扩容
*/
V oldVal = null;
synchronized (f) {
if (tabAt(tab, i) == f) { //再次取出要存储的位置的元素，跟前面取出来的比较
if (fh >= 0) { //取出来的元素的hash值大于0，当转换为树之后，hash值为-2
binCount = 1;
for (Node<K,V> e = f;; ++binCount) { //遍历这个链表
K ek;
if (e.hash == hash && //要存的元素的hash，key跟要存储的位置的节点的相同的时候，替换掉该节点的value即可
((ek = e.key) == key ||
(ek != null && key.equals(ek)))) {
oldVal = e.val;
if (!onlyIfAbsent) //当使用putIfAbsent的时候，只有在这个key没有设置值得时候才设置
e.val = value;
break;
}
Node<K,V> pred = e;
if ((e = e.next) == null) { //如果不是同样的hash，同样的key的时候，则判断该节点的下一个节点是否为空，
pred.next = new Node<K,V>(hash, key, //为空的话把这个要加入的节点设置为当前节点的下一个节点
value, null);
break;
}
}
}
else if (f instanceof TreeBin) { //表示已经转化成红黑树类型了
Node<K,V> p;
binCount = 2;
if ((p = ((TreeBin<K,V>)f).putTreeVal(hash, key, //调用putTreeVal方法，将该元素添加到树中去
value)) != null) {
oldVal = p.val;
if (!onlyIfAbsent)
p.val = value;
}
}
}
}
if (binCount != 0) {
if (binCount >= TREEIFY_THRESHOLD) //当在同一个节点的数目达到8个的时候，则扩张数组或将给节点的数据转为tree
treeifyBin(tab, i);
if (oldVal != null)
return oldVal;
break;
}
}
}
addCount(1L, binCount); //计数
return null;
}
从put源码可看，JDK8版本更多使用的cas编程方式控制线程安全， 必要时也会使用synchronized 代码块保证线程安全。
在put方法的详解中，我们可以看到，在同一个节点的个数超过8个的时候，会调用treeifyBin方法来看看是扩容还是转化为一棵树
同时在每次添加完元素的addCount方法中，也会判断当前数组中的元素是否达到了sizeCtl的量，如果达到了的话，则会进入transfer方法去扩容
/**
* Replaces all linked nodes in bin at given index unless table is
* too small, in which case resizes instead.
* 当数组长度小于64的时候，扩张数组长度一倍，否则的话把链表转为树
*/
private final void treeifyBin(Node<K,V>[] tab, int index) {
Node<K,V> b; int n, sc;
if (tab != null) {
System.out.println("treeifyBin方\t==>数组长："+tab.length);
if ((n = tab.length) < MIN_TREEIFY_CAPACITY) //MIN_TREEIFY_CAPACITY 64
tryPresize(n << 1); // 数组扩容
else if ((b = tabAt(tab, index)) != null && b.hash >= 0) {
synchronized (b) { //使用synchronized同步器，将该节点出的链表转为树
if (tabAt(tab, index) == b) {
TreeNode<K,V> hd = null, tl = null; //hd：树的头(head)
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) //把Node组成的链表，转化为TreeNode的链表，头结点任然放在相同的位置
hd = p; //设置head
else
tl.next = p;
tl = p;
}
setTabAt(tab, index, new TreeBin<K,V>(hd));//把TreeNode的链表放入容器TreeBin中
}
}
}
}
}
可以看到当需要扩容的时候，调用的时候tryPresize方法，看看trePresize的源码
/**
* 扩容表为指可以容纳指定个数的大小（总是2的N次方）
* 假设原来的数组长度为16，则在调用tryPresize的时候，size参数的值为16<<1(32)，此时sizeCtl的值为12
* 计算出来c的值为64,则要扩容到sizeCtl≥为止
* 第一次扩容之后 数组长：32 sizeCtl：24
* 第二次扩容之后 数组长：64 sizeCtl：48
* 第二次扩容之后 数组长：128 sizeCtl：94 --> 这个时候才会退出扩容
*/
private final void tryPresize(int size) {
/*
* MAXIMUM_CAPACITY = 1 << 30
* 如果给定的大小大于等于数组容量的一半，则直接使用最大容量，
* 否则使用tableSizeFor算出来
* 后面table一直要扩容到这个值小于等于sizeCtrl(数组长度的3/4)才退出扩容
*/
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;
// printTable(tab); 调试用的
/*
* 如果数组table还没有被初始化，则初始化一个大小为sizeCtrl和刚刚算出来的c中较大的一个大小的数组
* 初始化的时候，设置sizeCtrl为-1，初始化完成之后把sizeCtrl设置为数组长度的3/4
* 为什么要在扩张的地方来初始化数组呢？这是因为如果第一次put的时候不是put单个元素，
* 而是调用putAll方法直接put一个map的话，在putALl方法中没有调用initTable方法去初始化table，
* 而是直接调用了tryPresize方法，所以这里需要做一个是不是需要初始化table的判断
*/
if (tab == null || (n = tab.length) == 0) {
n = (sc > c) ? sc : c;
if (U.compareAndSwapInt(this, SIZECTL, sc, -1)) { //初始化tab的时候，把sizeCtl设为-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;
}
}
}
/*
* 一直扩容到的c小于等于sizeCtl或者数组长度大于最大长度的时候，则退出
* 所以在一次扩容之后，不是原来长度的两倍，而是2的n次方倍
*/
else if (c <= sc || n >= MAXIMUM_CAPACITY) {
break; //退出扩张
}
else if (tab == table) {
int rs = resizeStamp(n);
/*
* 如果正在扩容Table的话，则帮助扩容
* 否则的话，开始新的扩容
* 在transfer操作，将第一个参数的table中的元素，移动到第二个元素的table中去，
* 虽然此时第二个参数设置的是null，但是，在transfer方法中，当第二个参数为null的时候，
* 会创建一个两倍大小的table
*/
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;
/*
* transfer的线程数加一,该线程将进行transfer的帮忙
* 在transfer的时候，sc表示在transfer工作的线程数
*/
if (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))
transfer(tab, nt);
}
/*
* 没有在初始化或扩容，则开始扩容
*/
else if (U.compareAndSwapInt(this, SIZECTL, sc,
(rs << RESIZE_STAMP_SHIFT) + 2)) {
transfer(tab, null);
}
}
}
}
在tryPresize方法中，并没有加锁，允许多个线程进入，如果数组正在扩张，则当前线程也去帮助扩容。
数组扩容的主要方法就是transfer方法
/**
* Moves and/or copies the nodes in each bin to new table. See
* above for explanation.
* 把数组中的节点复制到新的数组的相同位置，或者移动到扩张部分的相同位置
* 在这里首先会计算一个步长，表示一个线程处理的数组长度，用来控制对CPU的使用，
* 每个CPU最少处理16个长度的数组元素,也就是说，如果一个数组的长度只有16，那只有一个线程会对其进行扩容的复制移动操作
* 扩容的时候会一直遍历，知道复制完所有节点，没处理一个节点的时候会在链表的头部设置一个fwd节点，这样其他线程就会跳过他，
* 复制后在新数组中的链表不是绝对的反序的
*/
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) //MIN_TRANSFER_STRIDE 用来控制不要占用太多CPU
stride = MIN_TRANSFER_STRIDE; // subdivide range //MIN_TRANSFER_STRIDE=16
/*
* 如果复制的目标nextTab为null的话，则初始化一个table两倍长的nextTab
* 此时nextTable被设置值了(在初始情况下是为null的)
* 因为如果有一个线程开始了表的扩张的时候，其他线程也会进来帮忙扩张，
* 而只是第一个开始扩张的线程需要初始化下目标数组
*/
if (nextTab == null) { // initiating
try {
@SuppressWarnings("unchecked")
Node<K,V>[] nt = (Node<K,V>[])new Node<?,?>[n << 1];
nextTab = nt;
} catch (Throwable ex) { // try to cope with OOME
sizeCtl = Integer.MAX_VALUE;
return;
}
nextTable = nextTab;
transferIndex = n;
}
int nextn = nextTab.length;
/*
* 创建一个fwd节点，这个是用来控制并发的，当一个节点为空或已经被转移之后，就设置为fwd节点
* 这是一个空的标志节点
*/
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 (U.compareAndSwapInt
(this, TRANSFERINDEX, nextIndex,
nextBound = (nextIndex > stride ?
nextIndex - stride : 0))) {
bound = nextBound;
i = nextIndex - 1;
advance = false;
}
}
if (i < 0 || i >= n || i + n >= nextn) {
int sc;
if (finishing) { //已经完成转移
nextTable = null;
table = nextTab;
sizeCtl = (n << 1) - (n >>> 1); //设置sizeCtl为扩容后的0.75
return;
}
if (U.compareAndSwapInt(this, SIZECTL, sc = sizeCtl, sc - 1)) {
if ((sc - 2) != resizeStamp(n) << RESIZE_STAMP_SHIFT) {
return;
}
finishing = advance = true;
i = n; // recheck before commit
}
}
else if ((f = tabAt(tab, i)) == null) //数组中把null的元素设置为ForwardingNode节点(hash值为MOVED[-1])
advance = casTabAt(tab, i, null, fwd);
else if ((fh = f.hash) == MOVED)
advance = true; // already processed
else {
synchronized (f) { //加锁操作
if (tabAt(tab, i) == f) {
Node<K,V> ln, hn;
if (fh >= 0) { //该节点的hash值大于等于0，说明是一个Node节点
/*
* 因为n的值为数组的长度，且是power(2,x)的，所以，在&操作的结果只可能是0或者n
* 根据这个规则
* 0--> 放在新表的相同位置
* n--> 放在新表的（n+原来位置）
*/
int runBit = fh & n;
Node<K,V> lastRun = f;
/*
* lastRun 表示的是需要复制的最后一个节点
* 每当新节点的hash&n -> b 发生变化的时候，就把runBit设置为这个结果b
* 这样for循环之后，runBit的值就是最后不变的hash&n的值
* 而lastRun的值就是最后一次导致hash&n 发生变化的节点(假设为p节点)
* 为什么要这么做呢？因为p节点后面的节点的hash&n 值跟p节点是一样的，
* 所以在复制到新的table的时候，它肯定还是跟p节点在同一个位置
* 在复制完p节点之后，p节点的next节点还是指向它原来的节点，就不需要进行复制了，自己就被带过去了
* 这也就导致了一个问题就是复制后的链表的顺序并不一定是原来的倒序
*/
for (Node<K,V> p = f.next; p != null; p = p.next) {
int b = p.hash & n; //n的值为扩张前的数组的长度
if (b != runBit) {
runBit = b;
lastRun = p;
}
}
if (runBit == 0) {
ln = lastRun;
hn = null;
}
else {
hn = lastRun;
ln = null;
}
/*
* 构造两个链表，顺序大部分和原来是反的
* 分别放到原来的位置和新增加的长度的相同位置(i/n+i)
*/
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)
/*
* 假设runBit的值为0，
* 则第一次进入这个设置的时候相当于把旧的序列的最后一次发生hash变化的节点(该节点后面可能还有hash计算后同为0的节点)设置到旧的table的第一个hash计算后为0的节点下一个节点
* 并且把自己返回，然后在下次进来的时候把它自己设置为后面节点的下一个节点
*/
ln = new Node<K,V>(ph, pk, pv, ln);
else
/*
* 假设runBit的值不为0，
* 则第一次进入这个设置的时候相当于把旧的序列的最后一次发生hash变化的节点(该节点后面可能还有hash计算后同不为0的节点)设置到旧的table的第一个hash计算后不为0的节点下一个节点
* 并且把自己返回，然后在下次进来的时候把它自己设置为后面节点的下一个节点
*/
hn = new Node<K,V>(ph, pk, pv, hn);
}
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
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;
else
loTail.next = p;
loTail = p;
++lc;
}
else {
if ((p.prev = hiTail) == null)
hi = p;
else
hiTail.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;
setTabAt(nextTab, i, ln);
setTabAt(nextTab, i + n, hn);
setTabAt(tab, i, fwd);
advance = true;
}
}
}
}
}
}
到这里，ConcurrentHashMap的put操作和扩容都介绍的差不多了，
下面的两点一定要注意：
1·复制之后的新链表不是旧链表的绝对倒序。
2·在扩容的时候每个线程都有处理的步长，最少为16，在这个步长范围内的数组节点只有自己一个线程来处理
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 &&
//获取table[i] 的node元素
(e = tabAt(tab, (n - 1) & h)) != null) {
if ((eh = e.hash) == h) {
if ((ek = e.key) == key || (ek != null && key.equals(ek)))
return e.val;
}
else if (eh < 0)
return (p = e.find(h, key)) != null ? p.val : null;
while ((e = e.next) != null) {
if (e.hash == h &&
((ek = e.key) == key || (ek != null && key.equals(ek))))
return e.val;
}
}
return null;
}
//确保多线程可见，并且保证获取到是内存中最新的table[i] 元素值
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);
}
get源码也没有加锁操作，操作原理跟jdk1.7版本一样，这里就不累赘了。
场景1：多线程复合操作时是否能保证线程安全
答案是不能，原因： ConcurrentHashMap 使用锁分离(jdk7)/cas(jdk8)方式保证并发环境下，添加/删除操作安全，但这进针对的是单个put 或者 remove方法，如果多个方法配合复合使用，依然需要额外加锁。
场景2：多线程同时添加相同hash 码值时转换成红黑树时，是否存在并发问题
答案是可以保证线程安全，原因：ConcurrentHashMap 链表转换成红黑树时，对转换方法做加锁防护了
resize() 方法
JDK1.7中的实现：
跟HashMap的 resize() 没太大区别，都是在 put() 元素时去做的扩容，所以在1.7中的实现是获得了锁之后，在单线程中去做扩容（1.new个2倍数组 2.遍历old数组节点搬去新数组）。
JDK1.8中的实现：
jdk1.8的扩容支持并发迁移节点，从old数组的尾部开始，如果该桶被其他线程处理过了，就创建一个 ForwardingNode 放到该桶的首节点，hash值为-1，其他线程判断hash值为-1后就知道该桶被处理过了。
计算size
JDK1.7中的实现：
static final class Segment<K,V> extends ReentrantLock implements Serializable {
private static final long serialVersionUID = 2249069246763182397L;
// 最大尝试获取锁次数，tryLock可能会阻塞，准备锁住segment操作获取锁。
在多处理器中，用一个有界的尝试次数，保证在定位node的时候，可以从缓存直接获取。
static final int MAX_SCAN_RETRIES =
Runtime.getRuntime().availableProcessors() > 1 ? 64 : 1;
//segment内部的Hash table，访问HashEntry，通过具有volatile的entryAt/setEntryAt方法
transient volatile HashEntry<K,V>[] table;
//segment的table中HashEntry的数量，只有在lock或其他保证可见性的volatile reads中，才可以访问count
transient int count;
//在segment上所有的修改操作数。尽管可能会溢出，但它为isEmpty和size方法，
提供了有效准确稳定的检查或校验。只有在lock或其他保证可见性的volatile reads
中，才可以访问
transient int modCount;
transient int threshold;
final float loadFactor;
Segment(float lf, int threshold, HashEntry<K,V>[] tab) {
this.loadFactor = lf;
this.threshold = threshold;
this.table = tab;
}
}
先采用不加锁的方式，计算两次，如果两次结果一样，说明是正确的，返回。
如果两次结果不一样，则把所有 segment 锁住，重新计算所有 segment的 Count 的和
JDK1.8中的实现：
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
sumCount有两个重要的属性baseCount和counterCells,如果counterCells不为空，那么总共的大小就是baseCount与遍历counterCells的value值累加获得的。
//先利用sumCount()计算，然后如果值超过int的最大值，就返回int的最大值。
//但是有时size就会超过最大值，这时最好用mappingCount方法,返回的一个估值
public int size() {
long n = sumCount();
return ((n < 0L) ? 0 :
(n > (long)Integer.MAX_VALUE) ? Integer.MAX_VALUE :
(int)n);
}
//注：mappingcount值是返回的一个估值，不是精准值
public long mappingCount() {
long n = sumCount();
return (n < 0L) ? 0L : n; // ignore transient negative values
}
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)
sum += a.value;
}
}
return sum;
}
baseCount是从哪里来的？
//当没有线程争用时，使用这个变量计数
private transient volatile long baseCount;
一个volatile变量，在addCount方法会使用它，而addCount方法在put结束后会调用,在put操作结束后，更新计数。
if ((as = counterCells) != null ||
!U.compareAndSwapLong(this, BASECOUNT, b = baseCount, s = b + x))
static final class CounterCell {
volatile long value;
CounterCell(long x) { value = x; }
}
在并发情况下，如果CAS修改baseCount失败后，就会使用到CounterCell类，会创建一个对象，通常对象的volatile的value属性是1。
if (as == null || (m = as.length - 1) < 0 ||
(a = as[ThreadLocalRandom.getProbe() & m]) == null ||
!(uncontended =
U.compareAndSwapLong(a, CELLVALUE, v = a.value, v + x))) {
fullAddCount(x, uncontended);
return;
}
如果上面CAS操作也失败了，在fullAddCount方法中，会继续死循环操作，直到成功。那么最终那个没有被baseCount记录到的数据就被CounterCell记录了，结果也是返回俩个数据相加的和。
ConcurrentHashMap的同步机制
前面分析了下ConcurrentHashMap的源码，那么，对于一个映射集合来说，ConcurrentHashMap是如果来做到并发安全，又是如何做到高效的并发的呢？
首先是读操作，从源码中可以看出来，在get操作中，根本没有使用同步机制，也没有使用unsafe方法，所以读操作是支持并发操作的。
那么写操作呢？
分析这个之前，先看看什么情况下会引起数组的扩容，扩容是通过transfer方法来进行的。而调用transfer方法的只有trePresize、helpTransfer和addCount三个方法。
这三个方法又是分别在什么情况下进行调用的呢？
·tryPresize是在treeIfybin和putAll方法中调用，treeIfybin主要是在put添加元素完之后，判断该数组节点相关元素是不是已经超过8个的时候，如果超过则会调用这个方法来扩容数组或者把链表转为树。
·helpTransfer是在当一个线程要对table中元素进行操作的时候，如果检测到节点的HASH值为MOVED的时候，就会调用helpTransfer方法，在helpTransfer中再调用transfer方法来帮助完成数组的扩容
·addCount是在当对数组进行操作，使得数组中存储的元素个数发生了变化的时候会调用的方法。
所以引起数组扩容的情况如下：
·
只有在往map中添加元素的时候，在某一个节点的数目已经超过了8个，同时数组的长度又小于64的时候，才会触发数组的扩容。
·当数组中元素达到了sizeCtl的数量的时候，则会调用transfer方法来进行扩容
那么在扩容的时候，可以不可以对数组进行读写操作呢？
事实上是可以的。当在进行数组扩容的时候，如果当前节点还没有被处理（也就是说还没有设置为fwd节点），那就可以进行设置操作。
如果该节点已经被处理了，则当前线程也会加入到扩容的操作中去。
那么，多个线程又是如何同步处理的呢？
在ConcurrentHashMap中，同步处理主要是通过Synchronized和unsafe两种方式来完成的。
·在取得sizeCtl、某个位置的Node的时候，使用的都是unsafe的方法，来达到并发安全的目的
·当需要在某个位置设置节点的时候，则会通过Synchronized的同步机制来锁定该位置的节点。
·在数组扩容的时候，则通过处理的步长和fwd节点来达到并发安全的目的，通过设置hash值为MOVED
·当把某个位置的节点复制到扩张后的table的时候，也通过Synchronized的同步机制来保证现程安全
HashTable
HashTable和HashMap的实现原理几乎一样，差别无非是
HashTable不允许key和value为null
HashTable是线程安全的
但是HashTable线程安全的策略实现代价却太大了，简单粗暴，get/put所有相关操作都是synchronized的，这相当于给整个哈希表加了一把大锁。
多线程访问时候，只要有一个线程访问或操作该对象，那其他线程只能阻塞，相当于将所有的操作串行化，在竞争激烈的并发场景中性能就会非常差。