目录
一.数组是什么？
内存分配：
特点：
数组的实现原理：
时间复杂度：
二.Java数组的实现：
总结：
一.数组是什么？
数组（Array） 是一种数据结构，用于存储相同类型的元素集合。数组在内存中是连续分配的，所有的元素都使用相同的数据类型，并且可以通过下标（索引）来访问特定元素。数组是一种常见的线性数据结构，适合用于高效的随机访问操作。
内存分配：
//8字节的markword
//4字节的class指针（压缩class指针的情况）
//4字节的数组大小（决定了数组最大容量是2的32次方）
//java中所有的对象大小都是8字节的整数倍，不足的要用对齐字节补足
//int[] array = {1,2,3,4,5} => 8 + 4 + 4 + 5 * 4 + 4(alignment补齐) = 40字节特点：
- 固定大小：数组在创建时需要指定大小，大小一旦确定，不能更改。
- 连续内存空间：数组的元素在内存中是连续存储的，这使得它在读取时可以快速通过索引定位。
- 索引从0开始：数组的索引是从0开始的，第一个元素的索引是0，最后一个元素的索引是
长度 - 1。 - 相同类型元素：数组中的所有元素必须是相同的数据类型。
数组的实现原理：
-
存储结构：数组在内存中以连续的地址空间存储。假设数组的起始地址为
base_address，每个元素的大小为size，则索引为i的元素的地址为base_address + i * size。这使得数组可以通过索引在常数时间内（O(1)）访问任意元素。 -
访问时间复杂度：由于数组元素在内存中的地址是可以直接计算的，数组的读取操作（通过索引）时间复杂度为 O(1)，即随机访问非常高效。
-
缺点：由于数组大小固定，插入和删除操作在数组中相对较慢，特别是当需要在数组中间插入或删除元素时，时间复杂度为 O(n)。
时间复杂度：
| 访问元素 | O(1) | 直接通过索引访问 |
| 修改元素 | O(1) | 直接通过索引修改 |
| 查找元素 | O(n) | 必须遍历整个数组（线性查找） |
| 插入元素 | O(n) | 插入元素需要移动后续元素 |
| 删除元素 | O(n) | 删除元素后需要移动后续元素 |
二.Java数组的实现：
Java的数组扩容机制：先创建更大容量的数组，然后将原来数组内的元素复制到新的数组，以此用新数组代替旧数组。
java">package ArrayStudy;import java.util.Arrays;
import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.IntStream;public class ArrayListCreateCode implements Iterable<Integer> {//创建动态数组ArrayList//size => 动态数组有效元素个数//容量扩容 => 先创建更大容量的数组，然后将原来数组内的元素复制到新的数组，以此用新数组代替旧数组private int size = 0;//逻辑大小private int capacity = 8;//容量private int[] array = {};//空数组，懒加载（刚开始没用就不数组的情况就不会加载，如果需要此数组就）//新增元素public void addList(int element){
// array[size] = element;
// size++;add(size, element);}// 插入元素public void add(int index, int element){checkAndGrow();// 添加逻辑if(index >= 0 && index < size){//数组间或数组内的元素拷贝(想要拷贝的数组,从哪拷贝,拷贝到的数组,拷贝到的数组的索引位置开始拷贝,拷贝元素个数)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++){System.out.println(array[i]);// 返回void// 提供array[i]// 上两条分析后可以使用Consumerconsumer.accept(array[i]);}}// 迭代器遍历@Overridepublic Iterator<Integer> iterator(){// 匿名内部类return new Iterator<Integer>() {int i = 0;@Overridepublic boolean hasNext() {// 有没有下一个元素return i < size;}@Overridepublic Integer next() {// 返回当前元素，并移动到下一个元素return array[i++];}};}// (整数)流的遍历public IntStream stream(){return IntStream.of(Arrays.copyOfRange(array,0,size));// 选择有效部分流式返回}// 删除元素public int remove(int index){int removed = array[index];System.arraycopy(array,index + 1,array,index,size - index - 1);size--;return removed;}
}
