java容器詳細解析上

来源:http://www.cnblogs.com/LipeiNet/archive/2016/09/22/5888513.html
-Advertisement-
Play Games

前言：在java開發中我們肯定會大量的使用集合，在這裡我將總結常見的集合類，每個集合類的優點和缺點，以便我們能更好的使用集合。下麵我用一幅圖來表示 其中淡綠色的表示介面，紅色的表示我們經常使用的類。 1：基本概念 Java容器類類庫的用途是保存對象，可以將其分為2個概念。 1.1：Collectio ...


前言：在java開發中我們肯定會大量的使用集合，在這裡我將總結常見的集合類，每個集合類的優點和缺點，以便我們能更好的使用集合。下麵我用一幅圖來表示

其中淡綠色的表示介面，紅色的表示我們經常使用的類。

1：基本概念

Java容器類類庫的用途是保存對象，可以將其分為2個概念。

1.1：Collection

一個獨立元素的序列，這些元素都服從一條或多條規則。其中List必須按照插入的順序保存元素、Set不能有重覆的元素、Queue按照排隊規則來確定對象的產生順序（通常也是和插入順序相同）

1.2：Map

一組成對的值鍵對對象，允許用鍵來查找值。ArrayList允許我們用數字來查找值，它是將數字和對象聯繫在一起。而Map允許我們使用一個對象來查找某個對象，它也被稱為關聯數組。或者叫做字典。

2：List

List承諾可以將元素維護在特定的序列中。List介面在Collection的基礎上加入了大量的方法，使得可以在List中間可以插入和移除元素。下麵主要介紹2種List

2.1：基本的ArrayList

它的優點在於隨機訪問元素快，但是在中間插入和移除比較慢

那麼現在我們就一起來看看為什麼ArrayList隨機訪問快，而插入移除比較慢。先說關於ArrayList的初始化。

ArrayList有三種方式進行初始化如下

private transient Object[] elementData;
public ArrayList() {
        this(10);
    }
  public ArrayList(int initialCapacity) {
        super();
        if (initialCapacity < 0)
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        this.elementData = new Object[initialCapacity];
    }
 public ArrayList(Collection<? extends E> c) {
        elementData = c.toArray();
        size = elementData.length;
        // c.toArray might (incorrectly) not return Object[] (see 6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    }

我們可以看出ArrayList其實就是採用的是數組（預設是長度為10的數組）。所有ArrayList在讀取的時候是具有和數組一樣的效率，它的時間複雜度為1。

插入尾部就是elementData[size++] = e;當然中間會進行擴容。現在主要說插入中間為什麼相對來說比較慢源碼如下

 public void add(int index, E element) {
        rangeCheckForAdd(index);//驗證（可以不考慮）

        ensureCapacityInternal(size + 1);  // Increments modCount!!（超過當前數組長度進行擴容）
        System.arraycopy(elementData, index, elementData, index + 1,
                         size - index);(核心代碼)
        elementData[index] = element;
        size++;
    }

System.arraycopy(elementData, index, elementData, index + 1)第一個參數是源數組，源數組起始位置，目標數組，目標數組起始位置，複製數組元素數目。那麼這個意思就是從index索性處每個元素向後移動一位，最後把索引為index空出來，並將element賦值給它。這樣一來我們並不知道要插入哪個位置，所以會進行匹配那麼它的時間賦值度就為n。

2.2：LinkedList

它是通過代價較低在List中間進行插入和移除，提供了優化的順序訪問，但是在隨機訪問方面相對較慢。但是他的特性功能要比ArrayList強大的多。支持Queue和Stack

ListedList採用的是鏈式存儲。鏈式存儲就會定一個節點Node。包括三部分前驅節點、後繼節點以及data值。所以存儲存儲的時候他的物理地址不一定是連續的。

我們看下它的中間插入實現

從代碼我們可以看出先獲取插入索引元素的前驅節點，然後把這個元素作為後繼節點，然後在創建新的節點，而新的節點前驅節點和獲取前驅節點相同，而後繼節點則等於要移動的這個元素。所以這裡是不需要迴圈的，從而在插入和刪除的時候效率比較高。

我們在來看看查詢（我們可以分析出它的效率要比ArrayList低了不少）

3：Set

Set也是一個集合，但是他的特點是不可以有重覆的對象，所以Set最常用的就是測試歸屬性，很容易的詢問出某個對象是否存在Set中。並且Set是具有和Collection完全一樣的介面，沒有額外的功能，只是表現的行為不同。

3.1：HashSet

HashSet查詢速度比較快，但是存儲的元素是隨機的並沒有排序，下麵我寫一段程式看一下

public static void main(String[] args){
        /**
         * 沒有順序可循，這是因為hashset採用的是散列（處於速度考慮）
         */
        Random random=new Random(47);
        Set<Integer> intset=new HashSet<Integer>();
        for (int i=0;i<10000;i++){
            intset.add(random.nextInt(30));
        }
        System.out.print(intset);
    }

3.2：TreeSet

TreeSet是將元素存儲紅-黑樹結構中，所以存儲的結果是有順序的（所以如果你想要自己存儲的集合有順序那麼選擇TreeSet）

public static void main(String[] args){
        Random random=new Random(47);
        Set<Integer> intset=new TreeSet<Integer>();
        for (int i=0;i<10000;i++){
            intset.add(random.nextInt(30));
        }
        System.out.print(intset);
    }

 關於LinkedHashSet後面再說。

4：Queue

Queue是隊列，隊列是典型的先進先出的容器，就是從容器的一端放入元素，從另一端取出，並且元素放入容器的順序和取出的順序是相同的。LinkedList提供了對Queue的實現，LinkedList向上轉型為Queue。其中Queue有offer、peek、element、pool、remove等方法

offer是將元素插入隊尾，返回false表示添加失敗。peek和element都將在不移除的情況下返回對頭，但是peek在對頭為null的時候返回null，而element會拋出NoSuchElementException異常。poll和remove方法將移除並返回對頭，但是poll在隊列為null，而remove會拋出NoSuchElementException異常，以下是例子

  public static void main(String[] args){
        Queue<Integer> queue=new LinkedList<Integer>();
        Random rand=new Random();
        for (int i=0;i<10;i++){
            queue.offer(rand.nextInt(i+10));
        }
        printQ(queue);
        Queue<Character> qc=new LinkedList<Character>();
        for (char c:"HelloWorld".toCharArray()){
            qc.offer(c);
        }
        System.out.println(qc.peek());
        printQ(qc);
        List<String> mystrings=new LinkedList<String>();
        mystrings.add("1");
        mystrings.get(0);
        Set<String> a=new HashSet<String>();
        Set<String> set=new HashSet<String>();
        set.add("1");
    }
    public static void printQ(Queue queue){
        while (queue.peek

從上面的輸出的結果我們可以看出結果並不是一個順序的，沒有規則的，這個時候如果想讓隊列按照規則輸出那麼這個時候我們就要考慮優先順序了，這個時候我們就應該使用PriorityQueue，這個時候如果在調用offer方法插入一個對象的時候，這個對象就會按照優先順序在對列中進行排序，預設的情況是自然排序，當然我們可以通過Comparator來修改這個順序（在下一篇講解）。PriorityQueue可以確保當你調用peek、pool、remove方法時，獲取的元素將是對列中優先順序最高的元素。ok我們再次通過代碼查看

 public static void main(String[] args) {
        PriorityQueue<Integer> priorityQueue = new PriorityQueue<Integer>();
        Random rand = new Random();
        for (int i = 0; i < 10; i++) {
            priorityQueue.offer(rand.nextInt(i + 10));
        }
        QueueDemo.printQ(priorityQueue);
        List<Integer>ints= Arrays.asList(25,22,20,18,14,9,3,1,1,2,3,9,14,18,21,23,25);
        priorityQueue=new PriorityQueue<Integer>(ints);
        QueueDemo.printQ(priorityQueue);
    }

從輸出可以看到，重覆是允許的，最小值擁有最高優先順序（如果是String，空格也可以算作值，並且比字母具有更高的優先順序）如果你想消除重覆，可以採用Set進行存儲，然後把Set作為priorityQueue對象的初始值即可。

5：Map

Map在實際開發中使用非常廣，特別是HashMap，想象一下我們要保存一個對象中某些元素的值，如果我們在創建一個對象顯得有點麻煩，這個時候我們就可以用上map了，HashMap採用是散列函數所以查詢的效率是比較高的，如果我們需要一個有序的我們就可以考慮使用TreeMap。這裡主要介紹一下HashMap的方法，大家註意HashMap的鍵可以是null，而且鍵值不可以重覆，如果重覆了以後就會對第一個進行鍵值進行覆蓋。

put進行添加值鍵對，containsKey驗證主要是否存在、containsValue驗證值是否存在、keySet獲取所有的鍵集合、values獲取所有值集合、entrySet獲取鍵值對。

 public static void main(String[] args){
        //Map<String,String> pets=new HashMap<String, String>();
        Map<String,String> pets=new TreeMap<String, String>();
        pets.put("1","張三");
        pets.put("2","李四");
        pets.put("3","王五");
        if (pets.containsKey("1")){
            System.out.println("已存在鍵1");
        }
        if (pets.containsValue("張三")){
            System.out.println("已存在值張三");
        }
        Set<String> sets=pets.keySet();
        Set<Map.Entry<String , String>> entrySet= pets.entrySet();
        Collection<String> values=  pets.values();
        for (String value:values){
            System.out.println(value+";");
        }
       for (String key:sets){
           System.out.print(key+";");
       }
        for (Map.Entry entry:entrySet){
            System.out.println("鍵："+entry.getKey());
            System.out.println("值："+entry.getValue());
        }
    }

6：Iterator和Foreach

現在foreach語法主要作用於數組，但是他也可以應用於所有的Collection對象。Collection之所以能夠使用foreach是由於繼承了Iterator這個介面。下麵我寫段代碼供大家查看

public class IteratorClass {
    public Iterator<String> iterator(){
      return new Itr();
    }
    private class Itr implements Iterator<String>{
        protected String[] words=("Hello Java").split(" ");
        private int index=0;
        public boolean hasNext() {
            return index<words.length;
        }
        public String next() {
            return words[index++];
        }
        public void remove() {
        }
    }
}
 Iterator iterators=new IteratorClass().iterator();
        for (Iterator it=iterator;iterators.hasNext();) {
            System.out.println(iterators.next());
        }
        while (iterators.hasNext()){
            System.out.println(iterators.next());
        }

從中我們可以看出foreach迴圈最終是轉換成 for (Iterator it=iterator;iterators.hasNext();)只不過jdk幫我們隱藏我們無法查看。下麵我們在來分析一個問題，關於List刪除問題。我們大多肯定使用過for迴圈或者foreach迴圈去刪除，但是結果很明顯會出現錯誤，那麼現在我們一起分析為啥會出現錯誤。

1：使用for迴圈刪除（出現錯誤分析）

2：foreach迴圈刪除（錯誤分析）

從上面我們得知foreach最終是會轉成Iterator的所以它首先會通過next來獲取元素，我們看代碼

 請看for迴圈刪除那段代碼，沒刪除一次modCount會++，所以第二次在次刪除的時候modCount由於增加和expectedModCount不等所以無法獲取元素也就無法刪除。

3：正確的刪除方式

採用迭代器代碼如下

 Iterator<String> iterator=userList.iterator();
        while (iterator.hasNext()){
            iterator.next();
            iterator.remove();
        }

請記住一定要加上iterator.next();這是因為在源碼中有一個lastRed，通過它來記錄是否是最後一個元素，如果不加上iterator.next()那麼lastRed=-1,在刪除驗證的時候有這麼一段代碼if (lastRet < 0)throw new IllegalStateException();所以就會拋出異常。

 

7：Collections和Arrays

這裡只介紹2個常用的Collections.addAll和Arrays.asList

addAll：

asList採用的是數組

可以看出最終轉換成ArrayList。

 8：總結

1）：數組是將數字和對象聯繫起來，它保存明確的對象，查詢對象時候不需要對查詢結果進行轉換，它可以是多維的，可以保存基本類型的數據，但是數組一旦生成，其容量不能改變。所以數組是不可以直接刪除和添加元素。

2）：Collection保存單一的元素，而Map保存相關聯的值鍵對，有了Java泛型，可以指定容器存放對象類型，不會將錯誤類型的對象放在容器中，取元素時候也不需要轉型。而且Collection和Map都可以自動調整其尺寸。容器不可以持有基本類型。

3）：像數組一樣，List也建立數字索性和對象的關聯，因此，數組和List都是排好序的容器，List可以自動擴容

4）：如果需要大量的隨機訪問就要使用ArrayList，如果要經常從中間插入和刪除就要使用LinkedList。

5）：各種Queue和Stack由LinkedList支持

6）：Map是一種將對象（而非數字）與對象相關聯的設計。HashMap用於快速訪問，TreeMap保持鍵始終處於排序狀態，所以不如HashMap快，而LinkedHashMap保持元素插入的順序，但是也通過散列提供了快速訪問的能力

7）：Set不接受重覆的元素，HashSet提供最快的訪問能力，TreeSet保持元素排序狀態，LinkedHashSet以插入順序保存元素。

 


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

-Advertisement-
Play Games
更多相關文章
  • JAVA 8 預設方法-Default Methods
    什麼是預設方法-Default Methods 簡單的說，就是可以在介面中定義一個已實現方法，且該介面的實現類不需要實現該方法； 如下示例： 為什麼要有預設方法 主要是為了方便擴展已有介面；如果沒有預設方法，加入給JDK中的某個介面添加一個新的抽象方法，那麼所有實現了該介面的類都得修改，影響將非常大 ...
  • Shiro —— Spring 環境下的使用
    一、使用 1.搭建基礎環境 （1）導入 Spring 和 Shiro 的 Jar 包 正常導入 spring jar包 導入日誌包 導入 shiro 包 （2）配置文件 web.xml spring-shiro.xml spring.xml 正常配置即可。 springmvc.xml 正常配置即可。 ...
  • 函數聲明和函數定義中的預設參數淺析
    ...
  • 轉載：分頁原理+分頁代碼+分頁類製作
    分頁顯示是一種非常常見的瀏覽和顯示大量數據的方法，屬於web編程中最常處理的事件之一。對於web編程的老手來說，編寫這種代碼實在是和呼吸一樣自然，但是對於初學者來說，常常對這個問題摸不著頭緒，因此特地撰寫此文對這個問題進行詳細的講解。一、分頁原理： 所謂分頁顯示，也就是將資料庫中的結果集人為的分成一 ...
  • Java漢字轉拼音
    項目比較簡單，主要是用來學習下，如果要開發的話需要看項目具體功能具體分析。。。 使用jar包：pinyin4j-2.5.0.jar，需要jar包的可以百度下 轉載請註明：李鋒鏑的個人博客 >> http://www.lifengdi.com/article/10041.html 轉載請註明：李鋒鏑的 ...
  • java 克隆
    1. About Java中， 對於基本數據類型可以使用"=" 來克隆，此時兩個對象除了相等是沒有任何關係的; 而對於引用類型, 卻不能簡單地使用"="來克隆，這與java記憶體空間使用有關。 java將記憶體空間分為兩塊， 即堆和棧。 在棧中保存基本類型和引用變數，在堆中保存對象。 對於引用變數而言， ...
  • java變數類型
    github地址:https://github.com/lily1010/java_learn Java語言支持的變數類型 ①局部變數 ②成員變數 ③類變數(靜態變數) Java局部變數 ①局部變數聲明在方法、構造方法或者語句塊中；②局部變數在方法、構造方法、或者語句塊被執行的時候創建，當它們執行完 ...
  • 【菜鳥玩Linux開發】在C++里操作MySQL
    MySQL是一個的開源關係型資料庫，對於服務端開發來說是一個優秀的選擇。本篇內容將介紹如何在C++程式里操作MySQL資料庫。 ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類