集合框架使用集合做什么集合的分類具體的實(shí)現(xiàn)類ListArrayListLinkedListSetTreeSetMapHashMapTreeMap數(shù)組窿祥、List彼宠、Set贞间、Map的數(shù)據(jù)轉(zhuǎn)換數(shù)組轉(zhuǎn) List數(shù)組和Set從Map中得到Set和List散列表（哈希表）的基本原理散列表是如何根據(jù)Key來(lái)快速找到它所匹配的 Value 呢 ？散列表的讀寫(xiě)操作寫(xiě)操作（put）讀操作（get）IteratorCollections排序查找排序List 集合排序TreeMap 排序自定義類排序外部指定排序本身?yè)碛信判?
# 集合框架

程序開(kāi)發(fā)并不是解決了業(yè)務(wù)的基本功能就完成了良姆，很多時(shí)候程序運(yùn)行的環(huán)境是有限制的。比如內(nèi)存小，CPU頻率低沟娱，或者是像手機(jī)這樣的設(shè)備壹罚，能源供應(yīng)有限葛作。在這種環(huán)境下，就需要程序能夠在有限的環(huán)境中提升效率猖凛。這就需要使用數(shù)據(jù)結(jié)構(gòu)和算法进鸠。

但是數(shù)據(jù)結(jié)構(gòu)與算法即便是學(xué)過(guò)，也未必在工作時(shí)能夠用好形病，而且通用性客年、性能等等也都是問(wèn)題。加上學(xué)習(xí)程序開(kāi)發(fā)的受眾群體越來(lái)越廣漠吻，讓程序員全部自己實(shí)現(xiàn)數(shù)據(jù)結(jié)構(gòu)與算法不是一個(gè)好的主意量瓜。所以現(xiàn)在很多語(yǔ)言為了能夠提升學(xué)習(xí)效率，降低學(xué)習(xí)門(mén)檻途乃，同時(shí)也為了讓程序有更好的執(zhí)行效率和通用性绍傲，就自帶了各種實(shí)現(xiàn)了數(shù)據(jù)結(jié)構(gòu)與算法的API集合。在Java中耍共，這就是我們現(xiàn)在要學(xué)習(xí)的「集合框架」

與現(xiàn)在常見(jiàn)到的數(shù)據(jù)結(jié)構(gòu)類庫(kù)一樣烫饼，Java也是將集合類庫(kù)的接口（interface）與實(shí)現(xiàn)（implementation）分離。所以我們的學(xué)習(xí)方式一般都是先搞明白接口的分類和關(guān)系试读，然后根據(jù)不同的接口來(lái)學(xué)習(xí)對(duì)應(yīng)的實(shí)現(xiàn)類杠纵。

## 使用集合做什么

1.  搬運(yùn)數(shù)據(jù)，集合可以存儲(chǔ)數(shù)據(jù)钩骇，然后通過(guò)API調(diào)用很方便就可以傳遞大量數(shù)據(jù)

2.  數(shù)據(jù)處理比藻，集合中可以直接對(duì)數(shù)據(jù)進(jìn)行操作铝量，比如統(tǒng)計(jì)、去重

3.  排序银亲，可以將數(shù)據(jù)按照需求進(jìn)行各種排序慢叨，然后再傳遞給調(diào)用者

## 集合的分類

Java的集合從 Collection 接口和 Map 接口入手

Map 接口和 Collection 沒(méi)有交集，它有自己的方式务蝠，只要標(biāo)準(zhǔn)庫(kù)后綴不是Map 結(jié)尾的拍谐，都是直接或者間接實(shí)現(xiàn)了Collection接口。

Collection 接口中常見(jiàn)的操作是數(shù)據(jù)的添加馏段、刪除

1.  add / addAll

2.  remove / removeAll / removeIf

借助 Iterator 接口赠尾，Collection 還具備了數(shù)據(jù)的循環(huán)

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n29" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public interface Collection<E> extends Iterable<E>{ 
 //... 
 //  對(duì)數(shù)據(jù)循環(huán)
 Iterator<E> iterator();
}</pre>

通過(guò) Iterable 接口， 標(biāo)準(zhǔn)庫(kù)中的集合都可以使用 forEach 循環(huán)毅弧。

## 具體的實(shí)現(xiàn)類

| 集合類型 | 描述 |
| --- | --- |
| ArrayList | 一種可以動(dòng)態(tài)增長(zhǎng)和縮減的索引序列 |
| LinkedList | 一種可以在任何位置進(jìn)行高效地插人和刪除操作的有序序列 |
| ArrayDeque | 一種用循環(huán)數(shù)組實(shí)現(xiàn)的雙端隊(duì)列 |
| HashSet | 一種沒(méi)有重復(fù)元素的無(wú)序集合 |
| TreeSet | 一種有序集 |
| EnumSet | 一種包含枚舉類型值的集 |
| LinkedHashSet | 一種可以記住元素插人次序的集 |
| PriorityQueue | 一種允許高效刪除最小元素的集合 |
| HashMap | 一種存儲(chǔ)鍵/ 值關(guān)聯(lián)的數(shù)據(jù)結(jié)構(gòu) |
| TreeMap | 一種鍵值有序排列的映射表 |
| EnumMap | 一種鍵值屬于枚舉類型的映射表 |
| LinkedHashMap | 一種可以記住腱/ 值項(xiàng)添加次序的映射表 |
| WeakHashMap | 一種其值無(wú)用武之地后可以被垃圾回收器回收的映射表 |
| IdentityHashMap | 一種用 == 而不是用equals 比較鍵值的映射表 |

**Collection**

**Map**

雖然類很多 气嫁，但是我們?cè)诮淌谥兄恍枰粠讉€(gè)類就可以了，分別是下面：

1.  ArrayList

2.  LinkedList

3.  HashSet

4.  HashMap

5.  TreeMap

然后加上工具類2個(gè)：

1.  Collections

2.  Arrays

## List

有序集合够坐，可以精確控制列表中每個(gè)元素的插入位置寸宵。通過(guò)整數(shù)索引獲取列表中的元素。List允許出現(xiàn)重復(fù)的值 元咙， 并可以精確控制列表中每個(gè)元素的插入位置梯影，通過(guò)整數(shù)索引獲取列表中的元素。

| 方法名 | 說(shuō)明 |
| --- | --- |
| add(E e) | 增加單個(gè)數(shù)據(jù) |
| addAll(Collection<? extends E> c) | 將一個(gè) Collection 集合的數(shù)據(jù)添加到現(xiàn)在的集合中 |
| remove(Object o) | 刪除指定的元素 |
| contains(Object o) | 判斷集合是否包含指定的元素 |
| size() | 得到集合的數(shù)據(jù)總數(shù) |
| isEmpty() | 判斷集合是否有數(shù)據(jù) |
| get(int index) | 通過(guò)索引獲取對(duì)應(yīng)的數(shù)據(jù)元素 |
| set(int index, E element) | 通過(guò)索引和新的元素替換原有內(nèi)容 |
| clear() | 清空數(shù)據(jù) |
| toArray() | 將List轉(zhuǎn)為對(duì)象數(shù)組 |

### ArrayList

ArrayList 是List 接口的大小可變數(shù)組的實(shí)現(xiàn)庶香。實(shí)現(xiàn)了所有可選列表操作甲棍， 并允許包括null 在內(nèi)的所有元素。除了實(shí)現(xiàn)List 接口外赶掖， 此類還提供一些方法來(lái)操作內(nèi)部用來(lái)存儲(chǔ)列表的數(shù)組的大懈忻汀（ 此類大致上等同于 vector 類， 但 vector 是同步的） 奢赂。

ArrayList 的底層是使用數(shù)組實(shí)現(xiàn)的陪白，看下面的圖

可以看到，數(shù)組中的每一個(gè)元素膳灶，都存儲(chǔ)在內(nèi)存單元中咱士，并且元素之間緊密排列，既不能打亂元素的存儲(chǔ)順序轧钓，也不能跳過(guò)某個(gè)存儲(chǔ)單元進(jìn)行存儲(chǔ)序厉。

ArrayList 底層既然是使用數(shù)組實(shí)現(xiàn)，那么特點(diǎn)就和數(shù)組一致：**查詢速度快毕箍，增刪速度慢**弛房。

每個(gè)ArrayList 實(shí)例都有一個(gè)容量。該容量是指用來(lái)存儲(chǔ)列表元素的數(shù)組的大小霉晕， 它總是至少等于列表的大小庭再。隨著向Array L ist 中小斷添加元素捞奕， 其容量也自動(dòng)增長(zhǎng)牺堰。并未指定增長(zhǎng)策略的細(xì)節(jié)拄轻，因?yàn)檫@不只是添加元素會(huì)帶來(lái)分?jǐn)偣潭〞r(shí)間開(kāi)銷那樣簡(jiǎn)單。我們可以使用默認(rèn)構(gòu)造函數(shù)創(chuàng)建容量為 10 的列表伟葫， 也可以初始化指定容量大小恨搓。

**ArrayList 指定初始容量大小的構(gòu)造器方法**

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n149" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public ArrayList(int initialCapacity) {
 if (initialCapacity > 0) {
 this.elementData = new Object[initialCapacity];
 } else if (initialCapacity == 0) {
 this.elementData = EMPTY_ELEMENTDATA;
 } else {
 throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
 }
}</pre>

**常用的操作**

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n151" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public static void main(String[] args) {

 ArrayList<Integer> list = new ArrayList<>();

 //  添加數(shù)據(jù)
 list.add(123);
 list.add(346);

 //  替換數(shù)據(jù)
 list.set(1, 777);

 //  將list中的所有數(shù)據(jù)放到 list2 中
 List<Integer> list2 = new ArrayList<>();
 list2.addAll( list );

 //  循環(huán)list2中所有的數(shù)據(jù)
 for (Integer integer : list2) {

 System.out.println( integer );

 //  刪除循環(huán)出的對(duì)象
 list2.remove(integer);
 }

 //  list 集合是否有數(shù)據(jù)
 if( !list.isEmpty() ) {

 System.out.println("list.size = "+ list.size());

 //  清空 list
 list.clear();
 }

 //  在清空l(shuí)ist后，再看list現(xiàn)在有多少數(shù)據(jù)
 System.out.println("list.size = "+ list.size());
}</pre>

### LinkedList

LinkedList 是一個(gè)鏈表結(jié)構(gòu)筏养，可當(dāng)作堆棧斧抱、隊(duì)列、雙端隊(duì)列 渐溶。鏈表是一種在物理上非連續(xù)辉浦、非順序的數(shù)據(jù)結(jié)構(gòu)，由若干節(jié)點(diǎn)（node）所組成茎辐。

**單鏈表**

單向鏈表的每一個(gè)節(jié)點(diǎn)包含兩部分宪郊，一部分是存放數(shù)據(jù)的變量data，另一部分是指向下一個(gè)節(jié)點(diǎn)的指針next拖陆。正如地下黨的聯(lián)絡(luò)方式弛槐，一級(jí)一級(jí)，單線傳遞：

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n158" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">private static class Node {
 int data;
 Node next;
}</pre>

**雙鏈表**

雙向鏈表比單向鏈表稍微復(fù)雜一些依啰，它的每一個(gè)節(jié)點(diǎn)除了擁有data和next指針乎串，還擁有指向前置節(jié)點(diǎn)的prev指針

和數(shù)組不同，鏈表存儲(chǔ)數(shù)據(jù)的時(shí)候速警，則采用了見(jiàn)縫插針的方式叹誉，鏈表的每一個(gè)節(jié)點(diǎn)分布在內(nèi)存的不同位置，依靠next指針關(guān)聯(lián)起來(lái)闷旧。這樣可以靈活有效地利用零散的碎片空間桂对。

LinkedList 做**數(shù)據(jù)的添加和刪除操作時(shí)速度很快，但是做查詢的時(shí)候速度就很慢**鸠匀，這和 ArrayList 剛好相反蕉斜。

適用 LinkedList 獨(dú)有的方法，**在集合前后做數(shù)據(jù)插入**

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n167" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public static void main(String[] args) {

 LinkedList<Integer> list = new LinkedList<>();

 list.add(123);
 //  添加相同的數(shù)據(jù)
 list.add(123);
 list.add(456);
 list.add(789);
 list.add(101);

 //  將數(shù)據(jù) 111 添加到 list 的末尾
 list.addLast(111);
 //  將數(shù)據(jù) 999 添加到 list的最前面
 list.addFirst(999);

 for (int i = 0; i < list.size(); i++) {
 System.out.println( list.get(i) );
 }

}</pre>

> 注意代碼中聲明和實(shí)現(xiàn)都是 LinkedList 缀棍， 如果聲明的是 List 接口 宅此， addFirst 和 addLast 方法是不可見(jiàn)的

## Set

Set 的特點(diǎn)是去重，如果相同的數(shù)據(jù)只會(huì)保留一個(gè)爬范。集合內(nèi)的數(shù)據(jù)是一個(gè)無(wú)序的狀態(tài)父腕，。當(dāng)然也有例外青瀑，TreeSet就是有序的璧亮。

| 方法名 | 說(shuō)明 |
| --- | --- |
| add(E e) | 增加單個(gè)數(shù)據(jù) |
| addAll(Collection<? extends E> c) | 將一個(gè) Collection 集合的數(shù)據(jù)添加到現(xiàn)在的集合中 |
| remove(Object o) | 刪除指定的元素 |
| contains(Object o) | 判斷集合是否包含指定的元素 |
| size() | 得到集合的數(shù)據(jù)總數(shù) |
| isEmpty() | 判斷集合是否有數(shù)據(jù) |
| clear() | 清空數(shù)據(jù) |
| toArray() | 將List轉(zhuǎn)為對(duì)象數(shù)組 |

可以看到萧诫，Set 和 List 中的方法都是相同的，作用也一致枝嘶。但是 Set 是沒(méi)有直接獲取數(shù)據(jù)的方法帘饶。我們更多的時(shí)候使用的是 List 和 Map。

Has hSet 由哈希表（ 實(shí)際上是一個(gè)HashM ap 實(shí)例） 支持群扶， 為基木操作提供了穩(wěn)定性能及刻， 這些基本操作包括add() 、remove() 竞阐、contains() 和size() 缴饭， 假定哈希函數(shù)將這些元素正確地分布在桶中。對(duì)此 set() 進(jìn)行迭代所需的時(shí)間與HashSet 實(shí)例的大新嬗ā（ 元素的數(shù)量） 和底層HashMap 實(shí)例（ 桶的數(shù)量）的“ 容量” 的和成比例颗搂。因此， 如果迭代性能很重要幕垦， 則不要將初始容量沒(méi)置得太高（ 或?qū)⒓虞d因了設(shè)置得太低） 丢氢。

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n203" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public static void main(String[] args) {

 HashSet set = new HashSet<>();

 set.add( new Object() );
 set.add( new Object() );
 set.add( "hello" );
 set.add( "hello" );
 set.add( "你好" );
 set.add( 123 );
 set.add( 123 );
 set.add( 234 );
 set.remove("你好");
 set.remove( new Object() );
 for (Object object : set) {
 System.out.println( object );
 }
}</pre>

以上代碼經(jīng)輸出可以看到：輸出的內(nèi)容沒(méi)有按照輸入時(shí)的順序進(jìn)行輸出。

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="" cid="n205" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">李四
8890
張三
azxcv
ABC</pre>

### TreeSet

Set 集合中的另類智嚷，存儲(chǔ)的數(shù)據(jù)時(shí)有序的

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n209" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public static void main(String[] args) {

 TreeSet<String> set = new TreeSet<>();
 set.add("8890");
 set.add("123");
 set.add("張三");
 set.add("李四");
 set.add("ABC");
 set.add("azxcv");

 for (String string : set) {
 System.out.println( string );
 }
}</pre>

輸出的結(jié)果：

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="" cid="n211" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">123
8890
ABC
azxcv
張三
李四</pre>

可以發(fā)現(xiàn)數(shù)據(jù)是按照數(shù)字卖丸、大寫(xiě)字母、小寫(xiě)字母盏道、漢字進(jìn)行排序的稍浆，但是漢字相關(guān)的數(shù)據(jù)本身沒(méi)有排序，可以嘗試將李四放在張三的數(shù)據(jù)上面看輸出的結(jié)果猜嘱。

## Map

Map 是一種把鍵對(duì)象和值對(duì)象進(jìn)行關(guān)聯(lián)的容器衅枫， 而一個(gè)值對(duì)象又可以是一個(gè)Map, 依次類推，這樣就可形成一個(gè)多級(jí)映射朗伶。

> 想想學(xué)習(xí)英語(yǔ)使用的詞典軟件弦撩，輸入英文（key）后，軟件會(huì)顯示出對(duì)應(yīng)的中文（value）论皆。Map就是在內(nèi)存中的這種結(jié)構(gòu)益楼。

**Key（鍵）：**

1.  和 set— 樣，鍵對(duì)象不允許重復(fù)点晴，這是為了保持查找結(jié)果的一致性感凤。 如果有兩個(gè)鍵對(duì)象一樣， 那你想得到那個(gè)鍵對(duì)象所對(duì)應(yīng)的值對(duì)象時(shí)就有問(wèn)題了粒督。

2.  在使用過(guò)程中某個(gè)鍵所對(duì)應(yīng)的值對(duì)象可能會(huì)發(fā)生變化陪竿， 這時(shí)會(huì)按照最后一次修改的值對(duì)象與鍵對(duì)應(yīng)（就是key同一個(gè)key有多次值綁定，最后一個(gè)就會(huì)覆蓋之前的）

3.  可以使用 null 作為 Key

**Value（值）:**

1.  值對(duì)象沒(méi)有唯一性的要求屠橄， 你可以將任意多個(gè)鍵都映射到一個(gè)值對(duì)象上族跛， 這不會(huì)發(fā)生任何問(wèn)題（ 不過(guò)對(duì)使用卻可能會(huì)造成不便闰挡， 你不知道你得到的到底是那一個(gè)鍵所對(duì)應(yīng)的值對(duì)象，所以請(qǐng)不要這樣做）

2.  可以使用 null 作為 Value

> Map 有兩種比較常用的實(shí)現(xiàn)： HashMap 和 TreeMap

**常用的方法**

| 方法名 | 說(shuō)明 |
| --- | --- |
| put(key , value) | 儲(chǔ)存數(shù)據(jù) |
| get(key) | 通過(guò)key得到值 |
| remove(key) | 通過(guò)key刪除對(duì)應(yīng)的值（key當(dāng)然也會(huì)刪除） |
| entrySet() | 獲取Map所有的Key礁哄，返回一個(gè)Set集合 |
| values() | 獲取Map所有的value长酗，返回一個(gè)List 集合 |
| containsKey(key) | 判斷Map中是否有輸入的參數(shù)：key |
| containsValue(value) | 判斷Map中是否有輸入的參數(shù)：value |
| size() | 判斷Map中數(shù)據(jù)的總數(shù) |
| clear() | 清空Map中所有的數(shù)據(jù) |
| isEmpty() | 判斷Map中是否有數(shù)據(jù) |

### HashMap

HashMap 用到了哈希碼的算法， 以便快速查找一個(gè)鍵姐仅。

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n273" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public static void main(String[] args) {

 HashMap<String, String> zsInfo = new HashMap<>();

 zsInfo.put("name", "張三");
 zsInfo.put("height", "173CM");
 zsInfo.put("sex", "男性");

 for (Map.Entry<String, String> info : zsInfo.entrySet()) {
 System.out.println( info );
 }
}</pre>

### TreeMap

TreeMap 是對(duì)鍵按序存放花枫， 因此它便有一些擴(kuò)展的方法刻盐， 比如 firstKey() 掏膏、lastKey() 等， 可以從TreeMap 中指定一個(gè)范圍以取得其子Map

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n277" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public static void main(String[] args) {

 TreeMap<String, String> tree = new TreeMap<>();

 tree.put("name", "Jack");
 tree.put("age", "22");
 tree.put("身高", "173");
 tree.put("sex", "man");
 tree.put("體重", "70KG");

 System.out.println("-------------------");
 for (Map.Entry<String, String> entry : tree.entrySet()) {
 System.out.println( entry );
 }
 System.out.println("-------------------");

 System.out.println("firstKey = "+ tree.firstKey());
 System.out.println("firstEntry = "+ tree.firstEntry());
 System.out.println("lastKey = "+ tree.lastKey());
 System.out.println("lastEntry = "+ tree.lastEntry());

}</pre>

## 數(shù)組敦锌、List馒疹、Set、Map的數(shù)據(jù)轉(zhuǎn)換

不同類型的集合相互轉(zhuǎn)換在程序開(kāi)發(fā)中都是非常常見(jiàn)的 API 操作乙墙，這些基礎(chǔ)操作一定要熟悉颖变。

### 數(shù)組轉(zhuǎn) List

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n283" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">/*
 * 數(shù)組轉(zhuǎn)List，但是這里要注意听想，Arrays.asList方法轉(zhuǎn)出來(lái)的雖然也叫ArrayList腥刹，
 * 但不是java.util.ArrayList，而是Arrays中的一個(gè)內(nèi)部類ArrayList汉买。兩者之間并不相等衔峰。
 * 內(nèi)部類ArrayList沒(méi)有實(shí)現(xiàn)remove、add等方法蛙粘，使用的話會(huì)報(bào)錯(cuò)垫卤。
 */
System.out.println("使用Arrays.asList將數(shù)組轉(zhuǎn)換為L(zhǎng)ist--------------------------------");
String str[] = { "中文", "計(jì)算機(jī)", "ABC", "123", "qq@qq.com" };

List<String> strList = Arrays.asList(str);

for (String string : strList) {
 System.out.println(string);
}

System.out.println("使用ArrayList構(gòu)造器方式再由Arrays.asList將數(shù)組轉(zhuǎn)換為L(zhǎng)ist----------");
// 使用下面的代碼的寫(xiě)法就不會(huì)有問(wèn)題了。
ArrayList<String> stringsList = new ArrayList<String>(Arrays.asList(str));
// 使用remove方法
stringsList.remove(3);

for (String string : stringsList) {
 System.out.println(string);
}

System.out.println("使用List.toArray方法將一個(gè)List轉(zhuǎn)換為數(shù)組(默認(rèn)為Object數(shù)組)----------");
Object[] strArr = stringsList.toArray();
for (Object object : strArr) {
 System.out.println(object.toString());
}</pre>

### 數(shù)組和Set

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n285" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">System.out.println("使用Arrays.asList將數(shù)組轉(zhuǎn)換為L(zhǎng)ist--------------------------------");
String str[] = { "中文", "計(jì)算機(jī)", "ABC", "123", "qq@qq.com" };

System.out.println("下面是數(shù)組轉(zhuǎn)Set ----------------------------------");

Set<String> strSet = new HashSet<String>(Arrays.asList(str));
for (String string : strSet) {
 System.out.println(string);
}
System.out.println("下面是將Set集合轉(zhuǎn)換為數(shù)組-------------");
Object[] objArr = strSet.toArray();
for (Object string : objArr) {
 System.out.println(string);
}</pre>

### 從Map中得到Set和List

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n287" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">Map<String, String> map = new HashMap<String, String>();
map.put("1", "A");
map.put("2", "B");
map.put("3", "C");

// 輸出所有的key , keySet()方法其實(shí)返回的就是一個(gè)Set集合出牧。
System.out.println("通過(guò)keySet輸出所有的key：" + map.keySet());

// 把map的值轉(zhuǎn)為一個(gè)List
List<String> stringList = new LinkedList<String>(map.values());
for (String string : stringList) {
 System.out.print(string + " ");
}</pre>

## 散列表（哈希表）的基本原理

上面 HashSet 和 HashMap 都使用了 散列表來(lái)做數(shù)據(jù)的檢索穴肘，那么什么是散列表 ，這個(gè)又有什么優(yōu)點(diǎn)呢 舔痕？

散列表也叫作哈希表（hash table）评抚，這種數(shù)據(jù)結(jié)構(gòu)提供了鍵（Key）和值（Value）的映射關(guān)系。只要給出一個(gè)Key伯复，就可以高效查找到它所匹配的Value慨代，時(shí)間復(fù)雜度接近于O(1)。

> 是不是想到了 Map 边翼？

### 散列表是如何根據(jù)Key來(lái)快速找到它所匹配的 Value 呢 鱼响？

在目前所學(xué)的數(shù)據(jù)結(jié)構(gòu)中，數(shù)組的查詢效率是最高的组底。散列表本質(zhì)就是一個(gè)數(shù)組丈积。不同的是**數(shù)組的下標(biāo)是數(shù)字**筐骇，但是**散列表的下標(biāo)是字符串**。這就需要設(shè)計(jì)一個(gè)中轉(zhuǎn)站江滨，通過(guò)某種方式铛纬，**把Key和數(shù)組下標(biāo)進(jìn)行轉(zhuǎn)換。這個(gè)中轉(zhuǎn)站就叫作哈希函數(shù)**唬滑。

在不同的語(yǔ)言中告唆，哈希函數(shù)的實(shí)現(xiàn)是不一樣的。我們以Java的HashMap為例晶密，來(lái)看看哈希函數(shù)的實(shí)現(xiàn)擒悬。

在Java及大多數(shù)面向?qū)ο蟮恼Z(yǔ)言中，每一個(gè)對(duì)象都有屬于自己的hashcode稻艰，這個(gè)hashcode是區(qū)分不同對(duì)象的重要標(biāo)識(shí)懂牧。無(wú)論對(duì)象自身的類型是什么，它們的hashcode都是一個(gè)整型變量尊勿。

既然都是整型變量僧凤，想要轉(zhuǎn)化成數(shù)組的下標(biāo)也就不難實(shí)現(xiàn)了。最簡(jiǎn)單的轉(zhuǎn)化方式是什么呢元扔？是按照數(shù)組長(zhǎng)度進(jìn)行取模運(yùn)算

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n300" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">index = HashCode (Key) % Array.length</pre>

> 其實(shí)JDK中的哈希函數(shù)為了提升效率躯保，使用的是位運(yùn)算。我們就假設(shè)使用的是模運(yùn)算

通過(guò)哈希函數(shù)澎语，我們可以把字符串或其他類型的Key途事，轉(zhuǎn)化成數(shù)組的下標(biāo)index。如給出一個(gè)長(zhǎng)度為8的數(shù)組咏连，則當(dāng)  key=001121時(shí)

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n304" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">index = HashCode ("001121") % Array.length = 1420036703 % 8 = 7</pre>

而當(dāng)key=this時(shí)盯孙，

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n306" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">index = HashCode ("this") % Array.length = 3559070 % 8 = 6</pre>

### 散列表的讀寫(xiě)操作

有了哈希函數(shù)，就可以在散列表中進(jìn)行讀寫(xiě)操作了祟滴。

#### 寫(xiě)操作（put）

寫(xiě)操作就是在散列表中插入新的鍵值對(duì)（在JDK中叫作Entry）振惰。如調(diào)用hashMap.put("002931", "王五")，意思是插入一組Key為002931垄懂、Value為王五的鍵值對(duì)骑晶。具體該怎么做呢？

1.  通過(guò)哈希函數(shù)草慧，把Key轉(zhuǎn)化成數(shù)組下標(biāo)5桶蛔。

2.  如果數(shù)組下標(biāo)5對(duì)應(yīng)的位置沒(méi)有元素，就把這個(gè)Entry填充到數(shù)組下標(biāo)5的位置

    由于數(shù)組的長(zhǎng)度是有限的漫谷，當(dāng)插入的Entry越來(lái)越多時(shí)仔雷，不同的Key通過(guò)哈希函數(shù)獲得的下標(biāo)有可能是相同的。例如002936這個(gè)Key對(duì)應(yīng)的數(shù)組下標(biāo)是2；002947這個(gè)Key對(duì)應(yīng)的數(shù)組下標(biāo)也是2碟婆。

**這種情況电抚，就叫作哈希沖突**

解決哈希沖突的方法主要有兩種，一種是開(kāi)放尋址法竖共，一種是鏈表法

1.  開(kāi)放尋址法的原理很簡(jiǎn)單蝙叛，當(dāng)一個(gè)Key通過(guò)哈希函數(shù)獲得對(duì)應(yīng)的數(shù)組下標(biāo)已被占用時(shí)，我們可以“另謀高就”公给，尋找下一個(gè)空檔位置

2.  HashMap數(shù)組的每一個(gè)元素不僅是一個(gè)Entry對(duì)象借帘，還是一個(gè)鏈表的頭節(jié)點(diǎn)。每一個(gè)Entry對(duì)象通過(guò)next指針指向它的下一個(gè)Entry節(jié)點(diǎn)淌铐。當(dāng)新來(lái)的Entry映射到與之沖突的數(shù)組位置時(shí)肺然，只需要插入到對(duì)應(yīng)的鏈表中即可

#### 讀操作（get）

讀操作就是通過(guò)給定的Key，在散列表中查找對(duì)應(yīng)的Value匣沼。例如調(diào)用 hashMap.get("002936")狰挡，意思是查找Key為002936的Entry在散列表中所對(duì)應(yīng)的值

1.  通過(guò)哈希函數(shù)捂龄，把Key轉(zhuǎn)化成數(shù)組下標(biāo)2释涛。

2.  找到數(shù)組下標(biāo)2所對(duì)應(yīng)的元素，如果這個(gè)元素的Key是002936倦沧，那么就找到了唇撬；如果這個(gè)Key不是002936也沒(méi)關(guān)系，由于數(shù)組的每個(gè)元素都與一個(gè)鏈表對(duì)應(yīng)展融，我們可以順著鏈表慢慢往下找窖认，看看能否找到與Key相匹配的節(jié)點(diǎn)。

## Iterator

iterator是為了實(shí)現(xiàn)對(duì)Java容器（collection）進(jìn)行遍歷功能的一個(gè)接口告希。  在iterator實(shí)現(xiàn)了Iterator接口后扑浸，相當(dāng)于把一個(gè)Collection容器的所有對(duì)象，做成一個(gè)線性表（List）燕偶，而iterator本身是一個(gè)指針喝噪，開(kāi)始時(shí)位于第一個(gè)元素之前。

| 方法 | 說(shuō)明 |
| --- | --- |
| hasNext() | 判斷 iterator 內(nèi)是否存在下1個(gè)元素指么，如果存在酝惧，返回true，否則返回false伯诬。（注意晚唇，這時(shí)上面的那個(gè)指針位置不變） |
| next() | 返回 iterator 內(nèi)下1個(gè)元素，同時(shí)上面的指針向后移動(dòng)一位盗似。如果不斷地循環(huán)執(zhí)行next()方法哩陕，就可以遍歷容器內(nèi)所有的元素了 |
| remove() | 刪除 iterator 內(nèi)指針的前1個(gè)元素，前提是至少執(zhí)行過(guò)1次next() |

遍歷1個(gè)ArrayList 和Linklist是十分容易的，遍歷1個(gè)Tree容器也不難悍及，但是實(shí)現(xiàn)機(jī)制是完全不同葵礼，而遍歷1個(gè)Set容器就無(wú)從下手了。  Iterator 這個(gè)接口讓各種容器自己去重寫(xiě)里面的hasNext()和next()方法并鸵。 不用關(guān)心各種容器的遍歷機(jī)制鸳粉，只要使用Iterator，會(huì)讓人覺(jué)得各種容器的遍歷方法都是一樣的园担，這就是Java接口的重要意義届谈。

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n353" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">HashMap zsInfo = new HashMap<>();

zsInfo.put("name", "張三");
zsInfo.put("height", "173CM");
zsInfo.put("sex", "男性");
zsInfo.put("skin-color", "白色");

zsInfo.put("height", "183CM");
zsInfo.remove("skin-color");

System.out.println("Iterator 循環(huán)------------------");
Iterator iterator = zsInfo.entrySet().iterator();

while( iterator.hasNext() ) {
 Map.Entry next = (Entry) iterator.next();
 System.out.println( next );
}</pre>

## Collections

Collections 是 Java 提供對(duì)Set 、List 和Map 等集合操作的工具類弯汰。

該工具類里提供了大量方法艰山，除了對(duì)集合元素進(jìn)行排序、查詢和修改等操作咏闪；還提供了將集合對(duì)象設(shè)置為不可變曙搬、對(duì)集合對(duì)象實(shí)現(xiàn)同步控制等方法。

### 排序

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n360" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">ArrayList nums = new ArrayList<>();
nums.add(2);
nums.add(0);
nums.add(-5);
nums.add(0);
nums.add(3);
System.out.println( nums );
Collections.reverse( nums );
System.out.println( nums);

Collections.sort( nums );
System.out.println( nums );

Collections.shuffle( nums );
System.out.println( nums );</pre>

### 查找

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n362" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">ArrayList nums = new ArrayList<>();
nums.add(2);
nums.add(0);
nums.add(-5);
nums.add(0);
nums.add(3);
System.out.println( nums );

System.out.println( Collections.max( nums ));
System.out.println( Collections.min( nums ));
Collections.replaceAll(nums, 0 , 1);
System.out.println( nums );

System.out.println( Collections.frequency(nums, 1));

Collections.sort(nums);
System.out.println( nums );

System.out.println( Collections.binarySearch(nums, 3 ));</pre>

## 排序

集合的排序有2種方式：

1.  集合內(nèi)部就擁有排序的能力鸽嫂。

    需要排序的能力的類實(shí)現(xiàn) Comparable 接口的方法

2.  集合本身沒(méi)有排序的能力纵装，可以通過(guò)外部指定排序的方式。

    在排序方法中据某，指定一個(gè)實(shí)現(xiàn)了 Comparator 接口的類的對(duì)象

Comparable是需要比較的對(duì)象來(lái)實(shí)現(xiàn)接口橡娄。這樣對(duì)象調(diào)用實(shí)現(xiàn)的方法來(lái)比較。對(duì)對(duì)象的耦合度高（需要改變對(duì)象的內(nèi)部結(jié)構(gòu)癣籽，破壞性大）挽唉。

Comparator相當(dāng)于一通用的比較工具類接口。需要定制一個(gè)比較類去實(shí)現(xiàn)它筷狼，重寫(xiě)里面的compare方法瓶籽，方法的參數(shù)即是需要比較的對(duì)象。對(duì)象不用做任何改變埂材，解耦塑顺。

### List 集合排序

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n376" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">List<Integer> list = new ArrayList<Integer>();

list.add(123);
list.add(999);
list.add(101);
list.add(33);
list.add(76);

Collections.sort(list);

for (Integer integer : list) {
 System.out.println( integer );
}</pre>

直接就可以得到自然升序，我們?cè)谏厦娴拇a中沒(méi)有看到任何接口楞遏，原因是List集合中的 Integer 類本身就實(shí)現(xiàn)了 Comparable 接口

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n378" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public final class Integer extends Number implements Comparable<Integer> {
 //...
}</pre>

### TreeMap 排序

treeMap 的示例中茬暇，我們使用了外部指定排序方式：Comparator

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n382" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">TreeMap<String, String> tree = new TreeMap<>(new Comparator<String>() {
 @Override
 public int compare(String o1, String o2) {
 return o2.compareTo(o1) ;  // 
 }
});

tree.put("name", "Jack");
tree.put("age", "22");
tree.put("身高", "173");
tree.put("sex", "man");
tree.put("體重", "70KG");

System.out.println("-------------------");
for (Map.Entry<String, String> entry : tree.entrySet()) {
 System.out.println( entry );
}</pre>

### 自定義類排序

當(dāng)我們自定義了一個(gè)類，也希望能夠進(jìn)行排序的話寡喝，就需要實(shí)現(xiàn) Comparator接口或者是 Comparable 接口了糙俗。

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n386" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public class User {
 private Integer uid;
 private String uname;
 //....
}</pre>

#### 外部指定排序

User 類沒(méi)有實(shí)現(xiàn) Comparable 接口，通過(guò) Collections 工具類的 sort 方法進(jìn)行排序预鬓，在 sort 方法的第二個(gè)參數(shù)上指定排序的規(guī)則

<pre spellcheck="false" class="md-fences md-end-block ty-contain-cm modeLoaded" lang="java" cid="n389" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: normal; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">List<User> list = new ArrayList<User>();

list.add( new User(110 ,"Mark") );
list.add( new User(101 ,"李四") );
list.add( new User(100 ,"張三") );
list.add( new User(111 ,"Jack") );

//  Comparator 接口因?yàn)槭峭獠颗判蚯缮В孕枰缹?duì)比的2個(gè)對(duì)象
Collections.sort(list , new Comparator<User>() {
 @Override
 public int compare(User o1, User o2) {
 return o2.getUid() - o1.getUid() ;
 }
});

for (User user : list) {
 System.out.println( user );
}</pre>

#### 本身?yè)碛信判?
因?yàn)槭莾?nèi)部排序赊颠，所以只需要傳入被排序的對(duì)象即可，另一個(gè)排序?qū)ο螽?dāng)然是對(duì)象本身劈彪，使用 this 指向即可竣蹦。

<pre spellcheck="false" class="md-fences mock-cm md-end-block" lang="java" cid="n393" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: pre-wrap; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">public class User implements Comparable<User> {

    private Integer uid;
    private String uname;

    public User(int i, String string) {
        this.uid = i;
        this.uname = string;
    }

    @Override
    public int compareTo(User o) {
        return this.getUid() - o.getUid() ;
    }

    public Integer getUid() {
        return uid;
    }

    public void setUid(Integer uid) {
        this.uid = uid;
    }

    public String getUname() {
        return uname;
    }

    public void setUname(String uname) {
        this.uname = uname;
    }

    @Override
    public String toString() {
        return "User [uid=" + uid + ", uname=" + uname + "]";
    }
}
</pre>

排序

<pre spellcheck="false" class="md-fences mock-cm md-end-block" lang="java" cid="n395" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: pre-wrap; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">List<User> list = new ArrayList<User>();

list.add( new User(110 ,"Mark") );
list.add( new User(101 ,"李四") );
list.add( new User(100 ,"張三") );
list.add( new User(111 ,"Jack") );

Collections.sort(list);

for (User user : list) {
    System.out.println( user );
}</pre>

輸出結(jié)果

<pre spellcheck="false" class="md-fences mock-cm md-end-block" lang="" cid="n397" mdtype="fences" style="box-sizing: border-box; overflow: visible; font-family: var(--monospace); font-size: 0.9em; display: block; break-inside: avoid; text-align: left; white-space: pre-wrap; background-image: inherit; background-position: inherit; background-size: inherit; background-repeat: inherit; background-attachment: inherit; background-origin: inherit; background-clip: inherit; background-color: rgb(248, 248, 248); position: relative !important; border: 1px solid rgb(231, 234, 237); border-radius: 3px; padding: 8px 4px 6px; margin-bottom: 15px; margin-top: 15px; width: inherit; color: rgb(51, 51, 51); font-style: normal; font-variant-ligatures: normal; font-variant-caps: normal; font-weight: 400; letter-spacing: normal; orphans: 2; text-indent: 0px; text-transform: none; widows: 2; word-spacing: 0px; -webkit-text-stroke-width: 0px; text-decoration-style: initial; text-decoration-color: initial;">User [uid=100, uname=張三]
User [uid=101, uname=李四]
User [uid=110, uname=Mark]
User [uid=111, uname=Jack]</pre>