引言
数组是最基本且重要的数据结构，理解并且吃透它是成为技术大牛的必经之路，今天就让咱们一起来用 Java 实现一个动态数组
设计
动态数组需要具备以下功能/函数
size() —— 数组元素的个数capacity() —— 可容纳元素的个数isEmpty() —— 判断当前数组是否为空get(index) —— 返回对应索引的元素，且若索引越界则愤然报错contains(item) —— 寻找指定值的元素并返回其中第一个出现的元素其索引，若未找到则返回 -1add(item) —— 往容器中添加新的元素，默认从后面追加insert(index, item) —— 在指定索引中插入元素prepend(item) —— 可以使用上面的 insert 函数，传参 index 为 0pop() —— 删除在数组末端的元素，并返回其值delete(index) —— 删除指定索引的元素，并把后面的元素依次前移remove(item) —— 删除指定值的元素，并返回其索引（即使有多个元素）ensureCapacityInternal(new_capacity) // 私有函数 若数组的大小到达其容积，则变大一倍
复制代码
时间复杂度
在数组末端增加/删除、定位、更新元素，只允许占 O(1) 的时间复杂度（平摊（amortized）去分配内存以获取更多空间）在数组任何地方插入/移除元素，只允许 O(n) 的时间复杂度
空间复杂度
因为在内存中分配的空间邻近，所以有助于提高性能空间需求 = （大于或等于 n 的数组容积）* 元素的大小。即便空间需求为 2n，其空间复杂度仍然是 O(n)
实现
在实现任何东西前，我们脑海里应该有个大致的模型/骨架，动态数组的骨架我们一开始要想好，在这里我采用静态数组来进行实现，本质上是在增加数据的时候额外做判断，如果当前的元素总量已经超过阈值，则做扩容的动作。通过这个方式可以跟专注于数据的移动和动态数组的设计层面
触发扩容条件：当前容量不够放下新的元素时进行扩容，为什么 HashMap 要设置扩容阈值
新建类
//为了让我们新建的数组更具备通用性// 第一是要实现迭代器接口(方便通过迭代器遍历数据)// 第二是引入范型，在有可能会有数据类型的变动的场景都可以考虑下范型，详情可看《冒号课堂 编程范式与OOP思想》public class MyArray<E> implements Iterable<E>{ //设置默认容量，容器初始化时如果没有指定则使用此值 private static final int DEFAULT_CAPACITY = 16; //设置为Object数组，用来真正存储数据用的，利用所有对象都可以向上转型为Object来达成存储任意对象的目的 Object [] elements; //记录数组的容量 private int capacity; //记录数组的真实大小也就是元素个数，用于快速返回size private int realSize; public MyArray() { this(DEFAULT_CAPACITY); }
public MyArray(final int capacity) { this.realSize = 0; this.capacity = capacity; this.elements = new Object[this.capacity]; }}
复制代码
size/capacity/isEmpty
这几个方法
//返回数组内元素个数 public int size() { return realIndex; } //返回底层数组大小 public int capacity() { return elements.length; } //判断数组是否为空 public boolean isEmpty() { return realSize == 0; }
复制代码
get/contains 方法的实现
get 方法的实现非常简单，本质上就是根据下标去查询底层数组的元素
//不支持查询null对象 public boolean contains(Object o) { return indexOf(o) >= 0; }
public int indexOf(Object o) { if (o == null) return -1; for (int i = 0; i < realSize; i++) if (o.equals(elements[i])) return i; return -1; }
复制代码
put 方法的实现
所有数据结构的写入一般都是最复杂的，因为为了提高读的性能只能在写的方式里下功夫
//超过阈值时需要进行扩容(阻塞扩容还是双buf并发扩容) public void add(E e) { if (realSize+1 > elements.length) { System.out.println("=======Array日志：容器放不下新增的元素，先进行扩容操作再做处理==========="); ensureCapacityInternal(); } elements[realSize] = e; realSize=realSize+1; }
//进行扩容，默认扩2倍 public void ensureCapacityInternal() { System.out.println(String.format("=======Array日志：开始进行扩容，扩容前容器大小是:%s, " + "真正大小是: %s ,当前数组内容为：\n%s===========", realSize, elements.length, JSONObject.toJSONString(elements))); int newLength = (int) (elements.length<<1); Object[] newArray = new Object[newLength]; System.arraycopy(elements, 0,newArray,0,realSize); elements = newArray; System.out.println(String.format("=======Array日志：扩容结束，扩容后容器大小是:%s, " + "真正大小是:%s,当前数组内容为：\n%s===========", realSize, elements.length, JSONObject.toJSONString(elements))); }
复制代码
insert/prepend
//超过阈值时需要进行扩容(阻塞扩容还是双buf并发扩容) public void insert(int index, E e) throws Exception{ if (index > this.capacity) { throw new Exception("不支持指定过大的下标插入数据！"); } elements[index] = e; }
复制代码
delete/pop/remove
public E remove(final int index) throws Exception{ final E oldElement = get(index); final int newSize = this.realSize - 1; System.arraycopy(elements, index + 1, elements, index, newSize - index); elements[this.realSize = newSize] = null; return oldElement; }
public E pop() throws Exception{ int index = this.realSize-1; final E oldElement = get(index); fastRemove(index); return oldElement; }
public void remove(E e) throws Exception{ while (indexOf(e)!=-1) { int index = indexOf(e); fastRemove(index); } }
复制代码
main 方法验证
public class Main { public static void main(String[] args) {
try { MyArray<Integer> myArray = new MyArray<>(); myArray.add(123); myArray.add(456); myArray.add(789); myArray.add(222); myArray.add(222); myArray.add(222); myArray.add(222); myArray.add(222); myArray.add(222); myArray.add(222); myArray.add(222); myArray.add(222); myArray.add(222); myArray.add(222); myArray.add(222); myArray.add(456); myArray.add(456); myArray.add(456); myArray.add(456); } catch (Exception e) { System.out.println(e.getMessage()); System.out.println(e.getCause()); e.printStackTrace(); } }}
复制代码
总结
通过实现这些方法我们可以发现，大部分操作本质上都是数据的移动，而且都是某一部分的数据平移，此时通过 JDK 的高性能移动数据函数 System.arraycopy 进行操作基本可以实现所有的操作，例如扩容、删除元素等动作
自己实现容器的过程中能够明显感觉到不同的设计适用于不同的场景，因此自己造轮子也有利于我们加深我们对某个设计的掌控程度。例如自己开发一个动态数组以及参考 JDK 实现的过程中，我们会发现根据指定下标获取元素的性能是最高的，但是如果要判断某个元素是否在容器内需要完整遍历完整个数组，在数组元素多的时候要尽量避免指定元素查询这样的操作
通过设计系统我们能够轻松看到 ArrayList 也是对数组的实现上做了某些 trade off 的，发散思考一下，在并发安全场景的数组可以怎么设计/玩？读远大于写的场景下又可以怎么玩？
零散的问答
JDK的ArrayList为什么没有指定下标放置元素？ 因为ArrayList是个动态数组，如果指定一个很大的位置放置一个元素会导致数组扩得很大不利于使用以及降低设计的复杂度JDK初始大小为什么设置为16？ ① 为2次幂方便通过左右移高效计算扩容后的大小 ② 容易跟内存对齐 ③ 过小的话前期容易触发扩容动作影响性能JDK/大数据组件中数据的移动常常会用到高性能System.arraycopy，它底层是怎么实现的？ 敬请期待或者自行查阅资料
复制代码
尾言
不积跬步无以至千里，在设计以及实现动态数组中的思考除了增加设计的知识，其实也会潜移默化的改变对设计思维，因此请不要忽略基础知识的储备，哪怕已经工作多年
评论