Java中的容器（集合）

来源:https://www.cnblogs.com/xihuantingfeng/archive/2019/10/02/11616389.html
-Advertisement-
Play Games

1、Java常用容器：List，Set，Map List： 繼承了Collection介面（public interface List<E> extends Collection<E> ），有序且允許出現重覆值。 Set： 繼承了Collection介面（public interface Set<E ...


1、Java常用容器：List，Set，Map

List：

  • 繼承了Collection介面（public interface List<E> extends Collection<E> ），有序且允許出現重覆值。

Set：

  • 繼承了Collection介面（public interface Set<E> extends Collection<E> ），無序且不允許出現重覆值。

Map：

  • 是一個使用鍵值對存儲的容器（public interface Map<K,V> ）。

2、Collection 和 Collections 的區別

Collection：

  • Collection是一個集合類的通用介面（源碼：public interface Collection<E> extends Iterable<E>）。
  • 通過查看源碼可以發現，其中包含的都是一些通用的集合操作介面，他的直接繼承介面有List和Set。

Collections：

  • Collections是一個集合工具類（源碼：public class Collections）。
  • 其中提供一系列對集合操作的靜態方法，比如排序：sort()，集合安全：synchronizedCollection()，反轉：reverse()等等。

3、ArrayList 和 LinkedList 的區別

ArrayList：

  • 底層數據結構是一個數組，查詢效率比較高，添加刪除較慢（預設添加在末尾，在指定位置添加元素效率比較低，因為需要將指定位置後續的元素都往後移位）。

LinkedList：

  • 底層數據結構是一個雙向鏈表（prev指向前節點，next指向後節點），查詢效率比較慢，添加刪除比較快。

4、ArrayList 和 Vector 的區別

ArrayList：

  • 非線程安全，讀取效率較高。

Vector：

  • 線程安全（源碼中顯示該類的方法使用了synchronized），讀取效率較低（推薦使用CopyOnWriteArrayList,該類適合讀多寫少的場景）。

5、HashMap 和 Hashtable 的區別

HashMap：

  • 非線程安全，允許空鍵值，執行效率相對較高（底層使用的數據結構是數組+鏈表+紅黑樹（jdk8）或者數組+鏈表（jdk7））。

Hashtable：

  • 線程安全，不允許空鍵值，執行效率相對較低（推薦使用ConcurrentHashMap）。

6、HashMap 和 TreeMap 的使用場景

HashMap：

  • 一般情況下進行插入，刪除，定位元素的話，使用HashMap（常用）。

TreeMap：

  • 如果需要使用有序的集合，推薦用TreeMap。

7、HashMap 實現原理

以put操作為例：

  • 首先會根據key的hashCode得到hash值（部分源碼：return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16)），依據hash值得到該元素在數組的位置（下標），如果該位置不存在元素，則將該元素直接放入此位置上；否則判斷元素是否相等，如果是，則覆蓋，否則使用拉鏈法解決衝突（創建一個鏈表，先加入的放到鏈尾，後加入的放在鏈頭，超過8位時，使用紅黑樹存儲）。
  • 放入的元素是包含了鍵值對的元素，而非僅僅只有值。

8、HashSet 實現原理

以add操作為例：

  • 進入add源碼（return map.put(e, PRESENT)==null），可以看到其底層是用map來實現的，只是傳入的值當做了map的key，而map的value使用的是統一的PRESENT。

9、迭代器：Iterator

Iterator：

  • 是一個輕量級的對象（創建代價小），主要用來對集合進行遍歷移除等操作。
  • 示例代碼如下
package com.spring.test.service.demo;

import java.util.*;

/**
 * @Author: philosopherZB
 * @Date: 2019/10/1
 */
public class Demo {
    public static void main(String[] args){
        List<String> list = new ArrayList<>(5);
        for(int i=0;i<5;i++){
            list.add("Test" + i);
            System.out.println("輸入：Test" + i);
        }
        //利用iterator()返回一個Iterator對象
        Iterator<String> it = list.iterator();
        //判斷是否還存在元素
        while(it.hasNext()){
            //第一次調用next()會返回集合中的第一個元素，之後返回下一個
            String s = it.next();
            if("Test3".equals(s))
                //移除某個元素
                it.remove();
        }
        list.forEach(l->{
            System.out.println(l);
        });
    }
}
View Code

10、ArrayList 擴容源碼解析（JDK8）

源碼解析：

  • 首先我們使用 ArrayList<String> list = new ArrayList<>(5)創建一個ArrayLsit，這表明創建的ArrayList初始容量為5.
  • 源碼如下：
    //預設初始容量10
    private static final int DEFAULT_CAPACITY = 10;
    //一個空的預設對象數組，當ArrayList(int initialCapacity)，ArrayList(Collection<? extends E> c)中的容量等於0的時候使用
    private static final Object[] EMPTY_ELEMENTDATA = {};
    //一個空的預設對象數組，用於ArrayList()構造器
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    //一個對象數組，transient表示不能序列化
    transient Object[] elementData;
    //數組大小
    private int size;

    //以傳入的容量構造一個空的list
    public ArrayList(int initialCapacity) {
        //如果傳入值大於0，則創建一個該容量大小的數組。
        if (initialCapacity > 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            //否則如果傳入值等於0，則創建預設空數組
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            //如果小於0則拋出異常
            throw new IllegalArgumentException("Illegal Capacity: "+
                    initialCapacity);
        }
    }
  • 接著我們使用add方法添加一個字元串到該list中，list.add("Test")。進入add源碼會發現，真正的擴容是發生在add操作之前的。
  • 源碼如下：
    //預設添加在數組末尾
    public boolean add(E e) {
        //添加之前先確認是否需要擴容
        ensureCapacityInternal(size + 1);  // Increments modCount!!
        //新加入的元素是添加在了數組的末尾，隨後數組size自增。
        elementData[size++] = e;
        return true;
    }
  • 進入ensureCapacityInternal()方法查看對應源碼如下：
    private void ensureCapacityInternal(int minCapacity) {
        //先通過calculateCapacity方法計算最終容量，以確認實際容量
        ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
    }
  • 到這一步，我們需要先進入calculateCapacity()方法看看他是如何計算最後容量的，源碼如下：
    private static int calculateCapacity(Object[] elementData, int minCapacity) {
        //如果elementData為預設空數組，則比較傳入值與預設值（10），返回兩者中的較大值
        //elementData為預設空數組指的是通過ArrayList()這個構造器創建的ArrayList對象
        if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            return Math.max(DEFAULT_CAPACITY, minCapacity);
        }
        //返回傳入值
        return minCapacity;
    }
  • 現在我們確認了最終容量，那麼進入ensureExplicitCapacity，查看源碼如下：
    private void ensureExplicitCapacity(int minCapacity) {
        modCount++;
        // overflow-conscious code
        //如果最終確認容量大於數組容量，則進行grow()擴容
        if (minCapacity - elementData.length > 0)
            grow(minCapacity);
    }
  • 可以看到，只有當最終容量大於數組容量時才會進行擴容。那麼以我們上面的例子而言具體分析如下：
  • 首先因為我們創建的時候就賦了初始容量5，所以elementData.length = 5。
  • 當我們add第一個元素的時候，minCapacity是等於size + 1 = 1的。
  • 此時minCapacity - elementData.length > 0條件不成立，所以不會進入grow(minCapacity)方法進行擴容。
  • 以此類推，只有添加到第五個元素的時候，minCapacity = 6 大於 elementData.length = 5，這時就會進入grow(minCapacity)方法進行擴容。
  • grow()以及hugeCapacity()源碼如下：
    //可分配的最大數組大小
    private static final int MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8;

    //擴容
    private void grow(int minCapacity) {
        // overflow-conscious code
        //oldCapacity表示舊容量
        int oldCapacity = elementData.length;
        //newCapacity表示新容量，計算規則為舊容量+舊容量的0.5，即舊容量的1.5倍。如果超過int的最大值會返回一個負數。
        //oldCapacity >> 1表示右移一位，對應除以2的1次方。
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        //如果新容量小於最小容量，則將最小容量賦值給新容量(有時手動擴容可能也會返回<0，對應方法為ensureCapacity())
        if (newCapacity - minCapacity < 0)
            newCapacity = minCapacity;
        //如果新容量大於MAX_ARRAY_SIZE，則執行hugeCapacity(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);
    }

    private static int hugeCapacity(int minCapacity) {
        //如果最小容量超過了int的最大值，minCapacity會是一個負數，此時拋出記憶體溢出錯誤
        if (minCapacity < 0) // overflow
            throw new OutOfMemoryError();
        //比較最小容量是否大於MAX_ARRAY_SIZE，如果是則返回Integer.MAX_VALUE，否則返回MAX_ARRAY_SIZE
        return (minCapacity > MAX_ARRAY_SIZE) ?
                Integer.MAX_VALUE :
                MAX_ARRAY_SIZE;
    }

 （以上所有內容皆為個人筆記，如有錯誤之處還望指正。）


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

-Advertisement-
Play Games
更多相關文章
  • python機器學習簡介
    [TOC]   機器學習是一門多領域交叉學科，涉及概率論、統計學、逼近論、凸分析、演算法複雜度理論等多門學科。專門研究電腦怎樣模擬或實現人類的學習行為，以獲取新的知識或技能，重新組織已有的知識結構使之不斷改善自身的性能。從數據中提取知識，也被稱為預測分析 或 統計學習。 &ems ...
  • python 爬蟲 user-agent 生成
    有些網站做了反爬技術，如：比較初級的通過判斷請求頭部中的user-agent欄位來檢測是否通過瀏覽器訪問的。 在爬這類網站時需要模擬user-agent user-agent.txt 百度網盤 鏈接：https://pan.baidu.com/s/1ramkIyjVSI2_GXbxypj1Dg 提取 ...
  • Python GUI文本編輯器
    使用Python編寫一個簡單的文本編輯器，需要展示一個用戶界面，功能包括打開、保存文本文件。 使用tkinter庫來編寫GUI。 ...
  • a++與++a，談談C++的參數傳遞
    先看一段代碼： mov eax,dword ptr [a] add eax,1 mov dword ptr [a],eax //這三行指令將a+1 mov ecx,dword ptr [a] mov dword ptr [ebp 0D0h],ecx //這兩行指令將a的值存儲到一個臨時地址（寄存器間 ...
  • STS安裝Drools
    Open Eclipse.- Open the menu "Help", menu item "Install new software..."- Click on the button "Add..." to add a new software site.- Fill in the name " ...
  • Java中的容器（集合）之ArrayList源碼解析
    1、ArrayList源碼解析 源碼解析： 如下源碼來自JDK8:。 （以上所有內容皆為個人筆記，如有錯誤之處還望指正。） ...
  • C語言入門-指針
    終於到了精髓的地方了，這確實有點懵，總感覺這太麻煩了，而且寫著也不爽，還是懷念py或者java，但也沒辦法，還是要繼續學下去。 一、運算符& 1. scanf("%d" , &i); 里的& 2. 獲取變數的地址，它的操作數必須是變數 3. 地址的大小是否與int相同取決於編譯器 &不能取的地址 & ...
  • python解釋器安裝與環境變數調試
    Python解釋器安裝與環境變數調試 Python解釋器安裝(3.6): www.python.org這個是python解釋器的官網，一定要牢記。 鑒於市場上有兩種python版本(2和3)，今天兩種版本都裝一下，互相學習，如有錯誤還請各位評論指正。 ![img](https://img2018.c ...
一周排行
    -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.數據驗證 在伺服器端進行嚴格的數據驗證，確保接收到的數據符合預期格 ...
所有分類