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

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

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