《Java 算法与数据结构》第 2 章：数组

terry 2年前 (2023-09-27) 阅读数 72 #数据结构与算法

1。简介

数组是数据结构还是数据类型？

数组只是一个名称。它可以描述一组操作或命名这组操作。数组数据操作由idx->val处理。它没有明确要求内存中必须存储连续数据来命名数据，而是通过连续索引idx，也可以线性访问连续数据。

所以当你定义了数据的存储方式时，你也就定义了数据结构。所以它也被归类为一种数据结构。

2。数组数据结构

数组（Array）是一种线性表数据结构。它使用多个连续的内存空间来存储多个相同类型的数据。

数组的特点：

数组是同一数据类型的元素的集合（int不能存储double）
数组中的每个元素都是按顺序存储的，在这个数组中它们在内存中是连续存储的订购。内存地址是连续的。
从数组中获取元素的时间复杂度为O(1)

1。一维数组

一维数组是最常用的数组，许多其他数据结构的变体也都是从一维数组派生而来。比如HashMap的拉链式寻址结构、ThreadLocal的开放式寻址结构都是从一维数组实现的。

2。二维数组

二维和多维数组在开发场景中应用很广泛，但是可以用在一些算法逻辑和数学计算中。

3。实现数组列表

在Java源码中，数组是一种非常常用的数据结构，其他很多数据结构也有数组的影子。在一些数据存储和使用场景中，基本都是使用ArrayList来代替LinkedList。具体性能分析请参见回复：LinkedList 插入比 ArrayList 快吗？你确定吗？

本章我们将利用数组结构的学习来实现一个简单的ArrayList，让使用Java的读者不仅了解数据结构，还了解Java源码实现。

源码地址：https://github.com/fuzhengwei/java-algorithms - Java算法与数据结构
本章源码：https://github.com/fuzhengwei/java-算法/ blob/ main/data-structs/src/main/java/cn/bugstack/algorithms/data/array/ArrayList.java

1。基本设计

数组是一种固定的、连续的、线性的数据结构，那么如果想把它作为一个自动扩展容量的数组列表，就需要做一些扩展。

/**
 * 默认初始化空间
 */
private static final int DEFAULT_CAPACITY = 10;
/**
 * 空元素
 */
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
/**
 * ArrayList 元素数组缓存区
 */
transient Object[] elementData;

在ArrayList初始化阶段，如果不指定大小，则默认初始化一个空元素。目前还没有标准长度。
那么什么时候给出初始长度呢？是第一次添加元素的时候，因为所有添加元素的操作还必须确定容量以及是否会扩容。那么在添加元素的时候就更容易统一处理了。
之后，随着物品的增加，容量会不够用。如果容量不足，则需要进行扩容操作。同时，旧的数据必须迁移到新的数组中。 所以数据迁移是一个比较耗时的操作

2。添加元素

public boolean add(E e) {
    // 确保内部容量
    int minCapacity = size + 1;
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    // 判断扩容操作
    if (minCapacity - elementData.length > 0) {
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity < 0) {
            newCapacity = minCapacity;
        }
        elementData = Arrays.copyOf(elementData, newCapacity);
    }
    // 添加元素
    elementData[size++] = e;
    return true;
}

这是一个简化的ArrayList#add操作

要确定实际容量和初始化容量，使用Math.max函数取最大值作为最小初始化空间。
下一步是判断minCapacity和元素数量是否已经达到扩容。 ArrayList的容量在第一次创建的时候肯定是进行扩容的，即初始化DEFAULT_CAPACITY = 10的容量。
Arrays.copyOf 实际上创建了一个新的空间数组，然后调用 System.arraycopy 迁移到新创建的数组。这样，后续所有的扩容操作就保持统一。
ArrayList扩容完成后，使用elementData[size++] = e；要添加的项目。

3。移除元素

ArrayList的重点离不开System.arraycopy的使用。它是一种本地方法，允许您从原始数组的特定位置迁移到新数组的指定位置和迁移量。。如图2-5所示，数据迁移删除Java算法中的测试代码元素

public E remove(int index) {
    E oldValue = (E) elementData[index];
    int numMoved = size - index - 1;
    if (numMoved > 0) {
        // 从原始数组的某个位置，拷贝到目标对象的某个位置开始后n个元素
        System.arraycopy(elementData, index + 1, elementData, index, numMoved);
    }
    elementData[--size] = null; // clear to let GC do its work
    return oldValue;
}

ArrayList元素删除是使用system.arraycopy将数据复制到确定元素位置后消失。覆盖需要移除的项目的位置。
此外，它会将删除的元素设置为零。一方面我们不会再去读取这个元素，另一方面也是为了GC

4。获取物品

public E get(int index) {
    return (E) elementData[index];
}
@Override
public String toString() {
    return "ArrayList{" +
            "elementData=" + Arrays.toString(elementData) +
            ", size=" + size +
            '}';
}

获取物品相对容易。，直接从带有索引的elementData中获取即可。这是一个 O(1) 操作。正是因为查找元素的方便性，ArrayList 才被如此广泛的使用。同时为了兼容性，可以通过元素来获取数据，而不是直接通过下标来获取数据，这就导致了HashMap的计算方式采用哈希值来计算下标，也导致了斐波那契哈希。它们的设计目的是尽可能接收时间复杂度接近 O(1) 的数据，同时尽可能减少元素冲突。 学习这些内容可以看付哥的《Java 面经手册》，也可以随着本系列章节内容的铺陈逐步覆盖算法。

4。数组列表测试

@Test
public void test_array_list() {
    cn.bugstack.algorithms.data.array.List<String> list = new ArrayList<>();
    list.add("01");
    list.add("02");
    list.add("03");
    list.add("04");
    list.add("05");
    list.add("06");
    list.add("07");
    list.add("08");
    list.add("09");
    list.add("10");
    list.add("11");
    list.add("12");
    
    System.out.println(list);
    
    list.remove(9);
    
    System.out.println(list);
}

测试结果

ArrayList{elementData=[01, 02, 03, 04, 05, 06, 07, 08, 09, 10, 11, 12, null, null, null], size=12}
ArrayList{elementData=[01, 02, 03, 04, 05, 06, 07, 08, 09, 11, 12, null, null, null, null], size=11}

Process finished with exit code 0