Java集合類知識點總結(jié)

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

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

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