2. 基础数据结构-数组

2. 基础数据结构-数组

2.1 概念

????????数组是一种数据结构，它是一个由相同类型元素组成的有序集合。在编程中，数组的定义是创建一个具有特定大小和类型的存储区域来存放多个值。数组可以是一维、二维或多维的。每个元素至少有一个索引或键来标识。

?2.2 数组特点

（1）固定大小：数组的大小在创建时就被确定下来，并且不能在后续操作中更改。这意味着一旦创建了数组，就不能添加或删除元素（除非使用新的数组来替换旧的数组）。
（2）相同数据类型：数组中的所有元素必须是同一数据类型的。例如，一个整数数组只能存储整数，而不能混杂着字符串或其他类型的数据。
（3）连续内存空间：数组中的元素在内存中是连续存放的。
（4）索引访问：数组元素是通过索引来访问的，索引通常从0开始。因此，第一个元素的索引是0，第二个元素的索引是1，以此类推。
（5）高效的随机访问：由于数组元素在内存中是连续存放的，所以可以快速地通过索引访问到任何一个元素，时间复杂度为O(1)。
（6）有序性：虽然数组本身并没有规定其元素必须按照特定顺序排列，但通常在编程中会把数组看作是有序的数据结构，因为它的元素是按索引顺序存储的。
（7）可变性：数组中元素值是可改变的，只要该元素的数据类型与数组元素类型兼容即可。
（8）一维、二维或多维：数组可以是一维的（即线性的），也可以是二维或多维的。多维数组通常用于表示表格数据或其他复杂的网格结构。

这些特性使得数组在许多场景下非常有用，尤其是在需要对大量同类型数据进行高效访问和处理的时候。

2.3 数组特点（扩展）

2.3.1 数组的存储

????????因为数组中的元素在内存中是连续存放的。这意味着可以通过计算每个元素相对于数组开始位置的偏移量来访问它们，从而提高访问速度。?数组起始地址为BaseAddress，可以使用公式BaseAddress+ i *size，计算出索引 i 元素的地址，i 即是索引，java和C等语言中，都是从0开始。size是每个元素占用的字节，例如int占用4字节，double占用8字节。

????????因此，数组的随机访问和数据规模无关，时间复杂度为O(1)。

2.3.2 空间占用

JAVA的数组结构包含：markword（8字节），class指针（4字节），数组大小（4字节）。

（1）数组本身是一个对象。每个Java对象都有一个对象头（Object Header），其中包含了类指针和Mark Word等信息。。Mark Word是HotSpot虚拟机设计的一种数据结构，用于存储对象的运行时元数据。

（2）Mark Word的作用主要包括：

? ? ? ? （2.1）对象的锁状态：Mark Word中的部分内容会根据对象是否被锁定而改变。例如，如果数组正在被synchronized同步块或方法保护，那么这部分内容将包含有关锁的信息，如线程ID、锁状态等。
? ? ? ? （2.2）垃圾收集信息：Mark Word还存储了与垃圾收集相关的信息，如对象的分代年龄和类型指针等。这对于垃圾收集器跟踪和回收对象非常关键。
其他标志位：除此之外，Mark Word可能还包括一些其他的标志位，如偏向锁标志、轻量级锁标志等。
? ? ? ? （2.3）需要注意的是，由于Mark Word是为整个对象服务的，所以它并不直接针对数组元素。数组元素的数据是存储在对象头之后的实例数据区域中。Mark Word主要是为了支持JVM进行各种操作，比如内存管理和并发控制等。

（3）类指针：类指针指向的是该对象所属的类元数据（Class Metadata）。这个指针对于运行时的动态绑定、方法调用以及反射操作非常重要。它存储了关于对象类型的所有信息，包括类名、父类、接口、字段、方法、常量池等。在64位JVM上，类指针通常占用8字节。而在32位JVM上，类指针占用4字节。

（4）数组大小：数组大小为4字节，因此决定了数组最大容量为2^32，数组元素+字节对齐（JAVA中所有对象的大小都是8字节的整数倍，不足的要用对齐字节补足）

例如：

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

该数组包含内容包括：

单位（字节）

markword（8）
class指针（4）	数组大小（4）
1（4）	2（4）
3（4）	4（4）
5（4）	字节对齐（4）

大小为：8+4+4+4*4+4+4=40字节

2.3.3 动态数组

????????因为数组的大小是固定的，所以数组中的元素并不能随意地添加和删除。这种数组称之为静态数组。

? ? ? ? JAVA中的ArrayList是已经创建好的动态数组。

插入或者删除性能时间复杂度：

? ? ? ? 头部位置：O(n)

? ? ? ? 中间位置：O(n)

? ? ? ? 尾部位置：O(1) 均摊来说

package org.alogorithm;


import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;

public class Main02 {

    public static void main(String[] args) {
        MyArray myArray = new MyArray();
        myArray.addLast(1);
        myArray.addLast(2);
        myArray.addLast(3);
        myArray.addLast(4);
        myArray.addLast(5);
        myArray.addLast(7);
        myArray.addLast(8);
        myArray.addLast(9);
        myArray.addLast(10);
        myArray.addLast(11);
        /*for (int i = 0; i < myArray.size; i++) {
            System.out.println(myArray.array[i]);
        }*/
        myArray.foreach((e) -> {
            //具体操作由调用方界定
            System.out.println(e + "Consumer");
        });
        myArray.add(2, 6);

        for (Integer integer : myArray) {
            System.out.println(integer + "Iterable");
        }

        System.out.println(myArray.remove(4)+"元素被删除");
        myArray.stream().forEach(e -> {
            System.out.println(e + "stream");
        });

    }

    static class MyArray implements Iterable<Integer> {
        private int size = 0;//逻辑大小
        private int capacity = 8;//容量
        private int[] array = {};

        public void addLast(int value) {
            /*array[size] = value;
            size++;*/
            add(size, value);
        }

        public void add(int index, int value) {
            //容量不够扩容
            checkAndGrow();
            /*
             * param1 ：要copy的数组
             * param1 ：copy的起始位置
             * param1 ：要存放数组
             * param1 ：要copy的个数
             * 这个方法表示要将array从index开始copy到index+1的位置，
             * copy的个数是数组的大小-index（index向后的元素）
             * */
            if (index >= 0 && index <= size) {
                System.arraycopy(array, index, array, index + 1, size - index);
            }
            //合并add方法
            array[index] = value;
            size++;
        }

        private void checkAndGrow() {
            if (size==0){
                array=new int[capacity];
            }else if (size == capacity) {
                capacity+=capacity>>1;
                int[] newArray = new int[capacity];
                //赋值数组
                System.arraycopy(array,0,newArray,0,size);
                array=newArray;
            }
        }

        //查询元素
        public int get(int index) {
            return array[index];
        }

        //遍历数组 1
        //查询元素
        public void foreach(Consumer<Integer> consumer) {
            for (int i = 0; i < size; i++) {
                //System.out.println(array[i]);
                //提供array[i]，不需要返回值
                consumer.accept(array[i]);
            }
        }


        //遍历数组2 迭代器模式
        @Override
        public Iterator<Integer> iterator() {
            //匿名内部类
            return new Iterator<Integer>() {
                int i = 0;

                @Override
                public boolean hasNext() {
                    //有没有下一个元素
                    return i < size;
                }

                @Override
                public Integer next() {
                    //返回当前元素，并将指针移向下一个元素
                    return array[i++];
                }
            };
        }

        //遍历数组3 数据流
        public IntStream stream() {
            return IntStream.of(Arrays.copyOfRange(array, 0, size));
        }

        public int remove(int index) {
            int removeed = array[index];
            System.arraycopy(array, index + 1, array, index, size - index - 1);
            size--;
            return removeed;
        }
    }
}

2.4 二维数组

（1）二维数组占32个字节，其中array[0]，array[1]，array[2]元素分别保存了指向三个一维数组的引用。

（2）三个一维数组各占40个字节。

（3）他们在内存布局上是连续的。

package org.alogorithm.array;
public class Main03 {
    public static void main(String[] args) {
        int rows = 1_000_000;
        int columns = 14;
        int[][] arr = new int[rows][columns];
        long ijStar = System.currentTimeMillis();
        ij(arr, rows, columns);
        long ijEnd = System.currentTimeMillis();
        System.out.println("ij执行时间为："+(ijEnd-ijStar));//ij执行时间为：10


        long jiStar = System.currentTimeMillis();
        ji(arr, rows, columns);
        long jiEnd = System.currentTimeMillis();
        System.out.println("ji执行时间为："+(jiEnd-jiStar));//ji执行时间为：47
    }

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

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

????????在计算机中，内存是分块存储的。每个内存块称为一个页（page）。当程序访问数组时，CPU会从内存中加载包含该元素所在的整个页面到高速缓存（cache）中。

在这个例子中，ij和ji两个方法的主要区别在于它们遍历数组的方式：

????????ij按行遍历数组：它首先遍历所有的行，然后在同一行内遍历列。
????????ji按列遍历数组：它先遍历所有的列，然后在同一列内遍历行。
由于现代计算机体系结构的设计特点，ij比ji更快的原因有以下几点：

? ? ? ? （1）缓存局部性（Cache Locality）：按行遍历数组时，相邻的元素在物理内存中彼此靠近，这使得CPU可以高效地利用缓存来加速数据访问。这是因为通常情况下，一次内存读取操作将加载一整块数据（通常是64字节），如果这一块数据中的多个元素被连续使用，那么这些元素很可能都在同一块缓存中，从而减少了对主内存的访问次数。
? ? ? ? （2）预取（Prefetching）：一些现代处理器具有预取机制，可以预测接下来可能需要的数据并提前将其加载到缓存中。按照行顺序遍历数组时，这种机制更有可能发挥作用，因为相邻的元素更可能在未来被访问。
综上所述，ij的遍历方式更适合计算机硬件的工作原理，因此执行速度更快。