不要小瞧數組
- 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
