本文章根據(jù)多篇文章整理和自己修改而成黍翎，很多已經(jīng)無法找到出處面徽，如果出現(xiàn)相同的信息，請見諒匣掸！
一趟紊、概覽
容器主要包括 Collection 和 Map 兩種，Collection 存儲著對象的集合碰酝，而 Map 存儲著鍵值對（兩個對象）的映射表霎匈。
Collection
1. Set
-
HashSet：
底層數(shù)據(jù)結(jié)構(gòu)是哈希表。(無序,唯一) 如何來保證元素唯一性? 依賴兩個方法：hashCode()和equals()
HashSet底層數(shù)據(jù)結(jié)構(gòu)采用哈希表實現(xiàn)送爸，元素?zé)o序且唯一铛嘱，線程不安全，效率高袭厂，可以存儲null元素墨吓，元素的唯一性是靠所存儲元素類型是否重寫hashCode()和equals()方法來保證的，如果沒有重寫這兩個方法纹磺，則無法保證元素的唯一性帖烘。
哈希表具體實現(xiàn)唯一性的比較過程:
1.哈希表的做法其實很簡單，就是把Key通過一個固定的算法函數(shù)既所謂的哈希函數(shù)轉(zhuǎn)換成一個int類型橄杨，然后就將該數(shù)字對數(shù)組長度進行取余秘症，取余結(jié)果就當(dāng)作數(shù)組的下標(biāo)照卦，將value存儲在以該數(shù)字為下標(biāo)的數(shù)組空間里，而當(dāng)使用哈希表進行查詢的時候乡摹，就是再次使用哈希函數(shù)將key轉(zhuǎn)換為對應(yīng)的數(shù)組下標(biāo)役耕，并定位到該空間獲取value，如此一來聪廉，就可以充分利用到數(shù)組的定位性能進行數(shù)據(jù)定位蹄葱。(但是hashCode值相同并不一定就是同一個值)
2.在存儲的適合發(fā)現(xiàn)hashCode值相同，再比較equals方法锄列。
3.equals相同，對象相同惯悠。（則無需儲存）
-
TreeSet：
底層數(shù)據(jù)結(jié)構(gòu)是紅黑樹邻邮。(唯一，有序)
如何保證元素排序的呢? 自然排序 比較器排序
如何保證元素唯一性的呢? 根據(jù)比較的返回值是否是0來決定
TreeSet底層數(shù)據(jù)結(jié)構(gòu)采用紅黑樹來實現(xiàn)克婶，元素唯一且已經(jīng)排好序筒严；唯一性同樣需要重寫hashCode和equals()方法，二叉樹結(jié)構(gòu)保證了元素的有序性情萤。根據(jù)構(gòu)造方法不同鸭蛙，分為自然排序（無參構(gòu)造）和比較器排序（有參構(gòu)造），自然排序要求元素必須實現(xiàn)Compareable接口筋岛，并重寫里面的compareTo()方法娶视，元素通過比較返回的int值來判斷排序序列，返回0說明兩個對象相同睁宰，不需要存儲肪获；比較器排需要在TreeSet初始化是時候傳入一個實現(xiàn)Comparator接口的比較器對象，或者采用匿名內(nèi)部類的方式new一個Comparator對象柒傻，重寫里面的compare()方法孝赫；
-
LinkedHashSet：
底層數(shù)據(jù)結(jié)構(gòu)是鏈表和哈希表。(FIFO插入有序,唯一) 1.由鏈表保證元素有序 2.由哈希表保證元素唯一
LinkedHashSet底層數(shù)據(jù)結(jié)構(gòu)采用鏈表和哈希表共同實現(xiàn)红符，鏈表保證了元素的順序與存儲順序一致青柄，哈希表保證了元素的唯一性。線程不安全预侯，效率高致开。
適用場景分析:
HashSet是基于Hash算法實現(xiàn)的，其性能通常都優(yōu)于TreeSet萎馅。為快速查找而設(shè)計的Set喇喉，我們通常都應(yīng)該使用HashSet，在我們需要排序的功能時校坑，我們才使用TreeSet拣技。
2. List
ArrayList: 優(yōu)點: 底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組千诬，查詢快，增刪慢膏斤。 缺點: 線程不安全徐绑，效率高
LinkedList: 優(yōu)點: 底層數(shù)據(jù)結(jié)構(gòu)是鏈表，查詢慢莫辨，增刪快傲茄。 缺點: 線程不安全，效率高
Vector: 優(yōu)點: 底層數(shù)據(jù)結(jié)構(gòu)是數(shù)組沮榜，查詢快盘榨，增刪慢。 缺點: 線程安全蟆融，效率低
3. Queue(JUC并發(fā)會有講解)
-
LinkedList：
可以用它來實現(xiàn)雙向隊列草巡。
-
PriorityQueue：
基于堆結(jié)構(gòu)實現(xiàn)，可以用它來實現(xiàn)優(yōu)先隊列型酥。
怎么選擇：
Map接口:
1. HashMap
Map 主要用于存儲鍵(key)值(value)對山憨，根據(jù)鍵得到值，因此鍵不允許重復(fù),但允許值重復(fù)弥喉。 HashMap 是一個最常用的Map,它根據(jù)鍵的HashCode 值存儲數(shù)據(jù),根據(jù)鍵可以直接獲取它的值郁竟，具有很快的訪問速度。 HashMap最多只允許一條記錄的鍵為Null;允許多條記錄的值為 Null; HashMap不支持線程的同步由境，即任一時刻可以有多個線程同時寫HashMap;可能會導(dǎo)致數(shù)據(jù)的不一致棚亩。如果需要同步，可以用 Collections的synchronizedMap方法使HashMap具有同步的能力虏杰，或者使用ConcurrentHashMap蔑舞。 HashMap基于哈希表結(jié)構(gòu)實現(xiàn)的 ，當(dāng)一個對象被當(dāng)作鍵時嘹屯，必須重寫hasCode和equals方法攻询。
2. LinkedHashMap
LinkedHashMap繼承自HashMap，它主要是用鏈表實現(xiàn)來擴展HashMap類州弟，HashMap中條目是沒有順序的钧栖，但是在LinkedHashMap中元素既可以按照它們插入圖的順序排序，也可以按它們最后一次被訪問的順序排序婆翔。
3. TreeMap
TreeMap基于紅黑樹數(shù)據(jù)結(jié)構(gòu)的實現(xiàn)拯杠，鍵值可以使用Comparable或Comparator接口來排序。TreeMap繼承自AbstractMap啃奴，同時實現(xiàn)了接口NavigableMap潭陪，而接口NavigableMap則繼承自SortedMap。SortedMap是Map的子接口，使用它可以確保圖中的條目是排好序的依溯。
在實際使用中老厌，如果更新圖時不需要保持圖中元素的順序，就使用HashMap黎炉，如果需要保持圖中元素的插入順序或者訪問順序枝秤，就使用LinkedHashMap，如果需要使圖按照鍵值排序，就使用TreeMap。
4. Hashtable
Hashtable和前面介紹的HashMap很類似傅瞻，它也是一個散列表，存儲的內(nèi)容是鍵值對映射腊瑟，不同之處在于，Hashtable是繼承自Dictionary的，Hashtable中的函數(shù)都是同步的，這意味著它也是線程安全的沐序，另外，Hashtable中key和value都不可以為null忿峻。
遍歷map實例
public class T {
public static void main(String[] args) {
Map<String, String> map = new HashMap<String, String>();
map.put("first", "linlin");
map.put("second", "好好學(xué)java");
map.put("third", "sihai");
map.put("first", "sihai2");
?
?
// 第一種：通過Map.keySet遍歷key和value
for (String key : map.keySet()) {
System.out.println(key + ":" + map.get(key));
}
?
System.out.println("==============================================");
?
// 第二種：通過Map.entrySet使用iterator遍歷key和value
Iterator<Map.Entry<String, String>> iterator = map.entrySet().iterator();
while (iterator.hasNext()){
Map.Entry<String, String> entry = iterator.next();
System.out.println(entry.getKey() + ":" + entry.getValue());
}
?
System.out.println("==============================================");
?
// 第三種：通過Map.entrySet遍歷key和value
for ( Map.Entry<String, String> entry: map.entrySet()) {
System.out.println(entry.getKey() + ":" + entry.getValue());
}
?
System.out.println("==============================================");
?
// 第四種：通過Map.values()遍歷所有的value，但是不能遍歷鍵key
for (String value: map.values()) {
System.out.println(value);
}
?
System.out.println("==============================================");
?
// 第五種辕羽，使用Lambda需要jdk1.8以后(推薦)
map.forEach((m,k)-> System.out.println(m + ":" + k));
}
}
總結(jié)圖解：
二逛尚、源碼分析
ArrayList
1. 概覽
因為 ArrayList 是基于數(shù)組實現(xiàn)的，所以支持快速隨機訪問刁愿。RandomAccess 接口標(biāo)識著該類支持快速隨機訪問绰寞。
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
數(shù)組的默認大小為 10。
private static final int DEFAULT_CAPACITY = 10;
2. 擴容
添加元素時使用 ensureCapacityInternal() 方法來保證容量足夠铣口，如果不夠時滤钱，需要使用 grow() 方法進行擴容，新容量的大小為 oldCapacity + (oldCapacity >> 1)脑题，也就是舊容量的 1.5 倍件缸。
擴容操作需要調(diào)用 Arrays.copyOf() 把原數(shù)組整個復(fù)制到新數(shù)組中，這個操作代價很高叔遂，因此最好在創(chuàng)建 ArrayList 對象時就指定大概的容量大小他炊，減少擴容操作的次數(shù)。
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!
elementData[size++] = e;
return true;
}
?
private void ensureCapacityInternal(int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
}
ensureExplicitCapacity(minCapacity);
}
?
private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
?
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
3. 序列化
ArrayList 基于數(shù)組實現(xiàn)已艰，并且具有動態(tài)擴容特性痊末，因此保存元素的數(shù)組不一定都會被使用，那么就沒必要全部進行序列化哩掺。
保存元素的數(shù)組 elementData 使用 transient 修飾凿叠，該關(guān)鍵字聲明數(shù)組默認不會被序列化。
transient Object[] elementData; // non-private to simplify nested class access
ArrayList 實現(xiàn)了 writeObject() 和 readObject() 來控制只序列化數(shù)組中有元素填充那部分內(nèi)容。
private void readObject(java.io.ObjectInputStream s)
throws java.io.IOException, ClassNotFoundException {
elementData = EMPTY_ELEMENTDATA;
?
// Read in size, and any hidden stuff
s.defaultReadObject();
?
// Read in capacity
s.readInt(); // ignored
?
if (size > 0) {
// be like clone(), allocate array based upon size not capacity
ensureCapacityInternal(size);
?
Object[] a = elementData;
// Read in all elements in the proper order.
for (int i=0; i<size; i++) {
a[i] = s.readObject();
}
}
}
private void writeObject(java.io.ObjectOutputStream s)
throws java.io.IOException{
// Write out element count, and any hidden stuff
int expectedModCount = modCount;
s.defaultWriteObject();
?
// Write out size as capacity for behavioural compatibility with clone()
s.writeInt(size);
?
// Write out all elements in the proper order.
for (int i=0; i<size; i++) {
s.writeObject(elementData[i]);
}
?
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
序列化時需要使用 ObjectOutputStream 的 writeObject() 將對象轉(zhuǎn)換為字節(jié)流并輸出盒件。而 writeObject() 方法在傳入的對象存在 writeObject() 的時候會去反射調(diào)用該對象的 writeObject() 來實現(xiàn)序列化蹬碧。反序列化使用的是 ObjectInputStream 的 readObject() 方法，原理類似履恩。
ArrayList list = new ArrayList();
ObjectOutputStream oos = new ObjectOutputStream(new FileOutputStream(file));
oos.writeObject(list);
4. Fail-Fast
modCount 用來記錄 ArrayList 結(jié)構(gòu)發(fā)生變化的次數(shù)锰茉。結(jié)構(gòu)發(fā)生變化是指添加或者刪除至少一個元素的所有操作，或者是調(diào)整內(nèi)部數(shù)組的大小切心，僅僅只是設(shè)置元素的值不算結(jié)構(gòu)發(fā)生變化飒筑。
在進行序列化或者迭代等操作時，需要比較操作前后 modCount 是否改變绽昏，如果改變了需要拋出 ConcurrentModificationException协屡。(在并發(fā)的情況下就可能會發(fā)生)
Vector
1. 同步
它的實現(xiàn)與 ArrayList 類似，但是使用了 synchronized 進行同步全谤。
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}
2. 擴容
Vector 的構(gòu)造函數(shù)可以傳入 capacityIncrement 參數(shù)肤晓，它的作用是在擴容時使容量 capacity 增長 capacityIncrement。如果這個參數(shù)的值小于等于 0认然，擴容時每次都令 capacity 為原來的兩倍补憾。
public Vector(int initialCapacity, int capacityIncrement) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+
initialCapacity);
this.elementData = new Object[initialCapacity];
this.capacityIncrement = capacityIncrement;
}
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
capacityIncrement : oldCapacity);
if (newCapacity - minCapacity < 0)
newCapacity = minCapacity;
if (newCapacity - MAX_ARRAY_SIZE > 0)
newCapacity = hugeCapacity(minCapacity);
elementData = Arrays.copyOf(elementData, newCapacity);
}
調(diào)用沒有 capacityIncrement 的構(gòu)造函數(shù)時，capacityIncrement 值被設(shè)置為 0卷员，也就是說默認情況下 Vector 每次擴容時容量都會翻倍盈匾。
public Vector(int initialCapacity) {
this(initialCapacity, 0);
}
?
public Vector() {
this(10);
}
3. 與 ArrayList 的比較
Vector 是同步的，因此開銷就比 ArrayList 要大毕骡，訪問速度更慢削饵。最好使用 ArrayList 而不是 Vector，因為同步操作完全可以由程序員自己來控制未巫；
Vector 每次擴容請求其大小的 2 倍（也可以通過構(gòu)造函數(shù)設(shè)置增長的容量）窿撬，而 ArrayList 是 1.5 倍。
4. 替代方案
可以使用 Collections.synchronizedList(); 得到一個線程安全的 ArrayList叙凡。
List<String> list = new ArrayList<>();
List<String> synList = Collections.synchronizedList(list);
也可以使用 concurrent 并發(fā)包下的 CopyOnWriteArrayList 類劈伴。
List<String> list = new CopyOnWriteArrayList<>();</pre>
三、重點問題重點分析:
一）說說List,Set,Map三者的區(qū)別握爷？
List(對付順序的好幫手)： List接口存儲一組不唯一（可以有多個元素引用相同的對象）宰啦，有序的對象
Set(注重獨一無二的性質(zhì)): 不允許重復(fù)的集合。不會有多個元素引用相同的對象饼拍。
Map(用Key來搜索的專家): 使用鍵值對存儲赡模。Map會維護與Key有關(guān)聯(lián)的值。兩個Key可以引用相同的對象师抄，但Key不能重復(fù)漓柑，典型的Key是String類型，但也可以是任何對象。
二）Arraylist 與 LinkedList 區(qū)別?
是否保證線程安全：
ArrayList和LinkedList都是不同步的辆布，也就是不保證線程安全瞬矩；底層數(shù)據(jù)結(jié)構(gòu)：
Arraylist底層使用的是Object數(shù)組；LinkedList底層使用的是 雙向鏈表 數(shù)據(jù)結(jié)構(gòu)（JDK1.6之前為循環(huán)鏈表锋玲，JDK1.7取消了循環(huán)景用。注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別，下面有介紹到２氧濉）插入和刪除是否受元素位置的影響： ①
ArrayList采用數(shù)組存儲伞插，所以插入和刪除元素的時間復(fù)雜度受元素位置的影響。 比如：執(zhí)行add(E e)方法的時候盾碗，ArrayList會默認在將指定的元素追加到此列表的末尾媚污，這種情況時間復(fù)雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話（add(int index, E element)）時間復(fù)雜度就為 O(n-i)廷雅。因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執(zhí)行向后位/向前移一位的操作耗美。 ②LinkedList采用鏈表存儲，所以插入航缀，刪除元素時間復(fù)雜度不受元素位置的影響商架，都是近似 O（1）而數(shù)組為近似 O（n）。是否支持快速隨機訪問：
LinkedList不支持高效的隨機元素訪問芥玉，而ArrayList支持蛇摸。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應(yīng)于get(int index)方法)飞傀。內(nèi)存空間占用： ArrayList的空間浪費主要體現(xiàn)在在list列表的結(jié)尾會預(yù)留一定的容量空間皇型，而LinkedList的空間花費則體現(xiàn)在它的每一個元素都需要消耗比ArrayList更多的空間（因為要存放直接后繼和直接前驅(qū)以及數(shù)據(jù)）诬烹。
ArrayList是實現(xiàn)了基于動態(tài)數(shù)組的數(shù)據(jù)結(jié)構(gòu)砸烦，LinkedList基于鏈表的數(shù)據(jù)結(jié)構(gòu)。
對于隨機訪問get和set绞吁，ArrayList覺得優(yōu)于LinkedList幢痘，因為LinkedList要移動指針。
對于新增和刪除操作add和remove家破，LinedList比較占優(yōu)勢颜说，因為ArrayList要移動數(shù)據(jù)。盡量避免同時遍歷和刪除集合汰聋。因為這會改變集合的大忻欧唷；
三）ArrayList 與 Vector 區(qū)別呢?為什么要用Arraylist取代Vector呢烹困？
Vector類的所有方法都是同步的玄妈。可以由兩個線程安全地訪問一個Vector對象、但是一個線程訪問Vector的話代碼要在同步操作上耗費大量的時間拟蜻。
Arraylist不是同步的绎签，所以在不需要保證線程安全時建議使用Arraylist。
四）HashSet與TreeSet與LinkedHashSet對比
HashSet不能保證元素的排列順序酝锅，順序有可能發(fā)生變化诡必，不是同步的，集合元素可以是null,但只能放入一個null搔扁。TreeSet是SortedSet接口的唯一實現(xiàn)類爸舒，TreeSet可以確保集合元素處于排序狀態(tài)。TreeSet支持兩種排序方式阁谆，自然排序 和定制排序碳抄，其中自然排序為默認的排序方式。向TreeSet中加入的應(yīng)該是同一個類的對象场绿。TreeSet判斷兩個對象不相等的方式是兩個對象通過equals方法返回false剖效，或者通過CompareTo方法比較沒有返回0自然排序 自然排序使用要排序元素的
CompareTo（Object obj）方法來比較元素之間大小關(guān)系，然后將元素按照升序排列焰盗。定制排序 自然排序是根據(jù)集合元素的大小璧尸，以升序排列，如果要定制排序熬拒，應(yīng)該使用
Comparator接口爷光，實現(xiàn)int compare(To1,To2)方法LinkedHashSet集合同樣是根據(jù)元素的hashCode值來決定元素的存儲位置，但是它同時使用鏈表維護元素的次序澎粟。這樣使得元素看起來像是以插入順序保存的蛀序，也就是說，當(dāng)遍歷該集合時候活烙，LinkedHashSet將會以元素的添加順序訪問集合的元素徐裸。LinkedHashSet在迭代訪問Set中的全部元素時，性能比HashSet好啸盏，但是插入時性能稍微遜色于HashSet重贺。
五）LinkedHashMap和HashMap，TreeMap對比
Hashtable與 HashMap類似,它繼承自Dictionary類回懦，不同的是:它不允許記錄的鍵或者值為空;它支持線程的同步气笙，即任一時刻只有一個線程能寫Hashtable,因此也導(dǎo)致了Hashtable在寫入時會比較慢。HashMap是一個最常用的Map,它根據(jù)鍵的HashCode值存儲數(shù)據(jù),根據(jù)鍵可以直接獲取它的值怯晕，具有很快的訪問速度潜圃，遍歷時，取得數(shù)據(jù)的順序是完全隨機的舟茶。LinkedHashMap保存了記錄的插入順序谭期，在用Iterator遍歷LinkedHashMap時蛉谜，先得到的記錄肯定是先插入的.也可以在構(gòu)造時用帶參數(shù)，按照應(yīng)用次數(shù)排序崇堵。在遍歷的時候會比HashMap慢型诚，不過有種情況例外，當(dāng)HashMap容量很大鸳劳，實際數(shù)據(jù)較少時狰贯，遍歷起來可能會比LinkedHashMap慢，因為LinkedHashMap的遍歷速度只和實際數(shù)據(jù)有關(guān)赏廓，和容量無關(guān)涵紊，而HashMap的遍歷速度和他的容量有關(guān)。TreeMap實現(xiàn)SortMap接口幔摸，能夠把它保存的記錄根據(jù)鍵排序,默認是按鍵值的升序排序摸柄，也可以指定排序的比較器，當(dāng)用Iterator 遍歷TreeMap時既忆，得到的記錄是排過序的驱负。我們用的最多的是
HashMap,HashMap里面存入的鍵值對在取出的時候是隨機的,在Map中插入、刪除和定位元素患雇，HashMap是最好的選擇跃脊。TreeMap取出來的是排序后的鍵值對。但
如果您要按**自然順序或自定義順序遍歷鍵**苛吱，那么TreeMap會更好酪术。LinkedHashMap 是HashMap的一個子類，如果需要輸出的順序和輸入的相同,那么用LinkedHashMap可以實現(xiàn),它還可以按讀取順序來排列翠储，像連接池中可以應(yīng)用绘雁。
六）HashMap 和 Hashtable 的區(qū)別
線程是否安全： HashMap 是非線程安全的，HashTable 是線程安全的援所；HashTable 內(nèi)部的方法基本都經(jīng)過
synchronized修飾庐舟。（如果你要保證線程安全的話就使用ConcurrentHashMap吧！）任斋；效率： 因為線程安全的問題继阻，HashMap 要比 HashTable 效率高一點耻涛。另外废酷，HashTable 基本被淘汰，不
要在代碼中使用它抹缕；對Null key 和Null value的支持： HashMap 中澈蟆，null 可以作為鍵，
這樣的鍵只有一個卓研，可以有一個或多個鍵所對應(yīng)的值為 null趴俘。睹簇。但是在HashTable 中 put 進的鍵值只要有一個 null，直接拋出 NullPointerException寥闪。初始容量大小和每次擴充容量大小的不同 ： ①創(chuàng)建時如果不指定容量初始值太惠，
Hashtable 默認的初始大小為11，之后每次擴充疲憋，容量變?yōu)樵瓉淼?n+1凿渊。HashMap 默認的初始化大小為16。之后每次擴充缚柳，容量變?yōu)樵瓉淼?倍埃脏。②創(chuàng)建時如果給定了容量初始值，那么 Hashtable 會直接使用你給定的大小秋忙，而 HashMap 會將其擴充為2的冪次方大小（HashMap 中的tableSizeFor()方法保證彩掐，下面給出了源代碼）。也就是說 HashMap 總是使用2的冪作為哈希表的大小,后面會介紹到為什么是2的冪次方灰追。底層數(shù)據(jù)結(jié)構(gòu)： JDK1.8 以后的 HashMap 在解決哈希沖突時有了較大的變化堵幽，
當(dāng)鏈表長度大于閾值（默認為8）時，將鏈表轉(zhuǎn)化為紅黑樹弹澎，以減少搜索時間谐檀。Hashtable 沒有這樣的機制。
七）HashMap 和 HashSet區(qū)別
如果你看過 HashSet 源碼的話就應(yīng)該知道：HashSet 底層就是基于 HashMap 實現(xiàn)的裁奇。（HashSet 的源碼非常非常少桐猬，因為除了 clone()、writeObject()刽肠、readObject()是 HashSet 自己不得不實現(xiàn)之外溃肪，其他方法都是直接調(diào)用 HashMap 中的方法。
八）HashSet如何檢查重復(fù)
當(dāng)你把對象加入HashSet時音五，HashSet會先計算對象的hashcode值來判斷對象加入的位置惫撰，同時也會與其他加入的對象的hashcode值作比較，如果沒有相符的hashcode躺涝，HashSet會假設(shè)對象沒有重復(fù)出現(xiàn)厨钻。但是如果發(fā)現(xiàn)有相同hashcode值的對象，這時會調(diào)用equals（）方法來檢查hashcode相等的對象是否真的相同坚嗜。如果兩者相同夯膀，HashSet就不會讓加入操作成功。
hashCode（）與equals（）的相關(guān)規(guī)定：
如果兩個對象相等苍蔬，則hashcode一定也是相同的
兩個對象相等,對兩個equals方法返回true
兩個對象有相同的hashcode值诱建，它們也不一定是相等的
綜上，equals方法被覆蓋過碟绑，則hashCode方法也必須被覆蓋
hashCode()的默認行為是對堆上的對象產(chǎn)生獨特值俺猿。如果沒有重寫hashCode()茎匠，則該class的兩個對象無論如何都不會相等（即使這兩個對象指向相同的數(shù)據(jù)）。
九）HashMap的底層實現(xiàn)
JDK1.8之前
JDK1.8 之前 HashMap 底層是數(shù)組和鏈表 結(jié)合在一起使用也就是鏈表散列押袍。HashMap 通過 key 的 hashCode 經(jīng)過擾動函數(shù)處理過后得到 hash 值诵冒，然后通過 (n - 1) & hash 判斷當(dāng)前元素存放的位置（這里的 n 指的是數(shù)組的長度），如果當(dāng)前位置存在元素的話谊惭，就判斷該元素與要存入的元素的 hash 值以及 key 是否相同造烁，如果相同的話，直接覆蓋午笛，不相同就通過拉鏈法解決沖突惭蟋。
所謂擾動函數(shù)指的就是 HashMap 的 hash 方法。使用 hash 方法也就是擾動函數(shù)是為了防止一些實現(xiàn)比較差的 hashCode() 方法 換句話說使用擾動函數(shù)之后可以減少碰撞药磺。
HashMap實現(xiàn)原理（比較好的描述）：HashMap以鍵值對（key-value）的形式來儲存元素告组，但調(diào)用put方法時，HashMap會通過hash函數(shù)來計算key的hash值癌佩，然后通過hash值&(HashMap.length-1)判斷當(dāng)前元素的存儲位置木缝，如果當(dāng)前位置存在元素的話，就要判斷當(dāng)前元素與要存入的key是否相同围辙，如果相同則覆蓋我碟，如果不同則通過拉鏈表來解決。JDk1.8時姚建，當(dāng)鏈表長度大于8時矫俺，將鏈表轉(zhuǎn)為紅黑樹。
JDK 1.8 HashMap 的 hash 方法源碼:
JDK 1.8 的 hash方法 相比于 JDK 1.7 hash 方法更加簡化掸冤，但是原理不變厘托。
static final int hash(Object key) {
int h;
// key.hashCode()：返回散列值也就是hashcode
// ^ ：按位異或
// >>>:無符號右移，忽略符號位稿湿，空位都以0補齊
return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}
對比一下 JDK1.7的 HashMap 的 hash 方法源碼：
static int hash(int h) {
// This function ensures that hashCodes that differ only by
// constant multiples at each bit position have a bounded
// number of collisions (approximately 8 at default load factor).
h ^= (h >>> 20) ^ (h >>> 12);
return h ^ (h >>> 7) ^ (h >>> 4);
}
相比于 JDK1.8 的 hash 方法 铅匹，JDK 1.7 的 hash 方法的性能會稍差一點點，因為畢竟擾動了 4 次饺藤。
所謂 “拉鏈法” 就是：將鏈表和數(shù)組相結(jié)合包斑。也就是說創(chuàng)建一個鏈表數(shù)組，數(shù)組中每一格就是一個鏈表涕俗。若遇到哈希沖突罗丰，則將沖突的值加到鏈表中即可。
JDK1.8之后
相比于之前的版本咽袜， JDK1.8之后在解決哈希沖突時有了較大的變化丸卷，當(dāng)鏈表長度大于閾值（默認為8）時枕稀，將鏈表轉(zhuǎn)化為紅黑樹询刹，以減少搜索時間谜嫉。
TreeMap、TreeSet以及JDK1.8之后的HashMap底層都用到了紅黑樹凹联。紅黑樹就是為了解決二叉查找樹的缺陷沐兰，因為二叉查找樹在某些情況下會退化成一個線性結(jié)構(gòu)。
十）HashMap 的長度為什么是2的冪次方
HashMap為了存取高效蔽挠，要盡量較少碰撞住闯，就是要盡量把數(shù)據(jù)分配均勻，每個鏈表長度大致相同澳淑，這個實現(xiàn)就在把數(shù)據(jù)存到哪個鏈表中的算法比原；
這個算法實際就是取模，hash%length杠巡，計算機中直接求余效率不如位移運算量窘，源碼中做了優(yōu)化hash&(length-1)， hash%length==hash&(length-1)的前提是length是2的n次方氢拥；
為什么這樣能均勻分布減少碰撞呢蚌铜？2的n次方實際就是1后面n個0，2的n次方-1 實際就是n個1嫩海； 例如長度為9時候冬殃，3&(9-1)=0 2&(9-1)=0 ，都在0上叁怪，碰撞了审葬； 例如長度為8時候，3&(8-1)=3 2&(8-1)=2 奕谭，不同位置上耳璧，不碰撞；
其實就是按位“與”的時候展箱，每一位都能 &1 旨枯，也就是和1111……1111111進行與運算
0000 0011 3
& 0000 1000 8
= 0000 0000 0
0000 0010 2
& 0000 1000 8
= 0000 0000 0
0000 0011 3
& 0000 0111 7
= 0000 0011 3
0000 0010 2
& 0000 0111 7
= 0000 0010 2
當(dāng)然如果不考慮效率直接求余即可（就不需要要求長度必須是2的n次方了）；
有人懷疑兩種運算效率差別到底有多少混驰，我做個測試：
/**
*
* 直接【求余】和【按位】運算的差別驗證
*/
public static void main(String[] args) {
long currentTimeMillis = System.currentTimeMillis();
int a=0;
int times = 10000*10000;
for (long i = 0; i < times; i++) {
a=9999%1024;
}
long currentTimeMillis2 = System.currentTimeMillis();
int b=0;
for (long i = 0; i < times; i++) {
b=9999&(1024-1);
}
long currentTimeMillis3 = System.currentTimeMillis();
System.out.println(a+","+b);
System.out.println("%: "+(currentTimeMillis2-currentTimeMillis));
System.out.println("&: "+(currentTimeMillis3-currentTimeMillis2));
}
?
結(jié)果：
783,783
%: 359
&: 93
十二）HashMap 多線程操作導(dǎo)致死循環(huán)問題
主要原因在于并發(fā)下的Rehash會造成元素之間會形成一個循環(huán)鏈表攀隔。不過，jdk 1.8 后解決了這個問題栖榨，但是還是不建議在多線程下使用 HashMap,因為多線程下使用 HashMap 還是會存在其他問題比如數(shù)據(jù)丟失昆汹。并發(fā)環(huán)境下推薦使用 ConcurrentHashMap。
Rehash：一般來說婴栽，Hash表這個容器當(dāng)有數(shù)據(jù)要插入時满粗，都會檢查容量有沒有超過設(shè)定的臨界值，如果超過愚争，需要增大Hash表的尺寸映皆，但是這樣一來挤聘，整個Hash表里的元素都需要被重算一遍。這叫rehash捅彻，這個成本相當(dāng)?shù)拇蟆?/p>
十三）comparable 和 Comparator的區(qū)別
comparable接口實際上是出自java.lang包 它有一個
compareTo(Object obj)方法用來排序comparator接口實際上是出自 java.util 包它有一個
compare(Object obj1, Object obj2)方法用來排序
一般我們需要對一個集合使用自定義排序時组去，我們就要重寫compareTo()方法或compare()方法，當(dāng)我們需要對某一個集合實現(xiàn)兩種排序方式步淹，比如一個song對象中的歌名和歌手名分別采用一種排序方法的話从隆，我們可以重寫compareTo()方法和使用自制的Comparator方法或者以兩個Comparator來實現(xiàn)歌名排序和歌星名排序，第二種代表我們只能使用兩個參數(shù)版的 Collections.sort().
四缭裆、并發(fā)下的集合不安全
1 List集合下的并發(fā)安全
public static void main(String[] args) {
List<String> list = new ArrayList();
for (int i = 0; i < 10; i++) {
new Thread(()->{
list.add(UUID.randomUUID().toString().substring(0,7));
System.out.println(list);
},String.valueOf(i)).start();
}
}
發(fā)現(xiàn)可能出現(xiàn)的異常情況
解決方案：
1. new Vector<>();
public static void main(String[] args) {
?
List<String> list = new Vector<>();
?
for (int i = 0; i < 10; i++) {
new Thread(()->{
list.add(UUID.randomUUID().toString().substring(0,7));
System.out.println(list);
},String.valueOf(i)).start();
}
}
2. 使用Collections.snychronizedList
public static void main(String[] args) {
List<String> list = Collections.synchronizedList(new ArrayList<>());
for (int i = 0; i < 10; i++) {
new Thread(()->{
list.add(UUID.randomUUID().toString().substring(0,7));
System.out.println(list);
},String.valueOf(i)).start();
}
}
3. 使用JUC編程下的CopyOnWriteArrayList<>();
讀寫分離
CopyOnWrite寫入是復(fù)制 cow 計算機程序設(shè)計領(lǐng)域的一直優(yōu)化策略键闺；
寫操作在一個復(fù)制的數(shù)組上進行，讀操作還是在原始數(shù)組中進行澈驼，讀寫分離艾杏，互不影響。
寫操作需要加鎖盅藻，防止并發(fā)寫入時導(dǎo)致寫入數(shù)據(jù)丟失购桑。
寫操作結(jié)束之后需要把原始數(shù)組指向新的復(fù)制數(shù)組。
public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
?
final void setArray(Object[] a) {
array = a;
}
@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
return (E) a[index];
}
適用場景
CopyOnWriteArrayList 在寫操作的同時允許讀操作氏淑，大大提高了讀操作的性能勃蜘，因此很適合讀多寫少的應(yīng)用場景。
但是 CopyOnWriteArrayList 有其缺陷：
內(nèi)存占用：在寫操作時需要復(fù)制一個新的數(shù)組假残，使得內(nèi)存占用為原來的兩倍左右缭贡；
數(shù)據(jù)不一致：讀操作不能讀取實時性的數(shù)據(jù)，因為部分寫操作的數(shù)據(jù)還未同步到讀數(shù)組中辉懒。
所以 CopyOnWriteArrayList 不適合內(nèi)存敏感以及對實時性要求很高的場景阳惹。
2. set集合
同上：
Set<String> list = Collections.synchronizedSet(new HashSet<>());
Set<String> list = new CopyOnWriteArraySet<>();
3. Map集合
解決方案：ConcurrentHashMap
// ConcurrentModificationException
public class MapTest {
public static void main(String[] args) {
// map 是這樣用的嗎？ 不是眶俩，工作中不用 HashMap
// 默認等價于什么莹汤？ new HashMap<>(16,0.75);
// Map<String, String> map = new HashMap<>();
Map<String, String> map = new ConcurrentHashMap<>();
for (int i = 1; i <=30; i++) {
new Thread(()->{
map.put(Thread.currentThread().getName(),UUID.randomUUID().toString().substring(
0,5));
System.out.println(map);
},String.valueOf(i)).start();
}
}
}
哈希表
1.介紹
哈希表就是一種以 鍵-值(key-indexed) 存儲數(shù)據(jù)的結(jié)構(gòu)，我們只要輸入待查找的值即key颠印，即可查找到其對應(yīng)的值纲岭。
哈希的思路很簡單，如果所有的鍵都是整數(shù)线罕，那么就可以使用一個簡單的無序數(shù)組來實現(xiàn)：將鍵作為索引止潮，值即為其對應(yīng)的值，這樣就可以快速訪問任意鍵的值钞楼。這是對于簡單的鍵的情況喇闸，我們將其擴展到可以處理更加復(fù)雜的類型的鍵。
2.鏈?zhǔn)焦１?/strong>
鏈?zhǔn)焦１韽母旧险f是由一組鏈表構(gòu)成。每個鏈表都可以看做是一個“桶”燃乍，我們將所有的元素通過散列的方式放到具體的不同的桶中衣厘。插入元素時表谊，首先將其鍵傳入一個哈希函數(shù)（該過程稱為哈希鍵）联逻，函數(shù)通過散列的方式告知元素屬于哪個“桶”觉渴，然后在相應(yīng)的鏈表頭插入元素夯秃。查找或刪除元素時座咆，用同們的方式先找到元素的“桶”，然后遍歷相應(yīng)的鏈表仓洼，直到發(fā)現(xiàn)我們想要的元素介陶。因為每個“桶”都是一個鏈表，所以鏈?zhǔn)焦１聿⒉幌拗瓢氐膫€數(shù)色建。然而哺呜，如果表變得太大，它的性能將會降低箕戳。
應(yīng)用場景
我們熟知的緩存技術(shù)（比如redis某残、memcached）的核心其實就是在內(nèi)存中維護一張巨大的哈希表，還有大家熟知的HashMap陵吸、ConcurrentHashMap等的應(yīng)用玻墅。
ConcurrentHashMap與HashMap等的區(qū)別
1. HashMap
我們知道HashMap是線程不安全的，在多線程環(huán)境下壮虫，使用Hashmap進行put操作會引起死循環(huán)澳厢，導(dǎo)致CPU利用率接近100%，所以在并發(fā)情況下不能使用HashMap囚似。
2. HashTable
HashTable和HashMap的實現(xiàn)原理幾乎一樣剩拢，差別無非是
HashTable不允許key和value為null
HashTable是線程安全的
但是HashTable線程安全的策略實現(xiàn)代價卻太大了，簡單粗暴饶唤，get/put所有相關(guān)操作都是synchronized的徐伐，這相當(dāng)于給整個哈希表加了一把大鎖，如下圖所示：
多線程訪問時候募狂，只要有一個線程訪問或操作該對象呵晨，那其他線程只能阻塞，相當(dāng)于將所有的操作串行化熬尺，在競爭激烈的并發(fā)場景中性能就會非常差摸屠。
3. ConcurrentHashMap
主要就是為了應(yīng)對hashmap在并發(fā)環(huán)境下不安全而誕生的，ConcurrentHashMap的設(shè)計與實現(xiàn)非常精巧粱哼，大量的利用了volatile季二，final，CAS等lock-free技術(shù)來減少鎖競爭對于性能的影響。
我們都知道Map一般都是數(shù)組+鏈表結(jié)構(gòu)（JDK1.8該為數(shù)組+紅黑樹）胯舷。
ConcurrentHashMap避免了對全局加鎖改成了局部加鎖操作刻蚯，這樣就極大地提高了并發(fā)環(huán)境下的操作速度，由于ConcurrentHashMap在JDK1.7和1.8中的實現(xiàn)非常不同桑嘶，接下來我們談?wù)凧DK在1.7和1.8中的區(qū)別炊汹。
JDK1.7版本的ConcurrentHashMap的實現(xiàn)原理
在JDK1.7中ConcurrentHashMap采用了數(shù)組+Segment+分段鎖的方式實現(xiàn)。
Segment(分段鎖)
ConcurrentHashMap中的分段鎖稱為Segment逃顶，它即類似于HashMap的結(jié)構(gòu)讨便，即內(nèi)部擁有一個Entry數(shù)組，數(shù)組中的每個元素又是一個鏈表,同時又是一個ReentrantLock（Segment繼承了ReentrantLock）以政。
內(nèi)部結(jié)構(gòu)
ConcurrentHashMap使用分段鎖技術(shù)霸褒，將數(shù)據(jù)分成一段一段的存儲，然后給每一段數(shù)據(jù)配一把鎖盈蛮，當(dāng)一個線程占用鎖訪問其中一個段數(shù)據(jù)的時候废菱，其他段的數(shù)據(jù)也能被其他線程訪問，能夠?qū)崿F(xiàn)真正的并發(fā)訪問抖誉。如下圖是ConcurrentHashMap的內(nèi)部結(jié)構(gòu)圖：
ConcurrentHashMap定位一個元素的過程需要進行兩次Hash操作殊轴。
第一次Hash定位到Segment，第二次Hash定位到元素所在的鏈表的頭部袒炉。
該結(jié)構(gòu)的優(yōu)劣勢：
壞處
這一種結(jié)構(gòu)的帶來的副作用是Hash的過程要比普通的HashMap要長
好處
寫操作的時候可以只對元素所在的Segment進行加鎖即可旁理，不會影響到其他的Segment，這樣梳杏，在最理想的情況下韧拒，ConcurrentHashMap可以最高同時支持Segment數(shù)量大小的寫操作（剛好這些寫操作都非常平均地分布在所有的Segment上）。
所以十性，通過這一種結(jié)構(gòu)叛溢，ConcurrentHashMap的并發(fā)能力可以大大的提高。
JDK1.8版本的ConcurrentHashMap的實現(xiàn)原理
JDK8中ConcurrentHashMap參考了JDK8 HashMap的實現(xiàn)劲适，采用了數(shù)組+鏈表+紅黑樹的實現(xiàn)方式來設(shè)計楷掉，如下圖所示：
內(nèi)部大量采用CAS操作，這里我簡要介紹下CAS霞势。
CAS是compare and swap的縮寫烹植，即我們所說的比較交換。cas是一種基于鎖的操作愕贡，而且是樂觀鎖草雕。在java中鎖分為樂觀鎖和悲觀鎖。悲觀鎖是將資源鎖住固以，等一個之前獲得鎖的線程釋放鎖之后墩虹，下一個線程才可以訪問嘱巾。而樂觀鎖采取了一種寬泛的態(tài)度，通過某種方式不加鎖來處理資源诫钓，比如通過給記錄加version來獲取數(shù)據(jù)旬昭，性能較悲觀鎖有很大的提高。
CAS 操作包含三個操作數(shù) —— 內(nèi)存位置（V）菌湃、預(yù)期原值（A）和新值(B)问拘。如果內(nèi)存地址里面的值和A的值是一樣的，那么就將內(nèi)存里面的值更新成B惧所。CAS是通過無限循環(huán)來獲取數(shù)據(jù)的骤坐，如果在第一輪循環(huán)中，a線程獲取地址里面的值被b線程修改了纯路，那么a線程需要自旋或油，到下次循環(huán)才有可能機會執(zhí)行寞忿。
JDK8中徹底放棄了Segment轉(zhuǎn)而采用的是Node驰唬，其設(shè)計思想也不再是JDK1.7中的分段鎖思想。
Node：保存key腔彰，value及key的hash值的數(shù)據(jù)結(jié)構(gòu)叫编。其中value和next都用volatile修飾，保證并發(fā)的可見性霹抛。
<strong>class Node<K,V> implements Map.Entry<K,V> {
final int hash;
final K key;
volatile V val;
volatile Node<K,V> next;
//... 省略部分代碼
} </strong>
Java8 ConcurrentHashMap結(jié)構(gòu)基本上和Java8的HashMap一樣搓逾，不過保證線程安全性。
在JDK8中ConcurrentHashMap的結(jié)構(gòu)杯拐，由于引入了紅黑樹霞篡，使得ConcurrentHashMap的實現(xiàn)非常復(fù)雜，我們都知道端逼，紅黑樹是一種性能非常好的二叉查找樹朗兵，其查找性能為O（logN），但是其實現(xiàn)過程也非常復(fù)雜顶滩，而且可讀性也非常差余掖，DougLea的思維能力確實不是一般人能比的，早期完全采用鏈表結(jié)構(gòu)時Map的查找時間復(fù)雜度為O（N）礁鲁，JDK8中ConcurrentHashMap在鏈表的長度大于某個閾值的時候會將鏈表轉(zhuǎn)換成紅黑樹進一步提高其查找性能盐欺。
ConcurrentHashMap總結(jié)
其實可以看出JDK1.8版本的ConcurrentHashMap的數(shù)據(jù)結(jié)構(gòu)已經(jīng)接近HashMap，相對而言仅醇，ConcurrentHashMap只是增加了同步的操作來控制并發(fā)冗美，從JDK1.7版本的ReentrantLock+Segment+HashEntry，到JDK1.8版本中synchronized+CAS+HashEntry+紅黑樹析二。
1. 數(shù)據(jù)結(jié)構(gòu)：取消了Segment分段鎖的數(shù)據(jù)結(jié)構(gòu)粉洼，取而代之的是數(shù)組+鏈表+紅黑樹的結(jié)構(gòu)。
2. 保證線程安全機制：JDK1.7采用segment的分段鎖機制實現(xiàn)線程安全，其中segment繼承自ReentrantLock漆改。JDK1.8采用CAS+Synchronized保證線程安全心铃。
3. 鎖的粒度：原來是對需要進行數(shù)據(jù)操作的Segment加鎖，現(xiàn)調(diào)整為對每個數(shù)組元素加鎖（Node）挫剑。
4. 鏈表轉(zhuǎn)化為紅黑樹:定位結(jié)點的hash算法簡化會帶來弊端,Hash沖突加劇,因此在鏈表節(jié)點數(shù)量大于8時去扣，會將鏈表轉(zhuǎn)化為紅黑樹進行存儲。
5. 查詢時間復(fù)雜度：從原來的遍歷鏈表O(n)樊破，變成遍歷紅黑樹O(logN)愉棱。
五、其他相關(guān)
二叉查找樹
要想了解二叉查找樹哲戚，我們首先看下二叉查找樹有哪些特性呢奔滑？
1， 左子樹上所有的節(jié)點的值均小于或等于他的根節(jié)點的值
2顺少， 右子數(shù)上所有的節(jié)點的值均大于或等于他的根節(jié)點的值
3朋其， 左右子樹也一定分別為二叉排序樹
我們來看下圖的這棵樹，他就是典型的二叉查找樹
這不是二分查找的思想嗎脆炎？確實梅猿，查找所需的最大次數(shù)等同于二叉查找樹的高度。當(dāng)然在插入節(jié)點的時候秒裕，也是這種思想袱蚓，一層一層的找到合適的位置插入。但是二叉查找樹有個比較大的缺陷几蜻，而且這個缺陷會影響到他的性能喇潘。我們先來看下有一種情況的插入操作：
如果初始的二叉查找樹只有三個節(jié)點，如下圖：
我們依次插入5個節(jié)點：7梭稚，6,5,4,3,颖低。看下圖插入之后的圖：
看出來了嗎哨毁？有沒有覺得很別扭枫甲，如果根節(jié)點足夠大，那是不是“左腿”會變的特別長扼褪，也就是說查找的性能大打折扣想幻，幾乎就是線性查找了。
那有沒有好的辦法解決這個問題呢话浇？解決這種多次插入新節(jié)點而導(dǎo)致的不平衡脏毯？這個時候紅黑樹就登場了。
紅黑樹
紅黑樹就是一種平衡的二叉查找樹幔崖，說他平衡的意思是他不會變成“瘸子”食店，左腿特別長或者右腿特別長渣淤。除了符合二叉查找樹的特性之外，還具體下列的特性：
1. 節(jié)點是紅色或者黑色
2. 根節(jié)點是黑色
3. 每個葉子的節(jié)點都是黑色的空節(jié)點（NULL）
4. 每個紅色節(jié)點的兩個子節(jié)點都是黑色的吉嫩。
5. 從任意節(jié)點到其每個葉子的所有路徑都包含相同的黑色節(jié)點价认。
看下圖就是一個典型的紅黑樹：
很多童鞋又會驚訝了，天啊這個條條框框也太多了吧自娩。沒錯用踩，正式因為這些規(guī)則，才能保證紅黑樹的自平衡忙迁。最長路徑不超過最短路徑的2倍脐彩。
1、當(dāng)插入和刪除節(jié)點姊扔，就會對平衡造成破壞惠奸，這時候需要對樹進行調(diào)整，從而重新達到平衡恰梢。那什么情況下會破壞紅黑樹的規(guī)則呢佛南？
向原來的紅黑樹插入值為14的新節(jié)點，由于父節(jié)點15是黑色節(jié)點删豺，所以這種情況沒有破壞結(jié)構(gòu)共虑，不需要做任何的改變愧怜。
2呀页、向原樹插入21呢？拥坛，看下圖：
由于父節(jié)點22是紅色節(jié)點蓬蝶，因此這種情況打破了紅黑樹的規(guī)則4，必須作出調(diào)整猜惋。那么究竟該怎么調(diào)整呢丸氛？有兩種方式【變色】和【旋轉(zhuǎn)】分為【左旋轉(zhuǎn)】和【右旋轉(zhuǎn)】。
【變色】：
為了符合紅黑樹的規(guī)則著摔，會把節(jié)點紅變黑或者黑變紅缓窜。下圖展示的是紅黑樹的部分，需要注意節(jié)點25并非根節(jié)點谍咆。因為21和22鏈接出現(xiàn)紅色禾锤，不符合規(guī)則4，所以把22紅變黑：
但這樣還是不符合規(guī)則5摹察，所以需要把25黑變紅恩掷，看下圖：
你以為現(xiàn)在結(jié)束了？天真供嚎，因為25和27又是兩個連續(xù)的紅色節(jié)點(規(guī)則4)黄娘，所以需要將27紅變黑峭状。
終于結(jié)束了，都滿足規(guī)則了逼争，舒服多了优床。
【左旋轉(zhuǎn)】
也就是逆時針旋轉(zhuǎn)兩個節(jié)點，使父節(jié)點被自己的右孩子取代誓焦，而自己成為自己的左孩子羔巢，聽起來嚇?biāo)廊耍苯涌磮D吧：
【右旋轉(zhuǎn)】
順時針旋轉(zhuǎn)兩個節(jié)點罩阵，使得自己的父節(jié)點被左孩子取代竿秆，而自己成為自己的右孩子，看不懂直接看圖吧：
看起來這么復(fù)雜稿壁，到底怎么用呢幽钢？確實很復(fù)雜，我們講下典型的例子傅是，大家參考下：
以剛才插入21節(jié)點的例子：
首先我們需要做的是變色匪燕，把節(jié)點25以及下方的節(jié)點變色：
由于17和25是連續(xù)的兩個紅色節(jié)點，那么吧節(jié)點17變黑嗎喧笔？這樣是不行的帽驯，你想這樣一來不就打破了規(guī)則4了嗎，而且根據(jù)規(guī)則2书闸，也不可能吧13變成紅色尼变。變色已經(jīng)無法解決問題了，所以只能進行旋轉(zhuǎn)了浆劲。13當(dāng)成X嫌术，17當(dāng)成Y，左旋轉(zhuǎn)試試看：
由于根節(jié)點必須是黑色牌借，所以需要變色度气，結(jié)果如下圖：
繼續(xù)，其中有兩條路徑（17-）8->6->NULL）的黑色節(jié)點個數(shù)不是3膨报，是4不符合規(guī)則磷籍。
這個時候需要把13當(dāng)做X，8當(dāng)做Y现柠，進行右旋轉(zhuǎn)：
最后根據(jù)規(guī)則變色：
這樣一來院领，我們終于結(jié)束了，經(jīng)過調(diào)整之后符合規(guī)則晒旅。
那我們費這么大力氣栅盲，這么復(fù)雜，這東西用在哪里废恋，有哪些應(yīng)用呢谈秫？
其實STL中的map就是用的紅黑樹扒寄。
TreeSet的兩種排序方式比較
1.基本數(shù)據(jù)類型默認按升序排序
2.自定義排序
（1）自然排序：重寫Comparable接口中的Compareto方法
（2）比較器排序：重寫Comparator接口中的Compare方法
compare(T o1,T o2) 比較用來排序的兩個參數(shù)。
o1：代表當(dāng)前添加的數(shù)據(jù)
o2：代表集合中已經(jīng)存在的數(shù)據(jù)
0： 表示 o1 == o2
-1(逆序輸出)： o1 < o2
1(正序輸出): o1 > o2 </pre>
1：o1 - o2（升序排列） -1：o2 - o1 (降序排列)
例子1
public class Test {
public static void main(String[] args) {
/**
* 自定義規(guī)則的TreeSet
* 客戶端排序：自己寫一個比較器拟烫，轉(zhuǎn)給TreeSet
*
* 比較規(guī)則
* 當(dāng)TreeSet集合添加數(shù)據(jù)的時候就會觸發(fā)比較器的compare()方法
*/
Comparator<Integer> comp = new Comparator<Integer>() {
/**
* o1 當(dāng)前添加的數(shù)據(jù)
* o2 集合中已經(jīng)存在的數(shù)據(jù)
* 0： 表示 o1 == o2
* -1 ： o1 < o2
* 1 : o1 > o2
*/
@Override
public int compare(Integer o1, Integer o2) {
System.out.println(o1+"--"+o2);
return o2 -o1; //輸出53 33 10该编，降序排序
// return 0; //只輸出一個元素：33
// return -1; //輸出53 10 33，倒序輸出
// return 1; //輸出33 10 55
}
};
Set<Integer> s2 = new TreeSet<>(comp);
s2.add(33);
s2.add(10);
s2.add(55);
System.out.println(s2); //輸入53 33 10硕淑，降序排序
}
}
例子2：
/**
* 使用TreeSet和Comparator（使用匿名類）课竣，寫Test.java
* 要求：對TreeSet中的元素
* 1，2置媳，3于樟，4，5拇囊，6迂曲，7，8寥袭，9路捧，10進行排列，
* 排序邏輯為奇數(shù)在前偶數(shù)在后传黄，
* 奇數(shù)按照升序排列杰扫，偶數(shù)按照降序排列
* 輸出結(jié)果：1 3 5 7 9 10 8 6 4 2
*/
public class Test {
public static void main(String[] args) {
Set<Integer> s = new TreeSet<>(new Comparator<Integer>() {
//重寫compare方法
@Override
public int compare(Integer o1, Integer o2) {
System.out.println("o1="+o1+" o2="+o2);
if(o2%2==0){
if (o1%2==0){
return o2 -o1;
}else{
return -1;
}
}else {
if (o1%2==0){
return 1;
}else{
return o1 -o2;
}
}
}
});
s.add(2);
s.add(6);
s.add(4);
s.add(1);
s.add(3);
s.add(5);
s.add(8);
s.add(10);
s.add(9);
s.add(7);
Iterator iterator = s.iterator();
while(iterator.hasNext()){
System.out.print(iterator.next()+" ");
}
?
}
}
輸出結(jié)果：
