数组

一、定义

在计算机科学中，数组是由一组元素（值或变量）组成的数据结构，每个元素有至少一个索引或键来标识

因为数组内的元素是连续存储的，所以数组中元素的地址，可以通过其索引计算出来，例如：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
• 外层数组大小：16字节对象头 + 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 会帮我们调用