Java基礎知識之什么是集合框架-有解無憂

Java基礎知識之什么是集合框架，前面的文章，我們已經學習了Java的一些基礎知識，比如泛型、注解等等內容，接著本博客繼續學習Java中一個很常見的內容，集合，

1、什么是Java中的集合框架？

Java Collections 框架由介面和類組成，集合框架是用于存盤資料和操作一組物件的統一架構，

集合框架提供了很多介面，比如Set、List、Queue、Deque、… ，實作類的有ArrayList、Vector、LinkedList、PriorityQueue、HashSet、LinkedHashSet、TreeSet、… ，這些實作類都是資料架構和演算法的應用，比如鏈表、紅黑樹、二叉樹等等，集合框架的類可以在java.util這里package里找到

2、Java 集合層次結構

Java Collection提供了很多類，功能比較強大，這里畫圖簡單描述一下Java中的主要類圖，先畫一個簡版，只畫一些最重要的介面，如圖，Java中的集合類比如HashSet、ArrayList、LinkedList等等都是繼承自Set、List、Queue、Deque這些介面，HashMap就是繼承自Map介面在這里插入圖片描述
用idea軟體畫出uml圖：

繼承自Map介面的uml類圖：

對集合框架有一個大概了解之后，下面挑幾個比較常用的進行描述

3、ArrayList

3.1、uml類圖結構

ArrayList是用的比較多的串列List，看一下ArrayList的類圖結構：

在這里插入圖片描述

3.2、宣告的屬性

簡單串列ArrayList原始碼里宣告的幾個比較重要的屬性

屬性	作用
DEFAULT_CAPACITY	默認的陣列容量
EMPTY_ELEMENTDATA	用于共享的Empty實體陣列
DEFAULTCAPACITY_EMPTY_ELEMENTDATA	也是一個空的實體陣列
elementData	ArrayList中真實存盤資料的容器
size	集合中的元素個數

下面簡單跟一下ArrayList原始碼

3.3、構造方法

public ArrayList() {
  this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
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);
 }
}

public ArrayList(Collection<? extends E> c) {
	// 將傳入的集合轉換為陣列
     elementData = c.toArray();
     if ((size = elementData.length) != 0) {
         // c.toArray might (incorrectly) not return Object[] (see 6260652)
         if (elementData.getClass() != Object[].class)
         	 // 賦值給elementData
             elementData = Arrays.copyOf(elementData, size, Object[].class);
     } else {
         // replace with empty array.
         this.elementData = EMPTY_ELEMENTDATA;
     }
 }

3.4、add方法

方法名	作用
`public boolean add(E e)`	將指定的元素添加到此串列的末尾
`public void add(int index, E element)`	在指定的index位置加上元素
`public boolean addAll(Collection<?> c)`	將指定集合的所有元素添加到list末尾
`public boolean addAll(int index,Collection<? extends E> c)`	在指定位置加上集合的所有元素

ArrayList add方法

public boolean add(E e) {
    // 校驗內部容量
   ensureCapacityInternal(size + 1);  // Increments modCount!!
   elementData[size++] = e;
   return true;
}

校驗內部容量

private void ensureCapacityInternal(int minCapacity) {
    // calculateCapacity計算內部容量
    // ensureExplicitCapacity繼續校驗
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

calculateCapacity計算內容容量

private static int calculateCapacity(Object[] elementData, int minCapacity) {
     // 判斷集合是否微empty陣列
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        // 比較最小容量和默認容量，得出最大值，做第一次擴容
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

ensureExplicitCapacity方法

private void ensureExplicitCapacity(int minCapacity) {
    // 實際修改集合的次數
    modCount++;

    // overflow-conscious code
    // 判斷最小容量是否大于陣列長度
    if (minCapacity - elementData.length > 0)
        // 將計算出來的最小容器傳值給grow核心擴容方法
        grow(minCapacity);
}

核心的擴容方法：

private void grow(int minCapacity) {
    // overflow-conscious code
    // 記錄陣列的實際長度
    int oldCapacity = elementData.length;
    // 擴容方法，原來容量的1.5倍，oldCapacity >> 1右移運算, 也即oldCapacity * (1/2)^1 
    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);
}

下面繼續跟一下其它型別的add方法
public void add(int index, E element)

public void add(int index, E element) {
   // 校驗index合法性
     rangeCheckForAdd(index);
	// 校驗內部容量
     ensureCapacityInternal(size + 1);  // Increments modCount!!
     // index+1的目的是在指定index，后面再空出一個index+1的位置
     System.arraycopy(elementData, index, elementData, index + 1,
                      size - index);
     // 陣列賦值
     elementData[index] = element;
	 // 計數器加1
     size++;
 }

public boolean addAll(Collection<? extends E> c)添加集合方法：

public boolean addAll(Collection<? extends E> c) {
    // 將集合轉換為Object型別的陣列
    Object[] a = c.toArray();
    // 計算要新增集合的陣列長度
    int numNew = a.length;
    // 加上新集合之后，校驗是否需要擴容
    ensureCapacityInternal(size + numNew);  // Increments modCount
    // 將陣列a的元素復制到elementData
    System.arraycopy(a, 0, elementData, size, numNew);
    // 計算器加上新增集合的元素數量
    size += numNew;
    // 新增陣列的元素個數不為0的情況就是新增成功
    return numNew != 0;
}

public boolean addAll(int index, Collection<? extends E> c)在指定的位置新增集合

public boolean addAll(int index, Collection<? extends E> c) {
        // 校驗index是否合法
        rangeCheckForAdd(index);
		// 將集合轉換為object陣列
        Object[] a = c.toArray();
        // 陣列的長度
        int numNew = a.length;
        // 校驗新增元素之后，是否需要擴容
        ensureCapacityInternal(size + numNew);  // Increments modCount
         // 計算陣列要加到集合的index下標
        int numMoved = size - index;
        if (numMoved > 0)
            // 調整elementData中資料的位置，給新插入的資料騰出空間
            System.arraycopy(elementData, index, elementData, index + numNew,
                             numMoved);
         // 復制陣列a的資料到elementData的指定位置
        System.arraycopy(a, 0, elementData, index, numNew);
        // 加上新增集合的元素數量
        size += numNew;
        // numNew不等于0說明新增成功
        return numNew != 0;
    }

4、Vector

4.1、UML類圖

在這里插入圖片描述

4.2、Vector和ArrayList的區別

這里可以嘗試著翻下Vector的原始碼，發現其本質也是一個陣列，這點是和ArrayList是一樣的，不同點是Vector是執行緒安全的，翻了原始碼發現很多方法都是有都是有加上同步鎖的synchronized

public synchronized void insertElementAt(E obj, int index) {
    modCount++;
    if (index > elementCount) {
        throw new ArrayIndexOutOfBoundsException(index
                                                 + " > " + elementCount);
    }
    ensureCapacityHelper(elementCount + 1);
    System.arraycopy(elementData, index, elementData, index + 1, elementCount - index);
    elementData[index] = obj;
    elementCount++;
}

Vector實作邏輯和ArrayList很像，所以就不過多描述

5、HashSet

5.1、Uml類圖

在這里插入圖片描述

5.2、HashSet本質？

這里還是要跟下原始碼，在idea里點到原始碼里去，可以看出其實HashSet是通過HashMap實作的，所以后面看下hashMap實作就行

public HashSet() {
       map = new HashMap<>();
   }

public HashSet(Collection<? extends E> c) {
        map = new HashMap<>(Math.max((int) (c.size()/.75f) + 1, 16));
        addAll(c);
    }

6、TreeSet

6.1、uml類圖

在這里插入圖片描述

6.2、TreeSet本質

跟下原始碼，可以發現TreeSet實作還是通過TreeMap實作的，所以待會再看看TreeMap怎么實作的就可以

public TreeSet() {
    this(new TreeMap<E,Object>());
 }

7、TreeMap

7.1、uml類圖

在這里插入圖片描述

7.2、TreeMap實作

翻下原始碼，從原始碼看起來似乎很熟悉，沒錯，TreeMap就是通過紅黑樹實作的，對紅黑樹比較熟悉的，應該可以馬上看出來，不熟悉的讀者可以參考我之前的博客資料結構系列之Java手寫實作紅黑樹

TreeMap成員變數

// 比較器
private final Comparator<? super K> comparator;
// 根節點 
  private transient Entry<K,V> root;
  /**
  * The number of entries in the tree 樹節點數量
  */
  private transient int size = 0;
  /**
  * The number of structural modifications to the tree. 記錄修改次數
  */
  private transient int modCount = 0;

定義一棵紅黑樹資訊，一棵紅黑樹都會有左節點left、右節點right、父節點parent、紅黑樹節點的顏色color、同時會保存key和value

static final class Entry<K,V> implements Map.Entry<K,V> {
        K key;
        V value;
        Entry<K,V> left;
        Entry<K,V> right;
        Entry<K,V> parent;
        boolean color = BLACK
        // ...
}

put方法，新增節點

public V put(K key, V value) {
    Entry<K,V> t = root;
    // 第一次put，將新節點直接設定為root節點
    if (t == null) {
        compare(key, key); // type (and possibly null) check
        // 構建root節點
        root = new Entry<>(key, value, null);
        size = 1;
        // 修改次數
        modCount++;
        return null;
    }
    // cmp比較的值
    int cmp;
    Entry<K,V> parent;
    // split comparator and comparable paths
    Comparator<? super K> cpr = comparator;
    // 進行比較，找到哪個節點作為新節點的parent節點
    if (cpr != null) {
        do {
            parent = t;
            cmp = cpr.compare(key, t.key);
            if (cmp < 0)
                 // 新節點值比當前節點值小，繼續找左節點
                t = t.left;
            else if (cmp > 0)
                // 找右節點
                t = t.right;
            else
               //插入的值在容器中有相同的值 直接覆寫
                return t.setValue(value);
        } while (t != null);
    }
    else {
        if (key == null)
            throw new NullPointerException();
            //比較器為空就創建一個比較器
        @SuppressWarnings("unchecked")
            Comparable<? super K> k = (Comparable<? super K>) key;
            // 找到一個節點作為新節點的parent節點
        do {
            parent = t;
            cmp = k.compareTo(t.key);
            if (cmp < 0)
                t = t.left;
            else if (cmp > 0)
                t = t.right;
            else
                return t.setValue(value);
        } while (t != null);
    }
    // 新增節點的父節點
    Entry<K,V> e = new Entry<>(key, value, parent);
    if (cmp < 0)
        // 新節點作為左子節點
        parent.left = e;
    else
         // 作為右子節點
        parent.right = e;
      // 變色和旋轉
    fixAfterInsertion(e);
    size++;
    modCount++;
    return null;
}

前面的邏輯其實就是和二叉搜索樹的邏輯是很相似的，只是紅黑樹新增節點之后要通過變色或者是左旋右旋來保持紅黑樹的平衡

具體邏輯看一下fixAfterInsertion(node);，這個邏輯比較關鍵，這里做一下比較詳細的描述，這里分情況分析

場景1：紅黑樹是Empty的，這是最簡單的場景，直接將新節點作為根節點就行，不過紅黑樹有個特性，根節點都是黑色的，所以將新節點涂黑就行
場景2：新增節點的父節點是黑節點，由于新增的節點都是紅色的節點，所以這種情況不會影響平衡，直接新增就行
場景3：新增結點的父結點為紅結點且為祖父節點的左子節點
- 場景3.1：新節點的叔叔節點是紅色的
  這種情況，如圖005是新增節點，其叔叔節點是009是紅色的，這種情況，需要做下變色，祖父節點008變為紅色，父親節點006變為黑色，叔叔節點009也變為黑色，這樣整棵紅黑色就可以平衡
- 場景3.2：叔叔節點是黑色，且新增節點作為右子節點
  這種情況要做的是將新節點008指向父節點003，同時做左旋
- 場景3.3：叔叔節點是黑色，且新增節點作為左子節點
  這種情況，需要將父節點008變黑色，祖父節點011變為紅色，同時圍繞祖父節點011做右旋
場景4：新增結點的父結點為紅結點，且為祖父節點的右子節點
這種場景也有3種情況，不過和場景3是相反的，這種不做詳細描述

private void fixAfterInsertion(Entry<K,V> x) {
   // 新增的節點都是紅色的
   x.color = RED;
    // 父節點是紅色的情況才需要調整紅黑樹
   while (x != null && x != root && x.parent.color == RED) {
        // 父節點作為祖父節點的左子樹
       if (parentOf(x) == leftOf(parentOf(parentOf(x)))) {
            // 找到叔叔節點
           Entry<K,V> y = rightOf(parentOf(parentOf(x)));
           // case1 : 叔叔節點也是紅色
           if (colorOf(y) == RED) {
               setColor(parentOf(x), BLACK);
               setColor(y, BLACK);
               setColor(parentOf(parentOf(x)), RED);
               x = parentOf(parentOf(x));
           } else {
                // case2 ： 叔叔節點是黑色，且新增節點是右子節點
               if (x == rightOf(parentOf(x))) {
                  // 將父節點和新增節點調換
                   x = parentOf(x);
                   // 從父節點處做左旋
                   rotateLeft(x);
               }
               // case 3 : 叔叔節點是黑色，且新增節點是左子節點
               setColor(parentOf(x), BLACK);
               setColor(parentOf(parentOf(x)), RED);
               rotateRight(parentOf(parentOf(x)));
           }
       } else { //情況與上面邏輯對稱
           Entry<K,V> y = leftOf(parentOf(parentOf(x)));
           if (colorOf(y) == RED) {
               setColor(parentOf(x), BLACK);
               setColor(y, BLACK);
               setColor(parentOf(parentOf(x)), RED);
               x = parentOf(parentOf(x));
           } else {
               if (x == leftOf(parentOf(x))) {
                   x = parentOf(x);
                   rotateRight(x);
               }
               setColor(parentOf(x), BLACK);
               setColor(parentOf(parentOf(x)), RED);
               rotateLeft(parentOf(parentOf(x)));
           }
       }
   }
    // root節點肯定是黑色
   root.color = BLACK;
}

紅黑樹的邏輯相對比較復雜，比較詳細的參考我上篇博客

8、HashMap

HashMap的邏輯也是相對比較復雜的，所以后面有時間再寫一篇比較詳細的文章對hashMap原始碼進行描述，本博客只做概述，目的是簡述Java中的集合框架，通過原始碼的簡單分析，讓讀者有更深層次的理解

8.1、什么是HashMap？

HashMap 基于哈希表的 Map 介面實作，是以 key-value 存盤形式存在，HashMap 的實作不是同步的，這意味著它不是執行緒安全的，它的 key、value 都可以為 null，此外，HashMap 中的映射不是有序的，

8.2、HashMap的特性

Hash存盤無序的
key和value都可以存盤null值，但是key只能存唯一的一個null值
jdk8之前的資料結構是陣列+鏈表，Jdk8之后變成陣列+鏈表+紅黑樹
閥值大于8并且陣列長度大于64才會轉為紅黑樹

8.3、JDK1.7

在這里插入圖片描述

8.4、JDK1.8

在這里插入圖片描述

轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/295398.html

標籤：java

上一篇：SpringBoot發送郵件

下一篇：第二階段的面試題