数组的实现原理（Java版）
目录
一.数组是什么？
内存分配：
特点：
数组的实现原理：
时间复杂度：
二.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的数组扩容机制：先创建更大容量的数组，然后将原来数组内的元素复制到新的数组，以此用新数组代替旧数组。
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]
// 上两条分析后可以使用Consumer
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(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;
}
}
总结：
- 数组 是存储相同类型数据的基本数据结构，它提供了高效的随机访问。
- 数组的主要操作包括访问、修改、遍历、获取长度等。
- 数组的时间复杂度很高效（访问O(1)，但插入和删除需要O(n)）。