Java集合框架

image

ZERO

????持續(xù)更新 請(qǐng)關(guān)注：https://zorkelvll.cn/blogs/zorkelvll/articles/2018/12/16/1544926812927

背景

????本文主要是記錄在學(xué)習(xí) Java集合框架過程中的一些知識(shí)點(diǎn)備忘！

20181218

1、List VS Set VS Map

  • List:核心區(qū)別在于有序性，該接口存儲(chǔ)一組不唯一（可以有多個(gè)元素引用相同的對(duì)象）、有序的對(duì)象
  • Set:核心區(qū)別在于唯一性，該接口是不允許元素重復(fù)的集合，即不會(huì)有多個(gè)元素引用相同的對(duì)象
  • Map:核心趨避在于鍵值對(duì)存儲(chǔ)，搜索效率較高；Map會(huì)維護(hù)與Key有關(guān)聯(lián)的值，兩個(gè)Key可以引用相同的對(duì)象，但Key不能重復(fù)，典型的Key是String類型，也可以是任何對(duì)象

2、Arraylist VS LinkedList

Arraylist底層使用的是數(shù)組（=>存儲(chǔ)、讀取效率高，插入刪除特定位置效率低【時(shí)間復(fù)雜度浸塑為O（n）】）；LinkedList底層使用的是雙向循環(huán)鏈表數(shù)據(jù)結(jié)構(gòu)（插入刪除特定位置俠侶特別高【時(shí)間復(fù)雜度近似為O（1）】）

3、Arraylist VS Vector

Vector類所有方法均是同步的，多個(gè)線程可以安全地訪問一個(gè)Vector對(duì)象，但是相比較而言的一個(gè)線程訪問Vector時(shí)程序代碼需要在同步操作室耗費(fèi)大量的時(shí)間；而Arraylist不是同步的！

20181217

1、HashMap為什么是線程不安全的？

在多線程下，進(jìn)行put操作可能會(huì)導(dǎo)致HashMap死循環(huán)問題，原因在于HashMap的擴(kuò)容resize()方法；

這是由于擴(kuò)容是新建一個(gè)數(shù)組，復(fù)制原數(shù)據(jù)到數(shù)組；又由于數(shù)組下標(biāo)掛有鏈表，因此也需要復(fù)制鏈表，但是多線程操作可能導(dǎo)致出現(xiàn)環(huán)形鏈表，例如：

若2個(gè)線程同時(shí)擴(kuò)容，比如線程1先將A復(fù)制到新的hash表中，然后接著復(fù)制B到鏈頭,本來B.next = null到此也就結(jié)束了（跟線程2過程一樣）；但是，由于線程2擴(kuò)容的原因，將B.next = A,繼續(xù)復(fù)制A，讓A.next=B,由此出現(xiàn)B.next=A;A.next=B

（線程2：將0-A->B->NULL =》0-B->A->NULL，則線程1：0->B->A->B）

=》JDK1.8中已經(jīng)解決了死循環(huán)問題(在resize方法中，聲明兩個(gè)引用地址，維護(hù)兩個(gè)鏈表，依次在末端添加新元素，在多線程操作情況下，無非是第二個(gè)線程重復(fù)第一個(gè)線程一模一樣的操作而已)，雖然多線程put操作不會(huì)導(dǎo)致死循環(huán)問題，但依然有其他的弊端如數(shù)據(jù)丟失等問題，因此多線程情況下還是應(yīng)該使用ConcurrentHashMap

2、HashMap VS HashSet

HashSet底層是基于HashMap實(shí)現(xiàn)的，HashSet中的方法除了clone\writeObject\readObject方法外，其他方法都是直接調(diào)用HashMap中的方法的

  • HashMap實(shí)現(xiàn)了Map接口，HashSet實(shí)現(xiàn)了Set接口
  • HashMap存儲(chǔ)鍵值對(duì)，HashSet僅存儲(chǔ)對(duì)象
  • HashMap調(diào)用put方法向map中添加元素，HashSet調(diào)用add方法向Set中添加元素
  • HashMap使用鍵Key計(jì)算HashCode；HashSet使用成員對(duì)象來計(jì)算hashcode值
  • HashMap相對(duì)于HashSet較快，因?yàn)樗鞘褂梦ㄒ坏逆I獲取對(duì)象

3、ConcurrentHashMap VS Hashtable

二者的區(qū)別主要體現(xiàn)于線程安全的實(shí)現(xiàn)方式上不同

  • 底層數(shù)據(jù)結(jié)構(gòu)：JDK1.7中的ConcurrentHashMap底層采用分段的數(shù)組+鏈表實(shí)現(xiàn)，JDK1.8則采用的是跟HashMap1.8的結(jié)構(gòu)一樣，即數(shù)組+鏈表/紅黑二叉樹；Hashtable和JDK1.8之前的HashMap底層數(shù)據(jù)結(jié)構(gòu)類似也是采用的數(shù)組+鏈表形式，數(shù)組是HashMap的主體，鏈表則主要是為了解決哈希沖突而存在的
  • 實(shí)現(xiàn)線程安全的方式(重要)：（1）JDK1.7中，ConcurrentHashMap(分段鎖)對(duì)整個(gè)桶數(shù)組進(jìn)行分割分段（Segment），每一把鎖只鎖容器其中一部分?jǐn)?shù)據(jù)，多線程訪問容器里不同數(shù)據(jù)段的數(shù)據(jù)，就不會(huì)存在鎖競(jìng)爭(zhēng)，提高并發(fā)訪問率（默認(rèn)分配16個(gè)Segment，筆Hashtable效率提高16倍）；而在JDK1.8中則摒棄了Segment的概念，直接使用Node數(shù)組+鏈表+紅黑樹的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)，并發(fā)控制使用synchronized和CAS來操作（JDK1.6以后對(duì)synchronized鎖做了很多優(yōu)化），整個(gè)看起來就像是優(yōu)化過且線程安全的HashMap，盡管在DJK1.8中還能夠看得到Segment的數(shù)據(jù)結(jié)構(gòu)，但已經(jīng)簡(jiǎn)化了屬性只是為了兼容舊版本；（2）Hashtable(同一把鎖)：使用synchronized來保證線程安全，效率非常低下；當(dāng)一個(gè)線程訪問同步方法時(shí)，其他線程也訪問同步方法，可能會(huì)進(jìn)入阻塞或輪詢狀態(tài)，如使用put添加元素，則另一個(gè)線程不能使用put添加元素也不能使用get，競(jìng)爭(zhēng)會(huì)越來越激烈效率越低

4、ConcurrentHashMap線程安全的具體實(shí)現(xiàn)方式/底層實(shí)現(xiàn)原理

  • JDK1.7：將數(shù)據(jù)分為一段一段的存儲(chǔ)，然后給每一段數(shù)據(jù)配一把鎖，當(dāng)一個(gè)線程占用鎖訪問其中一個(gè)段數(shù)據(jù)時(shí)，其他段的數(shù)據(jù)也能被其他線程訪問；

ConcurrentHashMap是由Segment數(shù)組結(jié)構(gòu)和HashEntry數(shù)組結(jié)構(gòu)組成；Segment實(shí)現(xiàn)了ReentrantLock,是一種可重入鎖，扮演鎖的角色；HashEntry用于存儲(chǔ)鍵值對(duì)數(shù)據(jù)

一個(gè)ConcurrentHashMap中包含一個(gè)Segment數(shù)組，Segment的結(jié)構(gòu)與HashMap類似，是一種數(shù)組和鏈表結(jié)構(gòu)，一個(gè)Segment包含一個(gè)HashEntry數(shù)組，每個(gè)HashEntry是一個(gè)鏈表結(jié)構(gòu)的元素，每個(gè)Segment守護(hù)著一個(gè)HashEntry數(shù)組里的元素，當(dāng)對(duì)HashEntry數(shù)組的數(shù)據(jù)進(jìn)行修改時(shí)，必須首先獲得對(duì)應(yīng)的Segment的鎖

  • JDK1.8:ConcurrentHashMap取消了Segment分段鎖，采用CAS和synchronized來保證并發(fā)安全，數(shù)據(jù)結(jié)構(gòu)跟HashMap1.8類似，數(shù)組+鏈表/紅黑二叉樹

synchronized只鎖定當(dāng)前鏈表或紅黑二叉樹的首節(jié)點(diǎn)，這樣只要hash不沖突，就不會(huì)產(chǎn)生并發(fā)，效率又提升N倍

5、集合框架底層數(shù)據(jù)結(jié)構(gòu)總結(jié)

  • Collection

List:

(1)Arraylist:Object數(shù)組
(2)Vector:Object數(shù)組
(3)LinkedList:雙向鏈表（JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán)）

Set:

(1)HashSet（無序，唯一）：基于HashMap實(shí)現(xiàn)，底層采用HashMap來保存元素
(2)LinkedHashSet:繼承于HashSet，且其內(nèi)部是通過LinkedHashMap實(shí)現(xiàn)的
(3)TreeSet(有序，唯一)：紅黑樹（自平衡的排序二叉樹）

  • Map

    (1)HashMap:JDK1.8之前是由數(shù)組+鏈表組成，數(shù)組是其主體，鏈表主要是為了解決哈希沖突而存在的（拉鏈法解決沖突）；JDK1.8之后在解決哈希沖突時(shí)，增加了紅黑樹數(shù)據(jù)結(jié)構(gòu)即當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)8）時(shí)，則會(huì)將鏈表轉(zhuǎn)化為紅黑樹以減少搜索時(shí)間
    (2)LinkedHashMap:繼承于HashMap，底層仍然是基于拉鏈?zhǔn)缴⒘薪Y(jié)構(gòu)即數(shù)組+鏈表/紅黑樹，在此基礎(chǔ)之上增加了一條雙向鏈表，使得該結(jié)構(gòu)可以保持鍵值對(duì)的插入順序，同時(shí)通過鏈表進(jìn)行相應(yīng)的操作，實(shí)現(xiàn)了訪問順序相關(guān)邏輯
    (3)Hashtable:數(shù)據(jù)+鏈表組成，數(shù)組是其主體，鏈表則主要是為了解決哈希沖突而存在的
    (4)TreeMap:紅黑樹（自平衡的排序二叉樹）

20181216

1、ArrayList VS LinkedList

  • 是否線程安全：二者均是不同步的，即不保證線程安全；
  • 底層數(shù)據(jù)結(jié)構(gòu)：ArrayList - Object數(shù)組，LinkedList - 雙向鏈表數(shù)據(jù)結(jié)構(gòu)（JDK1.6之前為循環(huán)鏈表，JDK1.7取消了循環(huán)，注意雙向鏈表和雙向循環(huán)鏈表的區(qū)別）
  • 插入和刪除是否受元素位置的影響：（1）數(shù)組，因此插入和刪除元素的時(shí)間復(fù)雜度受元素位置的影響，近似為O(n);(2)鏈表，因此插入和刪除元素的時(shí)間復(fù)雜度不受元素位置的影響，近似為O(1)
  • 是否支持快速隨機(jī)訪問：LinkedList不支持高效的隨機(jī)元素訪問，而ArrayList支持，直接通過元素的序號(hào)快速獲取元素對(duì)象
  • 內(nèi)存空間占用：ArrayList的空間浪費(fèi)主要是list列表的結(jié)尾會(huì)預(yù)留一定的容量空間，而LinkedList的空間花費(fèi)則體現(xiàn)在它的每一個(gè)元素都需要消耗比ArrayList更多的空間（因?yàn)橐娣胖苯雍罄^和直接前驅(qū)以及數(shù)據(jù)）

=>

  • RandomAccess接口：該接口中無任何定義，因此只是一個(gè)標(biāo)識(shí)，即標(biāo)識(shí)實(shí)現(xiàn)這個(gè)接口的類具有隨機(jī)訪問功能！
  • binarySearch()方法：該方法會(huì)判斷傳參List是否是RandomAccess的實(shí)例，若是則調(diào)用indexedBinarySearch方法，否則調(diào)用iteratorBinarySearch方法

=>

  • ArrayList實(shí)現(xiàn)了RandomAccess接口，LinkedList沒有實(shí)現(xiàn)；
  • 數(shù)組天然支持隨機(jī)訪問，時(shí)間復(fù)雜度O(1),因此稱為快速隨機(jī)訪問；鏈表需要遍歷到特定位置才能訪問特定位置的元素，時(shí)間復(fù)雜度為O(n)，所以不支持快速隨機(jī)訪問
  • ArrayList是實(shí)現(xiàn)了RandomAccess接口，是表明了其具有快速隨機(jī)訪問功能，該接口僅是標(biāo)識(shí)，并不是說ArrayList實(shí)現(xiàn)了該接口才具有快速隨機(jī)訪問功能的

=>

  • 實(shí)現(xiàn)了RandomAccess接口的List，優(yōu)先使用普通for循環(huán)，其次是foreach

  • 未實(shí)現(xiàn)RandomAccess接口的List，優(yōu)先選擇iterator遍歷(foreach遍歷底層也是通過iterator實(shí)現(xiàn)的)，大size的List數(shù)據(jù)不要使用普通for循環(huán)

  • 雙向鏈表：也即雙鏈表，是鏈表的一種，它的每個(gè)數(shù)據(jù)節(jié)點(diǎn)均有兩個(gè)指針，分別指向直接后繼和直接前驅(qū)；因此，從雙向鏈表中的任意一個(gè)節(jié)點(diǎn)開始，均可以很方便地訪問它的前驅(qū)節(jié)點(diǎn)和后繼節(jié)點(diǎn)，一般都是構(gòu)造雙向循環(huán)鏈表，JDK1.6之前的LinkedList底層使用的就是雙向循環(huán)鏈表

2、ArrayList VS Vector

  • Vector類的所有方法均是同步的，兩個(gè)線程可以安全地訪問同一個(gè)Vector對(duì)象，但是一個(gè)線程訪問Vector需要在同步操作上耗費(fèi)大量的時(shí)間
  • ArrayList不是同步的，不需要保證線程安全時(shí)建議使用ArrayList

3、HashMap的底層實(shí)現(xiàn)

  • JDK1.8之前：

底層是“數(shù)組+鏈表”數(shù)據(jù)結(jié)構(gòu)，即鏈表散列；

HashMap通過key的hashCode經(jīng)過擾動(dòng)函數(shù)處理過后得到hash值，然后通過(n-1)&hash判斷當(dāng)前元素存放的位置（n即數(shù)組的長(zhǎng)度），如果當(dāng)前位置存在元素的話則判斷該元素與要存入的h元素的ash值以及key是否相同，如果相同的話則直接覆蓋，否則不相同則通過拉鏈法解決沖突

擾動(dòng)函數(shù)：也就是HashMap的hash方法，該方法即擾動(dòng)函數(shù)主要是為了防止一些實(shí)現(xiàn)比較差的hashCode方法，以減少碰撞

hash方法源碼：

//jdk1.8方法相較于jdk1.7更加簡(jiǎn)化，但是原理不變
static final int hash(Object key) {
      int h;
      // key.hashCode()：返回散列值也就是hashcode
      // ^ ：按位異或
      // >>>:無符號(hào)右移，忽略符號(hào)位，空位都以0補(bǔ)齊
      return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

//jdk1.7，該方法性能會(huì)稍差一點(diǎn)點(diǎn)，因?yàn)楫吘箶_動(dòng)了4次
static int hash(int h) {
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

拉鏈法：將鏈表和數(shù)組相結(jié)合，即創(chuàng)建一個(gè)鏈表數(shù)組，數(shù)組中每一格都是一個(gè)鏈表，若遇到hash沖突則將沖突的值加到鏈表中即可

  • JDK1.8之后

在JDK1.8中，對(duì)于解決哈希沖突有了較大的變化，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)8），則會(huì)將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時(shí)間

TreeMap、TreeSet以及JDK1.8之后的HashMap底層均用到紅黑樹，紅黑樹就是為了解決二叉查找樹的缺陷，因?yàn)槎娌檎覙湓谀承┣闆r下會(huì)退化成一個(gè)線性結(jié)構(gòu)

4、HashMap VS HashTable

  • 線程安全：HashMap非線程安全，HashTable線程安全；HashTable內(nèi)部的方法基本都是經(jīng)過synchronized修飾的（若需要保證線程安全的話，可以使用ConcurrentHashMap）
  • 效率：由于線程安全的問題，HashTable的效率比HashMap低一點(diǎn)，且HashTable已經(jīng)基本被淘汰，不要在代碼中使用它
  • 對(duì)Null key 和Null value的支持：HashMap中，null可以作為主鍵，這樣的鍵只有一個(gè)，可以有一個(gè)或多個(gè)鍵所對(duì)應(yīng)的值為null；但是在HashTable中put進(jìn)的鍵值只要有一個(gè)null，則直接拋出NullPointerException
  • 初始容量大小&每次擴(kuò)充容量大小的不同：（1）創(chuàng)建時(shí)若未指定初始容量值，HashTable默認(rèn)初始大小為11，每次擴(kuò)充容量變?yōu)樵瓉淼?n+1;HashMap默認(rèn)初始大小為16，每次擴(kuò)充容量變?yōu)樵瓉淼?倍；（2）創(chuàng)建時(shí)若指定初始容量值，則HashTable會(huì)直接使用給定的大小，而HashMap會(huì)將其擴(kuò)充為2的冪次方大?。℉ashMap中的tableSizeFor方法保證）
  • 底層數(shù)據(jù)結(jié)構(gòu)：JDK1.8以后的HashMap在解決哈希沖突時(shí)，當(dāng)鏈表長(zhǎng)度大于閾值（默認(rèn)8），則會(huì)將鏈表轉(zhuǎn)化為紅黑樹以減少搜索時(shí)間，而HashTable則沒有這樣的機(jī)制

5、HashMap的長(zhǎng)度為什么是2的冪次方

為了能夠讓HashMap存取高效，盡量減少碰撞，也即要盡量把數(shù)據(jù)分配均勻！Hash值范圍是-2147483648~2147483648，共約40億映射空間，只要hash函數(shù)映射的比較均勻松散，一般很難出現(xiàn)碰撞，但是40億長(zhǎng)度的數(shù)組在內(nèi)存中存放不下的，因此這個(gè)散列值是不能直接使用的

=>考慮先對(duì)數(shù)組的長(zhǎng)度進(jìn)行取模運(yùn)算，計(jì)算的余數(shù)用來作為存放的位置也即數(shù)組下標(biāo)，即數(shù)組下標(biāo)的計(jì)算方法是“(n-1) & hash”，其中n為數(shù)組長(zhǎng)度,這也就是為什么HashMap的長(zhǎng)度是2的冪次方

=>為什么是2的冪次方？：：取模運(yùn)算，首先就是采用%操作進(jìn)行實(shí)現(xiàn)，=>"取余%操作中，在除數(shù)是2的冪次方時(shí)，等價(jià)于與其除數(shù)減一的與&操作，也即hash%length == hash&(length-1),,這個(gè)等價(jià)的前提就是length是2的n次方"

=>并且，在采用二進(jìn)制位操作&，相對(duì)于%能夠提高運(yùn)算效率，這也是為什么HashMap的長(zhǎng)度要是2的冪次方！

說明：本JavaGuide系列博客為來源于https://github.com/Snailclimb/JavaGuide
等學(xué)習(xí)網(wǎng)站或項(xiàng)目中的知識(shí)點(diǎn)，均為自己手打鍵盤系列且內(nèi)容會(huì)根據(jù)繼續(xù)學(xué)習(xí)情況而不斷地調(diào)整和完善！

?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀點(diǎn)，簡(jiǎn)書系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

  • 姓名：房小慧 學(xué)號(hào)：17101223361 專業(yè)：軟件工程 【嵌牛導(dǎo)讀】：在Java開發(fā)過程中，Java環(huán)境變量的...
    happyforev_2e3c閱讀 2,458評(píng)論 0贊 3
  • 向黑夜借了眼睛 窺探塵世被安葬呼吸聲 我聽見遠(yuǎn)處汽笛聲被撕裂了心臟 飄渺 往，比心府更深的地方隕落 如果不曾看見 ...
    弓谷所長(zhǎng)閱讀 424評(píng)論 0贊 4
  • 民歌:小時(shí)候爸爸唱在那桃花盛開的地方 戲?。盒r(shí)候，鄉(xiāng)里的電影院戲劇演出/黃梅戲高中畢業(yè)，14年 民樂：大學(xué)時(shí)候磁...
    乞丐女王閱讀 198評(píng)論 0贊 0
  • 插件開發(fā)系列 Android Studio插件開發(fā)1之插件介紹與環(huán)境搭建Android Studio插件開發(fā)2之A...
    Axlchen閱讀 2,002評(píng)論 0贊 4

友情鏈接更多精彩內(nèi)容