一、定义
在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识
因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来，例如：int[] array = {1,2,3,4,5}
知道了数组的数据起始地址 ，就可以由公式
计算出索引
元素的地址
-
即索引，在 Java、C 等语言都是从 0 开始
-
是每个元素占用字节，例如
占
，
占
二、空间占用
Java 中数组结构为
- 8 字节 markword
- 4 字节 class 指针（压缩 class 指针的情况）
- 4 字节 数组大?。ň龆耸樽畲笕萘渴?
）
- 数组元素 + 对齐字节（java 中所有对象大小都是 8 字节的整数倍[^12]，不足的要用对齐字节补足）
int[] array = {1, 2, 3, 4, 5};的大小为 40 个字节，组成如下
image.png
8 + 4 + 4 + 5*4 + 4(alignment)
数组随机访问性能：即根据索引查找元素，时间复杂度是
三、动态数组
动态数组的增删改查
package com.hcx.algorithm.arr;
import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;
/**
* @Title: DynamicArray.java
* @Package com.hcx.algorithm.arr
* @Description: 动态数组
* @Author: hongcaixia
* @Date: 2024/12/26 17:02
* @Version V1.0
*/
public class DynamicArray implements Iterable<Integer>{
// 逻辑大小
private int size = 0;
// 容量
private int capacity = 8;
private int[] arr = {};
/**
* 往最后位置插入元素
* @param element
*/
public void addLast(int element) {
// arr[size] = element;
// size++;
addIndex(size, element);
}
/**
* 按照索引添加元素
* @param index
* @param element
*/
public void addIndex(int index, int element) {
//检查容量
checkAndGrow();
if(index>0 && index<size){
System.arraycopy(arr,index,arr,index+1,size-index);
}
arr[index]=element;
size++;
}
/**
* 检查容量并扩容
*/
private void checkAndGrow() {
//第一次添加 创建初始容量的数组
if (size == 0) {
arr = new int[capacity];
} else if (size == capacity) {
//扩容为原来的1.5倍
capacity += capacity >> 1;
int[] newArr = new int[capacity];
System.arraycopy(arr, 0, newArr, 0, size);
arr = newArr;
}
}
/**
* 根据索引移除元素
* @param index
* @return
*/
public int remove(int index) {
int removed = arr[index];
// 不是最后一个元素才需要移动
if (index < size - 1) {
System.arraycopy(arr, index + 1, arr, index, size - index - 1);
}
size--;
return removed;
}
/**
* 遍历数组
* @param consumer
*/
public void foreach(Consumer<Integer> consumer){
for (int i = 0; i < size; i++) {
consumer.accept(arr[i]);
}
}
/**
* 迭代器遍历
* @return
*/
@Override
public Iterator<Integer> iterator() {
return new Iterator<Integer>() {
int i = 0;
//有没有下一个元素
@Override
public boolean hasNext() {
return i < size;
}
//返回当前元素，指针移动到下一个元素
@Override
public Integer next() {
return arr[i++];
}
};
}
/**
* stream 遍历
* @return
*/
public IntStream stream() {
return IntStream.of(Arrays.copyOfRange(arr, 0, size));
}
}
插入或删除性能
头部位置，时间复杂度是
中间位置，时间复杂度是
尾部位置，时间复杂度是 （均摊来说）
四、二维数组
int[][] array = {
{11, 12, 13, 14, 15},
{21, 22, 23, 24, 25},
{31, 32, 33, 34, 35},
};
内存图.png
- 二维数组占 32 个字节，其中 array[0]，array[1]，array[2] 三个元素分别保存了指向三个一维数组的引用
- 三个一维数组各占 40 个字节
- 它们在内层布局上是连续的
对一个二维数组
-
是外层数组的长度，可以看作 row 行
-
是内层数组的长度，可以看作 column 列
- 当访问
，
时，就相当于
- 先找到第
- 再找到此内层数组中第
个元素（列）
- 先找到第
byte[][] array = {
{11, 12, 13, 14, 15},
{21, 22, 23, 24, 25},
{31, 32, 33, 34, 35},
};
已知 array 对象起始地址是 0x1000，那么 23 这个元素的地址:
- 起始地址 0x1000
- 外层数组大?。?6字节对象头 + 3元素 * 每个引用4字节 + 4 对齐字节 = 32 = 0x20
- 第一个内层数组大小：16字节对象头 + 5元素 * 每个byte1字节 + 3 对齐字节 = 24 = 0x18
- 第二个内层数组，16字节对象头 = 0x10，待查找元素索引为 2
- 最后结果 = 0x1000 + 0x20 + 0x18 + 0x10 + 2*1 = 0x104a
五、局部性原理
只讨论空间局部性
- cpu 读取内存（速度慢）数据后，会将其放入高速缓存（速度快）当中，如果后来的计算再用到此数据，在缓存中能读到的话，就不必读内存了
- 缓存的最小存储单位是缓存行（cache line），一般是 64 bytes，一次读的数据少了不划算，因此最少读 64 bytes 填满一个缓存行，因此读入某个数据时也会读取其临近的数据，这就是所谓空间局部性
对效率的影响
比较 ij 和 ji 两个方法的执行效率
public class TestCacheLine {
/**
* 二维数组遍历，先行后列
* @param a
* @param rows
* @param cols
*/
public static void ij(int[][] a, int rows, int cols) {
long sum = 0L;
for (int i = 0; i < rows; i++) {
for (int j = 0; j < cols; j++) {
sum += a[i][j];
}
}
System.out.println(sum);
}
/**
* 二维数组遍历，先列后行
* @param a
* @param rows
* @param cols
*/
public static void ji(int[][] a, int rows, int cols) {
long sum = 0L;
for (int j = 0; j < cols; j++) {
for (int i = 0; i < rows; i++) {
sum += a[i][j];
}
}
System.out.println(sum);
}
public static void main(String[] args) {
int rows = 1000000;
int cols = 15;
int[][] arr = new int[rows][cols];
StopWatch sw = new StopWatch();
sw.start();
ij(arr, rows, cols);
sw.stop();
System.out.println("=====ij: "+sw.getElapsedTimeInNanos()); //15531671
sw.start();
ji(arr, rows, cols);
sw.stop();
System.out.println("=====ji: "+sw.getElapsedTimeInNanos()); // 77156768
}
}
ij 的效率比 ji 快很多:
- 缓存是有限的，当新数据来了后，一些旧的缓存行数据就会被覆盖
- 如果不能充分利用缓存的数据，就会造成效率低下
以 ji 执行为例，第一次内循环要读入 这条数据，由于局部性原理，读入
的同时也读入了
，如图所示（但是这个数据对于ij的执行，是用上了的）
image.png
但很遗憾，第二次内循环要的是 这条数据，缓存中没有，于是再读入了下图的数据
image.png
因为 包括
这些数据虽然读入了缓存，却没有及时用上，而缓存的大小是有限的，等执行到第九次内循环时
image.png
缓存的第一行数据已经被新的数据 覆盖掉了，以后如果再想读，比如
，又得到内存去读了
同理可以分析 ij 函数则能充分利用局部性原理加载到的缓存数据
六、越界检查
java 中对数组元素的读写都有越界检查，类似于下面的代码
bool is_within_bounds(int index) const {
return 0 <= index && index < length();
}
此检查代码，不需要由程序员自己来调用，JVM 会帮我们调用
