Java集合類知識(shí)點(diǎn)總結(jié)

PAGE15Java集合類Java集合類 11. Map 31.1. HashMap 31.1.1. 底層實(shí)現(xiàn) 31.1.2. 特點(diǎn) 31.1.3. 源碼分析 41.1.4. 多線程可能出現(xiàn)的問題 51.2. ConcurrentHashMap 61.2.1. 底層實(shí)現(xiàn) 61.2.2. 源碼分析 71.3. HashTable 91.3.1. HashTable是線程安全的，因?yàn)樗蟹椒ㄉ隙技恿藄ynchronized關(guān)鍵字。 91.3.2. HashTable的key和value都不可以為null。 91.3.3. 擴(kuò)容時(shí)，capacity=2*capacity+1 91.3.4. 數(shù)組默認(rèn)大小為11 91.3.5. 查找下標(biāo)時(shí)，沒有使用hash&length-1，而是直接進(jìn)行計(jì)算的 91.4. TreeMap 101.4.1. 底層實(shí)現(xiàn)為紅黑樹 101.4.2. TreeMap是一個(gè)有序的key-value集合，基于紅黑樹實(shí)現(xiàn)。該映射根據(jù)其鍵的自然順序進(jìn)行排序，或者根據(jù)創(chuàng)建時(shí)提供的Comparator進(jìn)行排序 101.4.3. 接口實(shí)現(xiàn) 101.4.4. Entry 111.5. LinkedHashMap 111.5.1. 底層是數(shù)組+鏈表+紅黑樹+雙向鏈表 111.5.2. 維護(hù)鏈表順序和訪問順序 111.5.3. LinkedHashMap可以通過構(gòu)造參數(shù)accessOrder來指定雙向鏈表是否在元素被訪問后改變其在雙向鏈表中的位置。 111.5.4. 當(dāng)accessOrder為true時(shí)，get方法和put方法都會(huì)調(diào)用recordAccess方法使得最近使用的Entry移到雙向鏈表的末尾；當(dāng)accessOrder為默認(rèn)值false時(shí)，recordAccess方法什么也不會(huì)做。 111.5.5. LRU實(shí)現(xiàn) 112. Collection 122.1. List 122.1.1. ArrayList 122.1.2. LinkedList 132.1.3. CopyOnWriteArrayList 132.2. Set 142.2.1. HashSet 142.2.2. TreeSet 152.2.3. LinkedHashSet 15MapHashMap底層實(shí)現(xiàn)1.7數(shù)組+鏈表數(shù)組的優(yōu)點(diǎn)是訪問速度快，但是插入刪除操作慢因?yàn)閿?shù)組在內(nèi)存中是連續(xù)存放的，因此存取很快鏈表的優(yōu)點(diǎn)是插入刪除速度快，但是訪問速度慢由于鏈表不是連續(xù)存放的，因此插入刪除時(shí)，只需要修改前后指針的指向即可，不需要移動(dòng)元素位置1.8數(shù)組+鏈表+紅黑樹拉鏈法由頭插法改為了尾插法因?yàn)轭^插法在多線程的時(shí)候可能會(huì)導(dǎo)致死循環(huán)鏈表長(zhǎng)度大于8的時(shí)候轉(zhuǎn)化為紅黑樹紅黑樹的時(shí)間復(fù)雜度為logn,線性表查找的平均時(shí)間復(fù)雜度為n/2,因此在鏈表長(zhǎng)度為8時(shí)進(jìn)行轉(zhuǎn)化效率最高紅黑樹的轉(zhuǎn)化也是比較消耗性能的鏈表個(gè)數(shù)超過8則鏈表轉(zhuǎn)換成樹結(jié)構(gòu)，鏈表個(gè)數(shù)小于8則樹結(jié)構(gòu)轉(zhuǎn)換成鏈表特點(diǎn)存取的時(shí)間復(fù)雜度為O(1)源碼分析put()1.判斷key是否為null，如果為null，調(diào)用putlForNullKey，將key插入到數(shù)組下標(biāo)為0的位置2.調(diào)用hash()方法計(jì)算key的hashcode，得到hash值3.調(diào)用indexFor()方法進(jìn)行取模運(yùn)算，得到元素的下標(biāo)位置1.indexFor方法為：h&(length-1)2.使用與運(yùn)算，計(jì)算速度更快，因?yàn)槎M(jìn)制運(yùn)算比十進(jìn)制運(yùn)算效率更高(十進(jìn)制運(yùn)算還需要將二進(jìn)制轉(zhuǎn)化為十進(jìn)制)3.length之所以要設(shè)定為2次冪，就是為了這個(gè)indexFor方法服務(wù)4.可以讓散列更加均勻，length-1的最后一位為1，因此進(jìn)行與運(yùn)算時(shí)，可以散列到奇數(shù)和偶數(shù)的下標(biāo)位置，如果對(duì)length直接取模，由于length為2次冪，所以最后一位一定為0，所以與運(yùn)算的結(jié)果一定是偶數(shù)，這也就導(dǎo)致奇數(shù)下標(biāo)的位置不能被散列到。4.依次和該下標(biāo)位置上的鏈表中的node節(jié)點(diǎn)比較key是否相等e.hash==hash&&((k=e.key)==key||key.equals(k))首先判斷e.hash==hash是因?yàn)椴煌膋ey值也可能被散列到同一個(gè)位置，因此首先判斷hash值，如果不相等則兩個(gè)key肯定不等如果相等，再通過==和equals比較是否相等，之所以要先判斷hash值是否相等，是因?yàn)閑qual()很耗性能，因此先判斷hash值能夠提高效率重寫了hashcode()方法就必須重寫equals方法5.如果相等，更新value值，如果不相等，使用頭插法(1.7)/尾插法(1.8)將entry(1.7)/Node(1.8)插入到鏈表中g(shù)et()和put()方法類似，獲取到桶的下標(biāo)，再在鏈表上查找key值，再獲取key對(duì)應(yīng)的value值resize()當(dāng)hashmap中的元素個(gè)數(shù)超過數(shù)組大小*loadFactor時(shí)，就會(huì)進(jìn)行數(shù)組擴(kuò)容擴(kuò)容時(shí)，令capacity為原來的兩倍。1.7時(shí)，需要new一個(gè)新數(shù)組，并對(duì)舊數(shù)組上的所有元素進(jìn)行indexFor()操作確定下標(biāo)地址,這一步很費(fèi)時(shí)，1.8時(shí)只需判斷hash值的左邊新增的那一位是否為1，即可判斷此節(jié)點(diǎn)是留在原地lo還是移動(dòng)去高位hi,如果為1，則移動(dòng)去高位，否則不變1.7時(shí)，擴(kuò)容的時(shí)候可能出現(xiàn)死循環(huán)，1.8沒有這個(gè)問題構(gòu)造方法在第一次put()的時(shí)候，數(shù)組才初始化數(shù)組的長(zhǎng)度為大于指定值的最小二次冪數(shù)組默認(rèn)大小為16多線程可能出現(xiàn)的問題1.擴(kuò)容時(shí)可能出現(xiàn)死循環(huán)2.put的時(shí)候可能被失效/覆蓋線程A,B同時(shí)調(diào)用addEntry方法，同時(shí)獲取到了相同的頭節(jié)點(diǎn)，然后A寫入新的頭結(jié)點(diǎn)之后，B也寫入新的頭結(jié)點(diǎn)，那B的寫入操作就會(huì)覆蓋A的寫入操作造成A的寫入操作丟失。3.修改的時(shí)候可能被覆蓋線程A,B先后修改同一key值的value，會(huì)導(dǎo)致覆蓋4.put非null元素后get出來的卻是null擴(kuò)容時(shí)調(diào)用的transfer方法，在獲取數(shù)組的每個(gè)頭節(jié)點(diǎn)的時(shí)候，在將e=頭節(jié)點(diǎn)之后，都會(huì)將頭節(jié)點(diǎn)置空，此時(shí)get可能導(dǎo)致獲取到的值為0ConcurrentHashMap底層實(shí)現(xiàn)1.7segment數(shù)組+HashEntry數(shù)組(數(shù)組+鏈表)chm由一個(gè)segment數(shù)組組成segment每個(gè)segment元素包含一個(gè)HashEntry數(shù)組，每個(gè)HashEntry包含一個(gè)鏈表HashEntry大部分成員變量都為finalfinalkkeyvolatileVvaluefinalinthashfinalHashEntry<K,V>next1.8數(shù)組+鏈表+紅黑樹源碼分析put()基本流程1.7通過兩次hash確定第一次Hash定位到Segment通過segmentFor()函數(shù)進(jìn)行,計(jì)算方式也和indexFor()相同SegmentMaskssize-1SegmentShift32-sshiftssize是大于ConcurrentLevel的最小二次冪第二次Hash定位到元素所在的鏈表的頭部定位方法和HashMap中的indexFor()相同通過segment.lock加鎖1.8通過兩次hash確定通過CAS+synchronized加鎖1.如果沒有hash沖突就直接通過CAS插入2.如果有hash沖突或者CAS操作失敗，說明存在并發(fā)情況，使用synchronized加鎖3.如果插入成功就調(diào)用addCount（）方法統(tǒng)計(jì)size，并且檢查是否需要擴(kuò)容源碼分析1.ensureSegment1.判斷是否被其他線程初始化，這里使用了getObjectVolatile()方法

2.使用segment[0]的屬性來初始化其他槽

3.使用while()循環(huán)，內(nèi)部使用CAS操作，嘗試初始化槽2.segment.put()get()get不需要加鎖，因?yàn)镠ashEntry的value值設(shè)定為了volatile如果get()到的是null值，則可能這個(gè)key，value對(duì)正在put的過程中，如果出現(xiàn)這種情況，那么就通過lock加鎖來保證取出的value是完整的resize()構(gòu)造函數(shù)先根據(jù)ConcurrentLevel構(gòu)造出Segment數(shù)組Segment數(shù)組大小是不大于concurrentLevel的最大的2的指數(shù)每個(gè)Segment中的HashEntry數(shù)組的大小都是大于指定大小的最小二次冪每個(gè)hashEntry的大小為大于initialCapacity/concurrentLevel的最小二次冪初始參數(shù)initialCapacity(每個(gè)HashEntry的長(zhǎng)度)loadFactor：擴(kuò)容因子concurrencyLevel：并發(fā)度，指Segment數(shù)組的長(zhǎng)度remove在定位到待刪除元素的位置以后，程序就將待刪除元素前面的那一些元素全部復(fù)制一遍，然后再一個(gè)一個(gè)重新接到鏈表上去。尾結(jié)點(diǎn)指向e的下一個(gè)結(jié)點(diǎn)。e后面的結(jié)點(diǎn)不需要復(fù)制，它們可以重用。因?yàn)镠ashEntry中的next是final，所以只能先把待刪除之前的元素復(fù)制了再刪除sizesize操作就是遍歷了兩次Segment，每次記錄Segment的modCount值，然后將兩次的modCount進(jìn)行比較，如果相同，則表示期間沒有發(fā)生過寫入操作，就將原先遍歷的結(jié)果返回，如果不相同，就需要將所有的Segment都鎖住，然后一個(gè)一個(gè)遍歷了，HashTableHashTable是線程安全的，因?yàn)樗蟹椒ㄉ隙技恿藄ynchronized關(guān)鍵字。HashTable的key和value都不可以為null。擴(kuò)容時(shí)，capacity=2*capacity+1數(shù)組默認(rèn)大小為11查找下標(biāo)時(shí)，沒有使用hash&length-1，而是直接進(jìn)行計(jì)算的TreeMap底層實(shí)現(xiàn)為紅黑樹能夠保證樹總是平衡的，如果插入刪除導(dǎo)致樹不平衡，會(huì)自動(dòng)進(jìn)行調(diào)整變色左旋右旋查找的平均時(shí)間復(fù)雜度為O(logN)主要規(guī)則1.每個(gè)節(jié)點(diǎn)或者是黑色，或者是紅色。2.根節(jié)點(diǎn)是黑色3.葉子節(jié)點(diǎn)為黑色4.如果一個(gè)節(jié)點(diǎn)是紅色的，則它的子節(jié)點(diǎn)必須是黑色的5.從一個(gè)節(jié)點(diǎn)到該節(jié)點(diǎn)的子孫節(jié)點(diǎn)的所有路徑上包含相同數(shù)目的黑節(jié)點(diǎn)。TreeMap是一個(gè)有序的key-value集合，基于紅黑樹實(shí)現(xiàn)。該映射根據(jù)其鍵的自然順序進(jìn)行排序，或者根據(jù)創(chuàng)建時(shí)提供的Comparator進(jìn)行排序接口實(shí)現(xiàn)NavigableMap是SortedMap接口的子接口，在其基礎(chǔ)上擴(kuò)展了一些方法，例如floorEntry，lowEntry,ceilingEntry等為了防止外部修改Entry，使用了ExportEntry修飾floorEntry等方法SortedMap定義按照key排序的Map結(jié)構(gòu)，能夠令Map按照key的自然順序或者構(gòu)造器順序進(jìn)行排序。Entry包含了left，right，parent節(jié)點(diǎn)LinkedHashMap底層是數(shù)組+鏈表+紅黑樹+雙向鏈表同時(shí)使用一個(gè)額外的雙向鏈表來維護(hù)鏈表的訪問順序維護(hù)鏈表順序和訪問順序Node節(jié)點(diǎn)額外增加了before和after指針，用于維護(hù)鏈表的訪問順序next指針用來維護(hù)鏈表順序LinkedHashMap可以通過構(gòu)造參數(shù)accessOrder來指定雙向鏈表是否在元素被訪問后改變其在雙向鏈表中的位置。當(dāng)accessOrder為true時(shí)，get方法和put方法都會(huì)調(diào)用recordAccess方法使得最近使用的Entry移到雙向鏈表的末尾；當(dāng)accessOrder為默認(rèn)值false時(shí)，recordAccess方法什么也不會(huì)做。LRU實(shí)現(xiàn)插入數(shù)據(jù)后對(duì)調(diào)用afterNodeInsertion，afterNodeInsertion()方法中會(huì)調(diào)用removeEldestEntry，如果removeEldestEntry(first)返回true，按照LRU策略，那么會(huì)刪除頭節(jié)點(diǎn)(注意這里刪除的是頭節(jié)點(diǎn)?。?！所以每次訪問元素或者插入元素之后都要將該元素放到鏈表末尾)。這個(gè)也是實(shí)現(xiàn)LRU的關(guān)鍵點(diǎn)?。。。。ollectionListArrayList底層實(shí)現(xiàn)動(dòng)態(tài)數(shù)組能夠?qū)崿F(xiàn)隨機(jī)存取實(shí)現(xiàn)了RandomAccess接口fail-fast機(jī)制在使用迭代器遍歷list時(shí)，如果modCount和expectedCount不匹配，就會(huì)直接拋出異常modCount在AbstractList中定義使用迭代器自帶的remove()函數(shù)的時(shí)候，如果刪除了list中元素，不會(huì)出現(xiàn)fail-fast,因?yàn)榈鲿?huì)調(diào)整modCount和expectedCount值自定義了序列化方法因?yàn)閍rrayList的底層數(shù)組中，可能存在值為null的元素，序列化這些元素是沒有意義的，因此自定義了序列化方法，只序列化數(shù)組中非null的元素通過readObject()和writeObject()方法實(shí)現(xiàn)源碼實(shí)現(xiàn)擴(kuò)容：capacity=1.5*capacity通過Arrays.copyOf()System.copyOf()每次擴(kuò)容的時(shí)候，都會(huì)傳入一個(gè)minCapacity,即擴(kuò)容之后的數(shù)組長(zhǎng)度，對(duì)于add方法，是原size+1,對(duì)于addAll方法，是size+newSize,如果原數(shù)組長(zhǎng)度*1.5仍不能存放所需的元素，那么就會(huì)直接令數(shù)組長(zhǎng)度為minCapacityArrayList是插入前擴(kuò)容,擴(kuò)容邏輯為ensureCapacityInternal()>ensureExplicitCapacity()>grow()LinkedList底層實(shí)現(xiàn)雙向鏈表常用apiaddofferremove適合插入刪除多的場(chǎng)合CopyOnWriteArrayList和ArrayList基本一模一樣