数组

在计算机科学中，数组是由一组元素(值或变量)，组成的数据结构，每个元素有至少一个索引(index)或键(key)来识别。因为数组内元素是连续存储的，所以数组中元素的地址，可以通过索引计算出来

静态数组：数组的大小在创建时就确定，无法进行修改；无法对静态数组进行增删操作

性能

空间占用

Java中数组结构

对象头部分：8字节的markdown(记录对象的哈希码，垃圾回收时的分代年龄，给对象加锁锁的信息等等)

对象头部分：4字节class指针

4字节数组大小(决定了数组最大容量是2^32)

数组元素+对齐字节(Java中所有对象大小都是8字节的整数倍，不足要用对齐字节补足)

随机访问

即根据索引查询元素，时间复杂度是O(1)

动态数组(集合)

集合：作为一个容器（长度可变，自动扩容）存储的是引用数据类型，不可以存放基本数据类型（将基本数据类型变成对应的包装类即可存放）

引用数据类型：类，字符串，数组

集合的实质就是数组，扩容就是将原有数组的数组复制到另一个更大的数组中

基本数据类型（8种）	4整2浮1布尔1字符
整数	byte、short、int、long
浮点	float、double
布尔	boolean
字符	char

定义集合

类名：ArrayList 

创建对象（下文中都有的集合对象均用list）

ArrayList list = new ArrayList();

泛型：限定集合中存储数据的类型（字符串 String，数组等）

ArrayList<泛型>list =new ArrayList<泛型>();

随着JDK的更新，新写法

ArrayList<泛型>list =new ArrayList<>()；

最后输出打印这个集合

System.out.println(list);

打印结果：打印对象不是地址值，而是集合中的数据内容，体现在[]里，用逗号隔开

例如：[aaa，bbb，ccc]

随着JDK不断跟进，集合又可以存放基本数据类型

ArrayList<int> list = new ArrayList<>();

list.add(10);

这里有一个add

在这里就要引入集合的几个基本成员方法

从“增删改查”四个角度

增

布尔类型 list.add(内容)

例ArrayList<String> list = new ArrayList<>();

list.add(“aa”)；

boolean result=list.add(“aa”)；

添加成功，result就是ture（永远都会添加成功）

但是如果添加的元素与定义集合的数据类型不同，程序会直接报错不会返回false

删

布尔类型 list.remove(内容)  

例list.remove(“aa”)；

boolean result=list.remove(“aa”)；

如果集合中有这个元素，可以删除，result为true；没有这个元素，无法删除，result为false。

如果一个集合中有多个相同的元素，使用remove方法删除，删除的都是索引最靠前的那个元素

重载：根据索引来删除，返回值为被删除的元素。集合的索引与数组相同。

例String str=list.remove(0);//删除第一个元素

改

list.set(index，内容)

用方法给的“内容”修改了index索引上原本的元素，返回数据为被替换的元素

查

list.get(index)

通过索引查询单个元素

获取集合的长度：int size()，遍历循环写法与数组使用索引相同

手搓源码认识动态数组

public class DynamicArray implements Iterable<Integer>{
    //逻辑大小
    private int size = 0;
    //容量
    private int capacity = 10;//Java中Arraylist初始容量是10
    //private int[] array = new int[capacity];
    private int[] array = {};//懒惰初始化

    //添加
    public void addLast(int element) {
    //    array[size++] = element;
        add(size, element);
    }

    //插入
    public void add(int index, int element) {

        checkAndGrow();

        //添加逻辑
        if (index >= 0 || index < size) {
            //数组间/内元素拷贝
            //System.arraycopy(拷贝数组, 起始位置, 目标数组, 目标数组位置, 拷贝元素个数);
            System.arraycopy(array, index, array, index + 1, size - index);
        }
        array[index] = element;
        size++;
    }

    private void checkAndGrow() {
        //容量检查
        if (size == 0) {
            array = new int[capacity];
        }else if (size == capacity) {
            //扩容1.5倍
            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];
    }

    //遍历
    public void foreach(Consumer<Integer> consumer) {
        for (int i = 0; i < size; i++) {
            //提供array[i]
            //返回void
            consumer.accept(array[i]);
        }
    }

    //迭代器遍历
    @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++];
            }
        };
    }

    //流的方式遍历
    public IntStream stream() {
        //return IntStream.of(array);
        //只复制有效部分
        return IntStream.of(Arrays.copyOfRange(array,0,size));//[0,size)
    }

    //删除方法
    public int remove(int index) {
        int removed = array[index];
        if (index < size - 1) {
            System.arraycopy(array, index + 1,
                    array, index, size - index - 1);
        }
        size--;
        return removed;
    }
}

插入或删除性能

头部位置，时间复杂度O(n)

中间位置，时间复杂度O(n)

尾部位置，时间复杂度是O(1) (均摊)

基本数据类型对应的包装类(除了两个较为特殊的，其他均是首字母从小写变成大写)

byte--Byte

short--Short

char--Character

int--Integer

long--Long......

例如

ArrayList<Integer> list=new ArrayList<>(); list.add(1);

ArrayList<Character> list=new ArrayList<>();list.add('a');

缓存与局部性原理

对于二维数组，现有两种求和方法

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);
    }

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);
    }

内存的读写速率是纳秒级别，CPU的运算速率是皮秒级别

加入缓存 缓存从内存中读写的最小单位 缓存行 64字节 cacheline

空间局部性（Spatial Locality）
在一段时间内，被访问过的存储单元附近的其他存储单元，也很可能在不久后被访问。
若程序访问了地址为 A 的数据，则地址接近 A 的数据，在近期被访问的概率显著提高