一、 簡介ArrayList

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

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

1.基本概念：

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

2,.作用：

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

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

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

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

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

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

二、 內部實現(xiàn)

2.1 數(shù)據(jù)結構：動態(tài)數(shù)組

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

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

總的來說，ArrayList通過動態(tài)擴容的方式，利用數(shù)組實現(xiàn)了一個動態(tài)數(shù)組，提供了高效的隨機訪問和動態(tài)增刪元素的功能。

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

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

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

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

總的來說，ArrayList的add()方法實現(xiàn)原理就是對內部數(shù)組的擴容和元素的添加操作。

2.3 擴容機制：ensureCapacity()方法的實現(xiàn)原理

在使用ArrayList時，如果我們預先知道將要插入的元素數(shù)量，可以使用ensureCapacity()方法來預先分配內部數(shù)組大小。調用了一個名為ensureCapacityInternal()的私有方法。這個方法首先會判斷當前內部數(shù)組是否已經足夠大來容納新增的元素，如果不夠大，則會進行擴容：

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

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

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

三、 常見操作分析

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

在Java中，ArrayList的get()方法實際上是通過調用數(shù)組的索引來獲取指定位置的元素。ArrayList內部維護了一個Object類型的數(shù)組來存儲元素。

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

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

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

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

這個操作可以通過以下幾個步驟來實現(xiàn)：

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

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

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

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

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

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

總之，ArrayList的set()方法的實現(xiàn)原理是通過數(shù)組索引定位和替換元素來完成的，而且可能需要動態(tài)調整內部數(shù)組的大小。

四、 性能分析

4.1 時間復雜度分析

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

下面是ArrayList的常見操作及其時間復雜度分析：

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

需要注意的是，ArrayList的插入和刪除操作涉及到元素的移動，當集合的大小較大時，這些操作可能會導致性能下降。如果需要頻繁進行插入和刪除操作，可以考慮使用LinkedList來代替ArrayList，因為LinkedList對于插入和刪除操作的時間復雜度是O(1)。

4.2 空間復雜度分析

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

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

需要注意的是，ArrayList的實際空間占用可能會比集合中的元素數(shù)量多一些，因為它預留了一些額外的容量供后續(xù)添加元素使用。當集合的元素數(shù)量接近或超過內部數(shù)組的容量時，ArrayList會自動進行擴容操作，重新分配更大的數(shù)組并將原有元素復制到新數(shù)組中，這可能會導致空間復雜度的增加。

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

4.3 與LinkedList的比較

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

下面是ArrayList和LinkedList的比較：

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

五、 源碼解讀

5.1 成員變量

5.2 構造方法

5.3 trimToSize()方法

5.4 indexOf()方法

5.5 clone()方法

5.6 get()方法

5.7 set()方法

5.8 add()方法

5.9 remove()方法

5.10 addAll()方法

六、 案例分析與實例演示

6.1 案例分析

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

為了方便管理，我們可以使用ArrayList來存儲學生對象。

首先定義一個學生類，包含姓名、年齡、性別三個屬性：

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對象，并添加學生信息：

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

輸出結果如下：

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

6.2 實例演示

演示一下如何使用ArrayList實現(xiàn)一個簡單的購物車程序。

首先定義一個商品類，包含名稱和價格兩個屬性：

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對象，并添加商品信息：

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對象
        ArrayList<Product> cart = new ArrayList<>();
        // 添加商品信息
        cart.add(new Product("可樂", 3.5));
        cart.add(new Product("薯片", 5.0));
        cart.add(new Product("巧克力", 8.0));
        // 輸出商品信息
        System.out.println("歡迎來到購物車！");
        for (Product product : cart) {
            System.out.println(product.getName() + " 價格：" + product.getPrice());
        }
        // 計算總價
        double totalPrice = 0;
        while (true) {
            System.out.print("請輸入要購買的商品編號（輸入-1結束）：");
            int index = scanner.nextInt();
            if (index == -1) {
                break;
            }
            Product product = cart.get(index);
            System.out.println("已選擇 " + product.getName() + " 價格：" + product.getPrice());
            totalPrice += product.getPrice();
        }
        System.out.println("總價：" + totalPrice);
    }
}

運行程序，輸出結果如下：

歡迎來到購物車！
可樂 價格：3.5
薯片 價格：5.0
巧克力 價格：8.0
請輸入要購買的商品編號（輸入-1結束）：0
已選擇 可樂 價格：3.5
請輸入要購買的商品編號（輸入-1結束）：1
已選擇 薯片 價格：5.0
請輸入要購買的商品編號（輸入-1結束）：2
已選擇 巧克力 價格：8.0
請輸入要購買的商品編號（輸入-1結束）：-1
總價：16.5

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

最新評論