Java中的集合(下)
### 11.3.3 List實(shí)現(xiàn)類(lèi)的區(qū)別
#### 1、Vector和ArrayList的區(qū)別
核心類(lèi)庫(kù)中List接口有兩個(gè)實(shí)現(xiàn)類(lèi)：Vector和ArrayList。它們的底層物理結(jié)構(gòu)都是數(shù)組，我們稱為動(dòng)態(tài)數(shù)組。
（1）ArrayList是新版的動(dòng)態(tài)數(shù)組，線程不安全，效率高，Vector是舊版的動(dòng)態(tài)數(shù)組，線程安全，效率低。
（2）動(dòng)態(tài)數(shù)組的擴(kuò)容機(jī)制不同，ArrayList擴(kuò)容為原來(lái)的1.5倍，Vector擴(kuò)容增加為原來(lái)的2倍。
（3）數(shù)組的初始化容量，如果在構(gòu)建ArrayList與Vector的集合對(duì)象時(shí)，沒(méi)有顯式指定初始化容量，那么Vector的內(nèi)部數(shù)組的初始容量默認(rèn)為10，而ArrayList在JDK1.6及之前的版本也是10，JDK1.7之后的版本ArrayList初始化為長(zhǎng)度為0的空數(shù)組，之后在添加第一個(gè)元素時(shí)，再創(chuàng)建長(zhǎng)度為10的數(shù)組。
ArrayList在第1次添加時(shí)再創(chuàng)建數(shù)組是為了避免浪費(fèi)。因?yàn)楹芏喾椒ǖ姆祷刂凳茿rrayList類(lèi)型，需要返回一個(gè)ArrayList的對(duì)象，例如：后期從數(shù)據(jù)庫(kù)查詢對(duì)象的方法，返回值很多就是ArrayList。有可能你要查詢的數(shù)據(jù)不存在，要么返回null，要么返回一個(gè)沒(méi)有元素的ArrayList對(duì)象。
#### 2、ArrayList與LinkedList的區(qū)別
動(dòng)態(tài)數(shù)組底層的物理結(jié)構(gòu)是數(shù)組，因此根據(jù)索引訪問(wèn)的效率非常高。但是==非末尾==位置的插入和刪除效率不高，因?yàn)樯婕暗揭苿?dòng)元素。==末尾位置==的插入和刪除不涉及移動(dòng)元素。另外添加操作時(shí)涉及到擴(kuò)容問(wèn)題，就會(huì)增加時(shí)空消耗。
鏈表底層的物理結(jié)構(gòu)是鏈表，因此根據(jù)索引訪問(wèn)的效率不高，但是插入和刪除不需要移動(dòng)元素，只需要修改前后元素的指向關(guān)系即可，而且鏈表的添加不會(huì)涉及到擴(kuò)容問(wèn)題。
## 11.4 棧和隊(duì)列
### 11.4.1 棧
堆棧是一種先進(jìn)后出（FILO：first in last out）或后進(jìn)先出（LIFO：last in first out）的結(jié)構(gòu)。
棧只是邏輯結(jié)構(gòu)，其物理結(jié)構(gòu)可以是數(shù)組，也可以是鏈表，即棧結(jié)構(gòu)分為順序棧和鏈?zhǔn)綏！?/p>
核心類(lèi)庫(kù)中的棧結(jié)構(gòu)有Stack和LinkdeList。Stack就是順序棧，它是Vector的子類(lèi)。LinkedList是鏈?zhǔn)綏！?/p>
體現(xiàn)棧結(jié)構(gòu)的操作方法：
* peek()方法：查看棧頂元素，不彈出
* pop()方法：彈出棧
* push(E e)方法：壓入棧
```java
package com.atguigu.list;
import org.junit.Test;
import java.util.LinkedList;
import java.util.Stack;
public class TestStack {
@Test
public void test1(){
Stack<Integer> list = new Stack<>();
list.push(1);
list.push(2);
list.push(3);
System.out.println("list = " + list);
System.out.println("list.peek()=" + list.peek());
System.out.println("list.peek()=" + list.peek());
System.out.println("list.peek()=" + list.peek());
/*
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
*/
while(!list.empty()){
System.out.println("list.pop() =" + list.pop());
}
}
@Test
public void test2(){
LinkedList<Integer> list = new LinkedList<>();
list.push(1);
list.push(2);
list.push(3);
System.out.println("list = " + list);
System.out.println("list.peek()=" + list.peek());
System.out.println("list.peek()=" + list.peek());
System.out.println("list.peek()=" + list.peek());
/*
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());
System.out.println("list.pop() =" + list.pop());//java.util.NoSuchElementException
*/
while(!list.isEmpty()){
System.out.println("list.pop() =" + list.pop());
}
}
}
```### 11.4.2 隊(duì)列
隊(duì)列（Queue）是一種（但并非一定）先進(jìn)先出（FIFO）的結(jié)構(gòu)。
隊(duì)列是邏輯結(jié)構(gòu)，其物理結(jié)構(gòu)可以是數(shù)組，也可以是鏈表。隊(duì)列有普通隊(duì)列、雙端隊(duì)列、并發(fā)隊(duì)列等等，核心類(lèi)庫(kù)中的隊(duì)列實(shí)現(xiàn)類(lèi)有很多（后面會(huì)學(xué)到很多），LinkdeList是雙端隊(duì)列的實(shí)現(xiàn)類(lèi)。
==Queue==除了基本的 `Collection`操作外，==隊(duì)列==還提供其他的插入、提取和檢查操作。每個(gè)方法都存在兩種形式：一種拋出異常（操作失敗時(shí)），另一種返回一個(gè)特殊值（`null` 或 `false`，具體取決于操作）。`Queue` 實(shí)現(xiàn)通常不允許插入 元素，盡管某些實(shí)現(xiàn)（如 ）并不禁止插入 。即使在允許 null 的實(shí)現(xiàn)中，也不應(yīng)該將 插入到 中，因?yàn)? 也用作 方法的一個(gè)特殊返回值，表明隊(duì)列不包含元素。
| | *拋出異常* | *返回特殊值* |
| ---- | ---------- | ------------ |
| 插入 | add(e) | offer(e) |
| 移除 | remove() | poll() |
| 檢查 | element() | peek() |
==Deque==，名稱 *deque* 是“double ended queue==（雙端隊(duì)列）==”的縮寫(xiě)，通常讀為“deck”。此接口定義在雙端隊(duì)列兩端訪問(wèn)元素的方法。提供插入、移除和檢查元素的方法。每種方法都存在兩種形式：一種形式在操作失敗時(shí)拋出異常，另一種形式返回一個(gè)特殊值（`null` 或 `false`，具體取決于操作）。Deque接口的實(shí)現(xiàn)類(lèi)有ArrayDeque和LinkedList，它們一個(gè)底層是使用數(shù)組實(shí)現(xiàn)，一個(gè)使用雙向鏈表實(shí)現(xiàn)。
| | **第一個(gè)元素（頭部）** | | **最后一個(gè)元素（尾部）** | |
| -------- | ---------------------- | ------------- | ------------------------ | ------------ |
| | *拋出異常* | *特殊值* | *拋出異常* | *特殊值* |
| **插入** | addFirst(e) | offerFirst(e) | addLast(e) | offerLast(e) |
| **移除** | removeFirst() | pollFirst() | removeLast() | pollLast() |
| **檢查** | getFirst() | peekFirst() | getLast() | peekLast() |
此接口擴(kuò)展了 `Queue`接口。在將雙端隊(duì)列用作隊(duì)列時(shí)，將得到 FIFO（先進(jìn)先出）行為。將元素添加到雙端隊(duì)列的末尾，從雙端隊(duì)列的開(kāi)頭移除元素。從 `Queue` 接口繼承的方法完全等效于 `Deque` 方法，如下表所示：
| **`Queue` 方法** | **等效 `Deque` 方法** |
| ---------------- | --------------------- |
| add(e) | addLast(e) |
| offer(e) | offerLast(e) |
| remove() | removeFirst() |
| poll() | pollFirst() |
| element() | getFirst() |
| peek() | peekFirst() |
雙端隊(duì)列也可用作 LIFO（后進(jìn)先出）堆棧。應(yīng)優(yōu)先使用此接口而不是遺留 `Stack` 類(lèi)。在將雙端隊(duì)列用作堆棧時(shí)，元素被推入雙端隊(duì)列的開(kāi)頭并從雙端隊(duì)列開(kāi)頭彈出。堆棧方法完全等效于 `Deque` 方法，如下表所示：
| **堆棧方法** | **等效 `Deque` 方法** |
| ------------ | --------------------- |
| push(e) | addFirst(e) |
| pop() | removeFirst() |
| peek() | peekFirst() |
結(jié)論：Deque接口的實(shí)現(xiàn)類(lèi)既可以用作FILO堆棧使用，又可以用作FIFO隊(duì)列使用。
```java
package com.atguigu.queue;
import java.util.LinkedList;
public class TestQueue {
public static void main(String[] args) {
LinkedList<String> list = new LinkedList<>();
list.addLast("張三");
list.addLast("李四");
list.addLast("王五");
list.addLast("趙六");
while (!list.isEmpty()){
System.out.println("list.removeFirst()=" + list.removeFirst());
}
}
}
```
## 11.5 Map
### 11.5.1 概述
現(xiàn)實(shí)生活中，我們常會(huì)看到這樣的一種集合：IP地址與主機(jī)名，身份證號(hào)與個(gè)人，系統(tǒng)用戶名與系統(tǒng)用戶對(duì)象等，這種一一對(duì)應(yīng)的關(guān)系，就叫做映射。Java提供了專門(mén)的集合類(lèi)用來(lái)存放這種對(duì)象關(guān)系的對(duì)象，即`java.util.Map<K,V>`接口。Map接口的常用實(shí)現(xiàn)類(lèi)：HashMap、TreeMap、LinkedHashMap和Properties。其中HashMap是 Map 接口使用頻率最高的實(shí)現(xiàn)類(lèi)。
我們通過(guò)查看`Map`接口描述，發(fā)現(xiàn)`Map<K,V>`接口下的集合與`Collection<E>`接口下的集合，它們存儲(chǔ)數(shù)據(jù)的形式不同。
* `Collection`中的集合，元素是孤立存在的（理解為單身），向集合中存儲(chǔ)元素采用一個(gè)個(gè)元素的方式存儲(chǔ)。
* `Map`中的集合，元素是成對(duì)存在的(理解為夫妻)。每個(gè)元素由鍵與值兩部分組成，通過(guò)鍵可以找對(duì)所對(duì)應(yīng)的值。
* `Collection`中的集合稱為單列集合，`Map`中的集合稱為雙列集合。
* 需要注意的是，`Map`中的集合不能包含重復(fù)的鍵，值可以重復(fù)；每個(gè)鍵只能對(duì)應(yīng)一個(gè)值（這個(gè)值可以是單個(gè)值，也可以是個(gè)數(shù)組或集合值）。
### 11.5.2 Map常用方法
1、添加操作
* V put(K key,V value)：添加一對(duì)鍵值對(duì)
* void putAll(Map<? extends K,? extends V> m)：添加一組鍵值對(duì)
2、刪除
* void clear()：清空map
* V remove(Object key)：根據(jù)key刪除一對(duì)鍵值對(duì)
* default boolean remove(Object key,Object value)：刪除匹配的(key,value)
3、修改value（JDK1.8新增）
- default V replace(K key, V value)：找到目標(biāo)key，替換value
- default boolean replace(K key,V oldValue,V newValue)：找到目標(biāo)(key,value)，替換value
- default void replaceAll(BiFunction<? super K,? super V,? extends V> function)：按照指定要求替換value
4、元素查詢的操作
* V get(Object key)：根據(jù)key返回value
* boolean containsKey(Object key)：判斷key是否存在
* boolean containsValue(Object value)：判斷value是否存在
* boolean isEmpty()：判斷map是否為空
* int size()：獲取鍵值對(duì)的數(shù)量
5、遍歷
Map的遍歷，不能支持foreach，因?yàn)镸ap接口沒(méi)有繼承java.lang.Iterable<T>接口。只能用如下方式遍歷：
（1）分開(kāi)遍歷：
* 單獨(dú)遍歷所有key：Set<K> keySet()
* 單獨(dú)遍歷所有value：Collection<V> values()
（2）成對(duì)遍歷：
* 遍歷所有鍵值對(duì)：Set<Map.Entry<K,V>> entrySet()
* 遍歷的是映射關(guān)系Map.Entry類(lèi)型的對(duì)象，Map.Entry是Map接口的內(nèi)部接口。每一種Map內(nèi)部有自己的Map.Entry的實(shí)現(xiàn)類(lèi)。在Map中存儲(chǔ)數(shù)據(jù)，實(shí)際上是將Key---->value的數(shù)據(jù)存儲(chǔ)在Map.Entry接口的實(shí)例中，再在Map集合中插入Map.Entry的實(shí)例化對(duì)象，如圖示：
（3）調(diào)用forEach方法遍歷
- default void forEach(BiConsumer<? super K,? super V> action)
```java
package com.atguigu.map;
import org.junit.Test;
import java.util.HashMap;
import java.util.function.BiFunction;
public class TestMapMethod {
@Test
public void test1(){
//創(chuàng)建 map對(duì)象
HashMap<String, String> map = new HashMap<String, String>();
//添加元素到集合
map.put("黃曉明", "楊穎");
map.put("文章", "馬伊琍");
map.put("文章", "姚笛");
map.put("鄧超", "孫儷");
System.out.println(map.size());
System.out.println(map);
}
@Test
public void test2(){
HashMap<String, String> map = new HashMap<String, String>();
//添加模范夫妻
map.put("黃曉明", "楊穎");
map.put("文章", "馬伊琍");
map.put("鄧超", "孫儷");
System.out.println(map);
//刪除鍵值對(duì)
map.remove("文章");
System.out.println(map);
map.remove("黃曉明","楊穎");
System.out.println(map);
}
@Test
public void test3(){
HashMap<String, String> map = new HashMap<String, String>();
//添加夫妻
map.put("黃曉明", "楊穎");
map.put("文章", "馬伊琍");
map.put("鄧超", "孫儷");
map.put("張三", null);
System.out.println(map);
//修改value
map.replace("文章","姚笛");
System.out.println(map);
map.replace("黃曉明","楊穎", "angelababy");
System.out.println(map);
map.replaceAll(new BiFunction<String, String, String>() {
@Override
public String apply(String key, String value) {
return value == null ? "如花" : value;
}
});
System.out.println(map);
}
@Test
public void test4(){
HashMap<String, String> map = new HashMap<String, String>();
//添加元素到集合
map.put("黃曉明", "楊穎");
map.put("文章", "馬伊琍");
map.put("鄧超", "孫儷");
// 想要查看 誰(shuí)的媳婦 是誰(shuí)
System.out.println(map.get("黃曉明"));
System.out.println(map.get("鄧超"));
}
@Test
public void test4(){
HashMap<String, String> map = new HashMap<String, String>();
//添加元素到集合
map.put("黃曉明", "楊穎");
map.put("文章", "馬伊琍");
map.put("鄧超", "孫儷");
//遍歷所有key
System.out.println("所有key：");
Set<String> keySet = map.keySet();
for (String key : keySet) {
System.out.println(key);
}
//遍歷所有value
System.out.println("所有value：");
Collection<String> values = map.values();
for (String value : values) {
System.out.println(value);
}
//遍歷所有鍵值對(duì)
System.out.println("所有鍵值對(duì)：");
Set<Map.Entry<String, String>> entries = map.entrySet();
for (Map.Entry<String, String> entry : entries) {
System.out.println(entry);
}
//調(diào)用forEach方法遍歷所有鍵值對(duì)
System.out.println("所有鍵值對(duì)：");
BiConsumer<String,String> c = new BiConsumer<>() {
@Override
public void accept(String key, String value) {
System.out.println(key+" vs "+value);
}
};
map.forEach(c);
}
}
```### 11.5.3 Map接口的實(shí)現(xiàn)類(lèi)們
#### **1、HashMap和Hashtable**
HashMap和Hashtable都是哈希表。HashMap和Hashtable判斷兩個(gè) key 相等的標(biāo)準(zhǔn)是：兩個(gè) key 的hashCode 值相等，并且 equals() 方法也返回 true。因此，為了成功地在哈希表中存儲(chǔ)和獲取對(duì)象，用作鍵的對(duì)象必須實(shí)現(xiàn) hashCode 方法和 equals 方法。
* Hashtable是線程安全的，任何非 null 對(duì)象都可以用作鍵或值。
* HashMap是線程不安全的，并允許使用 null 值和 null 鍵。
示例代碼：添加員工姓名為key，薪資為value
```java
package com.atguigu.map;
import org.junit.Test;
import java.util.HashMap;
import java.util.Hashtable;
import java.util.Map;
import java.util.Set;
public class TestHashMap {
@Test
public void test01(){
HashMap<String,Double> map = new HashMap<>();
map.put("張三", 10000.0);
//key相同，新的value會(huì)覆蓋原來(lái)的value
//因?yàn)镾tring重寫(xiě)了hashCode和equals方法
map.put("張三", 12000.0);
map.put("李四", 14000.0);
//HashMap支持key和value為null值
String name = null;
Double salary = null;
map.put(name, salary);
System.out.println(map);
}
@Test
public void test02(){
Hashtable<String,Double> map = new Hashtable<>();
map.put("張三", 10000.0);
//key相同，新的value會(huì)覆蓋原來(lái)的value
//因?yàn)镾tring重寫(xiě)了hashCode和equals方法
map.put("張三", 12000.0);
map.put("李四", 14000.0);
//Hashtable不支持key和value為null值
/*String name = null;
Double salary = null;
map.put(name, salary);*/
System.out.println(map);
}
}
```#### **2、LinkedHashMap**
LinkedHashMap 是 HashMap 的子類(lèi)。此實(shí)現(xiàn)與 HashMap 的不同之處在于，后者維護(hù)著一個(gè)運(yùn)行于所有條目的雙重鏈接列表。此鏈接列表定義了迭代順序，該迭代順序通常就是將鍵插入到映射中的順序（插入順序）。
示例代碼：添加員工姓名為key，薪資為value
```java
package com.atguigu.map;
import java.util.LinkedHashMap;
import java.util.Map;
import java.util.Set;
public class TestLinkedHashMap {
public static void main(String[] args) {
LinkedHashMap<String,Double> map = new LinkedHashMap<>();
map.put("張三", 10000.0);
//key相同，新的value會(huì)覆蓋原來(lái)的value
//因?yàn)镾tring重寫(xiě)了hashCode和equals方法
map.put("張三", 12000.0);
map.put("李四", 14000.0);
//HashMap支持key和value為null值
String name = null;
Double salary = null;
map.put(name, salary);
System.out.println(map);
}
}
```#### **3、TreeMap**
基于紅黑樹(shù)（Red-Black tree）的 NavigableMap 實(shí)現(xiàn)。該映射根據(jù)其鍵的自然順序進(jìn)行排序，或者根據(jù)創(chuàng)建映射時(shí)提供的 Comparator 進(jìn)行排序，具體取決于使用的構(gòu)造方法。
代碼示例：添加員工姓名為key，薪資為value
```java
package com.atguigu.map;
import java.util.Comparator;
import java.util.Map.Entry;
import java.util.Set;
import java.util.TreeMap;
import org.junit.Test;
public class TestTreeMap {
@Test
public void test1() {
TreeMap<String,Integer> map = new TreeMap<>();
map.put("Jack", 11000);
map.put("Alice", 12000);
map.put("zhangsan", 13000);
map.put("baitao", 14000);
map.put("Lucy", 15000);
//String實(shí)現(xiàn)了Comparable接口，默認(rèn)按照Unicode編碼值排序
System.out.println(map);
}
@Test
public void test2() {
//指定定制比較器Comparator，按照Unicode編碼值排序，但是忽略大小寫(xiě)
TreeMap<String,Integer> map = new TreeMap<>(new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o1.compareToIgnoreCase(o2);
}
});
map.put("Jack", 11000);
map.put("Alice", 12000);
map.put("zhangsan", 13000);
map.put("baitao", 14000);
map.put("Lucy", 15000);
System.out.println(map);
}
}
```#### **4、Properties**
Properties 類(lèi)是 Hashtable 的子類(lèi)，Properties 可保存在流中或從流中加載。屬性列表中每個(gè)鍵及其對(duì)應(yīng)值都是一個(gè)字符串。
存取數(shù)據(jù)時(shí)，建議使用setProperty(String key,String value)方法和getProperty(String key)方法。
代碼示例：
```java
package com.atguigu.map;
import org.junit.Test;
import java.util.Properties;
public class TestProperties {
@Test
public void test01() {
Properties properties = System.getProperties();
String fileEncoding = properties.getProperty("file.encoding");//當(dāng)前源文件字符編碼
System.out.println("fileEncoding = " + fileEncoding);
}
@Test
public void test02() {
Properties properties = new Properties();
properties.setProperty("user","chai");
properties.setProperty("password","123456");
System.out.println(properties);
}
}
```### 11.5.4 Set集合與Map集合的關(guān)系
Set的內(nèi)部實(shí)現(xiàn)其實(shí)是一個(gè)Map。即HashSet的內(nèi)部實(shí)現(xiàn)是一個(gè)HashMap，TreeSet的內(nèi)部實(shí)現(xiàn)是一個(gè)TreeMap，LinkedHashSet的內(nèi)部實(shí)現(xiàn)是一個(gè)LinkedHashMap。
部分源代碼摘要：
HashSet源碼：
```java
public HashSet() {
map = new HashMap<>();
}
public HashSet(Collection<? extends E> c) {
map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
addAll(c);
}
public HashSet(int initialCapacity, float loadFactor) {
map = new HashMap<>(initialCapacity, loadFactor);
}
public HashSet(int initialCapacity) {
map = new HashMap<>(initialCapacity);
}
//這個(gè)構(gòu)造器是給子類(lèi)LinkedHashSet調(diào)用的
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
map = new LinkedHashMap<>(initialCapacity, loadFactor);
}
```LinkedHashSet源碼：
```java
public LinkedHashSet(int initialCapacity, float loadFactor) {
super(initialCapacity, loadFactor, true);//調(diào)用HashSet的某個(gè)構(gòu)造器
}
public LinkedHashSet(int initialCapacity) {
super(initialCapacity, .75f, true);//調(diào)用HashSet的某個(gè)構(gòu)造器
}
public LinkedHashSet() {
super(16, .75f, true);
}
public LinkedHashSet(Collection<? extends E> c) {
super(Math.max(2*c.size(), 11), .75f, true);//調(diào)用HashSet的某個(gè)構(gòu)造器
addAll(c);
}
```TreeSet源碼：
```java
public TreeSet() {
this(new TreeMap<E,Object>());
}
public TreeSet(Comparator<? super E> comparator) {
this(new TreeMap<>(comparator));
}
public TreeSet(Collection<? extends E> c) {
this();
addAll(c);
}
public TreeSet(SortedSet<E> s) {
this(s.comparator());
addAll(s);
}
```但是，咱們存到Set中只有一個(gè)元素，又是怎么變成(key,value)的呢？
以HashSet中的源碼為例：
```java
private static final Object PRESENT = new Object();
public boolean add(E e) {
return map.put(e, PRESENT)==null;
}
public Iterator<E> iterator() {
return map.keySet().iterator();
}
```原來(lái)是，把添加到Set中的元素作為內(nèi)部實(shí)現(xiàn)map的key，然后用一個(gè)常量對(duì)象PRESENT對(duì)象，作為value。
這是因?yàn)镾et的元素不可重復(fù)和Map的key不可重復(fù)有相同特點(diǎn)。Map有一個(gè)方法keySet()可以返回所有key。
### 11.5.5 哈希表的原理分析
#### 1、二叉樹(shù)了解
二叉樹(shù)（Binary tree）是樹(shù)形結(jié)構(gòu)的一個(gè)重要類(lèi)型。二叉樹(shù)特點(diǎn)是每個(gè)結(jié)點(diǎn)最多只能有兩棵子樹(shù)，且有左右之分。許多實(shí)際問(wèn)題抽象出來(lái)的數(shù)據(jù)結(jié)構(gòu)往往是二叉樹(shù)形式，二叉樹(shù)的存儲(chǔ)結(jié)構(gòu)及其算法都較為簡(jiǎn)單，因此二叉樹(shù)顯得特別重要。
前序遍歷：ABDHIECFG
中序遍歷：HDIBEAFCG
后序遍歷：HIDEBFGCA
以下是幾種經(jīng)典的二叉樹(shù)：
1、滿二叉樹(shù)： 除最后一層無(wú)任何子節(jié)點(diǎn)外，每一層上的所有結(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn)的二叉樹(shù)。 第n層的結(jié)點(diǎn)數(shù)是2的n-1次方，總的結(jié)點(diǎn)個(gè)數(shù)是2的n次方-1
2、完全二叉樹(shù)： 葉結(jié)點(diǎn)只能出現(xiàn)在最底層的兩層，且最底層葉結(jié)點(diǎn)均處于次底層葉結(jié)點(diǎn)的左側(cè)。
3、平衡二叉樹(shù)：平衡二叉樹(shù)（Self-balancing binary search tree）又被稱為AVL樹(shù)（有別于AVL算法），且具有以下性質(zhì)：它是一 棵空樹(shù)或它的左右兩個(gè)子樹(shù)的高度差的絕對(duì)值不超過(guò)1，并且左右兩個(gè)子樹(shù)都是一棵平衡二叉樹(shù)， 但不要求非葉節(jié)點(diǎn)都有兩個(gè)子結(jié)點(diǎn) 。平衡二叉樹(shù)的常用實(shí)現(xiàn)方法有紅黑樹(shù)、AVL、替罪羊樹(shù)、Treap、伸展樹(shù)等。例如紅黑樹(shù)的要求：
- 節(jié)點(diǎn)是紅色或者黑色
- 根節(jié)點(diǎn)是黑色
- 每個(gè)葉子的節(jié)點(diǎn)都是黑色的空節(jié)點(diǎn)（NULL）
- 每個(gè)紅色節(jié)點(diǎn)的兩個(gè)子節(jié)點(diǎn)都是黑色的。
- 從任意節(jié)點(diǎn)到其每個(gè)葉子的所有路徑都包含相同的黑色節(jié)點(diǎn)數(shù)量。
當(dāng)我們插入或刪除節(jié)點(diǎn)時(shí)，可能會(huì)破壞已有的紅黑樹(shù)，使得它不滿足以上5個(gè)要求，那么此時(shí)就需要進(jìn)行處理：
1、recolor ：將某個(gè)節(jié)點(diǎn)變紅或變黑
2、rotation ：將紅黑樹(shù)某些結(jié)點(diǎn)分支進(jìn)行旋轉(zhuǎn)（左旋或右旋）
使得它繼續(xù)滿足以上的5個(gè)要求。
例如：插入了結(jié)點(diǎn)21之后，紅黑樹(shù)處理成：
#### 2、 哈希表的數(shù)據(jù)結(jié)構(gòu)
請(qǐng)看PPT
## 11.6 集合框架
## 11.7 Collections工具類(lèi)
參考操作數(shù)組的工具類(lèi)：Arrays。
Collections 是一個(gè)操作 Set、List 和 Map 等集合的工具類(lèi)。Collections 中提供了一系列靜態(tài)的方法對(duì)集合元素進(jìn)行排序、查詢和修改等操作，還提供了對(duì)集合對(duì)象設(shè)置不可變、對(duì)集合對(duì)象實(shí)現(xiàn)同步控制等方法：
* public static <T> boolean addAll(Collection<? super T> c,T... elements)將所有指定元素添加到指定 collection 中。
* public static <T> int binarySearch(List<? extends Comparable<? super T>> list,T key)在List集合中查找某個(gè)元素的下標(biāo)，但是List的元素必須是T或T的子類(lèi)對(duì)象，而且必須是可比較大小的，即支持自然排序的。而且集合也事先必須是有序的，否則結(jié)果不確定。
* public static <T> int binarySearch(List<? extends T> list,T key,Comparator<? super T> c)在List集合中查找某個(gè)元素的下標(biāo)，但是List的元素必須是T或T的子類(lèi)對(duì)象，而且集合也事先必須是按照c比較器規(guī)則進(jìn)行排序過(guò)的，否則結(jié)果不確定。
* public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)在coll集合中找出最大的元素，集合中的對(duì)象必須是T或T的子類(lèi)對(duì)象，而且支持自然排序
* public static <T> T max(Collection<? extends T> coll,Comparator<? super T> comp)在coll集合中找出最大的元素，集合中的對(duì)象必須是T或T的子類(lèi)對(duì)象，按照比較器comp找出最大者
* public static void reverse(List<?> list)反轉(zhuǎn)指定列表List中元素的順序。
* public static void shuffle(List<?> list) List 集合元素進(jìn)行隨機(jī)排序，類(lèi)似洗牌
* public static <T extends Comparable<? super T>> void sort(List<T> list)根據(jù)元素的自然順序?qū)χ付?List 集合元素按升序排序
* public static <T> void sort(List<T> list,Comparator<? super T> c)根據(jù)指定的 Comparator 產(chǎn)生的順序?qū)?List 集合元素進(jìn)行排序
* public static void swap(List<?> list,int i,int j)將指定 list 集合中的 i 處元素和 j 處元素進(jìn)行交換
* public static int frequency(Collection<?> c,Object o)返回指定集合中指定元素的出現(xiàn)次數(shù)
* public static <T> void copy(List<? super T> dest,List<? extends T> src)將src中的內(nèi)容復(fù)制到dest中
* public static <T> boolean replaceAll(List<T> list，T oldVal，T newVal)：使用新值替換 List 對(duì)象的所有舊值
* Collections 類(lèi)中提供了多個(gè) synchronizedXxx() 方法，該方法可使將指定集合包裝成線程同步的集合，從而可以解決多線程并發(fā)訪問(wèn)集合時(shí)的線程安全問(wèn)題
* Collections類(lèi)中提供了多個(gè)unmodifiableXxx()方法，該方法返回指定 Xxx的不可修改的視圖。
```java
package com.atguigu.collections;
import org.junit.Test;
import java.text.Collator;
import java.util.*;
public class TestCollections {
@Test
public void test11(){
/*
public static <T> boolean replaceAll(List<T> list，T oldVal，T newVal)：使用新值替換 List 對(duì)象的所有舊值
*/
List<String> list = new ArrayList<>();
Collections.addAll(list,"hello","java","world","hello","hello");
Collections.replaceAll(list, "hello","chai");
System.out.println(list);
}
@Test
public void test10(){
List<Integer> list = new ArrayList<>();
for(int i=1; i<=5; i++){//1-5
list.add(i);
}
List<Integer> list2 = new ArrayList<>();
for(int i=11; i<=13; i++){//11-13
list2.add(i);
}
list.addAll(list2);
System.out.println(list);//[1, 2, 3, 4, 5, 11, 12, 13]
}
@Test
public void test09(){
/*
* public static <T> void copy(List<? super T> dest,List<? extends T> src)將src中的內(nèi)容復(fù)制到dest中
*/
List<Integer> list = new ArrayList<>();
for(int i=1; i<=5; i++){//1-5
list.add(i);
}
List<Integer> list2 = new ArrayList<>();
for(int i=11; i<=13; i++){//11-13
list2.add(i);
}
Collections.copy(list, list2);
System.out.println(list);
List<Integer> list3 = new ArrayList<>();
for(int i=11; i<=20; i++){//11-20
list3.add(i);
}
Collections.copy(list, list3);//java.lang.IndexOutOfBoundsException: Source does not fit in dest
System.out.println(list);
}
@Test
public void test08(){
/*
public static int frequency(Collection<?> c,Object o)返回指定集合中指定元素的出現(xiàn)次數(shù)
*/
List<String> list = new ArrayList<>();
Collections.addAll(list,"hello","java","world","hello","hello");
int count = Collections.frequency(list, "hello");
System.out.println("count = " + count);
}
@Test
public void test07(){
/*
public static void swap(List<?> list,int i,int j)將指定 list 集合中的 i 處元素和 j 處元素進(jìn)行交換
*/
List<String> list = new ArrayList<>();
Collections.addAll(list,"hello","java","world");
Collections.swap(list,0,2);
System.out.println(list);
}
@Test
public void test06() {
/*
* public static <T extends Comparable<? super T>> void sort(List<T> list)根據(jù)元素的自然順序?qū)χ付?List 集合元素按升序排序
* public static <T> void sort(List<T> list,Comparator<? super T> c)根據(jù)指定的 Comparator 產(chǎn)生的順序?qū)?List 集合元素進(jìn)行排序
*/
List<Man> list = new ArrayList<>();
list.add(new Man("張三",23));
list.add(new Man("李四",24));
list.add(new Man("王五",25));
Collections.sort(list);
System.out.println(list);
Collections.sort(list, new Comparator<Man>() {
@Override
public int compare(Man o1, Man o2) {
return Collator.getInstance(Locale.CHINA).compare(o1.getName(),o2.getName());
}
});
System.out.println(list);
}
@Test
public void test05(){
/*
public static void shuffle(List<?> list) List 集合元素進(jìn)行隨機(jī)排序，類(lèi)似洗牌，打亂順序
*/
List<String> list = new ArrayList<>();
Collections.addAll(list,"hello","java","world");
Collections.shuffle(list);
System.out.println(list);
}
@Test
public void test04(){
/*
public static void reverse(List<?> list)反轉(zhuǎn)指定列表List中元素的順序。
*/
List<String> list = new ArrayList<>();
Collections.addAll(list,"hello","java","world");
System.out.println(list);
Collections.reverse(list);
System.out.println(list);
}
@Test
public void test03(){
/*
* public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
* <T extends Object & Comparable<? super T>>：要求T必須繼承Object，又實(shí)現(xiàn)Comparable接口，或者T的父類(lèi)實(shí)現(xiàn)Comparable接口
* 在coll集合中找出最大的元素，集合中的對(duì)象必須是T或T的子類(lèi)對(duì)象，而且支持自然排序
* public static <T> T max(Collection<? extends T> coll,Comparator<? super T> comp)
* 在coll集合中找出最大的元素，集合中的對(duì)象必須是T或T的子類(lèi)對(duì)象，按照比較器comp找出最大者
*
*/
List<Man> list = new ArrayList<>();
list.add(new Man("張三",23));
list.add(new Man("李四",24));
list.add(new Man("王五",25));
/*Man max = Collections.max(list);//要求Man實(shí)現(xiàn)Comparable接口，或者父類(lèi)實(shí)現(xiàn)
System.out.println(max);*/
Man max = Collections.max(list, new Comparator<Man>() {
@Override
public int compare(Man o1, Man o2) {
return o2.getAge()-o2.getAge();
}
});
System.out.println(max);
}
@Test
public void test02(){
/*
* public static <T> int binarySearch(List<? extends Comparable<? super T>> list,T key)
* 要求List集合的元素類(lèi)型 實(shí)現(xiàn)了 Comparable接口，這個(gè)實(shí)現(xiàn)可以是T類(lèi)型本身也可以T的父類(lèi)實(shí)現(xiàn)這個(gè)接口。
* 說(shuō)明List中的元素支持自然排序功能。
* 在List集合中查找某個(gè)元素的下標(biāo)，但是List的元素必須是T或T的子類(lèi)對(duì)象，而且必須是可比較大小的，即支持自然排序的。而且集合也事先必須是有序的，否則結(jié)果不確定。
* public static <T> int binarySearch(List<? extends T> list,T key,Comparator<? super T> c)
* 說(shuō)明List集合中元素的類(lèi)型<=T，Comparator<? super T>說(shuō)明要傳入一個(gè)Comparator接口的實(shí)現(xiàn)類(lèi)對(duì)象，實(shí)現(xiàn)類(lèi)泛型的指定要求>=T
* 例如：List中存儲(chǔ)的是Man（男）對(duì)象，T可以是Person類(lèi)型，實(shí)現(xiàn)Comparator的時(shí)候可以是 Comparator<Person>
* 例如：List中存儲(chǔ)的是Man（男）對(duì)象，T可以是Man類(lèi)型，實(shí)現(xiàn)Comparator的時(shí)候可以是 Comparator<Person>
* 在List集合中查找某個(gè)元素的下標(biāo)，但是List的元素必須是T或T的子類(lèi)對(duì)象，而且集合也事先必須是按照c比較器規(guī)則進(jìn)行排序過(guò)的，否則結(jié)果不確定。
*
* 二分查找要求數(shù)組或List必須是“有大小順序”。
* 二分查找的思路： 和[mid]元素比較，如果相同，就找到了，不相同要看大小關(guān)系，決定去左邊還是右邊繼續(xù)查找。
*/
List<Man> list = new ArrayList<>();
list.add(new Man("張三",23));
list.add(new Man("李四",24));
list.add(new Man("王五",25));
// int index = Collections.binarySearch(list, new Man("王五", 25));//要求實(shí)現(xiàn)Comparable接口
// System.out.println(index);
int index = Collections.binarySearch(list, new Man("王五", 25), new Comparator<Person>() {
@Override
public int compare(Person o1, Person o2) {
return o1.getAge() - o2.getAge();
}
});
System.out.println(index);
}
@Test
public void test01(){
/*
public static <T> boolean addAll(Collection<? super T> c,T... elements)將所有指定元素添加到指定 collection 中。
Collection的集合的元素類(lèi)型必須>=T類(lèi)型
*/
Collection<Object> coll = new ArrayList<>();
Collections.addAll(coll, "hello","java");
Collections.addAll(coll, 1,2,3,4);
Collection<String> coll2 = new ArrayList<>();
Collections.addAll(coll2, "hello","java");
// Collections.addAll(coll2, 1,2,3,4);//String和Integer之間沒(méi)有父子類(lèi)關(guān)系
}
}
```## 11.8 Arrays工具類(lèi)
public static <T> List<T> asList(T... a)：將指定元素添加到一個(gè)固定大小的列表中，并返回列表。
```java
@Test
public void test(){
List<String> list = Arrays.asList("hello", "java", "world");
System.out.println(list);
try {
list.add("chai");
} catch (Exception e) {
e.printStackTrace();
}
try {
list.remove("hello");
} catch (Exception e) {
e.printStackTrace();
}
}
```
