數組

Yuqi 發布于2019-08-19 11:35 / 2286人閱讀

摘要：二數組擴容及拷貝數組的擴容數組是根據固定容量創建的，在必要的時候我們需要對數組進行擴容初始長度為下面決定需要對數組進行擴容對原數組進行內容拷貝在對數組進行拷貝時除了利用循環遍歷數組元素進行拷貝外，推薦使用更高效的方法。

PS：如果覺得文章有什么地方寫錯了，哪里寫得不好，或者有什么建議，歡迎指點。

一、認識數組

數組是一種線性表數據結構。它用一塊連續的內存空間，來存儲相同類型的一組數據。

1. 概念的理解 線性表:

顧名思義，線性表就是數據排列成像一條線一樣的結構。每個線性表上的數據最多只有前和后兩個方向，數組，鏈表，棧，隊列等都是典型的線性表結構。

與其相對立的，在非線性表中，數據之間并不是簡單的前后關系，像樹，堆，圖等都是典型的非線性表。

連續的內存空間和相同類型的數據：

即計算機分配連續的內存單元來存儲數據，相同類型的數據即每個內存單元的大小是相同的。

如聲明一個長度為 5 的 int 類型的數組 int[] arr = new int[5] ，計算機給數組分配了一塊連續的內存空間，其中內存塊的首地址為 base_address = 0xc0000160e0，每個內存單元占 4 個字節：

2. 高效的隨機訪問

數組的一個特點是可以根據下標隨機訪問數組元素，其時間復雜度為 O(1)，那么它是如何實現的呢？

計算機分配的內存單元存儲數據時，也會為內存單元分配一個地址，然后可以通過地址來訪問內存中的數據。由數組的內存空間連續的特性，當需要訪問某個元素時，它會通過下面的尋址公式來計算出該元素存儲的內存地址：

// 一維數組 arr[n]：
arr[i]_address = base_address + i * data_type_size

// 二維數組 arr[m][n]：
address = base_address + (i * n + j) * data_type_size

其中 data_type_size 表示數組中每個元素的大小，如在 int 型的數組 arr 中，data_type_size 就為 4 個字節。

這樣，便可以很快的根據內存地址來讀取數據。

3. 低效的“插入”和“刪除”

在數組中，為了保持內存數據的連續性，會導致插入、刪除這兩個操作比較低效。

例如在 插入操作 中，假設數組的長度為 n，若我們要在數組的第 k 個位置插入一個數據，為了把第 k 個位置騰出來給新的數據，我們需要將第 k ~ n 這部分的元素都順序地向后挪一位： arr[i] = arr[i-1] 。其時間復雜度為 O(n)。

而在 刪除操作 中，若我們要刪除數組的第 k 個元素，為了內存的連續性，就需要將第 k ~ n 這部分的元素都順序地向前挪一位： arr[i] = arr[i+1] 。其時間復雜度為 O(n)。

插入和刪除操作的優化

然而在很多我們不需要考慮數組中元素的有序性，數組只被當作一個存儲數據的集合的時候，為了避免大規模的數據搬移，我們可以對插入和刪除操作做一些優化。例如：

如果要將某個數據插入到第 k 個位置，可以直接將第 k 為的數據搬移到數組元素的末尾，然后將新的元素值直接賦值給第 k 個元素；

如果要將第 k 個元素刪除，可以直接將數組的最后一個元素賦值給第 k 個元素，然后刪除最后一個元素即可。

這樣，其時間復雜度就會降為 O(1) 。

4. 容器與數組的比較

對于數組類型，Java 中的 ArrayList 容器是基于數組實現的，那么二者相比各有什么優點和適用場景呢？

ArrayList 的優勢是方便，適合在一般的業務中使用。它將很多數組的操作細節封裝起來了，如數據的插入、刪除、數組的擴容。ArrayList 無法存儲基本類型，比如 int、double，需要封裝為 Integer、Double 類，而自動裝箱/拆箱的操作會有一定的性能消耗；

相對于容器來說，數組的使用雖然麻煩一點，但它的性能會優于容器，更適合用于底層的開發和追求極致性能的優化。

二、數組擴容及拷貝 1. 數組的擴容

數組是根據固定容量創建的，在必要的時候我們需要對數組 arr 進行擴容：

// 初始長度為 10
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
    arr[i] = i+1;
}
...
// 下面決定需要對數組 arr 進行擴容
int[] newArr = new int[arr.length*2];

// 對原數組進行內容拷貝
for (int i = 0; i < arr.length; i++) {
    newArr[i] = arr[i];
}

arr = newArr;

在對數組進行拷貝時除了利用 for 循環遍歷數組元素進行拷貝外，推薦使用更高效的 System.arraycopy() 方法。

2. System.arraycopy() 方法拷貝數組

System.arraycopy() 使用 native 關鍵字修飾，大大加快程序性能，為 JVM 內部固有方法。它通過手工編寫匯編或其他優化方法來進行 Java 數組拷貝，這種方式比起直接在 Java 上進行 for 循環或 clone 是更加高效的。數組越大體現地越明顯。

該方法用于從指定源數組中進行拷貝操作，可以指定開始位置，拷貝指定長度的元素到指定目標數組中。其聲明如下：

public static native void arraycopy(Object src,  int srcPos, Object dest, int destPos, int length);

參數說明：

src：要被復制的數組，

srcPos：被復制的數組開始復制的下標，

dest：目標數組，也就是要把數據放進來的數組，

destPos：從目標數組第幾個下標開始放入數據，

length：被復制的數組中拿幾個數值放到目標數組中；

例，數組 arr 進行擴容：

// 初始長度為 10
int[] arr = new int[10];
for (int i = 0; i < arr.length; i++) {
    arr[i] = i+1;
}
...
// 下面決定需要對數組 arr 進行擴容
int[] newArr = new int[arr.length*2];
System.arraycopy(arr,0,newArr,0,10); // 對原數組進行內容拷貝
arr = newArr;

絕大部分數組和基于數組實現的容器（ArrayList 等）的擴容都是基于 System.arraycopy() 方法進行操作的。

歡迎您的點贊、收藏和評論！
（完）

云服務器 GPU云服務器 java數組數組相加多維數組轉一維數組數組java二維數組二維數組轉換一維數組

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://specialneedsforspecialkids.com/yun/77472.html

C語言進階：指針的進階

摘要：本章節在此基礎上，對語言階段指針進行更深層次的研究。數組指針的類型由數組類型決定，先找出數組的類型去掉名就是類型。相當于數組指針所指向數組的數組名。數組指針指向整個數組，將其看作二維數組并解引用得到一行的首元素，從而遍歷訪問。 ...

浠ラ箍 2021-09-02 15:15 評論0 收藏0
犀牛書——CHAP7：數組

摘要：數組有以下特點無類型數組元素可以是任意元素。因此，當小于數組最大索引時，大于的數組元素會被刪除。原數組不會改變將數組元素轉換為字符串并連接在一起。默認將數組元素用，連接，傳入的參數即為連接符。 showImg(https://box.worktile.com/view/fcfcdf2c99b14edfb6768085955ae253?pid=4b0845b09ca94218a955f8...

Alfred 2019-08-19 18:40 評論0 收藏0
JS基礎06「數組」

摘要：為了維持此規則不變化，數組有兩個特殊的行為。運算符對數組返回并且對于除了函數以外的所有對象都是如此。解決方案是檢查對象的類屬性，對數組而言該屬數組數組是值的有序集合。每個值叫做一個元素，而每個元素在數組中有一個位置，以數字表示，稱為索引。 JavaScript 數組是無類型的，數組元素可以是任意類型，并且同一個數組中的不同元素也可能有不同的類型。數組的元素甚至也可能是對象或其他數組...

forrest23 2019-08-26 10:58 評論0 收藏0
JavaScript數組

摘要：與稀疏數組對立的為密集數組，密集數組的索引會被持續的創建，并且其元素的數量等于其長度。創建一個長度為的數組，并初始化了個元素使用構造函數創建數組對象的時候，關鍵字是可以省略的。另外使用和刪除元素是影響數組的長度的。說明：本文只總結了JavaScript數組在web端的行為，不包括NodeJs端的行為。本文不涉及類型化數組（TypedArray）的討論、總結。一、什么是數組數組的定...

HtmlCssJs 2019-08-23 10:23 評論0 收藏0
java知識體系梳理-->數組

摘要：知識體系梳理流程圖一維數組數組概述數組是指一組數據的集合，數組中的每個數據被稱作元素。定義打印數組元素方法按照給定的格式打印題目分析通過觀察發現，要實現按照指定格式，打印數組元素操作。按照這種方式，數組循環多圈以后，就完成了數組元素的排序。知識體系梳理流程圖 showImg(https://segmentfault.com/img/bVXwAi?w=902&h=652); 一維數組 ...

james 2019-08-15 12:23 評論0 收藏0
《javascript高級程序設計》筆記_數組稀疏數組偽數組

摘要：數組是數據的有序列表，與其他語言不同的是，數組的每一項可以保存任何類型的數據。如下的代碼創建的就是一個密集數組稀疏數組與密集數組相反，并不強制要求數組元素是緊密相連的，即允許間隙的存在。數組是數據的有序列表，與其他語言不同的是，ECMAScript 數組的每一項可以保存任何類型的數據。也就是說，可以用數組的第一個位置來保存字符串，用第二位置來保存數值，用第三個位置來保存對象，以此類...

pepperwang 2019-08-21 11:56 評論0 收藏0