1. 單列集合Collection

• 指的是在集合里面放的是單個(gè)的對(duì)象
• Collection 接口有兩個(gè)重要的子接口 List、Set
• Collection提供了size()方法，List提供了get()方法
  
  

1.0 Collection接口實(shí)現(xiàn)類的特點(diǎn)

1. Collection接口的實(shí)現(xiàn)子類可以存放多個(gè)元素，每個(gè)元素可以是Object；
2. Collection的實(shí)現(xiàn)類，有些可以存放重復(fù)的元素，有些不可以；
3. Collection的實(shí)現(xiàn)類，有些是有序的（比如List），有些是無(wú)序的（比如Set）；
4. Collection接口沒有直接的實(shí)現(xiàn)子類，通過它的子接口Set和List來(lái)實(shí)現(xiàn)的；

1.1 Collection常用方法

1. add添加單個(gè)元素,只要是Object的子類，都可以往里放,輸入整數(shù)存在一個(gè)自動(dòng)裝箱的過程
   
2. remove()刪除指定的元素
   remove構(gòu)成重載: remove(Object 0) 返回布爾值; remove(int index) 返回被刪除的對(duì)象
   
3. contains()查找某個(gè)元素是否存在
   
4. size()獲取元素個(gè)數(shù),從1開始計(jì)數(shù)
   
5. addAll()可以添加多個(gè)元素
   可以在某個(gè)下標(biāo)存入一個(gè)實(shí)現(xiàn)了Collection接口的ArrayList
   
6. removeAll()刪除多個(gè)元素
   參數(shù)為一個(gè)實(shí)現(xiàn)了Collection接口的ArrayList
   
7. clear()清空
   
8. isEmpty()判斷是否為空
   
9. containsAll()查找多個(gè)元素是否都存在
   參數(shù)為一個(gè)實(shí)現(xiàn)了Collection接口的ArrayList
   

1.2 繼承了Iterable接口

1. 由于Collection實(shí)現(xiàn)了Iterable接口，所以所有實(shí)現(xiàn)了Collection接口的集合類都有一個(gè)iterator()方法，返回一個(gè)實(shí)現(xiàn)了Iterator接口的對(duì)象，即迭代器；
   
2. iterator.next()取不到值的時(shí)候，NoSuchElementException；

1.3 Collection接口遍歷元素的方法

1.3.1 Iterator迭代器

Iterator對(duì)象稱為迭代器，主要用于遍歷Collection集合中的元素；所有實(shí)現(xiàn)了Collection接口的實(shí)現(xiàn)類都有這個(gè)方法；(shortcuts: itit)

1. 遍歷collection集合，得到collection對(duì)象對(duì)應(yīng)的迭代器；iterator.next()，返回下一個(gè)元素，類型Object；
   obj編譯類型是Object，運(yùn)行類型是實(shí)際存的對(duì)象；
   
2. 如果要再次遍歷，需要重置迭代器； 當(dāng)?shù)鞯竭_(dá)最后一個(gè)元素時(shí)，重置迭代器
   

1.3.2 增強(qiáng)for循環(huán)

1. 增強(qiáng)for循環(huán)底層仍然是用的迭代器；所以可以認(rèn)為增強(qiáng)for循環(huán)就是簡(jiǎn)化版的迭代器遍歷；(shortcuts: I、iter)
   
   返回一個(gè)Iterator對(duì)象；
   
   調(diào)用iterator.hasNext()方法,判斷是不是集合中的最后一個(gè)對(duì)象；
   如果不是，調(diào)用iterator.next()取得下一個(gè)對(duì)象；
   

1.4 List接口

List支持索引；

1. List接口中的元素是有序的(添加順序和取出順序一致)，并且元素可以重復(fù)；
   
2. List集合中的每個(gè)元素都有其對(duì)應(yīng)的順序索引，List支持索引，索引從0開始；
   

1.4.1 List常用方法

1. void add(int index, Object ele); 在index位置插入ele對(duì)象；如果沒有index，則默認(rèn)在最后插入；
   
2. addAll(int index, Collection c);從index處將集合c中所有的元素添加進(jìn)來(lái)；
   boolean addAll(int index, Collection c);
   boolean addAll(Collection c);
   
3. int indexOf(Object o); 返回o對(duì)象在集合中首次出現(xiàn)的索引；
   
4. int lastIndexOf(Object o);返回o對(duì)象在集合中最后一次出現(xiàn)的索引；
   
5. Object remove(int index); 移除給定索引處的元素，并返回該元素
   boolean remove(Object o);
   
6. Object set(int index, Object ele); 設(shè)置index處的元素為ele，相當(dāng)于替換
   index不可以越界：IndexOutOfBoundsException
   
7. List subList(int fromIndex, int toIndex); 截取fromIndex到toIndex的元素，返回一個(gè)集合
   前閉后開，fromIndex <= 返回的元素 < toIndex; [fromIndex, toIndex);
   

1.4.2 List接口遍歷元素的方法

1. Iterator迭代器
   
2. 增強(qiáng)for循環(huán)
   
3. 普通for循環(huán)
   

1.4.3 ArrayList類

1. ArrayList 線程不安全,Vector 線程安全；
2. ArrayList中維護(hù)了一個(gè)Object類型的數(shù)組elementData；transient Object[] elementData;（transient修飾的屬性表示這個(gè)屬性不會(huì)被序列化）；
3. 當(dāng)創(chuàng)建ArrayList對(duì)象時(shí)，如果使用的是無(wú)參構(gòu)造器，則初始elementData的容量為0；第一次添加時(shí)，elementData擴(kuò)容為10，第二次添加時(shí)，elementData則擴(kuò)容為原來(lái)的1.5倍；
4. 如果使用的是指定大小的構(gòu)造器，則初始elementData為指定大小，如果需要擴(kuò)容，則直接擴(kuò)容為原來(lái)的1.5倍；

1.4.3.1 ArrayList底層源碼，1.5倍擴(kuò)容，Object[]數(shù)組

transient 瞬間；短暫的
final DEFAULTCAPACITY_EMPTY_ELEMENTDATA = 0；
final DEFAULT_CAPACITY = 10;

private static int calculateCapacity(Object[] elementData, int minCapacity) {
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        return minCapacity;
    }

    private void ensureCapacityInternal(int minCapacity) {
    	//calculateCapacity()返回的是10或者elementData數(shù)組的容量
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }

    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;

        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
    
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //向右移動(dòng)一位，除以2，1.5倍
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        // minCapacity is usually close to size, so this is a win:
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    
public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
    }

1. 使用無(wú)參構(gòu)造器創(chuàng)建ArrayList源碼
   
   1.1 創(chuàng)建了一個(gè)空的elementData數(shù)組
   
   
   1.2 先確定是否要擴(kuò)容；然后然后再執(zhí)行賦值操作
   
   1.3 ensureCapacityInternal(): 該方法確定minCapacity(最小容量)
   (1) 第一次擴(kuò)容為10
   
   1.4 (1) modCount++；modCount用來(lái)記錄當(dāng)前這個(gè)集合被修改的次數(shù)，防止被多線程操作；
   (2) 如果elementData容量不夠，就調(diào)用grow()去擴(kuò)容
   
   1.5 使用擴(kuò)容機(jī)制來(lái)確定要擴(kuò)容到多大；
   (1) 第一次擴(kuò)容后newCapacity=10；
   原因：elenmentData數(shù)組的長(zhǎng)度為0，賦給oldCapacity；oldCapacity向右移一位，即: oldCapacity + oldCapacity / 2，賦給newCapacity，則newCapacity的值還為0；此時(shí)minCapacity為10，newCapacity < minCapacity，所以將minCapacity賦給newCapacity。
   (2) 第二次擴(kuò)容及其以后，按照1.5倍擴(kuò)容；
   (3) 擴(kuò)容使用的是Arrays.copyOf(); 保證原來(lái)數(shù)據(jù)安全的情況下，再增加空間；
   
   1.6. Idea再Debug情況下，顯示的數(shù)據(jù)默認(rèn)是已簡(jiǎn)化的，如果希望看到完成的數(shù)據(jù)，需要做設(shè)置
   
   
2. 使用有參構(gòu)造器創(chuàng)建和使用ArrayList
   
   2.1 創(chuàng)建了一個(gè)指定大小的elementData數(shù)組(Object[capacity])
   如果是有參的構(gòu)造器，那么擴(kuò)容機(jī)制是：第一次按照elementData的1.5倍擴(kuò)容，整個(gè)執(zhí)行流程還是和前面一樣；
   

1.4.4 Vector類

1. Vector類底層也是一個(gè)對(duì)象數(shù)組；protected Object[] elementData;

2. Vector是線程同步的，即線程安全，Vector常用方法都帶有synchronized；

1.4.4.1 Vector底層源碼，2倍擴(kuò)容

1. 使用無(wú)參構(gòu)造器創(chuàng)建Vector
   
   1.1 new Vector()底層：調(diào)用無(wú)參構(gòu)造器，初始容量為10，initialCapacity=10；
   
   Vector(int)，調(diào)用一個(gè)參數(shù)的構(gòu)造器
   
   Vector(int,int)，調(diào)用兩個(gè)參數(shù)的構(gòu)造器1.2 執(zhí)行add()操作；
   1.3 確定是否需要擴(kuò)容【minCapacity - elementData.length > 0】
   
   1.4 如果需要的elementData大小不夠用，就擴(kuò)容2倍；
   newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity);
   
2. 使用有參構(gòu)造器創(chuàng)建Vector，初始容量為指定大??；
   
   
   
3. 使用兩個(gè)參數(shù)的構(gòu)造器：Vector(int,int)，可以自定義擴(kuò)容步長(zhǎng)；
   
   
   capacityIncrement > 0 ? capacityIncrement : oldCapacity
   

1.4.4.2 ArrayList 和Vector比較

1. Vector如果是無(wú)參構(gòu)造器，則默認(rèn)初始容量為10，之后擴(kuò)容按照2倍擴(kuò)容；
   如果是有參構(gòu)造器則第一次指定大小，之后擴(kuò)容按照2倍擴(kuò)容；
2. ArrayList第一次擴(kuò)容為10，第二次擴(kuò)容及其以后，按照1.5倍擴(kuò)容；

1.4.5 LinkedList類

1. LinkedList中維護(hù)了兩個(gè)屬性first和last，分別指向首結(jié)點(diǎn)和尾結(jié)點(diǎn)；
2. 每個(gè)節(jié)點(diǎn)中(Node對(duì)象)，又維護(hù)了prev、next、item三個(gè)屬性；其中通過prev指向前一個(gè)，通過next指向后一個(gè)，最終實(shí)現(xiàn)雙向鏈表；
3. 所有LinkedList的元素的添加和刪除，不是通過數(shù)組完成的，所以效率極高；
4. LinkedList也是線程不安全的；

1.4.5.1 簡(jiǎn)單實(shí)現(xiàn)雙向鏈表

• 從頭到尾循環(huán)鏈表
  
• 從尾到頭循環(huán)鏈表
  
• 添加節(jié)點(diǎn)
  
  

1.4.5.2 LinkedList底層源碼，沒有擴(kuò)容，雙向鏈表

1. 調(diào)用無(wú)參構(gòu)造器后LinkedList的屬性first=null，last=null
   
   size大小為0，只是做了一個(gè)初始化
   
   
   1.2 執(zhí)行add方法；
   
   1.2.1 添加第一個(gè)節(jié)點(diǎn)，加入到雙向鏈表的最后；
   
   
   1.2.2 LinkedList的first屬性和last屬性都指向了同一個(gè)節(jié)點(diǎn)，這個(gè)節(jié)點(diǎn)兩頭為空，item值為1；
   
   1.2.3 內(nèi)存布局圖：
   
   1.2.4 向鏈表添加第二個(gè)節(jié)點(diǎn)
   
2. remove()，默認(rèn)刪除第一個(gè)節(jié)點(diǎn)；（新版本遺棄了此方法）
   
   
   
   
   2.1 首先讓f指向first，即f指向了第一個(gè)節(jié)點(diǎn)；
   
   2.2 將f.next即第二個(gè)節(jié)點(diǎn)賦給了next
   
   2.3 將第一個(gè)節(jié)點(diǎn)的item和next置空
   
   2.4 first指向next，即first也指向了第二個(gè)節(jié)點(diǎn)
   
   2.5 將next.pre置空，此時(shí)第一個(gè)節(jié)點(diǎn)成為垃圾；
   
3. linkedList.set(1,999); 修改某個(gè)節(jié)點(diǎn)對(duì)象；索引從0開始；
4. linkedList.get(1); 取得第二個(gè)節(jié)點(diǎn)對(duì)象；

1.4.5.3 ArrayList和LinkedList比較

1.5 Set接口，不提供索引

1. Set接口是無(wú)序的（添加順序和取出順序不一致），原因： 添加元素時(shí)，會(huì)根據(jù)元素的哈希值進(jìn)行排序；排序后，位置就固定了；
2. 不允許重復(fù)元素，最后只能包含一個(gè)null；
   
3. Set接口的實(shí)現(xiàn)類沒有索引；
4. Set接口的遍歷方式

• 迭代器
• 增強(qiáng)for循環(huán)
  

4. HashSet底層機(jī)制: HashMap，即：數(shù)組+鏈表+紅黑樹

1.5.1 HashSet

1.5.1.1 簡(jiǎn)單實(shí)現(xiàn)數(shù)組+鏈表

1. 數(shù)組+鏈表
   
   

1.5.1.2 HashSet底層機(jī)制，數(shù)組+鏈表+紅黑樹

LinkedList、HashSet和HashMap都是在添加元素時(shí)初始化大小的，只有Vector是通過無(wú)參構(gòu)造器初始化容量的；
final Object PRESENT = new Object();
final DEFAULT_LOAD_FACTOR=0.75;
final DEFAULT_INITIAL_CAPACITY = 1 << 4;//16

tips:

1. HashSet的底層是HashMap；
2. HashSet添加元素時(shí)，先得到hash值，根據(jù)hash值 &（n-1）得到索引值；
3. 找到存儲(chǔ)數(shù)據(jù)的數(shù)組[表]table，看這個(gè)索引位置是否已經(jīng)有元素；
   (1)如果沒有，直接添加；
   (2)如果有，調(diào)用equals方法[程序員自己定義]比較，如果相同，放棄添加; 如果不相同，添加到最后；
4. 在jdk8中，如果一條鏈表的元素個(gè)數(shù)超過TREEIFY_THRESHOLD（默認(rèn)值是8）[即到第九個(gè)元素時(shí)],并且table數(shù)組的大小 >= MIN_TREEIFY_CAPACITY（默認(rèn)是64），就會(huì)轉(zhuǎn)化成紅黑樹；
   實(shí)操：
5. 調(diào)用HashSet無(wú)參構(gòu)造器
   
   
   調(diào)用HashMap的構(gòu)造器，將加載因子賦予0.75
   
6. 執(zhí)行第一個(gè)add(“java”)方法，（e就是加的元素）
   
   private static final Object PRESENT = new Object(); 起到占位作用；
   
   2.1 進(jìn)入到put方法; key=e=“java”，value=PRESENT
   
   2.2 進(jìn)入到hash(key)方法
   如果key=null，返回一個(gè)0；
   如果key不等于null，將key的hashCode無(wú)符號(hào)右移十六位（防止沖突），返回key的哈希值；
   
   2.3 進(jìn)入到putVal()方法
   
   2.4 如果table的大小為0，進(jìn)入到resize()方法，給table賦DEFAULT_INITIAL_CAPACITY（16）
   tips:
   (n - 1) & hash 決定key的索引（即應(yīng)該在table的哪個(gè)位置存放）
   table是HashMap里的屬性，是存放節(jié)點(diǎn)的數(shù)組
   
   
   
   這是HashMap留給子類(比如linkedHashMap)實(shí)現(xiàn)的一個(gè)方法
   
7. 執(zhí)行第二個(gè)add(“php”)方法
   
8. 執(zhí)行第三個(gè)add(“java”)方法
   
   
   
   

final V putVal(int hash, K key, V value, boolean onlyIfAbsent,
                       boolean evict) {
            Node<K,V>[] tab; Node<K,V> p; int n, i;//定義了輔助變量
            //table 就是 HashMap的一個(gè)屬性，類型是 Node[]，存放節(jié)點(diǎn)的數(shù)組
            //if語(yǔ)句表示如果當(dāng)前這個(gè)table是空或者大小為0
            //  就第一次擴(kuò)容到16
            if ((tab = table) == null || (n = tab.length) == 0)
                n = (tab = resize()).length;
            //(1)根據(jù)key得到的哈希值去計(jì)算 該key應(yīng)該存放到table表的哪個(gè)索引
            //   并且把這個(gè)索引位置的對(duì)象賦給輔助變量p
            //(2)接下來(lái)就要判斷這個(gè)索引位置的對(duì)象(即p)是否為空
            //如果p為null(表示這個(gè)索引位置還沒有存放數(shù)據(jù)),將創(chuàng)建一個(gè)Node(key="java",value=PRESENT)
            //放在該位置tab[i] = newNode(hash, key, value, null);
            //   Node(hash,key,value,null)
            //          這個(gè)value只起到占位作用[value=PRESENT]
            //          這個(gè)哈希值用于比較下一次存放的key和這個(gè)key是否相等
            //          null就是next
            if ((p = tab[i = (n - 1) & hash]) == null)
                tab[i] = newNode(hash, key, value, null);
            else {
                //一個(gè)開發(fā)技巧tip：在需要局部變量(輔助變量)的時(shí)候，再創(chuàng)建
                Node<K,V> e; K k;
                //老韓的理解：
                //如果當(dāng)前索引位置對(duì)應(yīng)的鏈表的第一個(gè)元素和準(zhǔn)備添加進(jìn)來(lái)的key哈希值相同
                //并且滿足下列條件之一：
                //  條件一：如果準(zhǔn)備加入的key和(即p指向的Node節(jié)點(diǎn)處的key)這個(gè)索引處的key是同一個(gè)對(duì)象
                //  條件二：或著p指向的Node節(jié)點(diǎn)的key經(jīng)equals方法和準(zhǔn)備加入的key比較后相同(不是同一個(gè)對(duì)象，但是內(nèi)容相同)
                //則不能在此處添加
                //自己的理解：
                //就是判斷這個(gè)索引處的對(duì)象是否為空，如果不為空，且兩個(gè)key哈希值相同，
                //且經(jīng)equals()比較內(nèi)容也相同[程序員自己定義標(biāo)準(zhǔn)]，則不能在此處添加
                //總結(jié)：第一個(gè)if語(yǔ)句判斷和表的第一個(gè)節(jié)點(diǎn)是否相同，不同則要考慮表的情況進(jìn)行添加操作
                //     如果表是紅黑樹，則執(zhí)行putTreeVal()方法添加
                //     如果不是紅黑樹，則判斷key和每一個(gè)節(jié)點(diǎn)是否都相同，如果沒有相同的則添加在末尾
                if (p.hash == hash &&
                    //[自己的理解]這個(gè)if里的語(yǔ)句就是如果兩個(gè)即傳進(jìn)來(lái)的key和p指向的位置的第一個(gè)節(jié)點(diǎn)完全一樣，則不能在此處添加
                    ((k = p.key) == key || (key != null && key.equals(k))))
                    e = p;
                //這里判斷p是否是一顆紅黑樹
                //  如果是一顆紅黑樹，就調(diào)用putTreeVal方法來(lái)進(jìn)行比較添加
                else if (p instanceof TreeNode)
                    e = ((TreeNode<K,V>)p).putTreeVal(this, tab, hash, key, value);
                else {
                    //如果table對(duì)應(yīng)的索引位置已經(jīng)是一個(gè)鏈表，就使用for循環(huán)依次比較
                    //  (1)依次和該鏈表的每一個(gè)節(jié)點(diǎn)比較后都不相同，則添加在鏈表末尾;
                    //     注意在把元素添加到鏈表末尾后，立即判斷 該鏈表是否已經(jīng)達(dá)到8個(gè)節(jié)點(diǎn)
                    //     如果達(dá)到8個(gè)節(jié)點(diǎn)，就調(diào)用treeifyBin() 對(duì)當(dāng)前這個(gè)鏈表進(jìn)行樹化(轉(zhuǎn)成紅黑樹)
                    //     注意，在轉(zhuǎn)成紅黑樹時(shí)，還進(jìn)行一個(gè)判斷：
                    //     if (tab == null || (n = tab.length) < MIN_TREEIFY_CAPACITY(64))
                    //          resize();
                    //     如果上面條件成立，對(duì)table表擴(kuò)容。
                    //     只有上面條件不成立時(shí)，才轉(zhuǎn)成紅黑樹；
                    //  (2)依次和該鏈表的每一個(gè)節(jié)點(diǎn)比較，如果有相同的情況，直接break
                    for (int binCount = 0; ; ++binCount) {
                        if ((e = p.next) == null) {//e可以當(dāng)作一個(gè)指針，比較完之后通過p.next指向下一個(gè)節(jié)點(diǎn)
                            p.next = newNode(hash, key, value, null);//加到鏈表末尾
                            if (binCount >= TREEIFY_THRESHOLD[8] - 1) // -1 for 1st
                                treeifyBin(tab, hash);
                            break;//從這里退出循環(huán)e為空
                        }
                        if (e.hash == hash &&
                            ((k = e.key) == key || (key != null && key.equals(k))))
                            break;//從這里退出循環(huán)e不為空
                        p = e;
                    }
                }
                if (e != null) { // existing mapping for key
                    V oldValue = e.value;
                    if (!onlyIfAbsent || oldValue == null)
                        e.value = value;
                    afterNodeAccess(e);
                    return oldValue;
                }
            }
            ++modCount;
            //size 每加入一個(gè)Node(h,k,v,next)節(jié)點(diǎn), size++
            if (++size > threshold)
                resize();
            afterNodeInsertion(evict);
            return null;
        }

1.5.1.3 HashSet擴(kuò)容+紅黑樹機(jī)制

1. //容量: 0->16->32->64->128
   //臨界值:0->12->24->48->96
   HashSet底層是HashMap，第一次添加時(shí)，table數(shù)組擴(kuò)容到16，臨界值(threshold)是12;
   
   
2. 如果table數(shù)組元素增加到了臨界值12，就會(huì)擴(kuò)容到16 * 2=32，新的臨界值就是32*0.75=24，依此類推；
3. 在jdk8中，如果一條鏈表的元素個(gè)數(shù)超過TREEIFY_THRESHOLD（默認(rèn)值是8）[即到第九個(gè)元素時(shí)],并且table數(shù)組的大小 >= MIN_TREEIFY_CAPACITY（默認(rèn)是64），就會(huì)轉(zhuǎn)化成紅黑樹；否則仍然采用數(shù)組擴(kuò)容機(jī)制
4. 每加入一個(gè)Node(h,k,v,next)節(jié)點(diǎn), size就會(huì)++
   

public class HashSetIncrement {
    public static void main(String[] args) {
        HashSet hashSet = new HashSet();
        for (int i = 1; i <= 100; i++) {
            hashSet.add(new Dog(i));
        }
        System.out.println(hashSet);
    }
}
class Dog {
    private int age = 1;

    public Dog(int age) {
        this.age = age;
    }

    @Override
    public int hashCode() {
        return 100;
    }
}

練習(xí)題

1. 重寫equals方法，兩個(gè)都勾選，說明只有兩個(gè)字段都相同equals才返回true；
   
2. 重寫hashCode方法，兩個(gè)都勾選，說明只有兩個(gè)字段都相同hashCode才返回true；
   
   

1.5.2 LinkedHashSet

1. LinkedHashSet是HashSet的子類;
2. LinkedHashSet底層是一個(gè)LinkedHashMap，底層維護(hù)了一個(gè)數(shù)組+雙向鏈表;
3. LinkedHashSet使用雙向鏈表維護(hù)元素的次序，所以元素看起來(lái)是以插入順序保存的；（取出順序和插入順序一致）
4. LinkedHashSet根據(jù)元素的hashCode值來(lái)決定元素的存儲(chǔ)位置;
5. LinkedHashSet不允許重復(fù)元素；
   (LinkedHashSet有head和tail)；

1.5.2.1 數(shù)組+雙向鏈表

1. 每一個(gè)節(jié)點(diǎn)都有before和after屬性，這樣可以形成雙向鏈表；
2. 在添加一個(gè)元素時(shí)，先求hash值，再求索引，確定該元素在table中的位置，然后將添加的元素加入到雙向鏈表，如果已經(jīng)存在(原則和HashSet一致)，則放棄添加；這樣在遍歷LinkedHashSet是也能確保插入順序和遍歷順序一致；
   tail.after = newElement;
   newElement.before = tail;
   tail = newElement;
3. 第一次添加時(shí)將數(shù)組擴(kuò)容到16；
4. 數(shù)組類型是HashMap$Node[]；存放的節(jié)點(diǎn)類型是LinkedHashMap$Entry;Entry是一個(gè)靜態(tài)內(nèi)部類，實(shí)現(xiàn)了雙向鏈表，Node只是單向鏈表；
   
   
   只確定了loadfactor和threshold
   
   
   
   
   LinkedHashSet底層維護(hù)的是LinkedHashMap（是HashMap的子類）
   
   LinkedHashMap底層維護(hù)的是HashMap：數(shù)據(jù)+雙向鏈表
   
   數(shù)組類型是HashMap$Node, 數(shù)組存放的節(jié)點(diǎn)類型是LinkedHashMap$Entry ?(多態(tài)數(shù)組)
   
   原因：LinkedHashMap.Entry<K,V> extends HashMap.Node<K,V>

1.5.3 TreeSet

當(dāng)使用無(wú)參構(gòu)造器創(chuàng)建TreeSet并添加元素的時(shí)候，插入順序和取出順序不一致（這是因?yàn)門reeSet會(huì)默認(rèn)按照傳入的key從小到大排序）
原因：創(chuàng)建TreeSet對(duì)象時(shí)如果傳入了一個(gè)Comparator對(duì)象，就用實(shí)現(xiàn)的compare方法比較；如果沒有傳入Comparator對(duì)象，則以添加對(duì)象的實(shí)現(xiàn)的Comparable接口的compareTo方法比較；

當(dāng)傳入第一個(gè)元素時(shí)，若這個(gè)元素沒有實(shí)現(xiàn)Comparable接口，則會(huì)報(bào)錯(cuò)


以后傳入的對(duì)象如果沒有實(shí)現(xiàn)Comparable接口，也會(huì)報(bào)類轉(zhuǎn)換異常ClassCastException

解決方案：讓對(duì)象實(shí)現(xiàn)Comparable接口，重寫compareTo方法；
去重機(jī)制：
創(chuàng)建TreeSet對(duì)象時(shí)如果傳入了一個(gè)Comparator對(duì)象，就用實(shí)現(xiàn)的compare方法去除重復(fù)元素，如果方法返回0，就認(rèn)為不應(yīng)該添加；如果沒有傳入Comparator對(duì)象，則以添加對(duì)象的實(shí)現(xiàn)的Comparable接口的compareTo方法去除重復(fù)元素；

1. 使用無(wú)參構(gòu)造器創(chuàng)建TreeSet并添加元素
   
2. 使用TreeSet 提供的一個(gè)有參構(gòu)造器，傳入一個(gè)比較器(匿名內(nèi)部類)，指定一個(gè)排序規(guī)則
   
   treeSet底層是treeMap；
   
   treeSet構(gòu)造器，把傳入的實(shí)現(xiàn)了 Comparator接口的匿名內(nèi)部類傳給了TreeMap的屬性comparator；
   當(dāng)調(diào)用treeSet.add()方法時(shí)，在底層會(huì)執(zhí)行到:
   
   能不能加得進(jìn)去，要看compare()比較的內(nèi)容，如果內(nèi)容相等，即cmp返回0，這個(gè)key就不會(huì)加入
   
   在這里會(huì)動(dòng)態(tài)綁定到：匿名內(nèi)部類的compare()方法
   
   這里是長(zhǎng)度相等就相同，所以長(zhǎng)度相等的加不進(jìn)去；
   

2. 雙列集合(Map)：

• 指的是在集合里面放的是鍵值對(duì)
• Map 接口的實(shí)現(xiàn)子類是雙列集合，存放的是 k-v
• Map接口沒有繼承迭代器，不能使用迭代器遍歷，也不能使用增強(qiáng)for循環(huán)遍歷
  
  

2.1 Map接口實(shí)現(xiàn)類的特點(diǎn)

1. Map用于保存具有映射關(guān)系的數(shù)據(jù)Key-Value；
2. Map中的key、value可以是任意引用類型，封裝進(jìn)HashMap的Node內(nèi)部類中；
   
3. Map中的數(shù)據(jù)key不允許重復(fù),原因：根據(jù)hash值和equals判斷
4. 當(dāng)有相同的key時(shí)，就相當(dāng)于替換value值
5. Map中的value值可以重復(fù)；
6. Map【Hashtable、Properties除外】中的key、value都可以為null，但key只能有一個(gè)null，value可以有多個(gè)；
7. 習(xí)慣是key放字符串，但是key可以放任意類型
8. 通過get()方法傳入一個(gè)key，返回key對(duì)應(yīng)的value，value只有一個(gè)；
9. k-v 最后都是 HashMap$Node node = newNode(hash,key,value,null);
10. k-v 為了方便程序員的遍歷，還會(huì)創(chuàng)建 EntrySet 集合，該集合存放的元素的類型是 Entry, 而一個(gè)Entry對(duì)象就有k,v -> EntrySet<Entry<K,V>>
    
11. 在EntrySet中，定義的類型是 Map.Entry,但是實(shí)際上存放的還是HashMap$Node,這是因?yàn)镠ashMap$Node 實(shí)現(xiàn)了 Map.Entry接口
    
12. 把HashMap$Node 對(duì)象 存放到entrySet集合，方便我們的遍歷，因?yàn)镸ap.Entry提供了重要的方法
    
    
13. HashMap沒有做同步互斥，沒有syntronized，因此是線程不安全的；

@SuppressWarnings({"all"})
public class MapSource {
    public static void main(String[] args) {
        Map map = new HashMap();
        map.put("No1","scott");
        map.put("No2","zzw");
        map.put(new Person("zzw"),new Car());
        //1.k-v 最后都是 HashMap$Node node = newNode(hash,key,value,null)
        //2.k-v 為了方便程序員的遍歷，還會(huì)創(chuàng)建 EntrySet 數(shù)組，該集合存放的元素的類型是 Entry，但元素的運(yùn)行類型是Node
        //  而一個(gè)Entry對(duì)象就有k,v EntrySet<Entry<K,V>>
        //  即：transient Set<Map.Entry<K,V>> entrySet;
        //3.在EntrySet中，定義的類型是 Map.Entry,但是實(shí)際上存放的還是HashMap$Node
        //  這是因?yàn)镠ashMap$Node 實(shí)現(xiàn)了 Map.Entry接口
        //4.把HashMap$Node 對(duì)象 存放到entrySet，方便我們的遍歷，因?yàn)镸ap.Entry提供了重要的方法
        //  K getKey();
        //  V getValue();
        Set set = map.entrySet();
        System.out.println(set.getClass());//HashMap$EntrySet 是HashMap的一個(gè)內(nèi)部類
        for (Object obj : set) {
            System.out.print(obj + " ");
            System.out.println(obj.getClass());//HashMap$Node
            //為了從HashMap$Node中取出k-v
            //1.先向下轉(zhuǎn)型
            Map.Entry entry = (Map.Entry) obj;
            System.out.println(entry.getKey());
            System.out.println(entry.getValue());
        }
        Set set1 = map.keySet();
        System.out.println(set1.getClass());//HashMap$KeySet
        Collection values = map.values();
        System.out.println(values.getClass());//HashMap$Values
    }
}
class Person {
    private String name;

    public Person(String name) {
        this.name = name;
    }
}
class Car {

}

2.2 Map常用方法，不支持索引

1. put(key,value) 添加鍵值對(duì)
2. remove(k,v) remove(k)
3. get(k)
4. size() 獲取k-v個(gè)數(shù)
5. isEmpty() 是否為空
6. clear() 清空鍵值對(duì)
7. containsKey():查找鍵是否存在
   

2.3 Map接口三組遍歷方法

2.3.1 keySet+增強(qiáng)for循環(huán)

2.3.2 keySet+迭代器

2.3.3 values()+增強(qiáng)for循環(huán)

2.3.4 values()+迭代器

2.3.5 EntrySet+增強(qiáng)for循環(huán)

2.3.6 EntrySet+迭代器

2.4 HashMap擴(kuò)容機(jī)制

1. HashMap底層維護(hù)了Node類型的數(shù)組table，默認(rèn)為null；
2. 當(dāng)創(chuàng)建HashMap對(duì)象時(shí)，將加載因子(loadfactor)初始化為0.75；
   
3. 當(dāng)添加k，v時(shí)，通過key的哈希值得到在table的索引，然后判斷該索引處是否有元素。如果沒有元素，則直接添加；
   
   如果有元素，則判斷該索引處的key是否和準(zhǔn)備加入的key相等；
   
   如果key相同，則執(zhí)行完if語(yǔ)句直接跳到，替換value【e.value = value;】
   
   如果key不相同，需要判斷是樹結(jié)構(gòu)，還是鏈表結(jié)構(gòu)，然后做出相應(yīng)處理；
   樹結(jié)構(gòu)
   
   鏈表結(jié)構(gòu)中，如果每個(gè)元素的key都不相同，則會(huì)一直循環(huán)到鏈表的最后
   
   添加時(shí)，發(fā)現(xiàn)容量不對(duì)，則需要擴(kuò)容；
   
4. 第一次添加，需要將table擴(kuò)容為16，臨界值threshold為12,；
   
   以后再次擴(kuò)容，則需要將table擴(kuò)容為2倍；臨界值也變?yōu)樵瓉?lái)的2倍，即24，以此類推；
   
5. 在java8中，如果在binCount到達(dá)TREEIFY_THRESHOLD-1，即一條鏈表的元素超過TREEIFY_THRESHOLD（默認(rèn)為8），
   
   個(gè)數(shù)： 2 3 4 5 6 7 8 9
   binCount: 0 1 2 3 4 5 6 7
   并且table表的大小超過MIN_TREEIFY_CAPACITY（默認(rèn)為64），就會(huì)進(jìn)行樹化，變?yōu)榧t黑樹；
   

1. 如果底層的table 數(shù)組為null，或者 length=0，則擴(kuò)容到16，調(diào)用resize()方法;
2. 取出hash值對(duì)應(yīng)的table的索引位置的Node，如果為null，就直接把加入的k-v創(chuàng)建成一個(gè)Node，加入即可；
   tab[i] = newNode(hash, key, value, null);
3. 如果key相同，則替換value【e.value = value;】 走到e != null，說明那個(gè)位置有元素并且元素相同，所以在這里不在添加；這段代碼專門替換value值；
   
4. 剪枝：紅黑樹刪除節(jié)點(diǎn)到一定數(shù)量之后轉(zhuǎn)為鏈表；

public class HashMapSource01 {
    public static void main(String[] args) {
        Map hashMap = new HashMap();
        for (int i = 1; i <= 12; i++) {
            hashMap.put(new Dog(i),"zze");
        }
        Set entrySet = hashMap.entrySet();
        for(Object entry : entrySet) {
            System.out.println(entry);
        }
    }
}
//所有的Dog對(duì)象的hashCode都一樣
class Dog {
    private int age;

    public Dog(int age) {
        this.age = age;
    }

    @Override
    public int hashCode() {
        return 100;
    }

    @Override
    public String toString() {
        return "Dog{" +
                "age=" + age +
                '}';
    }
}

2.5 Hashtable擴(kuò)容機(jī)制(數(shù)組+鏈表)

1. Hashtable存放的元素是鍵值對(duì)，使用方法基本上和HashMap一致；
   
2. Hashtable的鍵和值都不能為null，否則會(huì)拋出NullPointerException；
   
3. Hashtable是線程安全的，HashMap是線程不安全的；
4. Hashtable底層有一個(gè) Hashtable$Entry的數(shù)組。第一次初始化大小為11，臨界值是8；
   threshold = 11 * 0.75；
   
   Hashtable 底層維護(hù)的是一個(gè)Hashtable$Entry
   
5. 第二次擴(kuò)容
   table大小：11-》23
   臨界值：8 -》17
   
6. 擴(kuò)容會(huì)執(zhí)行addEntry(hash,key,value,index);
   當(dāng)數(shù)量大于等于臨界值時(shí)，擴(kuò)容
   
   大小變?yōu)樵瓉?lái)的2倍+1；newCapacity = (oldCapacity << 1) + 1;
   

2.5.1 Hashtable與HashMap比較

2.5.2 Properties實(shí)現(xiàn)類(繼承Hashtable)

1. Properties類繼承Hashtable類并實(shí)現(xiàn)了Map接口，也是使用鍵值對(duì)的形式來(lái)存儲(chǔ)數(shù)據(jù)；使用特點(diǎn)和Hashtable相似；
2. Properties還可以用于 從某個(gè)后綴名為properties的文件中，加載數(shù)據(jù)到Properties對(duì)象，并進(jìn)行讀取和修改；
3. Properties不允許鍵值為null；鍵或值為空會(huì)拋異常NullPointerException
4. xxx.properties文件常常作為配置文件【IO流】；

1. put()；添加鍵值對(duì)，及修改value值
   
2. get(key)方法，獲取value
3. remove()； 刪除鍵值對(duì)
   remove(Object key)
   boolean remove(Object key, Object value)
   

2.6 treeMap

當(dāng)使用無(wú)參構(gòu)造器創(chuàng)建TreeSet并添加元素的時(shí)候，插入順序和取出順序不一致（這是因?yàn)門reeSet會(huì)默認(rèn)從小到大升序排序）
第一次添加時(shí)，把key、value封裝到Entry對(duì)象，放入root

第二次添加時(shí)，遍歷所有的key

3. 小結(jié)

在開發(fā)中，選擇什么集合實(shí)現(xiàn)類，主要取決于業(yè)務(wù)操作特點(diǎn)，然后根據(jù)集合實(shí)現(xiàn)類特性進(jìn)行選擇，如下：

1. 先判斷存儲(chǔ)的類型：（一組對(duì)象即單列；一組鍵值對(duì)即雙列）
2. 一組對(duì)象[單列]：Collection接口
   • 允許重復(fù)：List
     • 增刪多：LinkedList 【底層維護(hù)了一個(gè)雙向鏈表】
     • 改查多：ArrayList 【底層維護(hù)了Object類型的可變數(shù)組】
   • 不允許重復(fù)：Set
     • 無(wú)序：HashSet 【底層是HashMap，維護(hù)了一個(gè)哈希表，即數(shù)組+鏈表+紅紅黑樹】
     • 排序：TreeSet
     • 插入和取出順序一致：LinkedHashSet，【底層維護(hù)的是數(shù)組+雙向鏈表】
3. 一組鍵值對(duì)[雙列]：Map
   3.1 鍵無(wú)序：HashMap【底層：哈希表 jdk7：數(shù)組+鏈表，jdk8：數(shù)組+鏈表+紅黑樹】
   3.2 鍵排序：TreeMap
   3.3 鍵插入和取出順序一致：LinkedHashMap
   讀取文件：Properties

3.1 Collections集合工具類

3.1.1 Collections.reverse()，反轉(zhuǎn)集合

3.1.2 Collections.shuffle()，打亂集合順序

3.1.3 Collections.sort(list); 默認(rèn)按照字符串大小升序排列

Comparator接口匿名內(nèi)部類的用法??傳送門

Collections.sort(list, Comparator comparator); 自定義排序規(guī)則
1)我們希望按照字符串的長(zhǎng)度大小排序

3.1.4 swap(list, int, int)；將指定集合中的i處元素和j處元素互換

3.1.5 Collections.max(collection); 根據(jù)元素的自然順序，返回指定集合中的最大值

Collections.max(collection, Comparator comparator); 自定義排序，返回指定集合中的最大值

6. Collections.min(collection); 根據(jù)元素的自然順序，返回指定集合中的最小值
   Collections.min(collection, Comparator comparator); 自定義排序，返回指定集合中的最小值

3.1.6 Collection.frequency(collection，Object); 返回指定集合中指定元素出現(xiàn)的次數(shù)

3.1.7 Collections.copy(List dest, List src); 把src集合中的數(shù)據(jù)拷貝到dest中去

3.1.8 Collections.replaceAll(List list, oldVal, newVal)；用newVal替換集合中的oldVal

文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-624456.html

3.2 史上巨坑題

public class Homework06 {
    public static void main(String[] args) {
        HashSet set = new HashSet();
        Person p1 = new Person(1001, "AA");
        Person p2 = new Person(1002, "BB");
        set.add(p1);//HashMap$Node tab[i] = newNode(hash, 1001, "AA", null);
        set.add(p2);//HashMap$Node tab[i] = newNode(hash, 1002, "BB", null);
        p1.name = "CC";
        set.remove(p1);//此時(shí)p1的哈希值改變了
        System.out.println(set);//p1,p2
        set.add(new Person(1001, "CC"));//true
        System.out.println(set);
        set.add(new Person(1001, "AA"));//true
    }
}
class Person {
    private int id;
    public String name;

    public Person(int id, String name) {
        this.id = id;
        this.name = name;
    }

    @Override
    public String toString() {
        return "Person{" +
                "id=" + id +
                ", name='" + name + '\'' +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        Person person = (Person) o;
        return id == person.id &&
                Objects.equals(name, person.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(id, name);
    }
}

到了這里，關(guān)于Java集合，超詳細(xì)整理，適合新手入門的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！