不要小瞧数组
- 2019 年 10 月 3 日
- 筆記
一、简介
本文开始梳理数据结构的内容，从数组开始，逐层深入。
二、java中的数组
在java中，数组是一种效率最高的存储和随机访问对象引用序列的方式。数组是一种线性序列，这使得元素访问非常快速。但是为了这种快速所付出的代价是数组对象的大小被固定，并且是在其整个生命周期中不可被改变，简单的来说可以理解为数组一旦被初始化，则其长度不可被改变。
从上面一段话中我们不难发现几个关键词：效率最高，随机访问，线性序列，长度固定。
从而我们对数组的优缺点就可见一斑：
优点：
随机访问。数组的随机访问速度是O（1）的时间复杂度。效率极高。 缺点：
长度固定。一旦初始化完成，数组的大小被固定。灵活性不足。
上面我们说数组是一种线性序列，如何理解这句话呢？简单来说就是将数据码成一排进行存放。
三、数组的内存分配
int[] a = new int[5];//数组的静态初始化
执行上面这行代码，JVM的内存是如何分布的呢？
如图所示根据代码的定义，该数组的长度为5，则在栈内存中开辟长度为5的连续内存空间。并且JVM会自动根据类型分配初始值。int 类型的初始值为0。如果类型为Integer，初始值为null（这是java基础内容）。
1 a[0] = 0; 2 a[1] = 1; 3 a[2] = 2; 4 a[3] = 3; 5 a[4] = 4;
如果再执行如上代码，内存分配如下：
正如以上代码所示，数组的存储效率也是极高的，可根据下标直接将目标元素存放至指定的位置。所以添加元素的时间复杂度也是O（1）级别的。
四、数组的二次封装。
本章我们的重点是封装一个属于自己的数组。对于二次封装的数组我们想要达到的效果如下所示：
1 使用java中的数组作为底层数据结构 2 数组的基本操作：增删改查等 3 使用泛型-增加灵活性 4 动态数组-解决数组最大的痛点
4.1、定义我们的动态数组类
1 /** 2 * 描述：动态数组类 3 * 4 * @Author shf 5 * @Date 2019/7/18 10:48 6 * @Version V1.0 7 **/ 8 public class Array<E> {// 使用泛型 9 private final static int DEFAULT_SIZE = 10;// 默认的数组容量 10 11 private E[] data;// 动态数组的底层容器 12 private int size;// 数组的长度 13 14 /** 15 * 根据传入的 capacity 定义一个指定容量的数组 16 * @param capacity 17 */ 18 public Array(int capacity){ 19 this.data = (E[])new Object[capacity]; 20 this.size = 0; 21 } 22 23 /** 24 * 无参构造方法 - 默认容量为 DEFAULT_SIZE = 10； 25 */ 26 public Array(){ 27 this(DEFAULT_SIZE); 28 } 29 }
TIPS： java中泛型不能直接 new 出来。需要new Object，然后强转为我们的泛型。 如下所示： this.data = (E[])new Object[capacity];
4.2，添加元素
对于我们的数组，我们需要规定数组中的元素都存放在 size – 1的位置。这样做首先我们能根据size参数知道，开辟的数组空间哪些被用了，哪些还没被用。另外一个重要作用就是判断我们的数组是不是已经满了，为后面的动态扩容奠定基础。
4.2.1、 向数组尾部添加元素
最初我们的数组如下图所示：
我们在数组的尾部添加一个元素也就是在size处添加一个元素。
代码实现一下：
1 /** 2 * 向数组的尾部 添加 元素 3 * @param e 4 */ 5 public void addLast(int e){ 6 if(size == data.length){ 7 throw new IllegalArgumentException("AddLast failed. Array is full."); 8 } 9 data[size] = e; 10 size ++; 11 }
4.2.2 、向索引 index 处添加元素
如下图所示，如果我们想在 index 为2的位置添加一个元素66。
如图中所示，我们想在 index = 2 的位置添加元素，我们需要将 index为2 到尾部的所有元素移动往后移动一个位置。然后将66方法 2索引位置。
接下来我们用代码实现一下这个过程。
1 /** 2 * 在 index 的位置插入一个新元素e 3 * @param index 4 * @param e 5 */ 6 public void add(int index, int e){ 7 8 if(size == data.length) 9 throw new IllegalArgumentException("Add failed. Array is full."); 10 11 if(index < 0 || index > size) 12 throw new IllegalArgumentException("Add failed. Require index >= 0 and index <= size."); 13 14 for(int i = size - 1; i >= index ; i --) 15 data[i + 1] = data[i]; 16 17 data[index] = e; 18 19 size ++; 20 }
我们发现有了这个方法，4.2.1中的向数组尾部添加元素就可以直接调用该方法，并且对于向数组头添加元素也是显而易见了。
1 /** 2 * 向数组 尾部 添加元素 3 * @param e 4 */ 5 public void addLast(E e){ 6 this.add(this.size, e); 7 } 8 9 /** 10 * 向数组 头部 添加元素 11 * @param e 12 */ 13 public void addFirst(E e){ 14 this.add(0, e); 15 }
4.3、删除
删除指定位置的元素。假设我们删除 index = 2位置的元素66。
如上图所示，我只需要将索引 2 以后的元素向前移动一个位置，并重新维护一下size即可。
代码实现一下上面过程：
1 /** 2 * 删除指定位置上的元素 3 * @param index 4 * @return 返回删除的元素 5 */ 6 public int remove(int index){ 7 if(index < 0 || index >= size) 8 throw new IllegalArgumentException("Remove failed. Index is illegal."); 9 10 int ret = data[index]; 11 for(int i = index + 1 ; i < size ; i ++) 12 data[i - 1] = data[i]; 13 size --; 14 return ret; 15 }
有了上面的方法，对于删除数组 头 或者 尾 部的元素就好办了
1 /** 2 * 删除第一个元素 3 * @return 4 */ 5 public E removeFirst(){ 6 return this.remove(0); 7 } 8 9 /** 10 * 从数组中删除最后一个元素 11 * @return 12 */ 13 public E removeLast(){ 14 return this.remove(this.size - 1); 15 }
4.4、查找，修改，搜索等操作
这些操作都是不改变数组长度的操作，逻辑相对来说就很简单了。
1 /** 2 * 获取 index 索引位置的元素 3 * @param index 4 * @return 5 */ 6 public E get(int index){ 7 if(index < 0 || index >= size){ 8 throw new IllegalArgumentException("获取失败，Index 参数不合法"); 9 } 10 return this.data[index]; 11 } 12 13 /** 14 * 获取第一个 15 * @return 16 */ 17 public E getFirst(){ 18 return get(0); 19 } 20 21 /** 22 * 获取最后一个 23 * @return 24 */ 25 public E getLast(){ 26 return get(this.size - 1); 27 } 28 29 /** 30 * 修改 index 元素位置的元素为e 31 * @param index 32 * @param e 33 */ 34 public void set(int index, E e){ 35 if(index < 0 || index >= size){ 36 throw new IllegalArgumentException("获取失败，Index 参数不合法"); 37 } 38 this.data[index] = e; 39 } 40 41 /** 42 * 查找数组中是否有元素 e 43 * @param e 44 * @return 45 */ 46 public Boolean contains(E e){ 47 for (int i = 0; i< size; i++){ 48 if(this.data[i].equals(e)){ 49 return true; 50 } 51 } 52 return false; 53 } 54 55 /** 56 * 查找数组中元素e所在的索引，如果不存在元素e，则返回-1 57 * @param e 58 * @return 59 */ 60 public int find(E e){ 61 for(int i=0; i< this.size; i++){ 62 if(this.data[i].equals(e)){ 63 return i; 64 } 65 } 66 return -1; 67 }
4.5、resize操作
既然是动态数组，resize操作就是我们的重中之重了。
4.5.1、扩容
扩容是添加操作触发的。
如图所示，如果我们继续往数组中添加元素100，这时我们就需要进行扩容了。我们将原来的容量 capacity 扩充为原来的两倍，然后再进行添加。即：capacity * 2 = 20；（以capacity默认为10为例）
扩容的临界值：size == capacity时继续添加。
首先将容量扩充为原来的2倍：
然后添加元素100
代码上，对于add方法我们要做如下改变：
1 /** 2 * 在 index 的位置插入一个新元素e 3 * @param index 4 * @param e 5 */ 6 public void add(int index, E e){ 7 if(index < 0 || this.size < index){ 8 throw new IllegalArgumentException("添加失败，要求参数 index >= 0 并且 index <= size"); 9 } 10 if(size == data.length){ 11 this.resize(2 * data.length);//扩容 12 } 13 for (int i = size - 1; i >= index; i--) { 14 data[i + 1] = data[i]; 15 } 16 data[index] = e; 17 size ++; 18 }
在添加元素之前，我们进行判断size == data.length（n*capacity，n代表扩容次数，如果我们用capacity，需要维护一个n，或者每次操作都要维护capacity，我们直接用data.length判断）
对于resize方法，逻辑就很简单了。新创建一个容量为newCapacity的数组，将原数组中的元素拷贝到新数组即可。从这可以发现，每次resize操作由于需要有一个copy操作，时间复杂度为O（n）。
1 /** 2 * 将数组容量调整为 newCapacity 大小 3 * @param newCapacity 4 */ 5 public void resize(int newCapacity){ 6 E[] newData = (E[]) new Object[newCapacity]; 7 for (int i = 0; i< this.size; i++){ 8 newData[i] = this.data[i]; 9 } 10 this.data = newData; 11 }
4.5.2、缩容
缩容在删除操作中触发。
接着上面的步骤，如果我们想删除元素100，该怎么做？
删除100元素后才达到resize的临界值 size == 1/2*capacity。所以缩容的时机为删除元素后当 size == 1/2的capacity时。
进行缩容操作：
如上图所示，这时size == 1/2*capacity，已经到了我们缩容的时机。
我们考虑一个问题，假如删除了元素100后，将容量缩为原来的1/2 = 10，如果这时，我又添加元素，是不是又得进行扩容，再删除一个元素，又得缩容。。。
这样频繁的进行扩容，缩容是不是很耗时？这种频繁的进行缩容和扩容会引起复杂度震荡。那我们该如何防止复杂度的震荡呢？很简单，假如我们为扩容–缩容取一个过渡带，即当容量为原来的1/4时再进行缩容是不是就可以避免这种问题了？答案，是的。
代码实现的两个重点：1，防止复杂度震荡。2，缩容发生在 删除一个元素后size == 当前容量的1/4时。
1 /** 2 * 删除指定位置上的元素 3 * @param index 4 * @return 5 */ 6 public E remove(int index){ 7 if(index < 0 || this.size <= index){ 8 throw new IllegalArgumentException("删除失败，Index 参数不合法"); 9 } 10 E ret = this.data[index]; 11 for(int i=index+1; i< this.size; i++){ 12 data[i-1] = data[i]; 13 } 14 size --; 15 this.data[this.size] = null; 16 if(size == this.data.length / 4 && this.data.length / 2 != 0){//防止复杂度的震荡，当size == 1/4capacity时。 17 this.resize(this.data.length / 2); 18 } 19 return ret; 20 }
五、动态数组的时间复杂度分析
5.1、增
addFirst(e) O(n)
addLast(e) O(1)
add(index, e) O(1)-O(n) = O(n)
所以add整体的复杂度最坏情况为O(n)。
5.2、删
removeLast(e) O(1)
removeFirst(e) O(n)
remove(index, e) O(1)-O(n) = O(n)
所以remove整体的复杂度最坏情况为O(n)。
5.3、resize的均摊复杂度
对于resize来说，每次进行一次resize，时间复杂度是O(n)。但是对于resize我们仅仅通过resize操作来界定其时间复杂度合理吗？考虑一个问题，resize操作是每次add或者remove操作都会触发的吗？答案肯定不是的。因为假设当前数组的容量为10，每次使用addLast添加一个元素，需要进行11次的添加操作，才会发生一次resize，一次resize对应10次的元素移动过程。也就是直到resize完成，一共进行了21次操作。假设capacity=n，addLast = n+1，触发resize共进行了2n+1次操作，所以对于addLast操作来说每一次操作，需要进行2次基本操作。
这样均摊计算，addLast的均摊复杂度就是O（1）级别的。均摊复杂度有时比计算最坏的情况更有意义，因为对坏的情况不是每次都发生的。
同理对于removeLast操作来说，均摊复杂度也是O(1)级别的。
5.4、resize操作的复杂度震荡
对于addLast和removeLast操作而言，时间复杂度都是O（1）级别的，但是当我们对这两个操作整体来看，在极端情况下可能会发生的有趣的案例
假设对于添加操作当数组size == capacity 扩容为当前容量的2倍。对于removeLast，达到当前数组容量的1/2，进行缩容，缩为当前容量的1/2。
当前数组的容量为10，这时反复进行addLast和removeLast操作。我们会发现有意思的情况就是对于两个复杂度为O（1）级别的操作，由于每次都触发resize操作，时间复杂度每次都是最坏的情况O（n）。这种由于某种操作造成的复杂度不断变化的情况称为-复杂度的震荡。
如何解决复杂度的震荡呢？上面我们也提到过，就是添加一个缓冲带，减少这种情况的发生。那就是当容量变为原来的1/4时进行缩容。所以对于addLast和removeLast的操作，中间间隔1/4容量的操作才会发生复杂度的震荡。这样我们就有效的减少了复杂度的震荡。
看到这里如果你发现我们手写的动态数组跟java中的ArrayList很相似的话，说明你对ArrayList的了解还是很不错的。
参考文献：
《玩转数据结构-从入门到进阶-刘宇波》
《数据结构与算法分析-Java语言描述》
如有错误的地方还请留言指正。
原创不易，转载请注明原文地址：https://www.cnblogs.com/hello-shf/p/11299383.html
