單列集合框架體系Collection

来源:https://www.cnblogs.com/mishaka/archive/2019/07/03/11129574.html
-Advertisement-
Play Games

單列集合框架體系 List 集合體系 主要實現類 依次為 ArrayList，LinkedList，Vector 。 List介面主要特征： 有序，可重覆，有索引，底層容量是動態擴容的。（代碼以JDK 1.8為例） ArrayList：是List介面的主要實現類，底層用數組實現： ,transien ...


單列集合框架體系

List 集合體系 主要實現類 依次為 ArrayList，LinkedList，Vector 。

List介面主要特征：

　　有序，可重覆，有索引，底層容量是動態擴容的。（代碼以JDK 1.8為例）

ArrayList：是List介面的主要實現類，底層用數組實現： ,transient Object[] elementData; 

　　　　　線程不安全的，查詢快，增加，刪除 慢（相對於LinkedList）

　　　　　JDK1.7預設初始長度是10，JDK1.8預設長度是0 ，在調用添加方法之後，才進行長度初始化（值是 10）。

　　　　　擴容是在當前的數據容量比集合內部數組長度大時，進行擴容，擴容時會先複製原有的數組，然後創建新數組，把原有數組放入新數組中，新數組長度擴圍原有的1.5倍，如果

　　　　 發現數組長度還是不夠用，那麼直接把當前的實際容量賦值給新數組的容量
private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }
public boolean add(E e) {
　　
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
　　　    //如果初始值為10 ，現在集合長度為10 ，在添加低11個元素的時候        
         //會符合下麵的判斷條件，進入擴容機制
        // overflow-conscious code
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
   // 先擴大1.5倍,作為新數組的使用長度，通過下麵判斷是否夠用
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        //擴容1.5倍的新數組長度還是不夠用，那麼直接把當前的實際容量賦值給新數組的容量
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
　　//調用java.util.Arrays 工具包下麵的複製數組方法

    elementData = Arrays.copyOf(elementData, newCapacity);
}
private static int hugeCapacity(int minCapacity) {
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity > MAX_ARRAY_SIZE) ?
            Integer.MAX_VALUE :
            MAX_ARRAY_SIZE;
    }
public static <T,U> T[] copyOf(U[] original, int newLength, Class<? extends T[]> newType) {
        @SuppressWarnings("unchecked")
        T[] copy = ((Object)newType == (Object)Object[].class)
            ? (T[]) new Object[newLength]
            : (T[]) Array.newInstance(newType.getComponentType(), newLength);
        System.arraycopy(original, 0, copy, 0,
                         Math.min(original.length, newLength));
        return copy;
    }

 

 LinkedList：底層是雙向鏈表實現的，有前後元素的地址存儲。

transient Node<E> first;
transient Node<E> last;
private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }
public boolean add(E e) {
        linkLast(e);
        return true;
    }
void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

 Vector：線程安全的，底層用 Object[] elementData  數組，擴容是原來的2倍長度 這個和ArrayList 是不一樣的

protected Object[] elementData;
public Vector(int initialCapacity) {
        this(initialCapacity, 0);
    }
public synchronized void addElement(E obj) {
        modCount++;
        ensureCapacityHelper(elementCount + 1);
        elementData[elementCount++] = obj;
    }
private void grow(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
　　　　　//擴容是原來的2倍長度
        int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                         capacityIncrement : oldCapacity);
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        if (newCapacity - MAX_ARRAY_SIZE > 0)
            newCapacity = hugeCapacity(minCapacity);
        elementData = Arrays.copyOf(elementData, newCapacity);
    }

 

Set集合體系 主要實現類依次為 HashSet，LinkedHashSet，TreeSet;

　　Set集合的特點：

　　　　無序不可重覆，這個不是指存取的順序，指的是數據存放在記憶體中的地址的無序性，簡單點說就是沒有索引排序，是用hash值來進行判斷。

　　　　其中HashSet 是Set 的主要實現類，如果沒有特殊情況的話，一般都使用這個類。

　　　　無序性：不是指隨機性，底層是數組+鏈表（JDK1.8 會把鏈表轉紅黑樹） 通過hashCode() 計算出對應的hash 值，然後通過hash 值計算出數據存儲在數組 對應的 地址上。

　　　　不可重覆性：先計算要存儲值 的hash 值，通過hash 值來計算在容器中數組存放的位置，如果當前數據的hash 值所在容器的位置沒有數據就直接存進去，

　　　　　　　　　　如果有，那麼就和容器中的值進行hash 值的比較，如果hash值相同，再計算當前值equals() 容器中該位置的值是否相等，如果相等就代表是同一個元素，就不存進容器中，

　　　　　　　　　　如果hash值不同，則直接存進容器中，JDK1.7 是把當前元素存進數組和鏈表的連接處(鏈表前端)，JDK1.8是把當前數據存進數據對應數組連接的鏈表的末端。保證元素的不可重覆性。

HashSet：可以存儲null 值，線程不安全的（簡單理解 :就是多線程情況下會不會產生數據不一致的問題，其實安不安全，基本就看是否是 加了鎖，或者是底層是不是用CAS 機制等來進行處理過），

　　　　  JDK1.7底層是 用數組+鏈表（單向鏈表）初始長度是 16 

LinkedHashSet：是HashSet 的 子類 通過創建LinkedHashSet 的構造方法，實際是調用的HashSet的私有方法來進行初始化操作，其中的初始化其實直接對應的是LinkedHashMap這個類。

　　　　　　　　簡單點說，實際上就是用LinkedHashMap 來進行實現的。底層是雙向鏈表

LinkedHashSet:源代碼截取

public class LinkedHashSet<E>
    extends HashSet<E>
    implements Set<E>, Cloneable, java.io.Serializable {
      public LinkedHashSet(int initialCapacity, float loadFactor) {
          super(initialCapacity, loadFactor, true);
      }
      public LinkedHashSet(int initialCapacity) {
           super(initialCapacity, .75f, true);
      }
      public LinkedHashSet() {
            super(16, .75f, true);
      }
}

HashSet 源代碼截取：

public class HashSet<E>
    extends AbstractSet<E>
    implements Set<E>, Cloneable, java.io.Serializable
{
    private transient HashMap<E,Object> map;    
    HashSet(int initialCapacity, float loadFactor, boolean dummy) {
        map = new LinkedHashMap<>(initialCapacity, loadFactor);
    }
}

LinkedHashMap 源代碼截取：

public class LinkedHashMap<K,V>
    extends HashMap<K,V>
    implements Map<K,V>
{
    static class Entry<K,V> extends HashMap.Node<K,V> {
        Entry<K,V> before, after;
        Entry(int hash, K key, V value, Node<K,V> next) {
            super(hash, key, value, next);
        }
    }
}

 

TreeSet：底層使用TreeMap實現，是一個可以排序的set集合。可以定製排序和比較排序，即實現指定泛型類中實體屬性自然排序，也可以通過構造函數來進行指定外部的比較器來進行比較排序。

　　　　需要註意的是，向TreeSet中添加的數據要是想同類型的。否則會報錯。

public class CollectionTest {
    public static void main(String[] args) {
        TreeSet treeSet = new TreeSet();
        treeSet.add("123");
        treeSet.add(123);

    }
}
//報錯信息如下
Exception in thread "main" java.lang.ClassCastException: java.lang.String cannot be cast to java.lang.Integer
    at java.lang.Integer.compareTo(Integer.java:52)
    at java.util.TreeMap.put(TreeMap.java:568)
    at java.util.TreeSet.add(TreeSet.java:255)
    at CollectionTest.main(CollectionTest.java:10)

　　如果不實現自然排序介面（Comparable），直接把值放進TreeSet 中還是會報錯：

public class CollectionTest {
    public static void main(String[] args) {
        TreeSet<User> treeSet = new TreeSet();
        treeSet.add(new User("Misaka",23));
        treeSet.add(new User("mikoto",24));
    }
}

Exception in thread "main" java.lang.ClassCastException: User cannot be cast to java.lang.Comparable
    at java.util.TreeMap.compare(TreeMap.java:1294)
    at java.util.TreeMap.put(TreeMap.java:538)
    at java.util.TreeSet.add(TreeSet.java:255)
    at CollectionTest.main(CollectionTest.java:9)

 實現Comparable代碼示例：

public class CollectionTest {
    public static void main(String[] args) {
        TreeSet<User> treeSet = new TreeSet();
        treeSet.add(new User("mikoto",24));
        treeSet.add(new User("Misaka",23));
        Iterator<User> iterator = treeSet.iterator();
        while (iterator.hasNext()){
            User user = iterator.next();
            System.out.println(user);
        }
    }
}

//省略 get，set，toString，構造等模板代碼
public class User implements Comparable{
    public int compareTo(Object o) {
        if (o instanceof User){
            User user = (User)o;
            Integer age = user.getAge();
            return  this.age.compareTo(age);
        }else {
            throw  new  RuntimeException("類型比較錯誤");
        }
    }
}

測試結果：
User{name='Misaka', age=23}
User{name='mikoto', age=24}

 實現Comparator 外部比較器代碼示例：

public class CollectionTest {
    public static void main(String[] args) {
        Comparator<User> comparator = new Comparator<User>() {
            public int compare(User o1, User o2) {
                return Integer.compare(o1.getAge(),o2.getAge());
            }
        };

        TreeSet<User> treeSet = new TreeSet(comparator);
        treeSet.add(new User("mikoto",24));
        treeSet.add(new User("Misaka",23));
        treeSet.add(new User("Misaka",3));
        treeSet.add(new User("Misaka",5));
        treeSet.add(new User("Misaka",6));
        treeSet.add(new User("Misaka",1));
        Iterator<User> iterator = treeSet.iterator();
        while (iterator.hasNext()){
            User user = iterator.next();
            System.out.println(user);
        }
    }
}

輸出結果：
User{name='Misaka', age=1}
User{name='Misaka', age=3}
User{name='Misaka', age=5}
User{name='Misaka', age=6}
User{name='Misaka', age=23}
User{name='mikoto', age=24}

 


您的分享是我們最大的動力!

-Advertisement-
Play Games
更多相關文章
  • python演算法與數據結構-隊列(44)
    一、隊列的介紹 隊列的定義：隊列是一種特殊的線性表，只允許在表的頭部（front處）進行刪除操作，在表的尾部（rear處）進行插入操作的線性數據結構，這種結構就叫做隊列。進行插入操作的一端稱為隊尾，進行刪除操作的一端稱為隊尾。 隊列的類型：鏈式隊列，即用鏈表實現的隊列。靜態隊列：即用數組實現的隊列。 ...
  • leadcode的Hot100系列--78. 子集--回溯
    上一篇說了使用位運算來進行子集輸出，這裡使用回溯的方法來進行排序。 回溯的思想，我的理解就是： 把解的所有情況轉換為樹或者圖，然後用深度優先的原則來對所有的情況進行遍歷解析。 當然，因為問題中會包涵這各種各樣的限制條件，我們可以用這些限制條件去減少遍歷的分支。 其實，比較著名的就是0 1背包問題，這 ...
  • Django 中自定義 Admin 樣式與功能
    [toc] 自定義 Admin 樣式與功能 1 頁面修改中文 1.1 語言設置為中文 settings.py 修改結果 1.2 應用管理設置為中文 應用/apps.py 修改結果 1.3 資料庫表設置為中文 應用/models.py 預設資料庫表在後臺中顯示都為複數形式，而中文沒有複數形式，因此將兩 ...
  • 表格樹控制項QtTreePropertyBrowser編譯成動態庫(設計師插件)
    [TOC] 原文鏈接： "表格樹控制項QtTreePropertyBrowser編譯成動態庫(設計師插件)" 一、回顧 上一篇文章 "超級實用的表格樹控制項 QtTreePropertyBrowser" 講了怎麼去編譯QtTreePropertyBrowser庫，並且可以簡單使用。由於我下載的庫是基於Q ...
  • 中文自然語言處理(NLP)(一)python jieba模塊
    1.jieba分詞的安裝 直接在cmd視窗當中pip install即可 2.jieba分詞的介紹 jieba分詞是目前比較好的中文分片語件之一，jieba分詞支持三種模式的分詞(精確模式、全模式、搜索引擎模式)，並且支持自定義詞典(這一點在特定的領域很重要，有時候需要根據領域的需要來添加特定的詞典 ...
  • 裝飾器函數
    裝飾器函數 開發封閉原則（先從別人偷來一波好文章，簡單易懂）   什麼是開放封閉原則？有的同學問開放，封閉這是兩個反義詞這還能組成一個原則麽？這不前後矛盾麽？其實不矛盾。開放封閉原則是分情況討論的。   我們的軟體一旦上線之後（比如你的軟體主要是多個函數組成的 ...
  • 01-二維數組中的查找
    1題目：在一個二維數組中（每個一維數組的長度相同），每一行都按照從左到右遞增的順序排序，每一列都按照從上到下遞增的順序排序。請完成一個函數，輸入這樣的一個二維數組和一個整數，判斷數組中是否含有該整數。 2思路：首先選取數組中右上角的數字。如果該數字等於要查找的數字，查找過程結束；如果該數字大於要查找 ...
  • SpringBoot2.0基礎案例分類總結，後續更新計劃說明
    一、基礎案例 1、基礎案例概覽 歷時一個半月，SpringBoot2.0基礎案例的文章基本更新完畢了，基礎案例包含了SpringBoot的基礎教程，高級應用，日誌配置，資料庫使用，事務管理等。關於SpringBoot2.0的基礎案例就更新到這裡了，後續會更新SpringBoot2.0和各種中間件的整 ...
一周排行
    -Advertisement-
    Play Games
  • 移動開發（一）：使用.NET MAUI開發第一個安卓APP
    移動開發（一）：使用.NET MAUI開發第一個安卓APP 對於工作多年的C#程式員來說，近來想嘗試開發一款安卓APP，考慮了很久最終選擇使用.NET MAUI這個微軟官方的框架來嘗試體驗開發安卓APP，畢竟是使用Visual Studio開發工具，使用起來也比較的順手，結合微軟官方的教程進行了安卓 ...
  • wpf ToggleButton選中效果和一個登錄界面
    前言 QuestPDF 是一個開源 .NET 庫，用於生成 PDF 文檔。使用了C# Fluent API方式可簡化開發、減少錯誤並提高工作效率。利用它可以輕鬆生成 PDF 報告、發票、導出文件等。 項目介紹 QuestPDF 是一個革命性的開源 .NET 庫，它徹底改變了我們生成 PDF 文檔的方 ...
  • 彈幕樹洞項目功能新增篇
    項目地址 項目後端地址： https://github.com/ZyPLJ/ZYTteeHole 項目前端頁面地址： ZyPLJ/TreeHoleVue (github.com) https://github.com/ZyPLJ/TreeHoleVue 目前項目測試訪問地址： http://tree ...
  • 第27篇 sqlserver2022詳細安裝步驟
    話不多說，直接開乾 一.下載 1.官方鏈接下載： https://www.microsoft.com/zh-cn/sql-server/sql-server-downloads 2.在下載目錄中找到下麵這個小的安裝包 SQL2022-SSEI-Dev.exe，運行開始下載SQL server； 二. ...
  • .NET 開源高性能 MQTT 類庫
    前言 隨著物聯網（IoT）技術的迅猛發展，MQTT（消息隊列遙測傳輸）協議憑藉其輕量級和高效性，已成為眾多物聯網應用的首選通信標準。 MQTTnet 作為一個高性能的 .NET 開源庫，為 .NET 平臺上的 MQTT 客戶端與伺服器開發提供了強大的支持。 本文將全面介紹 MQTTnet 的核心功能 ...
  • Serilog文檔翻譯系列（六） - 可用的接收器、增強器、格式化輸出
    Serilog支持多種接收器用於日誌存儲，增強器用於添加屬性，LogContext管理動態屬性，支持多種輸出格式包括純文本、JSON及ExpressionTemplate。還提供了自定義格式化選項，適用於不同需求。 ...
  • 警惕 Visual Studio 屬性求值副作用導致邏輯不符合預期
    目錄簡介獲取 HTML 文檔解析 HTML 文檔測試參考文章 簡介 動態內容網站使用 JavaScript 腳本動態檢索和渲染數據，爬取信息時需要模擬瀏覽器行為，否則獲取到的源碼基本是空的。 本文使用的爬取步驟如下： 使用 Selenium 獲取渲染後的 HTML 文檔 使用 HtmlAgility ...
  • [使用目前最新版]HybridCLR6.9.0+YooAsset2.2.4實現純C# Unity熱更新方案 (一)
    1.前言 什麼是熱更新 游戲或者軟體更新時，無需重新下載客戶端進行安裝，而是在應用程式啟動的情況下，在內部進行資源或者代碼更新 Unity目前常用熱更新解決方案 HybridCLR，Xlua，ILRuntime等 Unity目前常用資源管理解決方案 AssetBundles，Addressable， ...
  • 在 ASP.NET Core Web API 中使用操作篩選器統一處理通用操作
    本文章主要是在C# ASP.NET Core Web API框架實現向手機發送驗證碼簡訊功能。這裡我選擇是一個互億無線簡訊驗證碼平臺，其實像阿裡雲，騰訊雲上面也可以。 首先我們先去 互億無線 https://www.ihuyi.com/api/sms.html 去註冊一個賬號 註冊完成賬號後，它會送 ...
  • 第28篇 如何.net中實現高效可靠數據同步api
    通過以下方式可以高效，並保證數據同步的可靠性 1.API設計 使用RESTful設計，確保API端點明確，並使用適當的HTTP方法（如POST用於創建，PUT用於更新）。 設計清晰的請求和響應模型，以確保客戶端能夠理解預期格式。 2.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類