單列集合框架體系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
  • WPF 已知問題 監聽 WMI 事件導致觸摸失效
    示例項目結構 在 Visual Studio 中創建一個 WinForms 應用程式後，項目結構如下所示： MyWinFormsApp/ │ ├───Properties/ │ └───Settings.settings │ ├───bin/ │ ├───Debug/ │ └───Release/ ...
  • [STAThread]特性
    [STAThread] 特性用於需要與 COM 組件交互的應用程式，尤其是依賴單線程模型（如 Windows Forms 應用程式）的組件。在 STA 模式下，線程擁有自己的消息迴圈，這對於處理用戶界面和某些 COM 組件是必要的。 [STAThread] static void Main(stri ...
  • UWP WinUI3 傳入 AddHandler 的 RoutedEventHandler 類型與事件所需不匹配將拋出參數異常
    在WinForm中使用全局異常捕獲處理 在WinForm應用程式中，全局異常捕獲是確保程式穩定性的關鍵。通過在Program類的Main方法中設置全局異常處理，可以有效地捕獲並處理未預見的異常，從而避免程式崩潰。 註冊全局異常事件 [STAThread] static void Main() { / ...
  • .NET 多版本 WinForm 開源控制項庫 SunnyUI
    前言 給大家推薦一款開源的 Winform 控制項庫，可以幫助我們開發更加美觀、漂亮的 WinForm 界面。 項目介紹 SunnyUI.NET 是一個基於 .NET Framework 4.0+、.NET 6、.NET 7 和 .NET 8 的 WinForm 開源控制項庫，同時也提供了工具類庫、擴展 ...
  • .net core8 使用Swagger（附當前源碼）
    說明 該文章是屬於OverallAuth2.0系列文章，每周更新一篇該系列文章（從0到1完成系統開發）。 該系統文章，我會儘量說的非常詳細，做到不管新手、老手都能看懂。 說明：OverallAuth2.0 是一個簡單、易懂、功能強大的許可權+可視化流程管理系統。 有興趣的朋友，請關註我吧(*^▽^*) ...
  • WPF 什麼時候 VisualTreeHelper.GetDescendantBounds 將返回無窮大
    一、下載安裝 1.下載git 必須先下載並安裝git，再TortoiseGit下載安裝 git安裝參考教程：https://blog.csdn.net/mukes/article/details/115693833 2.TortoiseGit下載與安裝 TortoiseGit，Git客戶端，32/6 ...
  • C# 開源教程帶你輕鬆掌握數據結構與演算法
    前言 在項目開發過程中，理解數據結構和演算法如同掌握蓋房子的秘訣。演算法不僅能幫助我們編寫高效、優質的代碼，還能解決項目中遇到的各種難題。 給大家推薦一個支持C#的開源免費、新手友好的數據結構與演算法入門教程：Hello演算法。 項目介紹 《Hello Algo》是一本開源免費、新手友好的數據結構與演算法入門 ...
  • 第22篇 生成proto文件bat腳本
    1.生成單個Proto.bat內容 @rem Copyright 2016, Google Inc. @rem All rights reserved. @rem @rem Redistribution and use in source and binary forms, with or with ...
  • 記一次 .NET某上位機視覺程式 卡死分析
    一：背景 1. 講故事 前段時間有位朋友找到我，說他的窗體程式在客戶這邊出現了卡死，讓我幫忙看下怎麼回事？dump也生成了，既然有dump了那就上 windbg 分析吧。 二：WinDbg 分析 1. 為什麼會卡死 窗體程式的卡死，入口門檻很低，後續往下分析就不一定了，不管怎麼說先用 !clrsta ...
  • 醫學DICOM文件與PACS系統進行數據傳輸
    前言 人工智慧時代，人臉識別技術已成為安全驗證、身份識別和用戶交互的關鍵工具。 給大家推薦一款.NET 開源提供了強大的人臉識別 API，工具不僅易於集成，還具備高效處理能力。 本文將介紹一款如何利用這些API，為我們的項目添加智能識別的亮點。 項目介紹 GitHub 上擁有 1.2k 星標的 C# ...
所有分類