數(shù)組

Yuqi 發(fā)布于2019-08-19 11:35 / 2332人閱讀

摘要：二數(shù)組擴(kuò)容及拷貝數(shù)組的擴(kuò)容數(shù)組是根據(jù)固定容量創(chuàng)建的，在必要的時(shí)候我們需要對(duì)數(shù)組進(jìn)行擴(kuò)容初始長度為下面決定需要對(duì)數(shù)組進(jìn)行擴(kuò)容對(duì)原數(shù)組進(jìn)行內(nèi)容拷貝在對(duì)數(shù)組進(jìn)行拷貝時(shí)除了利用循環(huán)遍歷數(shù)組元素進(jìn)行拷貝外，推薦使用更高效的方法。

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

一、認(rèn)識(shí)數(shù)組

數(shù)組是一種線性表數(shù)據(jù)結(jié)構(gòu)。它用一塊連續(xù)的內(nèi)存空間，來存儲(chǔ)相同類型的一組數(shù)據(jù)。

1. 概念的理解 線性表:

顧名思義，線性表就是數(shù)據(jù)排列成像一條線一樣的結(jié)構(gòu)。每個(gè)線性表上的數(shù)據(jù)最多只有前和后兩個(gè)方向，數(shù)組，鏈表，棧，隊(duì)列等都是典型的線性表結(jié)構(gòu)。

與其相對(duì)立的，在非線性表中，數(shù)據(jù)之間并不是簡單的前后關(guān)系，像樹，堆，圖等都是典型的非線性表。

連續(xù)的內(nèi)存空間和相同類型的數(shù)據(jù)：

即計(jì)算機(jī)分配連續(xù)的內(nèi)存單元來存儲(chǔ)數(shù)據(jù)，相同類型的數(shù)據(jù)即每個(gè)內(nèi)存單元的大小是相同的。

如聲明一個(gè)長度為 5 的 int 類型的數(shù)組 int[] arr = new int[5] ，計(jì)算機(jī)給數(shù)組分配了一塊連續(xù)的內(nèi)存空間，其中內(nèi)存塊的首地址為 base_address = 0xc0000160e0，每個(gè)內(nèi)存單元占 4 個(gè)字節(jié)：

2. 高效的隨機(jī)訪問

數(shù)組的一個(gè)特點(diǎn)是可以根據(jù)下標(biāo)隨機(jī)訪問數(shù)組元素，其時(shí)間復(fù)雜度為 O(1)，那么它是如何實(shí)現(xiàn)的呢？

計(jì)算機(jī)分配的內(nèi)存單元存儲(chǔ)數(shù)據(jù)時(shí)，也會(huì)為內(nèi)存單元分配一個(gè)地址，然后可以通過地址來訪問內(nèi)存中的數(shù)據(jù)。由數(shù)組的內(nèi)存空間連續(xù)的特性，當(dāng)需要訪問某個(gè)元素時(shí)，它會(huì)通過下面的尋址公式來計(jì)算出該元素存儲(chǔ)的內(nèi)存地址：

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

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

其中 data_type_size 表示數(shù)組中每個(gè)元素的大小，如在 int 型的數(shù)組 arr 中，data_type_size 就為 4 個(gè)字節(jié)。

這樣，便可以很快的根據(jù)內(nèi)存地址來讀取數(shù)據(jù)。

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

在數(shù)組中，為了保持內(nèi)存數(shù)據(jù)的連續(xù)性，會(huì)導(dǎo)致插入、刪除這兩個(gè)操作比較低效。

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

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

插入和刪除操作的優(yōu)化

然而在很多我們不需要考慮數(shù)組中元素的有序性，數(shù)組只被當(dāng)作一個(gè)存儲(chǔ)數(shù)據(jù)的集合的時(shí)候，為了避免大規(guī)模的數(shù)據(jù)搬移，我們可以對(duì)插入和刪除操作做一些優(yōu)化。例如：

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

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

這樣，其時(shí)間復(fù)雜度就會(huì)降為 O(1) 。

4. 容器與數(shù)組的比較

對(duì)于數(shù)組類型，Java 中的 ArrayList 容器是基于數(shù)組實(shí)現(xiàn)的，那么二者相比各有什么優(yōu)點(diǎn)和適用場(chǎng)景呢？

ArrayList 的優(yōu)勢(shì)是方便，適合在一般的業(yè)務(wù)中使用。它將很多數(shù)組的操作細(xì)節(jié)封裝起來了，如數(shù)據(jù)的插入、刪除、數(shù)組的擴(kuò)容。ArrayList 無法存儲(chǔ)基本類型，比如 int、double，需要封裝為 Integer、Double 類，而自動(dòng)裝箱/拆箱的操作會(huì)有一定的性能消耗；

相對(duì)于容器來說，數(shù)組的使用雖然麻煩一點(diǎn)，但它的性能會(huì)優(yōu)于容器，更適合用于底層的開發(fā)和追求極致性能的優(yōu)化。

二、數(shù)組擴(kuò)容及拷貝 1. 數(shù)組的擴(kuò)容

數(shù)組是根據(jù)固定容量創(chuàng)建的，在必要的時(shí)候我們需要對(duì)數(shù)組 arr 進(jìn)行擴(kuò)容：

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

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

arr = newArr;

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

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

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

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

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

參數(shù)說明：

src：要被復(fù)制的數(shù)組，

srcPos：被復(fù)制的數(shù)組開始復(fù)制的下標(biāo)，

dest：目標(biāo)數(shù)組，也就是要把數(shù)據(jù)放進(jìn)來的數(shù)組，

destPos：從目標(biāo)數(shù)組第幾個(gè)下標(biāo)開始放入數(shù)據(jù)，

length：被復(fù)制的數(shù)組中拿幾個(gè)數(shù)值放到目標(biāo)數(shù)組中；

例，數(shù)組 arr 進(jìn)行擴(kuò)容：

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

絕大部分?jǐn)?shù)組和基于數(shù)組實(shí)現(xiàn)的容器（ArrayList 等）的擴(kuò)容都是基于 System.arraycopy() 方法進(jìn)行操作的。

歡迎您的點(diǎn)贊、收藏和評(píng)論！
（完）

云服務(wù)器 GPU云服務(wù)器 java數(shù)組數(shù)組相加多維數(shù)組轉(zhuǎn)一維數(shù)組數(shù)組java二維數(shù)組二維數(shù)組轉(zhuǎn)換一維數(shù)組

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/77472.html

發(fā)表評(píng)論

登陸后可評(píng)論

0條評(píng)論

Yuqi

男|高級(jí)講師

我要關(guān)注我要私信

TA的文章

tensorflow

閱讀 3530·2023-04-25 18:52
數(shù)據(jù)庫轉(zhuǎn)換

閱讀 2551·2021-11-22 15:31
Facebook 正計(jì)劃用新名稱重新命名公司

閱讀 1300·2021-10-22 09:54
騰訊云：免費(fèi)升級(jí)配置活動(dòng)，1核2G6M免費(fèi)升配2核4G6M，需要邀請(qǐng)5人助力

閱讀 3077·2021-09-29 09:42
軟件測(cè)試工程師要掌握的Linux系統(tǒng)命令-很全，但不是最全！

閱讀 661·2021-09-26 09:55
字節(jié)跳動(dòng)開源微服務(wù)中間件CloudWeGo

閱讀 991·2021-09-13 10:28
開發(fā)中遇到的問題總結(jié)

閱讀 1180·2019-08-30 15:56
我的一些開源項(xiàng)目（前端）

閱讀 2166·2019-08-30 15:55

亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

數(shù)組

相關(guān)文章

C語言進(jìn)階：指針的進(jìn)階

犀牛書——CHAP7：數(shù)組

**JS基礎(chǔ)06「數(shù)組」**

JavaScript數(shù)組

java知識(shí)體系梳理-->數(shù)組

《javascript高級(jí)程序設(shè)計(jì)》筆記_數(shù)組稀疏數(shù)組偽數(shù)組

發(fā)表評(píng)論

0條評(píng)論

Yuqi

男|高級(jí)講師

TA的文章

tensorflow

數(shù)據(jù)庫轉(zhuǎn)換

Facebook 正計(jì)劃用新名稱重新命名公司

騰訊云：免費(fèi)升級(jí)配置活動(dòng)，1核2G6M免費(fèi)升配2核4G6M，需要邀請(qǐng)5人助力

軟件測(cè)試工程師要掌握的Linux系統(tǒng)命令-很全，但不是最全！

字節(jié)跳動(dòng)開源微服務(wù)中間件CloudWeGo

開發(fā)中遇到的問題總結(jié)

我的一些開源項(xiàng)目（前端）

最新活動(dòng)

資訊專欄INFORMATION COLUMN

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！

數(shù)組

相關(guān)文章

發(fā)表評(píng)論

0條評(píng)論

男|高級(jí)講師

TA的文章

最新活動(dòng)

上云采購季！| 2核2G4M爆款云服務(wù)器低至59元/年，更有多臺(tái)、長期優(yōu)惠，快來選購！