目录
一、数组 — 概述
1.定义
2.特点
3.公式
小测试
二、数组的性能
1.空间占用
2.随机访问
三、动态数组
1.实现动态数组
2.新增元素(最后一个元素位置)
3.新增元素、数组扩容
4.检查数组容量
5.类中定义的其他方法
① 按索引查找元素
② 返回数组长度
③ 遍历数组
④ 遍历泛型
⑤ 函数式接口遍历
⑥ 迭代器遍历
⑦ Java流的方式遍历
⑧ 删除元素值
⑨ 重写比较方法
6.整体代码
① 类
② 测试类
7.插入或删除性能
四、二维数组
1.定义格式
2.内存分布及内存占用
五、数组的缓存与局部性原理
局部性原理
上帝,请赐予我平静,去接受我无法改变的;
给予我勇气,去改变我能改变的;
赐我智慧,分辨这两者的区别。
—— 24.9.8
一、数组 — 概述
1.定义
在计算机科学中,数组是由一组元素(值或变量)组成的数据结构。每个元素有至少一个索引或键来标识(元素的类型必须一致)
2.特点
数组内的元素是连续存储的,所以数组中元素的地址,可以通过其索引计算出来,例如:
int[] arr = {1,2,3,4,5}
// 0 1 2 3 4
3.公式
知道了数组的数据起始地址BaseAddress,就可以由公式BaseAddress + i * size计算出索引 i 元素的地址
① i 即索引,在Java、C等语言中都是从 0 开始
② size 是每个元素占用的字节,例如 int 占 4 位,double 占 8 位
小测试
byte[] array = {1,2,3,4,5};
已知array的数据的起始地址是0x7138f94c8,那么元素3的地址是什么?
0x7138f94c8 + 2*1 = 0x7138f94ca
16进制:0123456789abcdef
二、数组的性能
1.空间占用
Java 中数组结构为:
8字节 markword(记录对象的哈希码、锁的信息等)
4字节 class 指针(压缩类指针的情况)
4字节 数组大小(决定了数组最大容量是 232)
数组元素 + 对齐字节(java 中所有对象大小都是8字节的整数倍,不足的要用对齐字节补足)
例如:
int[] array = {1,2,3,4,5};
8 + 4 + 4 * 5 + 4(alignment)
markdown+指针+元素+对齐字节
2.随机访问
即根据索引查找元素,与数据规模没有关系,时间复杂度是O(1)
三、动态数组
1.实现动态数组
size —— 逻辑大小,代表数组中有效的元素个数
capacity —— 数组的容量,代表数组中最大可以容纳的元素数
public class demo1ArrayVectorInsert implements Iterable<Integer> {// 准备三个属性private int size = 0;// 逻辑大小private int capacity = 8;// 容量// 懒惰初始化思想private int[] array = {};
}
2.新增元素(最后一个元素位置)
public void addLast(int element){// size代表数组内有效元素个数// array[size] = element;// size++;add(size,element);}
3.新增元素、数组扩容
// 数组增加元素,需要先进行数组扩容// index:插入元素的位置索引,element:插入的元素// 如果容量不够,需要先扩容public void add(int index,int element){// 容量的检查checkAndGrow();// System.arraycopy(array,index,array,index+1,size-index):实现数组间的元素复制if(index < size && index >= 0) { // 拷贝到0-size-1的区间内// 从原始数组array的index索引开始,拷贝到同一个数组array,向后移动一位,拷贝size-index个元素System.arraycopy(array, index, array, index + 1, size - index);} else if (index == size) {array[index] = element;size ++;} else{// 对插入位置合法性进行判断System.out.println("Index out of bounds");return;}}
4.检查数组容量
private void checkAndGrow() {// 容量的检查if(size == 0){// 检查数组容量是否为8array = new int[capacity];} else if(size == capacity){// 数组容量已满,应进行扩容:1.5倍 1.618倍 2倍capacity = capacity + (capacity >> 1);// 复制到新数组int[] newArray = new int[capacity];System.arraycopy(array,0,newArray,0,size);array = newArray;}}
5.类中定义的其他方法
① 按索引查找元素
// 按索引查找元素public int get(int index) {return array[index];}
② 返回数组长度
// 返回数组长度public int length(){return array.length;}
③ 遍历数组
// 遍历数组public void forEach(){for(int i = 0; i < size; i++) {System.out.print(array[i]+" ");}System.out.println();}
④ 遍历泛型
// 遍历泛型public void forEachGenirics(Consumer<Integer> consumer){for (int i = 0; i < size; i++) {consumer.accept(array[i]);}}
⑤ 函数式接口遍历
// consumer函数式接口,consumer:一个参数,没有返回值public void Foreach(Consumer<Integer> consumer){for (int i = 0; i < size; i++) {// System.out.print(array[i]+" ");// 提供 array[i]// 返回 voidconsumer.accept(array[i]);System.out.print(" ");}System.out.println();}
⑥ 迭代器遍历
// 迭代器遍历@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {// 匿名内部类的写法int i = 0;@Override// 判断有没有下一个元素public boolean hasNext() {return i < size;}@Override// 返回当前元素,并移动到下一个元素public Integer next(){return array[i++];}};}
⑦ Java流的方式遍历
// Java流的方式进行遍历public IntStream stream(){return IntStream.of(array);}
⑧ 删除元素值
// 删除元素值public int remove(int index){if(index < size && index >= 0) {int removed = array[index];if(index < size - 1){System.arraycopy(array, index + 1, array, index, size - index - 1);}// arraycopy(原始数组,要移动的起始位置,目标数组,目标数组的起始位置),要移动的元素个数size--;return removed;}else {System.out.println("Index out of bounds");return 0;}}
⑨ 重写比较方法
// 重写比较方法@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;demo1ArrayVectorInsert integers = (demo1ArrayVectorInsert) o;return size == integers.size && capacity == integers.capacity && Objects.deepEquals(array, integers.array);}@Overridepublic int hashCode() {return Objects.hash(size, capacity, Arrays.hashCode(array));}
6.整体代码
① 类
package Day2Array;import java.util.Arrays;
import java.util.Iterator;
import java.util.Objects;
import java.util.function.Consumer;
import java.util.stream.IntStream;// Java自己实现ArrayList动态数组
// 迭代器遍历,实现一个接口Iterable
public class demo1ArrayVectorInsert implements Iterable<Integer> {// 准备三个属性private int size = 0;// 逻辑大小private int capacity = 8;// 容量// 懒惰初始化思想private int[] array = {};// 新增元素public void addLast(int element){// size代表数组内有效元素个数// array[size] = element;// size++;add(size,element);}// 数组增加元素,需要先进行数组扩容// index:插入元素的位置索引,element:插入的元素// 如果容量不够,需要先扩容public void add(int index,int element){// 容量的检查checkAndGrow();// System.arraycopy(array,index,array,index+1,size-index):实现数组间的元素复制if(index < size && index >= 0) { // 拷贝到0-size-1的区间内// 从原始数组array的index索引开始,拷贝到同一个数组array,向后移动一位,拷贝size-index个元素System.arraycopy(array, index, array, index + 1, size - index);} else if (index == size) {array[index] = element;size ++;} else{// 对插入位置合法性进行判断System.out.println("Index out of bounds");return;}}private void checkAndGrow() {// 容量的检查if(size == 0){// 检查数组容量是否为8array = new int[capacity];} else if(size == capacity){// 数组容量已满,应进行扩容:1.5倍 1.618倍 2倍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];}// 返回数组长度public int length(){return array.length;}// 遍历数组public void forEach(){for(int i = 0; i < size; i++) {System.out.print(array[i]+" ");}System.out.println();}// 遍历泛型public void forEachGenirics(Consumer<Integer> consumer){for (int i = 0; i < size; i++) {consumer.accept(array[i]);}}// consumer函数式接口,consumer:一个参数,没有返回值public void Foreach(Consumer<Integer> consumer){for (int i = 0; i < size; i++) {// System.out.print(array[i]+" ");// 提供 array[i]// 返回 voidconsumer.accept(array[i]);System.out.print(" ");}System.out.println();}// 迭代器遍历@Overridepublic Iterator<Integer> iterator() {return new Iterator<Integer>() {// 匿名内部类的写法int i = 0;@Override// 判断有没有下一个元素public boolean hasNext() {return i < size;}@Override// 返回当前元素,并移动到下一个元素public Integer next(){return array[i++];}};}// Java流的方式进行遍历public IntStream stream(){return IntStream.of(array);}// 删除元素值public int remove(int index){if(index < size && index >= 0) {int removed = array[index];if(index < size - 1){System.arraycopy(array, index + 1, array, index, size - index - 1);}// arraycopy(原始数组,要移动的起始位置,目标数组,目标数组的起始位置),要移动的元素个数size--;return removed;}else {System.out.println("Index out of bounds");return 0;}}// 重写比较方法@Overridepublic boolean equals(Object o) {if (this == o) return true;if (o == null || getClass() != o.getClass()) return false;demo1ArrayVectorInsert integers = (demo1ArrayVectorInsert) o;return size == integers.size && capacity == integers.capacity && Objects.deepEquals(array, integers.array);}@Overridepublic int hashCode() {return Objects.hash(size, capacity, Arrays.hashCode(array));}
}
② 测试类
package Day2Array;import org.junit.Test;
import org.junit.jupiter.api.DisplayName;public class test {@Test@DisplayName("删除遍历")public void test1() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();demo1ArrayVectorInsert.addLast(1);demo1ArrayVectorInsert.addLast(2);demo1ArrayVectorInsert.addLast(3);demo1ArrayVectorInsert.addLast(4);demo1ArrayVectorInsert.addLast(5);int res = demo1ArrayVectorInsert.get(4);System.out.println(res);}@Test@DisplayName("删除遍历")public void test2() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();demo1ArrayVectorInsert.addLast(1);demo1ArrayVectorInsert.addLast(2);demo1ArrayVectorInsert.addLast(3);demo1ArrayVectorInsert.addLast(4);demo1ArrayVectorInsert.addLast(5);// 遍历的方法// ① 自己写一个for循环,在类中写一个函数返回数组长度for (int i = 0; i < demo1ArrayVectorInsert.length(); i++) {System.out.print(demo1ArrayVectorInsert.get(i)+" ");}System.out.println(" ");// ② 在数组中写一个遍历的函数,调用函数demo1ArrayVectorInsert.forEach();// ③ 类定义一个接口,在数组中遍历的函数参数传递一个泛型,在调用函数时进行具体的实现demo1ArrayVectorInsert.forEach(element -> {demo1ArrayVectorInsert.forEach();System.out.print(element+" ");});// ④ 类定义一个接口,定义一个方法传递泛型类型,调用该方法时时进行具体的实现// 将来可以直接调用时修改函数,不需要再函数的定义内部进行代码的修改demo1ArrayVectorInsert.forEachGenirics(element -> {System.out.println(element);});// ⑤ 迭代器遍历:实现接口,用增强for循环使用demo1ArrayVectorInsert.Foreach(element->{demo1ArrayVectorInsert.forEach();System.out.print(element+" ");});}@Test@DisplayName("删除遍历")public void test3() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();demo1ArrayVectorInsert.addLast(1);demo1ArrayVectorInsert.addLast(2);demo1ArrayVectorInsert.addLast(3);demo1ArrayVectorInsert.addLast(4);demo1ArrayVectorInsert.addLast(5);for (Integer element : demo1ArrayVectorInsert) {// hashNext() next()System.out.print(element+" ");}}@Test@DisplayName("删除遍历")public void test4() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();demo1ArrayVectorInsert.addLast(1);demo1ArrayVectorInsert.addLast(2);demo1ArrayVectorInsert.addLast(3);demo1ArrayVectorInsert.addLast(4);demo1ArrayVectorInsert.addLast(5);demo1ArrayVectorInsert.stream().forEach(element->{System.out.print(element+" ");});}@Test@DisplayName("删除测试")public void test5() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();demo1ArrayVectorInsert.addLast(1);demo1ArrayVectorInsert.addLast(2);demo1ArrayVectorInsert.addLast(3);demo1ArrayVectorInsert.addLast(4);demo1ArrayVectorInsert.addLast(5);// 删除第三位,索引为2的元素int removed = demo1ArrayVectorInsert.remove(2);demo1ArrayVectorInsert.forEach();// 验证期望删除值与返回值是否相等if(3 == removed){System.out.println("true");}else{System.out.println("false");}int removed2 = demo1ArrayVectorInsert.remove(3);demo1ArrayVectorInsert.forEach();// 验证期望删除值与返回值是否相等if(5 == removed){System.out.println("true");}else{System.out.println("false");}}@Test@DisplayName("扩容数组")public void test6() {demo1ArrayVectorInsert demo1ArrayVectorInsert = new demo1ArrayVectorInsert();for (int i = 0; i < 9; i++) {demo1ArrayVectorInsert.addLast(i+1);}demo1ArrayVectorInsert demo1ArrayVectorInsert1 = new demo1ArrayVectorInsert();demo1ArrayVectorInsert1.add(0,1);demo1ArrayVectorInsert1.add(1,2);demo1ArrayVectorInsert1.add(2,3);demo1ArrayVectorInsert1.add(3,4);demo1ArrayVectorInsert1.add(4,5);demo1ArrayVectorInsert1.add(5,6);demo1ArrayVectorInsert1.add(6,7);demo1ArrayVectorInsert1.add(7,8);demo1ArrayVectorInsert1.add(8,9);System.out.println("创建的新数组与目标数组是否相等:"+ demo1ArrayVectorInsert1.equals(demo1ArrayVectorInsert));}
}
7.插入或删除性能
① 头部位置,时间复杂度是 O(n)
② 中间位置,时间复杂度是 O(n)
③ 尾部位置,时间复杂度是 O(1) (均摊来说)
四、二维数组
1.定义格式
int[][] array = {{11,12,13,14,15},{21,22,23,24,25},{31,32,33,34,35}};
2.内存分布及内存占用
i:代表外层数组的索引位置
j:代表内层数组的索引位置
五、数组的缓存与局部性原理
局部性原理
这里只讨论空间局部性
① cpu读取内存(速度慢)数据后,会将其放入高速缓存(速度快)当中,如果后来的计算再用到此数据在缓存中能读到的话,就不必读内存了
② 缓存的最小存储单位是缓存行(cache line),一般是 64 bytes,一次读的数据少了不划算,因此最少读 64 bvtes 填满一个缓存行,因此读入某个数据时也会读取其临近的数据,这就是所谓空间局部性
先行后列访问的是连续内存,先列后行访问的是非连续内存,相当于访问链表
先i后j:int[0][0] ——> [0][1] ——> [0][2]... ——> [0][j]int[1][0] ——> [1][1] ——> [1[2]... ——> [1][j]……int[i][0] ——> [i][1] ——> [i[2]... ——> [i][j]先j后i:int[0][0]int[1][0]int[2][0]…int[i][0]……int[][j]