主要內(nèi)容
- 數(shù)據(jù)結(jié)構(gòu)
- List集合
- Set集合
- Collections
第一章 數(shù)據(jù)結(jié)構(gòu)
2.1 數(shù)據(jù)結(jié)構(gòu)有什么用败富？
當你用著java里面的容器類很爽的時候，你有沒有想過摩窃，怎么ArrayList就像一個無限擴充的數(shù)組兽叮，也好像鏈表之類的。好用嗎猾愿？好用鹦聪，這就是數(shù)據(jù)結(jié)構(gòu)的用處，只不過你在不知不覺中使用了蒂秘。
現(xiàn)實世界的存儲泽本，我們使用的工具和建模。每種數(shù)據(jù)結(jié)構(gòu)有自己的優(yōu)點和缺點姻僧，想想如果Google的數(shù)據(jù)用的是數(shù)組的存儲规丽，我們還能方便地查詢到所需要的數(shù)據(jù)嗎？而算法撇贺，在這么多的數(shù)據(jù)中如何做到最快的插入赌莺，查找，刪除松嘶，也是在追求更快艘狭。
我們java是面向?qū)ο蟮恼Z言，就好似自動檔轎車喘蟆，C語言好似手動檔吉普缓升。數(shù)據(jù)結(jié)構(gòu)呢？是變速箱的工作原理蕴轨。你完全可以不知道變速箱怎樣工作港谊，就把自動檔的車子從 A點 開到 B點，而且未必就比懂得的人慢橙弱。寫程序這件事歧寺，和開車一樣，經(jīng)驗可以起到很大作用棘脐，但如果你不知道底層是怎么工作的斜筐，就永遠只能開車，既不會修車蛀缝，也不能造車顷链。當然了，數(shù)據(jù)結(jié)構(gòu)內(nèi)容比較多屈梁，細細的學起來也是相對費功夫的嗤练，不可能達到一蹴而就榛了。我們將常見的數(shù)據(jù)結(jié)構(gòu)：堆棧、隊列煞抬、數(shù)組霜大、鏈表和紅黑樹 這幾種給大家介紹一下，作為數(shù)據(jù)結(jié)構(gòu)的入門革答，了解一下它們的特點即可战坤。
2.2 常見的數(shù)據(jù)結(jié)構(gòu)
數(shù)據(jù)存儲的常用結(jié)構(gòu)有：棧、隊列残拐、數(shù)組途茫、鏈表和紅黑樹。我們分別來了解一下：
棧
- 棧：stack,又稱堆棧溪食，它是運算受限的線性表慈省，其限制是僅允許在標的一端進行插入和刪除操作，不允許在其他任何位置進行添加眠菇、查找、刪除等操作袱衷。
簡單的說：采用該結(jié)構(gòu)的集合捎废，對元素的存取有如下的特點
先進后出（即致燥，存進去的元素登疗，要在后它后面的元素依次取出后，才能取出該元素）嫌蚤。例如辐益，子彈壓進彈夾，先壓進去的子彈在下面脱吱，后壓進去的子彈在上面智政，當開槍時，先彈出上面的子彈箱蝠，然后才能彈出下面的子彈续捂。
棧的入口、出口的都是棧的頂端位置宦搬。
這里兩個名詞需要注意：
- 壓棧：就是存元素牙瓢。即，把元素存儲到棧的頂端位置间校，棧中已有元素依次向棧底方向移動一個位置矾克。
- 彈棧：就是取元素。即憔足，把棧的頂端位置元素取出胁附，棧中已有元素依次向棧頂方向移動一個位置酒繁。
隊列
- 隊列：queue,簡稱隊，它同堆棧一樣汉嗽，也是一種運算受限的線性表欲逃，其限制是僅允許在表的一端進行插入，而在表的另一端進行刪除饼暑。
簡單的說稳析，采用該結(jié)構(gòu)的集合，對元素的存取有如下的特點：
- 先進先出（即弓叛，存進去的元素彰居，要在后它前面的元素依次取出后，才能取出該元素）撰筷。例如陈惰，小火車過山洞，車頭先進去毕籽，車尾后進去抬闯；車頭先出來，車尾后出來关筒。
- 隊列的入口溶握、出口各占一側(cè)。例如蒸播，下圖中的左側(cè)為入口睡榆，右側(cè)為出口。
數(shù)組
- 數(shù)組:Array,是有序的元素序列袍榆，數(shù)組是在內(nèi)存中開辟一段連續(xù)的空間胀屿，并在此空間存放元素。就像是一排出租屋包雀，有100個房間宿崭，從001到100每個房間都有固定編號，通過編號就可以快速找到租房子的人馏艾。
簡單的說,采用該結(jié)構(gòu)的集合劳曹，對元素的存取有如下的特點：
- 查找元素快：通過索引，可以快速訪問指定位置的元素
增刪元素慢
-
指定索引位置增加元素：需要創(chuàng)建一個新數(shù)組琅摩，將指定新元素存儲在指定索引位置铁孵，再把原數(shù)組元素根據(jù)索引，復制到新數(shù)組對應索引的位置房资。如下圖
image.png -
指定索引位置刪除元素：需要創(chuàng)建一個新數(shù)組蜕劝，把原數(shù)組元素根據(jù)索引，復制到新數(shù)組對應索引的位置，原數(shù)組中指定索引位置元素不復制到新數(shù)組中岖沛。如下圖
image.png
鏈表
- 鏈表:linked list,由一系列結(jié)點node（鏈表中每一個元素稱為結(jié)點）組成暑始，結(jié)點可以在運行時i動態(tài)生成。每個結(jié)點包括兩個部分：一個是存儲數(shù)據(jù)元素的數(shù)據(jù)域婴削，另一個是存儲下一個結(jié)點地址的指針域廊镜。我們常說的鏈表結(jié)構(gòu)有單向鏈表與雙向鏈表，那么這里給大家介紹的是單向鏈表唉俗。
簡單的說嗤朴，采用該結(jié)構(gòu)的集合，對元素的存取有如下的特點：
- 多個結(jié)點之間虫溜，通過地址進行連接雹姊。例如，多個人手拉手衡楞，每個人使用自己的右手拉住下個人的左手吱雏，依次類推，這樣多個人就連在一起了瘾境。
查找元素慢：想查找某個元素歧杏，需要通過連接的節(jié)點，依次向后查找指定元素
-
增刪元素快：
- 增加元素：只需要修改連接下個元素的地址即可迷守。
image.png
-
刪除元素：只需要修改連接下個元素的地址即可得滤。
image.png
紅黑樹
- 二叉樹：binary tree ,是每個結(jié)點不超過2的有序樹（tree） 。
簡單的理解盒犹，就是一種類似于我們生活中樹的結(jié)構(gòu)，只不過每個結(jié)點上都最多只能有兩個子結(jié)點眨业。
二叉樹是每個節(jié)點最多有兩個子樹的樹結(jié)構(gòu)急膀。頂上的叫根結(jié)點，兩邊被稱作“左子樹”和“右子樹”龄捡。
如圖：
我們要說的是二叉樹的一種比較有意思的叫做紅黑樹卓嫂，紅黑樹本身就是一顆二叉查找樹，將節(jié)點插入后聘殖，該樹仍然是一顆二叉查找樹晨雳。也就意味著，樹的鍵值仍然是有序的奸腺。
紅黑樹的約束:
- 節(jié)點可以是紅色的或者黑色的
- 根節(jié)點是黑色的
- 葉子節(jié)點(特指空節(jié)點)是黑色的
- 每個紅色節(jié)點的子節(jié)點都是黑色的
- 任何一個節(jié)點到其每一個葉子節(jié)點的所有路徑上黑色節(jié)點數(shù)相同
紅黑樹的特點:
? 速度特別快,趨近平衡樹,查找葉子元素最少和最多次數(shù)不多于二倍
List集合
掌握了Collection接口的使用后餐禁，再來看看Collection接口中的子類，他們都具備那些特性呢突照？
接下來帮非，一起學習Collection中的常用幾個子類（java.util.List集合、java.util.Set集合）。
1.1 List接口介紹
java.util.List接口繼承自Collection接口末盔，是單列集合的一個重要分支筑舅，習慣性地會將實現(xiàn)了List接口的對象稱為List集合。在List集合中允許出現(xiàn)重復的元素陨舱，所有的元素是以一種線性方式進行存儲的翠拣，在程序中可以通過索引來訪問集合中的指定元素。另外游盲，List集合還有一個特點就是元素有序误墓，即元素的存入順序和取出順序一致。
看完API背桐，我們總結(jié)一下：
List接口特點：
- 它是一個元素存取有序的集合优烧。例如，存元素的順序是11链峭、22畦娄、33。那么集合中弊仪，元素的存儲就是按照11熙卡、22、33的順序完成的）励饵。
- 它是一個帶有索引的集合驳癌，通過索引就可以精確的操作集合中的元素（與數(shù)組的索引是一個道理）。
- 集合中可以有重復的元素役听，通過元素的equals方法颓鲜，來比較是否為重復的元素。
1.2 List接口中常用方法
List作為Collection集合的子接口典予，不但繼承了Collection接口中的全部方法甜滨，而且還增加了一些根據(jù)元素索引來操作集合的特有方法，如下：
-
public void add(int index, E element): 將指定的元素瘤袖，添加到該集合中的指定位置上衣摩。 -
public E get(int index):返回集合中指定位置的元素。 -
public E remove(int index): 移除列表中指定位置的元素, 返回的是被移除的元素捂敌。 -
public E set(int index, E element):用指定元素替換集合中指定位置的元素,返回值的更新前的元素艾扮。
List的子類
3.1 ArrayList集合
java.util.ArrayList集合數(shù)據(jù)存儲的結(jié)構(gòu)是數(shù)組結(jié)構(gòu)。元素增刪慢占婉，查找快泡嘴，由于日常開發(fā)中使用最多的功能為查詢數(shù)據(jù)、遍歷數(shù)據(jù)逆济，所以ArrayList是最常用的集合磕诊。
許多程序員開發(fā)時非常隨意地使用ArrayList完成任何需求填物，并不嚴謹，這種用法是不提倡的霎终。
3.2 LinkedList集合
java.util.LinkedList集合數(shù)據(jù)存儲的結(jié)構(gòu)是鏈表結(jié)構(gòu)滞磺。方便元素添加、刪除的集合莱褒。
LinkedList是一個雙向鏈表击困，那么雙向鏈表是什么樣子的呢，我們用個圖了解下
實際開發(fā)中對一個集合元素的添加與刪除經(jīng)常涉及到首尾操作广凸，而LinkedList提供了大量首尾操作的方法阅茶。這些方法我們作為了解即可：
-
public void addFirst(E e):將指定元素插入此列表的開頭。 -
public void addLast(E e):將指定元素添加到此列表的結(jié)尾谅海。 -
public E getFirst():返回此列表的第一個元素脸哀。 -
public E getLast():返回此列表的最后一個元素。 -
public E removeFirst():移除并返回此列表的第一個元素扭吁。 -
public E removeLast():移除并返回此列表的最后一個元素撞蜂。 -
public E pop():從此列表所表示的堆棧處彈出一個元素。 -
public void push(E e):將元素推入此列表所表示的堆棧侥袜。 -
public boolean isEmpty()：如果列表不包含元素蝌诡，則返回true。
LinkedList是List的子類枫吧，List中的方法LinkedList都是可以使用浦旱，這里就不做詳細介紹，我們只需要了解LinkedList的特有方法即可九杂。在開發(fā)時颁湖，LinkedList集合也可以作為堆棧，隊列的結(jié)構(gòu)使用例隆。（了解即可）
Set接口
java.util.Set接口和java.util.List接口一樣爷狈，同樣繼承自Collection接口，它與Collection接口中的方法基本一致裳擎，并沒有對Collection接口進行功能上的擴充，只是比Collection接口更加嚴格了思币。與List接口不同的是鹿响，Set接口中元素無序，并且都會以某種規(guī)則保證存入的元素不出現(xiàn)重復谷饿。
Set集合有多個子類惶我，這里我們介紹其中的java.util.HashSet、java.util.LinkedHashSet這兩個集合博投。
tips:Set集合取出元素的方式可以采用：迭代器绸贡、增強for。
3.1 HashSet集合介紹
java.util.HashSet是Set接口的一個實現(xiàn)類，它所存儲的元素是不可重復的听怕，并且元素都是無序的(即存取順序不一致)捧挺。java.util.HashSet底層的實現(xiàn)其實是一個java.util.HashMap支持。
HashSet是根據(jù)對象的哈希值來確定元素在集合中的存儲位置尿瞭，因此具有良好的存取和查找性能闽烙。保證元素唯一性的方式依賴于：hashCode與equals方法。
2.2 HashSet集合存儲數(shù)據(jù)的結(jié)構(gòu)（哈希表）
什么是哈希表呢声搁？
在JDK1.8之前黑竞，哈希表底層采用數(shù)組+鏈表實現(xiàn)，即使用鏈表處理沖突疏旨，同一hash值的鏈表都存儲在一個鏈表里很魂。但是當位于一個桶中的元素較多，即hash值相等的元素較多時檐涝，通過key值依次查找的效率較低遏匆。而JDK1.8中，哈希表存儲采用數(shù)組+鏈表+紅黑樹實現(xiàn)骤铃，當鏈表長度超過閾值（8）時拉岁，將鏈表轉(zhuǎn)換為紅黑樹，這樣大大減少了查找時間惰爬。
簡單的來說喊暖，哈希表是由數(shù)組+鏈表+紅黑樹（JDK1.8增加了紅黑樹部分）實現(xiàn)的，如下圖所示撕瞧。
看到這張圖就有人要問了陵叽，這個是怎么存儲的呢？
為了方便大家的理解我們結(jié)合一個存儲流程圖來說明一下：
總而言之丛版，JDK1.8引入紅黑樹大程度優(yōu)化了HashMap的性能巩掺，那么對于我們來講保證HashSet集合元素的唯一，其實就是根據(jù)對象的hashCode和equals方法來決定的页畦。如果我們往集合中存放自定義的對象胖替，那么保證其唯一，就必須復寫hashCode和equals方法建立屬于當前對象的比較方式豫缨。
2.3 HashSet存儲自定義類型元素
給HashSet中存放自定義類型元素時独令，需要重寫對象中的hashCode和equals方法，建立自己的比較方式好芭，才能保證HashSet集合中的對象唯一
2.4 LinkedHashSet
我們知道HashSet保證元素唯一燃箭，可是元素存放進去是沒有順序的，那么我們要保證有序舍败，怎么辦呢招狸？
在HashSet下面有一個子類java.util.LinkedHashSet敬拓，它是鏈表和哈希表組合的一個數(shù)據(jù)存儲結(jié)構(gòu)。
1.9 可變參數(shù)
在JDK1.5之后裙戏，如果我們定義一個方法需要接受多個參數(shù)乘凸，并且多個參數(shù)類型一致，我們可以對其簡化成如下格式：
修飾符 返回值類型 方法名(參數(shù)類型... 形參名){ }
其實這個書寫完全等價與
修飾符 返回值類型 方法名(參數(shù)類型[] 形參名){ }
只是后面這種定義挽懦，在調(diào)用時必須傳遞數(shù)組翰意，而前者可以直接傳遞數(shù)據(jù)即可。
JDK1.5以后信柿。出現(xiàn)了簡化操作冀偶。... 用在參數(shù)上，稱之為可變參數(shù)渔嚷。
同樣是代表數(shù)組进鸠，但是在調(diào)用這個帶有可變參數(shù)的方法時，不用創(chuàng)建數(shù)組(這就是簡單之處)形病，直接將數(shù)組中的元素作為實際參數(shù)進行傳遞客年，其實編譯成的class文件，將這些元素先封裝到一個數(shù)組中漠吻，在進行傳遞量瓜。這些動作都在編譯.class文件時，自動完成了途乃。
代碼演示：
public class ChangeArgs {
public static void main(String[] args) {
int[] arr = { 1, 4, 62, 431, 2 };
int sum = getSum(arr);
System.out.println(sum);
// 6 7 2 12 2121
// 求 這幾個元素和 6 7 2 12 2121
int sum2 = getSum(6, 7, 2, 12, 2121);
System.out.println(sum2);
}
/*
* 完成數(shù)組 所有元素的求和 原始寫法
public static int getSum(int[] arr){
int sum = 0;
for(int a : arr){
sum += a;
}
return sum;
}
*/
//可變參數(shù)寫法
public static int getSum(int... arr) {
int sum = 0;
for (int a : arr) {
sum += a;
}
return sum;
}
}
tips: 上述add方法在同一個類中绍傲，只能存在一個。因為會發(fā)生調(diào)用的不確定性
注意：如果在方法書寫時耍共，這個方法擁有多參數(shù)烫饼，參數(shù)中包含可變參數(shù)，可變參數(shù)一定要寫在參數(shù)列表的末尾位置试读。
Collections
2.1 常用功能
-
java.utils.Collections是集合工具類杠纵，用來對集合進行操作。部分方法如下：
-
public static <T> boolean addAll(Collection<T> c, T... elements):往集合中添加一些元素钩骇。 -
public static void shuffle(List<?> list) 打亂順序:打亂集合順序比藻。 -
public static <T> void sort(List<T> list):將集合中元素按照默認規(guī)則排序。 -
public static <T> void sort(List<T> list倘屹，Comparator<? super T> ):將集合中元素按照指定規(guī)則排序银亲。
我們發(fā)現(xiàn)還有個方法沒有講，public static <T> void sort(List<T> list唐瀑，Comparator<? super T> ):將集合中元素按照指定規(guī)則排序。
2.2 Comparator比較器
public static <T> void sort(List<T> list):將集合中元素按照默認規(guī)則排序插爹。
不過這次存儲的是字符串類型哄辣。
public class CollectionsDemo2 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("cba");
list.add("aba");
list.add("sba");
list.add("nba");
//排序方法
Collections.sort(list);
System.out.println(list);
}
}
結(jié)果：
[aba, cba, nba, sba]
我們使用的是默認的規(guī)則完成字符串的排序请梢，那么默認規(guī)則是怎么定義出來的呢？
說到排序了力穗，簡單的說就是兩個對象之間比較大小毅弧，那么在JAVA中提供了兩種比較實現(xiàn)的方式，一種是比較死板的采用java.lang.Comparable接口去實現(xiàn)当窗，一種是靈活的當我需要做排序的時候在去選擇的java.util.Comparator接口完成够坐。
那么我們采用的public static <T> void sort(List<T> list)這個方法完成的排序，實際上要求了被排序的類型需要實現(xiàn)Comparable接口完成比較的功能崖面，在String類型上如下：
public final class String implements java.io.Serializable, Comparable<String>, CharSequence {
String類實現(xiàn)了這個接口元咙，并完成了比較規(guī)則的定義，但是這樣就把這種規(guī)則寫死了巫员，那比如我想要字符串按照第一個字符降序排列庶香，那么這樣就要修改String的源代碼，這是不可能的了简识，那么這個時候我們可以使用
public static <T> void sort(List<T> list赶掖，Comparator<? super T> )方法靈活的完成，這個里面就涉及到了Comparator這個接口七扰，位于位于java.util包下奢赂，排序是comparator能實現(xiàn)的功能之一,該接口代表一個比較器，比較器具有可比性颈走！顧名思義就是做排序的膳灶，通俗地講需要比較兩個對象誰排在前誰排在后，那么比較的方法就是：
-
public int compare(String o1, String o2)：比較其兩個參數(shù)的順序疫鹊。兩個對象比較的結(jié)果有三種：大于袖瞻，等于，小于拆吆。
如果要按照升序排序聋迎，
則o1 小于o2，返回（負數(shù)）枣耀，相等返回0霉晕，01大于02返回（正數(shù)）
如果要按照降序排序
則o1 小于o2，返回（正數(shù)）捞奕，相等返回0牺堰，01大于02返回（負數(shù)）
操作如下:
public class CollectionsDemo3 {
public static void main(String[] args) {
ArrayList<String> list = new ArrayList<String>();
list.add("cba");
list.add("aba");
list.add("sba");
list.add("nba");
//排序方法 按照第一個單詞的降序
Collections.sort(list, new Comparator<String>() {
@Override
public int compare(String o1, String o2) {
return o2.charAt(0) - o1.charAt(0);
}
});
System.out.println(list);
}
}
結(jié)果如下：
[sba, nba, cba, aba]
2.3 簡述Comparable和Comparator兩個接口的區(qū)別。
Comparable：強行對實現(xiàn)它的每個類的對象進行整體排序颅围。這種排序被稱為類的自然排序辣卒，類的compareTo方法被稱為它的自然比較方法。只能在類中實現(xiàn)compareTo()一次枷恕，不能經(jīng)常修改類的代碼實現(xiàn)自己想要的排序。實現(xiàn)此接口的對象列表（和數(shù)組）可以通過Collections.sort（和Arrays.sort）進行自動排序斧抱，對象可以用作有序映射中的鍵或有序集合中的元素，無需指定比較器渐溶。
Comparator強行對某個對象進行整體排序辉浦。可以將Comparator 傳遞給sort方法（如Collections.sort或 Arrays.sort）茎辐，從而允許在排序順序上實現(xiàn)精確控制宪郊。還可以使用Comparator來控制某些數(shù)據(jù)結(jié)構(gòu)（如有序set或有序映射）的順序，或者為那些沒有自然順序的對象collection提供排序拖陆。
2.4 擴展
如果在使用的時候弛槐，想要獨立的定義規(guī)則去使用 可以采用Collections.sort(List list,Comparetor<T> c)方式，自己定義規(guī)則：
Collections.sort(list, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
return o2.getAge()-o1.getAge();//以學生的年齡降序
}
});
效果：
Student{name='rose', age=18}
Student{name='ace', age=17}
Student{name='jack', age=16}
Student{name='abc', age=16}
Student{name='mark', age=16}
如果想要規(guī)則更多一些慕蔚，可以參考下面代碼：
Collections.sort(list, new Comparator<Student>() {
@Override
public int compare(Student o1, Student o2) {
// 年齡降序
int result = o2.getAge()-o1.getAge();//年齡降序
if(result==0){//第一個規(guī)則判斷完了 下一個規(guī)則 姓名的首字母 升序
result = o1.getName().charAt(0)-o2.getName().charAt(0);
}
return result;
}
});
效果如下：
Student{name='rose', age=18}
Student{name='ace', age=17}
Student{name='abc', age=16}
Student{name='jack', age=16}
Student{name='mark', age=16}
