一、 簡(jiǎn)介ArrayList

1.1 介紹ArrayList的基本概念和作用

在Java中，ArrayList是一個(gè)實(shí)現(xiàn)了List接口的動(dòng)態(tài)數(shù)組。它可以根據(jù)需要自動(dòng)增加大小，因此可以存儲(chǔ)任意數(shù)量的元素。

1.基本概念：

• ArrayList是Java中常用的集合類之一，它可以存儲(chǔ)對(duì)象，并且可以根據(jù)索引訪問(wèn)和操作這些對(duì)象。
• ArrayList是基于數(shù)組實(shí)現(xiàn)的，但是它具有動(dòng)態(tài)擴(kuò)展的能力，因此可以動(dòng)態(tài)地增加和減少元素的數(shù)量。

2,.作用：

• 存儲(chǔ)數(shù)據(jù)：ArrayList可以用來(lái)存儲(chǔ)各種類型的數(shù)據(jù)，包括基本類型和對(duì)象類型。
• 動(dòng)態(tài)擴(kuò)展：由于ArrayList的大小是動(dòng)態(tài)的，因此它非常適合需要?jiǎng)討B(tài)增加和減少元素的場(chǎng)景。
• 方便操作：ArrayList提供了豐富的方法來(lái)操作元素，比如添加、刪除、查找等，使得對(duì)集合的操作變得非常便利。

總之，ArrayList在Java中是非常常用的數(shù)據(jù)結(jié)構(gòu)，它提供了動(dòng)態(tài)存儲(chǔ)數(shù)據(jù)的能力，以及豐富的操作方法，非常適合在開(kāi)發(fā)中使用。

1.2 與數(shù)組的區(qū)別和優(yōu)勢(shì)

ArrayList是一種動(dòng)態(tài)數(shù)組，它是基于數(shù)組實(shí)現(xiàn)的，但具有動(dòng)態(tài)擴(kuò)展和收縮的能力。與普通數(shù)組相比，ArrayList具有以下區(qū)別和優(yōu)勢(shì)：

• 大小動(dòng)態(tài)性：ArrayList的大小是動(dòng)態(tài)的，可以根據(jù)需要?jiǎng)討B(tài)擴(kuò)展和收縮。而普通數(shù)組的大小是固定的，一旦創(chuàng)建就無(wú)法改變。
• 自動(dòng)擴(kuò)展：當(dāng)ArrayList中的元素?cái)?shù)量超過(guò)當(dāng)前容量時(shí)，ArrayList會(huì)自動(dòng)進(jìn)行擴(kuò)展，而普通數(shù)組需要手動(dòng)重新分配內(nèi)存并復(fù)制數(shù)據(jù)。
• 插入和刪除元素效率高：ArrayList支持在任意位置插入和刪除元素，而普通數(shù)組在插入和刪除元素時(shí)需要移動(dòng)其他元素。
• 內(nèi)置方法和功能：ArrayList提供了許多便捷的方法和功能，如添加、刪除、查找等操作，使其更易于使用和操作。

總的來(lái)說(shuō)，ArrayList相對(duì)于普通數(shù)組來(lái)說(shuō)更加靈活、便捷，并且具有更高的操作效率。因此，在大多數(shù)情況下，使用ArrayList比使用普通數(shù)組更加方便和實(shí)用。

二、 內(nèi)部實(shí)現(xiàn)

2.1 數(shù)據(jù)結(jié)構(gòu)：動(dòng)態(tài)數(shù)組

在Java中，ArrayList是一個(gè)動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的類，它是基于數(shù)組實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組，可以自動(dòng)擴(kuò)容。下面是ArrayList的動(dòng)態(tài)數(shù)組原理：

• 內(nèi)部數(shù)組：ArrayList內(nèi)部使用一個(gè)數(shù)組來(lái)存儲(chǔ)元素。當(dāng)創(chuàng)建一個(gè)ArrayList時(shí)，會(huì)初始化一個(gè)初始容量的數(shù)組。
• 自動(dòng)擴(kuò)容：當(dāng)向ArrayList中添加元素時(shí)，如果當(dāng)前數(shù)組已滿，ArrayList會(huì)創(chuàng)建一個(gè)新的更大容量的數(shù)組，并將原數(shù)組中的元素復(fù)制到新數(shù)組中，然后將新元素添加到新數(shù)組中。
• 擴(kuò)容策略：ArrayList的擴(kuò)容策略是在每次擴(kuò)容時(shí)將當(dāng)前容量擴(kuò)大為原來(lái)的1.5倍，這種策略既能夠保證空間利用率，又能夠減少因頻繁擴(kuò)容而帶來(lái)的性能開(kāi)銷。
• 隨機(jī)訪問(wèn)：由于ArrayList內(nèi)部基于數(shù)組實(shí)現(xiàn)，因此支持隨機(jī)訪問(wèn)，可以通過(guò)索引直接訪問(wèn)數(shù)組中的元素，時(shí)間復(fù)雜度為O(1)。

總的來(lái)說(shuō)，ArrayList通過(guò)動(dòng)態(tài)擴(kuò)容的方式，利用數(shù)組實(shí)現(xiàn)了一個(gè)動(dòng)態(tài)數(shù)組，提供了高效的隨機(jī)訪問(wèn)和動(dòng)態(tài)增刪元素的功能。

2.2 添加元素：add()方法的實(shí)現(xiàn)原理

在Java中，ArrayList的add()方法用于向ArrayList中添加元素。

其實(shí)現(xiàn)原理如下：

• 在調(diào)用add()方法時(shí)，先檢查當(dāng)前ArrayList的大小和容量（即存儲(chǔ)空間是否足夠）。
• 如果當(dāng)前容量不夠，就進(jìn)行擴(kuò)容操作。一般情況下，會(huì)創(chuàng)建一個(gè)新的數(shù)組，將原數(shù)組中的元素復(fù)制到新數(shù)組中，并且為新數(shù)組分配更大的存儲(chǔ)空間。
• 然后將要添加的元素放入ArrayList的內(nèi)部數(shù)組中，并更新ArrayList的大小。
• 如果添加成功，則返回true，如果添加失敗，則返回false。

總的來(lái)說(shuō)，ArrayList的add()方法實(shí)現(xiàn)原理就是對(duì)內(nèi)部數(shù)組的擴(kuò)容和元素的添加操作。

2.3 擴(kuò)容機(jī)制：ensureCapacity()方法的實(shí)現(xiàn)原理

在使用ArrayList時(shí)，如果我們預(yù)先知道將要插入的元素?cái)?shù)量，可以使用ensureCapacity()方法來(lái)預(yù)先分配內(nèi)部數(shù)組大小。調(diào)用了一個(gè)名為ensureCapacityInternal()的私有方法。這個(gè)方法首先會(huì)判斷當(dāng)前內(nèi)部數(shù)組是否已經(jīng)足夠大來(lái)容納新增的元素，如果不夠大，則會(huì)進(jìn)行擴(kuò)容：

• 如果當(dāng)前內(nèi)部數(shù)組為空，則直接擴(kuò)容到指定容量大小。
• 否則，計(jì)算出新數(shù)組的容量大小，這個(gè)容量大小取決于原始數(shù)組的大小和擴(kuò)容因子（默認(rèn)為1.5倍）。
• 如果新數(shù)組容量大小小于所需容量，則按照所需容量分配新的數(shù)組；否則，按照新數(shù)組容量大小分配新的數(shù)組。
• 將原始數(shù)組中的元素復(fù)制到新數(shù)組中，并將新數(shù)組賦值給ArrayList對(duì)象的elementData變量。

import java.util.ArrayList;
public class EnsureCapacityExample {
    public static void main(String[] args) {
        // 創(chuàng)建一個(gè)空的ArrayList
        ArrayList<String> list = new ArrayList<>();
        // 預(yù)先設(shè)定ArrayList內(nèi)部數(shù)組的容量為20
        list.ensureCapacity(20);
        // 現(xiàn)在，ArrayList的內(nèi)部數(shù)組至少可以容納20個(gè)元素
        // 添加元素到ArrayList
        list.add("Element 1");
        list.add("Element 2");
        list.add("Element 3");
        // ...
    }
}

通過(guò)使用ensureCapacity()方法，我們可以避免由于頻繁擴(kuò)容帶來(lái)的性能損失，提高程序效率。

三、 常見(jiàn)操作分析

3.1 獲取元素：get()方法的實(shí)現(xiàn)原理

在Java中，ArrayList的get()方法實(shí)際上是通過(guò)調(diào)用數(shù)組的索引來(lái)獲取指定位置的元素。ArrayList內(nèi)部維護(hù)了一個(gè)Object類型的數(shù)組來(lái)存儲(chǔ)元素。

• 當(dāng)調(diào)用get()方法時(shí)，ArrayList會(huì)將傳入的索引作為數(shù)組的下標(biāo)，直接訪問(wèn)數(shù)組中對(duì)應(yīng)位置的元素，并返回該元素。
• 因?yàn)閿?shù)組的訪問(wèn)是基于內(nèi)存地址的，所以獲取元素的時(shí)間復(fù)雜度為O(1)，即常數(shù)時(shí)間復(fù)雜度。
• ArrayList的get()方法并不會(huì)對(duì)數(shù)組進(jìn)行拷貝或重新分配空間，因此在獲取元素時(shí)是非常高效的。
• 頻繁進(jìn)行插入、刪除等涉及數(shù)組擴(kuò)容的操作，可能會(huì)導(dǎo)致性能下降。

ArrayList的get()方法通過(guò)直接訪問(wèn)底層數(shù)組的方式快速獲取指定位置的元素。

3.2 刪除元素：remove()方法的實(shí)現(xiàn)原理

Java中的ArrayList類是基于數(shù)組實(shí)現(xiàn)的動(dòng)態(tài)數(shù)組，當(dāng)我們使用remove()方法從ArrayList中刪除元素時(shí)，這個(gè)方法會(huì)將指定位置的元素從內(nèi)部數(shù)組中移除，并將后續(xù)元素向前移動(dòng)一位。

這個(gè)操作可以通過(guò)以下幾個(gè)步驟來(lái)實(shí)現(xiàn)：

• 檢查待刪除的元素下標(biāo)是否越界，如果越界則拋出IndexOutOfBoundsException異常。
• 將要?jiǎng)h除的元素從內(nèi)部數(shù)組中移除，這個(gè)過(guò)程可以通過(guò)System.arraycopy()方法來(lái)實(shí)現(xiàn)，該方法可以將數(shù)組的某一范圍內(nèi)的元素復(fù)制到另一個(gè)位置上。
• 將后續(xù)元素向前移動(dòng)一位，以填補(bǔ)被刪除的空位。這個(gè)過(guò)程同樣可以通過(guò)System.arraycopy()方法來(lái)實(shí)現(xiàn)。

ps：ArrayList的remove()方法只能移除第一個(gè)與指定元素相等的元素。如果我們想要移除所有等于指定元素的元素，可以通過(guò)循環(huán)遍歷ArrayList并使用remove()方法來(lái)實(shí)現(xiàn)。

3.3 修改元素：set()方法的實(shí)現(xiàn)原理

Java中的ArrayList是一種基于數(shù)組的動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，它繼承了AbstractList類并實(shí)現(xiàn)了List接口。set()方法是ArrayList中的一個(gè)方法，用于將指定索引位置的元素替換為新的元素。

其實(shí)現(xiàn)原理如下：

• 首先，set()方法會(huì)檢查傳遞的索引是否在ArrayList范圍之內(nèi)。如果索引小于0或大于等于ArrayList的大小（size()方法返回的值），則會(huì)拋出IndexOutOfBoundsException異常。
• 如果索引有效，則會(huì)使用數(shù)組的索引定位到指定的元素，并將其替換為新的元素。
• set()方法返回被替換掉的元素。
• 在替換元素時(shí)，ArrayList可能需要調(diào)整內(nèi)部數(shù)組的大小。如果新元素的大小與當(dāng)前數(shù)組的容量不匹配，ArrayList會(huì)創(chuàng)建一個(gè)新數(shù)組，并將所有元素從舊數(shù)組復(fù)制到新數(shù)組中。

總之，ArrayList的set()方法的實(shí)現(xiàn)原理是通過(guò)數(shù)組索引定位和替換元素來(lái)完成的，而且可能需要?jiǎng)討B(tài)調(diào)整內(nèi)部數(shù)組的大小。

四、 性能分析

4.1 時(shí)間復(fù)雜度分析

在Java中，ArrayList是一個(gè)動(dòng)態(tài)數(shù)組實(shí)現(xiàn)的集合類，它提供了隨機(jī)訪問(wèn)和快速插入/刪除元素的功能。

下面是ArrayList的常見(jiàn)操作及其時(shí)間復(fù)雜度分析：

• 訪問(wèn)元素（get）：通過(guò)索引訪問(wèn)特定位置的元素，時(shí)間復(fù)雜度為O(1)。
• 插入元素（add）：在指定位置插入元素，平均時(shí)間復(fù)雜度為O(n)，最壞情況下需要將插入位置之后的元素都向后移動(dòng)，時(shí)間復(fù)雜度為O(n)。
• 刪除元素（remove）：刪除指定位置的元素，平均時(shí)間復(fù)雜度為O(n)，最壞情況下需要將刪除位置之后的元素都向前移動(dòng)，時(shí)間復(fù)雜度為O(n)。
• 查找元素（contains）：判斷集合中是否包含某個(gè)元素，平均時(shí)間復(fù)雜度為O(n)，需要遍歷整個(gè)集合來(lái)查找。
• 獲取集合大?。╯ize）：獲取集合中元素的數(shù)量，時(shí)間復(fù)雜度為O(1)。

需要注意的是，ArrayList的插入和刪除操作涉及到元素的移動(dòng)，當(dāng)集合的大小較大時(shí)，這些操作可能會(huì)導(dǎo)致性能下降。如果需要頻繁進(jìn)行插入和刪除操作，可以考慮使用LinkedList來(lái)代替ArrayList，因?yàn)?code>LinkedList對(duì)于插入和刪除操作的時(shí)間復(fù)雜度是O(1)。

4.2 空間復(fù)雜度分析

ArrayList的空間復(fù)雜度主要取決于兩個(gè)因素：集合中的元素?cái)?shù)量和內(nèi)部數(shù)組的容量。

• 元素?cái)?shù)量：ArrayList存儲(chǔ)的元素?cái)?shù)量，即集合的大小，會(huì)占用一定的空間。假設(shè)元素?cái)?shù)量為n，則空間復(fù)雜度為O(n)。
• 內(nèi)部數(shù)組容量：ArrayList內(nèi)部使用一個(gè)動(dòng)態(tài)數(shù)組來(lái)存儲(chǔ)元素，數(shù)組的容量可能會(huì)比集合的大小大一些，以容納未來(lái)添加的元素。假設(shè)數(shù)組的容量為m，則空間復(fù)雜度為O(m)。

需要注意的是，ArrayList的實(shí)際空間占用可能會(huì)比集合中的元素?cái)?shù)量多一些，因?yàn)樗?strong>預(yù)留了一些額外的容量供后續(xù)添加元素使用。當(dāng)集合的元素?cái)?shù)量接近或超過(guò)內(nèi)部數(shù)組的容量時(shí)，ArrayList會(huì)自動(dòng)進(jìn)行擴(kuò)容操作，重新分配更大的數(shù)組并將原有元素復(fù)制到新數(shù)組中，這可能會(huì)導(dǎo)致空間復(fù)雜度的增加。

在實(shí)際使用中，可以通過(guò)調(diào)整ArrayList的初始容量或使用構(gòu)造函數(shù)指定初始容量來(lái)控制空間復(fù)雜度。通常情況下，如果能夠預(yù)估集合的大小，設(shè)置一個(gè)適當(dāng)?shù)某跏既萘靠梢詼p少擴(kuò)容操作的頻率，提高性能。

4.3 與LinkedList的比較

ArrayList和LinkedList是Java中兩種常見(jiàn)的集合類，它們都實(shí)現(xiàn)了List接口，但在內(nèi)部實(shí)現(xiàn)和性能特點(diǎn)上有所不同。

下面是ArrayList和LinkedList的比較：

• 內(nèi)部實(shí)現(xiàn)：
• ArrayList：使用動(dòng)態(tài)數(shù)組實(shí)現(xiàn)，內(nèi)部維護(hù)一個(gè)可變長(zhǎng)度的數(shù)組來(lái)存儲(chǔ)元素。
• LinkedList：使用雙向鏈表實(shí)現(xiàn)，內(nèi)部由一系列節(jié)點(diǎn)組成，每個(gè)節(jié)點(diǎn)包含元素值和前后指針。
• 訪問(wèn)效率：
• ArrayList：由于使用數(shù)組實(shí)現(xiàn)，可以通過(guò)索引直接訪問(wèn)元素，因此隨機(jī)訪問(wèn)的效率很高，時(shí)間復(fù)雜度為O(1)。但在插入和刪除元素時(shí)，需要移動(dòng)數(shù)組中的元素，效率較低，時(shí)間復(fù)雜度為O(n)。
• LinkedList：插入和刪除元素的效率較高，因?yàn)橹恍枰{(diào)整節(jié)點(diǎn)的指針，時(shí)間復(fù)雜度為O(1)。但在隨機(jī)訪問(wèn)元素時(shí)，需要從頭節(jié)點(diǎn)開(kāi)始按序遍歷查找，效率較低，時(shí)間復(fù)雜度為O(n)。
• 空間占用：
• ArrayList：使用動(dòng)態(tài)數(shù)組，會(huì)預(yù)留一定容量的空間，當(dāng)元素?cái)?shù)量超過(guò)容量時(shí)，需要進(jìn)行擴(kuò)容操作。因此，可能會(huì)有額外的空間浪費(fèi)。
• LinkedList：使用鏈表結(jié)構(gòu)，每個(gè)節(jié)點(diǎn)除了存儲(chǔ)元素還需要存儲(chǔ)前后節(jié)點(diǎn)的指針，因此會(huì)略微增加一些額外空間。
• 適用場(chǎng)景：
• ArrayList：適合于隨機(jī)訪問(wèn)和遍歷操作較多的場(chǎng)景，例如根據(jù)索引訪問(wèn)元素、遍歷集合等。但在頻繁插入和刪除元素的情況下，性能相對(duì)較差。
• LinkedList：適合于頻繁插入和刪除元素的場(chǎng)景，例如實(shí)現(xiàn)隊(duì)列或棧等數(shù)據(jù)結(jié)構(gòu)。但在隨機(jī)訪問(wèn)元素時(shí)，性能相對(duì)較差。

五、 源碼解讀

5.1 成員變量

5.2 構(gòu)造方法

5.3 trimToSize()方法

5.4 indexOf()方法

5.5 clone()方法

5.6 get()方法

5.7 set()方法

5.8 add()方法

5.9 remove()方法

5.10 addAll()方法

六、 案例分析與實(shí)例演示

6.1 案例分析

假設(shè)有一個(gè)學(xué)生管理系統(tǒng)，需要存儲(chǔ)學(xué)生的信息，包括姓名、年齡、性別等。

為了方便管理，我們可以使用ArrayList來(lái)存儲(chǔ)學(xué)生對(duì)象。

首先定義一個(gè)學(xué)生類，包含姓名、年齡、性別三個(gè)屬性：

public class Student {
    private String name;
    private int age;
    private String gender;
    public Student(String name, int age, String gender) {
        this.name = name;
        this.age = age;
        this.gender = gender;
    }
    // getter 和 setter 方法省略
}

然后在主類中創(chuàng)建ArrayList對(duì)象，并添加學(xué)生信息：

import java.util.ArrayList;
public class Main {
    public static void main(String[] args) {
        // 創(chuàng)建ArrayList對(duì)象
        ArrayList<Student> list = new ArrayList<>();
        // 添加學(xué)生信息
        list.add(new Student("張三", 18, "男"));
        list.add(new Student("李四", 20, "女"));
        list.add(new Student("王五", 19, "男"));
        // 遍歷學(xué)生信息
        for (Student student : list) {
            System.out.println("姓名：" + student.getName() + " 年齡：" + student.getAge() + " 性別：" + student.getGender());
        }
    }
}

輸出結(jié)果如下：

姓名：張三 年齡：18 性別：男
姓名：李四 年齡：20 性別：女
姓名：王五 年齡：19 性別：男

6.2 實(shí)例演示

演示一下如何使用ArrayList實(shí)現(xiàn)一個(gè)簡(jiǎn)單的購(gòu)物車程序。

首先定義一個(gè)商品類，包含名稱和價(jià)格兩個(gè)屬性：

public class Product {
    private String name;
    private double price;
    public Product(String name, double price) {
        this.name = name;
        this.price = price;
    }
    // getter 和 setter 方法省略
}

然后在主類中創(chuàng)建ArrayList對(duì)象，并添加商品信息：

import java.util.ArrayList;
import java.util.Scanner;
public class ShoppingCart {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        // 創(chuàng)建ArrayList對(duì)象
        ArrayList<Product> cart = new ArrayList<>();
        // 添加商品信息
        cart.add(new Product("可樂(lè)", 3.5));
        cart.add(new Product("薯片", 5.0));
        cart.add(new Product("巧克力", 8.0));
        // 輸出商品信息
        System.out.println("歡迎來(lái)到購(gòu)物車！");
        for (Product product : cart) {
            System.out.println(product.getName() + " 價(jià)格：" + product.getPrice());
        }
        // 計(jì)算總價(jià)
        double totalPrice = 0;
        while (true) {
            System.out.print("請(qǐng)輸入要購(gòu)買的商品編號(hào)（輸入-1結(jié)束）：");
            int index = scanner.nextInt();
            if (index == -1) {
                break;
            }
            Product product = cart.get(index);
            System.out.println("已選擇 " + product.getName() + " 價(jià)格：" + product.getPrice());
            totalPrice += product.getPrice();
        }
        System.out.println("總價(jià)：" + totalPrice);
    }
}

運(yùn)行程序，輸出結(jié)果如下：

歡迎來(lái)到購(gòu)物車！
可樂(lè) 價(jià)格：3.5
薯片 價(jià)格：5.0
巧克力 價(jià)格：8.0
請(qǐng)輸入要購(gòu)買的商品編號(hào)（輸入-1結(jié)束）：0
已選擇 可樂(lè) 價(jià)格：3.5
請(qǐng)輸入要購(gòu)買的商品編號(hào)（輸入-1結(jié)束）：1
已選擇 薯片 價(jià)格：5.0
請(qǐng)輸入要購(gòu)買的商品編號(hào)（輸入-1結(jié)束）：2
已選擇 巧克力 價(jià)格：8.0
請(qǐng)輸入要購(gòu)買的商品編號(hào)（輸入-1結(jié)束）：-1
總價(jià)：16.5

到此這篇關(guān)于探秘Java動(dòng)態(tài)數(shù)組的機(jī)制與性能的文章就介紹到這了,更多相關(guān)Java動(dòng)態(tài)數(shù)組內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論