概述

定義

在計算機科學中，數(shù)組是由一組元素（值或變量）組成的數(shù)據(jù)結構，每個元素有至少一個索引或鍵來標識

In computer science, an array is a data structure consisting of a collection of elements (values or variables), each identified by at least one array index or key

因為數(shù)組內的元素是連續(xù)存儲的，所以數(shù)組中元素的地址，可以通過其索引計算出來，例如：

int[] array = {1,2,3,4,5}

知道了數(shù)組的數(shù)據(jù)起始地址 $BaseAddress$，就可以由公式 $BaseAddress+i?size$ 計算出索引 $i$ 元素的地址

• $i$ 即索引，在 Java、C 等語言都是從 0 開始
• $size$ 是每個元素占用字節(jié)，例如 $int$ 占 $4$，$double$ 占 $8$

小測試

byte[] array = {1,2,3,4,5}

已知 array 的數(shù)據(jù)的起始地址是 0x7138f94c8，那么元素 3 的地址是什么？

答：0x7138f94c8 + 2 * 1 = 0x7138f94ca

空間占用

Java 中數(shù)組結構為

• 8 字節(jié) markword
• 4 字節(jié) class 指針（壓縮 class 指針的情況）
• 4 字節(jié) 數(shù)組大小（決定了數(shù)組最大容量是 $2^{32}$）
• 數(shù)組元素 + 對齊字節(jié)（java 中所有對象大小都是 8 字節(jié)的整數(shù)倍[^12]，不足的要用對齊字節(jié)補足）

例如

int[] array = {1, 2, 3, 4, 5};

的大小為 40 個字節(jié)，組成如下

8 + 4 + 4 + 5*4 + 4(alignment)

隨機訪問性能

即根據(jù)索引查找元素，時間復雜度是 $O(1)$

邏輯大小和物理大小

數(shù)組的物理大小是它的數(shù)組單元的總數(shù)，或者說是在創(chuàng)建數(shù)組的時候，用來指定其容量的數(shù)字。

數(shù)組的邏輯大小，是它當前已供應用程序使用的項的數(shù)目。

當數(shù)組總是滿的時候，不用擔心他倆的區(qū)別，但是這種情況很少。

通常，邏輯大小的物理大小會告訴我們數(shù)組狀態(tài)的幾件重要的事：

• 如果邏輯大小為0，數(shù)組為空，則說明該數(shù)組不包含數(shù)據(jù)項；
• 如果數(shù)組包含的數(shù)據(jù)項，數(shù)組最后一項的索引為邏輯大小減1；
• 如果邏輯大小等于物理大小，數(shù)組已經(jīng)被數(shù)據(jù)填滿。

動態(tài)數(shù)組

java 版本

import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;/*** @author Ethan* @date 2023/3/20* @description*/
public class Ds01DynamicArray implements Iterable<Integer> {/***  邏輯大小*/private int size = 0;/***  容量*/private int capacity = 8;/*** 初始化數(shù)組為空*/private int[] array = {};/*** 向任意位置添加元素** @param index   索引位置* @param element 待添加元素*/public void add(int index, int element) {// 檢查容量大小，不夠要擴容checkAndGrow();// 如果插入的位置效益邏輯大小，那么要先把位置騰出來，索引位置以后得元素都要后移一位if (index >= 0 && index < size) {// 向后挪動, 空出待插入位置，使用數(shù)組的copy方法// 從哪書分別是源數(shù)組、源數(shù)組起始位置、目標數(shù)組、目標數(shù)組的起始位置、copy元素個數(shù)System.arraycopy(array, index,array, index + 1, size - index);}// 在指定位置插入元素array[index] = element;// 邏輯大小+1size++;}/*** 向最后位置 [size] 添加元素** @param element 待添加元素*/public void addLast(int element) {// 復用任意位置添加元素，插入位置是邏輯大小add(size, element);}/*** 容量檢查，不夠進行擴容*/private void checkAndGrow() {// 容量檢查if (size == 0) {array = new int[capacity];} else if (size == capacity) {// 進行擴容, 1.5 1.618 2capacity += capacity >> 1;int[] newArray = new int[capacity];System.arraycopy(array, 0,newArray, 0, size);array = newArray;}}/*** 從 [0 .. size) 范圍刪除元素** @param index 索引位置* @return 被刪除元素*/public int remove(int index) { // [0..size)// 要刪除的元素int removed = array[index];// 如果要刪除的元素索引小于邏輯大小-1，那么把目標索引的后面元素都向前移動一位if (index < size - 1) {// 向前挪動System.arraycopy(array, index + 1,array, index, size - index - 1);}// 邏輯大小-1size--;return removed;}/*** 查詢元素** @param index 索引位置, 在 [0..size) 區(qū)間內* @return 該索引位置的元素*/public int get(int index) {return array[index];}/*** 遍歷方法1** @param consumer 遍歷要執(zhí)行的操作, 入?yún)? 每個元素*/public void foreach(Consumer<Integer> consumer) {// 使用Consumer把拿到的元素交給調用者來使用，具體使用方法取決于調用者for (int i = 0; i < size; i++) {// 提供 array[i]// 返回 voidconsumer.accept(array[i]);}}/*** 遍歷方法2 - 迭代器遍歷，這個類要實現(xiàn)Iterator接口*/@Overridepublic Iterator<Integer> iterator() {// 使用匿名內部類，直接返回一個迭代器，實現(xiàn)接口的兩個方法return new Iterator<Integer>() {int i = 0;@Overridepublic boolean hasNext() { // 有沒有下一個元素return i < size;}@Overridepublic Integer next() { // 返回當前元素,并移動到下一個元素return array[i++];}};}/*** 遍歷方法3 - stream 遍歷** @return stream 流*/public IntStream stream() {return IntStream.of(Arrays.copyOfRange(array, 0, size));}}

• 這些方法實現(xiàn)，都簡化了 index 的有效性判斷，假設輸入的 index 都是合法的

插入或刪除性能

**頭部位置：**因為要把頭部后面的元素都移動一位，所以時間復雜度是 $O(n)$；

**中間位置：**一樣要移動指定索引位置后的元素，所以時間復雜度是 $O(n)$

**尾部位置：**可直接通過索引找到最后一個元素，且不需要移動元素，所以時間復雜度是 $O(1)$（均攤來說）

二維數(shù)組

所謂的二維數(shù)組就是數(shù)組中的數(shù)組，數(shù)組嵌套數(shù)組。如下：

int[][] array = {{11, 12, 13, 14, 15},{21, 22, 23, 24, 25},{31, 32, 33, 34, 35},
};

內存圖如下

• 最上面的二維數(shù)組占 32 個字節(jié)，其中 array[0]，array[1]，array[2] 三個元素分別保存了指向三個一維數(shù)組的引用

• 三個一維數(shù)組各占 40 個字節(jié)

• 它們在內層布局上是連續(xù)的

更一般的，對一個二維數(shù)組 $Array[m][n]$

• $m$ 是外層數(shù)組的長度，可以看作 row 行
• $n$ 是內層數(shù)組的長度，可以看作 column 列
• 當訪問 $Array[i][j]$，$0\le i<m,0\le j<n$時，就相當于
  • 先找到第 $i$ 個內層數(shù)組（行）
  • 再找到此內層數(shù)組中第 $j$ 個元素（列）

小測試

Java 環(huán)境下（不考慮類指針和引用壓縮，此為默認情況），有下面的二維數(shù)組

byte[][] array = {{11, 12, 13, 14, 15},{21, 22, 23, 24, 25},{31, 32, 33, 34, 35},
};

已知 array 對象起始地址是 0x1000，那么 23 這個元素的地址是什么？

答：

• 起始地址 0x1000
• 外層數(shù)組大小：16字節(jié)對象頭 + 3元素 * 每個引用4字節(jié) + 4 對齊字節(jié) = 32 = 0x20
• 第一個內層數(shù)組大小：16字節(jié)對象頭 + 5元素 * 每個byte1字節(jié) + 3 對齊字節(jié) = 24 = 0x18
• 第二個內層數(shù)組，16字節(jié)對象頭 = 0x10，待查找元素索引為 2
• 最后結果 = 0x1000 + 0x20 + 0x18 + 0x10 + 2*1 = 0x104a

局部性原理

這里只討論空間局部性

• cpu 讀取內存（速度慢）數(shù)據(jù)后，會將其放入高速緩存（速度快）當中，如果后來的計算再用到此數(shù)據(jù)，在緩存中能讀到的話，就不必讀內存了
• 緩存的最小存儲單位是緩存行（cache line），一般是 64 bytes，一次讀的數(shù)據(jù)少了不劃算啊，因此最少讀 64 bytes 填滿一個緩存行，因此讀入某個數(shù)據(jù)時也會讀取其臨近的數(shù)據(jù)，這就是所謂空間局部性

對效率的影響

比較下面 ij 和 ji 兩個方法的執(zhí)行效率

int rows = 1000000;
int columns = 14;
int[][] a = new int[rows][columns];StopWatch sw = new StopWatch();
sw.start("ij");
ij(a, rows, columns);
sw.stop();
sw.start("ji");
ji(a, rows, columns);
sw.stop();
System.out.println(sw.prettyPrint());

ij 方法

public static void ij(int[][] a, int rows, int columns) {long sum = 0L;for (int i = 0; i < rows; i++) {for (int j = 0; j < columns; j++) {sum += a[i][j];}}System.out.println(sum);
}

ji 方法

public static void ji(int[][] a, int rows, int columns) {long sum = 0L;for (int j = 0; j < columns; j++) {for (int i = 0; i < rows; i++) {sum += a[i][j];}}System.out.println(sum);
}

執(zhí)行結果

0
0
StopWatch '': running time = 96283300 ns
---------------------------------------------
ns         %     Task name
---------------------------------------------
016196200  017%  ij
080087100  083%  ji

可以看到 ij 的效率比 ji 快很多，為什么呢？

• 緩存是有限的，當新數(shù)據(jù)來了后，一些舊的緩存行數(shù)據(jù)就會被覆蓋
• 如果不能充分利用緩存的數(shù)據(jù)，就會造成效率低下

以 ji 執(zhí)行為例，第一次內循環(huán)要讀入 $[0,0]$ 這條數(shù)據(jù)，由于局部性原理，讀入 $[0,0]$ 的同時也讀入了 $[0,1]...[0,13]$，如圖所示

但很遺憾，第二次內循環(huán)要的是 $[1,0]$ 這條數(shù)據(jù)，緩存中沒有，于是再讀入了下圖的數(shù)據(jù)

這顯然是一種浪費，因為 $[0,1]...[0,13]$ 包括 $[1,1]...[1,13]$ 這些數(shù)據(jù)雖然讀入了緩存，卻沒有及時用上，而緩存的大小是有限的，等執(zhí)行到第九次內循環(huán)時

緩存的第一行數(shù)據(jù)已經(jīng)被新的數(shù)據(jù) $[8,0]...[8,13]$ 覆蓋掉了，以后如果再想讀，比如 $[0,1]$，又得到內存去讀了

同理可以分析 ij 函數(shù)則能充分利用局部性原理加載到的緩存數(shù)據(jù)

舉一反三

1. I/O 讀寫時同樣可以體現(xiàn)局部性原理

2. 數(shù)組可以充分利用局部性原理，那么鏈表呢？

   答：鏈表不行，因為鏈表的元素并非相鄰存儲

越界檢查

java 中對數(shù)組元素的讀寫都有越界檢查，類似于下面的代碼

bool is_within_bounds(int index) const        
{ return 0 <= index && index < length(); 
}

• 代碼位置：openjdk\src\hotspot\share\oops\arrayOop.hpp

只不過此檢查代碼，不需要由程序員自己來調用，JVM 會幫我們調用