终于，我读懂了所有Java集合——map篇(多线程)
多線程環境下的問題
1.8中hashmap的確不會因為多線程put導致死循環（1.7代碼中會這樣子），但是依然有其他的弊端，比如數據丟失等等。因此多線程情況下還是建議使用ConcurrentHashMap。
?
數據丟失：當多線程put的時候，當index相同而又同時達到鏈表的末尾時，另一個線程put的數據會把之前線程put的數據覆蓋掉，就會產生數據丟失。
if ((e = p.next) == null) {p.next = newNode(hash, key, value, null);}Hashtable
Hashtable同樣是基于哈希表實現的，同樣每個元素是一個key-value對，其內部也是通過單鏈表解決沖突問題，容量不足（超過了閾值）時，同樣會自動增長。
Hashtable也是JDK1.0引入的類，是線程安全的，能用于多線程環境中。
Hashtable同樣實現了Serializable接口，它支持序列化，實現了Cloneable接口，能被克隆。
Hashtable 的容量增加邏輯是乘2+1，保證奇數。
在應用數據分布在等差數據集合(如偶數)上時，如果公差與桶容量有公約數n，則至少有(n-1)/n數量的桶是利用不到的。
hash to index
int hash = key.hashCode(); int index = (hash & 0x7FFFFFFF) % tab.length;取與之后一定是一個非負數
0x7FFFFFFF is 0111 1111 1111 1111 1111 1111 1111 1111 : all 1 except the sign bit.
?(hash & 0x7FFFFFFF) will result in a positive integer.
?(hash & 0x7FFFFFFF) % tab.length will be in the range of the tab length.
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的訪問。
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);}}節點類型
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
重要屬性
?
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 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); }初始化
對于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 (U.compareAndSwapInt(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位中，
成員變量
@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中的位置。
1）如果這個位置是空的，那么直接放入，而且不需要加鎖操作。
2）如果這個位置存在結點，說明發生了hash碰撞，首先判斷這個節點的類型。
a）如果是MOVED節點，則表示正在擴容，幫助進行擴容
b）如果是鏈表節點(hash >=0）,則得到的結點就是hash值相同的節點組成的鏈表的頭節點。需要依次向后遍歷確定這個新加入的值所在位置。如果遇到hash值與key值都與新加入節點是一致的情況，則只需要更新value值即可。否則依次向后遍歷，直到鏈表尾插入這個結點。 如果加入這個節點以后鏈表長度大于8，就把這個鏈表轉換成紅黑樹。
c）如果這個節點的類型已經是樹節點的話，直接調用樹節點的插入方法進行插入新的值。
3）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
（有鎖，數組較小則擴容，較大則轉為紅黑樹
擴容
tryPresize
tryPresize在putAll以及treeifyBin中調用
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 ||!U.compareAndSwapLong(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 =U.compareAndSwapLong(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 (U.compareAndSwapInt(this, SIZECTL, sc, sc + 1))transfer(tab, nt);}// 當前線程是唯一的或是第一個發起擴容的線程? 此時nextTable=null else if (U.compareAndSwapInt(this, SIZECTL, sc,(rs << RESIZE_STAMP_SHIFT) + 2))// 發起擴容transfer(tab, null);s = sumCount();}} }?
transfer
當table容量不足的時候，即table的元素數量達到容量閾值sizeCtl，需要對table進行擴容。 整個擴容分為兩部分：
1）構建一個nextTable，大小為table的兩倍。
2）把table的數據復制到nextTable中。
這兩個過程在單線程下實現很簡單，但是ConcurrentHashMap是支持并發插入的，擴容操作自然也會有并發的出現，這種情況下，第二步可以支持節點的并發復制，這樣性能自然提升不少，但實現的復雜度也上升了一個臺階。
先看第一步，構建nextTable，毫無疑問，這個過程只能有單個線程進行nextTable的初始化。
通過Unsafe.compareAndSwapInt修改sizeCtl值，保證只有一個線程能夠初始化nextTable，擴容后的數組長度為原來的兩倍。
節點從table移動到nextTable，大體思想是遍歷、復制的過程。
1）首先根據運算得到需要遍歷的次數i，然后利用tabAt方法獲得i位置的元素f，初始化一個ForwardingNode實例fwd。
2）如果f==null，則在table中的i位置放入fwd，這個過程是采用
Unsafe.compareAndSwapObjectf方法實現的，很巧妙的實現了節點的并發移動。
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節點，以便要其他線程可以看到該節點已經處理過了，如此交叉進行，高效而又安全。
?
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（無鎖）
remove（有鎖）
分段鎖實現
采用 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個節點即可。
這基本上就是跳表的核心思想，其實也是一種通過“空間來換取時間”的一個算法，通過在每個節點中增加了向前的指針，從而提升查找的效率。
Map實現類之間的區別
HashMap與ConcurrentHashMap區別
1）前者允許key或value為null，后者不允許
2）前者不是線程安全的，后者是
HashMap、TreeMap與LinkedHashMap區別
1）HashMap遍歷時，取得數據的順序是完全隨機的；
TreeMap可以按照自然順序或Comparator排序；
LinkedHashMap可以按照插入順序或訪問順序排序，且get的效率（O(1)）比TreeMap（O(logn)）更高。
2）HashMap底層基于哈希表，數組+鏈表/紅黑樹；
TreeMap底層基于紅黑樹
LinkedHashMap底層基于HashMap與環形雙向鏈表
3）就get和put效率而言，HashMap是最高的，LinkedHashMap次之，TreeMap最次。
HashMap與Hashtable區別
1. 擴容策略：Hashtable在不指定容量的情況下的默認容量為11，而HashMap為16，Hashtable不要求底層數組的容量一定要為2的整數次冪（*2+1），而HashMap則要求一定為2的整數次冪（*2）。
2. 允許null：Hashtable中key和value都不允許為null，而HashMap中key和value都允許為null（key只能有一個為null，而value則可以有多個為null）。
3. 線程安全：前者不是線程安全的，后者是；
ConcurrentHashMap、Collections.synchronizedMap與Hashtable的異同
它們都是同步Map，但三者實現同步的機制不同；后兩者都是簡單地在方法上加synchronized實現的，鎖的粒度較大；前者是基于CAS和synchronized實現的，鎖的粒度較小，大部分都是lock-free無鎖實現同步的。
ConcurrentHashMap還提供了putIfAbsent同步方法。
總結
以上是生活随笔為你收集整理的终于，我读懂了所有Java集合——map篇(多线程)的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： 橙白oj18训练作业2-题解、代码
- 下一篇： leetcode136 只出现一次的数字