数据结构基础篇-线性表-数组

原文地址
数组可以说使我们编程中最常见的数据结构了，在代码中随处可见。我们可以很容易使用类似int[] ints = new int[4];这样的语法构建一个整数数组，那么你了解数组底层的原理吗？接下来我们就来结合数组的特点分析一下数组的原理，并实现一个简单的数组来帮助大家理解的原理。

数组的特点

高效的随机访问特性，使数组能够根据下标以O(1)的时间复杂度随机访问数组中的任意元素（请注意这里随机访问不是查询哦）。
相应的，为满足随机访问的特性，需要作出一些牺牲，对数组的元素做一些限制：

数组需要占用一块连续的物理内存
数组中元素的类型必须是一致的

只有满足了这两点，才能实现随机访问的特性。

数组如何实现随机访问的

由于数组分配在连续的内存中，我们可以很容易的通过起始地址 + 元素偏移量来定位具体的数组元素的内存地址，然后通过内存地址获取该地址保存的元素：

数组起始内存地址，即为数组分配的连续内存的起始地址
数组元素偏移量，即为该元素的下标 * 元素类型的长度
所以我们得出以下公式：

下标为i的元素的内存地址 = 数组起始内存地址 + 元素类型长度 * i

可以看到，数组根据下标访问元素时，只需要两次数值计算和一次内存读取操作，非常的高效。

数组的优点和缺点

我们先讨论优点：

随机访问特性能保证快速访问（包括修改）对应下标的数组元素，这项操作的代价很小（O(1)）。
CPU缓冲行的特性能够加速数组的访问，当然缓冲行不是我们这篇文章讨论的重点，我们可以简单的认为，CPU是对数组友好的，当我们访问一个数组元素时，CPU会机智的把这个元素后面的好多个元素一起给你，这样在你访问下一个元素时可能就不需要再去内存中读取了。

那么数组有什么缺点呢：

数组在初始化的时候必须指定容量，这就很不灵活，如果分配的太大，就会浪费空间，如果分配的太小，就需要动态扩容，而数组的扩容需要重新分配一块更大的空间，然后拷贝元素，很显然，这是一项O(n)时间复杂度的操作。
数组必须分配连续的内存，如果内存碎片过多，可能会导致内存分配失败。

这里需要补充一点： 理论上，数组的插入和删除操作因为涉及到元素的移动，所以时间复杂度是O(n)的，要差于链表在已知节点情况下的插入和删除操作，数组和链表的查询操作都需要遍历匹配，所以时间复杂度都是O(n)的。
但是事实上，得益于CPU的缓冲行机制，数组的连续存储优势会体现的非常明显，在大部分情况下（元素数量未达到一定规模的时候），数组的的插入、删除、查询都要快于链表，并且具备链表所没有的随机访问特性。

实现一个简单的int数组

理解了数组的原理，我们来动手实现一个int型数组，这里使用java实现，借助了Unsafe类来做内存分配。
源码可以查看我的github

public class IntArray {

    // 借助 sun.misc.Unsafe 直接分配内存
    private static final Unsafe UNSAFE = UnsafeUtil.getUnsafe();
    
    // int类型占用4个字节（byte）
    // 下标i的内存地址偏移量 == i * 4 == i << 2
    private static final int INDEX_SHIFT = 2;

    private final int length;

    // 该数组的内存起始地址
    private final long memoryAddress;

    /**
     * new int[length]
     */
    public IntArray(int length) {
        if (length < 0) {
            throw new IllegalArgumentException(String.valueOf(length));
        }

        this.length = length;
        // 分配一块连续的内存，保存这块内存的起始地址
        memoryAddress = UNSAFE.allocateMemory(length << INDEX_SHIFT);
        // 初始化这块内存
        UNSAFE.setMemory(memoryAddress, length << INDEX_SHIFT, (byte) 0);
    }

    /**
     * array[index] = data
     */
    public void set(int index, int data) {
        ensureIndexRange(index);
        // 根据 起始地址+数组下标*类型长度 计算出内存地址，然后将data保存到该地址
        UNSAFE.putInt(memoryAddress + (index << INDEX_SHIFT), data);
    }

    /**
     * array[index]
     */
    public int get(int index) {
        ensureIndexRange(index);
        // 根据 起始地址+数组下标*类型长度 计算出内存地址，然后获取该地址的int值
        return UNSAFE.getInt(memoryAddress + (index << INDEX_SHIFT));
    }

    /**
     * array.length
     */
    public int length() {
        return length;
    }

    private void ensureIndexRange(int index) {
        if (index < 0 || index >= length) {
            throw new IndexOutOfBoundsException(String.valueOf(index));
        }
    }

}