單列集合與泛型

Collection集合

最近剛學(xué)Java,隨便記點(diǎn)學(xué)習(xí)筆記

Collection下的兩個(gè)大類:List(含ArrayList,LinkedLisk,Vector)和Set(含HashSet,LinkedHashSet,TreeSet)

List系列集合:添加的元素是有序(存和取的順序是一樣的),可重復(fù),有索引 Set系列集合:添加的元素是無(wú)序,不重復(fù),無(wú)索引

Collection是單列集合的祖宗接口,它的功能是全部單列集合都可以繼承使用的

注意:Collection是一個(gè)接口,我們不能直接創(chuàng)建他的對(duì)象.為了學(xué)習(xí)Collection接口里的方法這里按如下方式創(chuàng)建:

Collection的遍歷方式

迭代器遍歷

迭代器在Java中的類是Iterator,迭代器是集合專用的遍歷方式,迭代器在遍歷集合的時(shí)候是不依賴索引的

Collection集合獲取迭代器:

方法名 說(shuō)明 Iterator iterator() 返回迭代器對(duì)象,默認(rèn)指向當(dāng)前集合的0索引

Iterator中常用方法

細(xì)節(jié)注意點(diǎn):

1. 遍歷結(jié)束后再訪問(wèn)報(bào)錯(cuò)NoSuchElementExcpetion

2. 迭代器遍歷完畢,指針不會(huì)復(fù)位.要再次遍歷需要重新創(chuàng)建迭代器對(duì)象

3. 迭代器遍歷時(shí)不能用集合的方法進(jìn)行增加或刪除,而用迭代器中的remove方法刪除,如果要添加暫時(shí)沒(méi)有辦法

增強(qiáng)for遍歷

• 底層就是迭代器,為了簡(jiǎn)化迭代器的代碼書寫的

• 它是JDK5之后出現(xiàn)的,內(nèi)部原理就是一個(gè)Iterator迭代器

• 所有的單列集合和數(shù)組才能用增強(qiáng)for遍歷

Lambda表達(dá)式遍歷

得益于JDK8開始的新技術(shù)Lambda表達(dá)式提供了一種更簡(jiǎn)單,更直接的遍歷集合的方式

List集合

• Collection的方法List都繼承了

• List集合因?yàn)橛兴饕?所以多了很多索引操作的方法

List集合系列刪除元素的方法

1. 直接刪除元素

2. 通過(guò)索引進(jìn)行刪除

注意上面會(huì)優(yōu)先認(rèn)為待刪除的1是index 在調(diào)用方法的時(shí)候,如果方法出現(xiàn)了重載現(xiàn)象,優(yōu)先調(diào)用實(shí)參和形參一致的那個(gè)方法,如果要?jiǎng)h除元素1,可以手動(dòng)裝箱:

List集合的遍歷方式

1. 迭代器遍歷

2. 列表迭代器遍歷

3. 增強(qiáng)for遍歷

4. Lambda表達(dá)式遍歷

5. 普通for循環(huán)(因?yàn)長(zhǎng)ist集合存在索引)

五種遍歷方式對(duì)比:

數(shù)據(jù)結(jié)構(gòu)

棧

后進(jìn)先出,先進(jìn)后出

隊(duì)列

先進(jìn)先出,后進(jìn)后出

數(shù)組

查詢快,增刪慢

鏈表

鏈表中的結(jié)點(diǎn)時(shí)獨(dú)立的對(duì)象,在內(nèi)存中是不連續(xù)的,每個(gè)結(jié)點(diǎn)包含數(shù)據(jù)值和下一個(gè)結(jié)點(diǎn)的地址

查詢慢,無(wú)論查詢哪個(gè)數(shù)據(jù)都要從頭開始找

紅黑樹

• 一種自平衡的二叉查找樹,1972年出現(xiàn),當(dāng)時(shí)被稱為平衡二叉B樹,1978年被修改為如今的"紅黑樹"

• 是一種特殊的二叉查找樹,紅黑樹的每一個(gè)結(jié)點(diǎn)上都有存儲(chǔ)位表示結(jié)點(diǎn)的顏色

• 每一個(gè)結(jié)點(diǎn)可以使紅或者黑,紅黑樹不是高度平衡的,它的平衡是通過(guò)"紅黑規(guī)則"實(shí)現(xiàn)的

紅黑規(guī)則

1. 每一個(gè)結(jié)點(diǎn)或是紅色的,或是黑色的

2. 根節(jié)點(diǎn)必須是黑色

3. 如果一個(gè)結(jié)點(diǎn)沒(méi)有子節(jié)點(diǎn)或父節(jié)點(diǎn),則該節(jié)點(diǎn)相應(yīng)的指針屬性值為Nil,這些Nil視為葉節(jié)點(diǎn),每個(gè)葉節(jié)點(diǎn)(Nil)是黑色的

4. 如果某一個(gè)節(jié)點(diǎn)是紅色,那么它的子節(jié)點(diǎn)必須是黑色(不能出現(xiàn)兩個(gè)紅色結(jié)點(diǎn)相連的情況)

5. 對(duì)每一個(gè)結(jié)點(diǎn),從該節(jié)點(diǎn)到其所有后代葉節(jié)點(diǎn)的簡(jiǎn)單路徑上,均包含相同數(shù)目的黑色結(jié)點(diǎn)

默認(rèn)顏色:紅色(效率高)

ArrayList集合底層原理

1. 利用空參創(chuàng)建的集合,在底層創(chuàng)建一個(gè)默認(rèn)長(zhǎng)度為0的數(shù)組

2. 添加第一個(gè)元素時(shí),底層會(huì)創(chuàng)建一個(gè)新的長(zhǎng)度為10的數(shù)組

3. 存滿時(shí),會(huì)擴(kuò)容1.5倍

4. 如果一次添加多個(gè)元素,1.5倍還放不下,則新創(chuàng)建數(shù)組的長(zhǎng)度以實(shí)際為準(zhǔn)

源碼分析見(jiàn)P190

LinkedList集合

• 底層數(shù)據(jù)結(jié)構(gòu)是雙鏈表,查詢慢,增刪快,如果操作的是首尾元素,速度也是極快的

• LinkedList本身多了很多直接操作首尾元素的特有API

并發(fā)修改異常底層原理集合底層有modCount變量記錄集合變化的次數(shù),每add一次或remove一次,這個(gè)變量都會(huì)自增,當(dāng)我們創(chuàng)建迭代器對(duì)象的時(shí)候,就會(huì)把這個(gè)次數(shù)告訴迭代器 調(diào)用next方法時(shí)會(huì)檢測(cè)當(dāng)前集合中最新的變化次數(shù)和一開始記錄的次數(shù)是否相同,如果相同,證明當(dāng)前集合沒(méi)有發(fā)生改變,如果不一樣,證明在迭代器遍歷集合的過(guò)程中,使用了集合中的方法添加/刪除了元素

如何避免并發(fā)修改異常:在使用迭代器或者是增強(qiáng)for遍歷集合的過(guò)程中,不要使用集合的方法添加或刪除元素

泛型

泛型是JDK5中引入的特性,可以在編譯階段約束操作的數(shù)據(jù)類型,并進(jìn)行檢查 格式:<數(shù)據(jù)類型> 注意:泛型只能支持引用數(shù)據(jù)類型

在JDK5前沒(méi)有泛型的時(shí)候,集合如何存儲(chǔ)數(shù)據(jù)?

結(jié)論:如果沒(méi)有給集合指定類型,默認(rèn)認(rèn)為所有的數(shù)據(jù)類型都是Object類型,此時(shí)可以往集合中添加任意的數(shù)據(jù)類型,帶來(lái)一個(gè)壞處:我們?cè)讷@取數(shù)據(jù)的時(shí)候,無(wú)法使用他的特有行為

此時(shí)推出了泛型:可以在添加數(shù)據(jù)的時(shí)候就把類型進(jìn)行統(tǒng)一,而且我們?cè)讷@取數(shù)據(jù)的時(shí)候也省的強(qiáng)轉(zhuǎn)了,非常的方便

泛型的好處:

• 統(tǒng)一數(shù)據(jù)類型

• 把運(yùn)行時(shí)期的問(wèn)題提前到了編譯期間,避免了強(qiáng)制類型轉(zhuǎn)換可能出現(xiàn)的異常,因?yàn)樵诰幾g階段類型就能確定下來(lái)

Java中的泛型是偽泛型

在編譯的時(shí)候,會(huì)檢查集合中的元素是否與泛型匹配,但是生成的class文件并沒(méi)有泛型,此過(guò)程成為泛型的擦除

泛型的細(xì)節(jié)

• 泛型中不能寫基本數(shù)據(jù)類型,而要寫包裝類

• 指定泛型的具體類型后,傳遞數(shù)據(jù)時(shí),可以傳入該類型或者其子類類型

• 如果不寫泛型,類型默認(rèn)是Object

泛型類

使用場(chǎng)景:當(dāng)一個(gè)類中,某個(gè)變量的數(shù)據(jù)類型不確定時(shí),就可以定義帶有泛型的類

泛型方法

方法中形參類型不確定時(shí)

• 方案1:可以使用類名后面定義的泛型(所有方法都能用)

• 方案2:在方法聲明上定義自己的泛型(只有本方法能用)

泛型接口

如何使用一個(gè)帶泛型的接口

• 方式1:實(shí)現(xiàn)類給出具體類型

• 方式2:實(shí)現(xiàn)類延續(xù)泛型,創(chuàng)建對(duì)象時(shí)再確定

泛型的繼承和通配符

• 泛型不具備繼承性,但是數(shù)據(jù)具備繼承性

如果想寫一個(gè)方法,雖然不確定類型,但是希望只能傳遞Ye,Fu,Zi 此時(shí)可以使用泛型的通配符: ?也表示不確定的類型,可以進(jìn)行類型的限定 ? extends E表示可以傳遞E或者E所有的子類類型 ? super E表示可以傳遞E或者E所有的父類類型

應(yīng)用場(chǎng)景:

1. 如果我們?cè)诙x類,方法,接口的時(shí)候,如果類型不確定,就可以定義泛型類,泛型方法,泛型接口

2. 如果類型不確定,但是能指導(dǎo)以后只能傳遞某個(gè)繼承體系的,就可以使用泛型的通配符

泛型的通配符: ? ? ? ?關(guān)鍵點(diǎn):可以限定類型的范圍

泛型小結(jié)

1. 什么是泛型? JDK5引入的特性,可以在編譯階段約束操作的數(shù)據(jù)類型,并進(jìn)行檢查

2. 泛型的好處?

• 統(tǒng)一數(shù)據(jù)類型

• 吧運(yùn)行時(shí)期的問(wèn)題提前到了編譯期間,避免了強(qiáng)制類型轉(zhuǎn)換可能出現(xiàn)的異常,因?yàn)樵诰幾g階段類型就能確定下來(lái)

3. 泛型的細(xì)節(jié)?

• 泛型中不能寫基本數(shù)據(jù)類型

• 指定泛型的具體類型后,傳遞數(shù)據(jù)時(shí),可以傳入該類型和他的子類類型

• 如果不寫泛型,類型默認(rèn)是Object

4. 哪里定義泛型?

• 泛型類:在類名后面定義泛型,創(chuàng)建該類對(duì)象的時(shí)候,確定類型

• 泛型方法:在修飾符后面定義方法,調(diào)用該方法的時(shí)候確定類型

• 泛型接口:在接口名后面定義泛型,實(shí)現(xiàn)類確定類型,實(shí)現(xiàn)類延續(xù)泛型

5. 泛型的繼承和通配符

• 泛型不具備繼承性,但是數(shù)據(jù)具備繼承性(即<>里面的東西具備繼承性)

• 泛型的通配符?

Set集合

• 無(wú)序:存取順序不一致

• 不重復(fù):可以去除重復(fù)

• 無(wú)索引:沒(méi)有帶索引的方法,所以不能使用普通for循環(huán)遍歷,也不能通過(guò)索引來(lái)獲取元素

實(shí)現(xiàn)類:

• HashSet:無(wú)序,不重復(fù),無(wú)索引

• LinkedHashSet:有序,不重復(fù),無(wú)索引

• TreeSet:可排序,不重復(fù),無(wú)索引

Set接口中的方法基本與Collection的API一致

遍歷方式:

1. 迭代器

2. 增強(qiáng)for

3. Lambda表達(dá)式

HashSet

底層采用哈希表存儲(chǔ)數(shù)據(jù),哈希表是一種對(duì)于增刪改查數(shù)據(jù)性能都較好的結(jié)構(gòu)

哈希表組成:

• JDK8以前:數(shù)組+鏈表

• JDK8開始:數(shù)組+鏈表+紅黑樹

哈希值:對(duì)象的整數(shù)表現(xiàn)形式

• 格努hashCode方法算出來(lái)的int類型的整數(shù)

• 該方法定義在Object類中,所有對(duì)象都可以調(diào)用,默認(rèn)使用地址值進(jìn)行計(jì)算

• 一般情況下,會(huì)重寫hashCode方法,利用對(duì)象內(nèi)部的屬性值計(jì)算哈希值

對(duì)象的哈希值特點(diǎn):

• 如果沒(méi)有重寫hashCode方法,不同對(duì)象計(jì)算出的哈希值是不同的

• 如果已經(jīng)重寫hashCode方法,不同的對(duì)象只要屬性值相同,計(jì)算出的哈希值就是一樣的

• 在小部分情況下,不同的屬性值或者不同的地址值計(jì)算出來(lái)的哈希值也有可能一樣

HashSet 底層原理

1. 創(chuàng)建一個(gè)默認(rèn)長(zhǎng)度16,默認(rèn)加載因子為0.75的數(shù)組,數(shù)組名table

2. 根據(jù)元素的哈希值跟數(shù)組的長(zhǎng)度計(jì)算出應(yīng)存入的位置

1. 判斷當(dāng)前位置是否為null,如果是null直接存入

2. 如果位置不為null,表示有元素,則調(diào)用equals方法比較屬性值

3. 一樣:不存 ? 不一樣:存入數(shù)組,形成鏈表 JDK8以前:新元素存入數(shù)組,老元素掛在新元素下面 JDK8以后:新元素直接掛在老元素下面

加載因子的作用:當(dāng)數(shù)組中存了個(gè)元素時(shí),數(shù)組會(huì)擴(kuò)容兩倍 當(dāng)鏈表長(zhǎng)度大于8而且數(shù)組長(zhǎng)度大于64,鏈表會(huì)自動(dòng)轉(zhuǎn)換為紅黑樹,提示查找效率 如果集合中存儲(chǔ)的是自定義對(duì)象,必須要重寫hashCode和equals方法

問(wèn)題1:HashSet為什么存和取的順序不一樣? 遍歷時(shí)會(huì)從數(shù)組的0索引開始沿著每一條鏈表(紅黑樹)遍歷的

問(wèn)題2:HashSet為什么沒(méi)有索引? 掛著的鏈表(紅黑樹)不好定義索引

問(wèn)題3:HashSet是利用什么機(jī)制保證數(shù)據(jù)去重的? HashCode方法和equals方法

LinkedHashSet

• 有序,不重復(fù),無(wú)索引

• 這里的有序指的是保證存儲(chǔ)和取出的元素順序一致

• 原理:底層數(shù)據(jù)結(jié)構(gòu)依然是哈希表,只是每個(gè)元素又額外多了一個(gè)雙鏈表的機(jī)制記錄存儲(chǔ)的順序

在以后如果僅僅要數(shù)據(jù)去重,默認(rèn)還是使用HashSet,因?yàn)樾室萀inkedHashSet要高

TreeSet

• 不重復(fù),無(wú)索引,可排序

• 可排序:按照元素的默認(rèn)規(guī)則(由小到大)排序

• TreeSet集合底層是基于紅黑樹的數(shù)據(jù)結(jié)構(gòu)實(shí)現(xiàn)排序的,增刪改查性能都很好

TreeSet集合默認(rèn)的規(guī)則

• 對(duì)于數(shù)值類型:Integer,Double默認(rèn)按照從小到大的順序進(jìn)行排序

• 對(duì)于字符,字符串類型:按照字符在ASCII碼表中的數(shù)字升序進(jìn)行排序

集合小結(jié)

1. 如果想要集合中的元素可重復(fù)

• 用ArrayList集合,基于數(shù)組的(最常使用)

2. 如果想要集合中的元素可重復(fù),而且當(dāng)前的增刪操作明顯多于查詢

• 用LinkedList集合,基于鏈表的

3. 如果想對(duì)集合中的元素去重

• 用HashSet集合,基于哈希表的(最常使用)

4. 如果想對(duì)集合中的元素去重,而且保證存取順序

• 用LinkedHashSet集合,基于哈希表和雙鏈表,效率低于HashSet

5. 如果想對(duì)集合中的元素進(jìn)行排序

• 用TreeSet集合,基于紅黑樹.后序也可以用List集合實(shí)現(xiàn)排序

源碼分析

HashSet,LinkedHashSet,TreeSet在底層都是new了一個(gè)對(duì)應(yīng)的雙列集合Map

往期傳送門: