Java ArrayList的实现原理详解
生活随笔
收集整理的這篇文章主要介紹了
Java ArrayList的实现原理详解
小編覺得挺不錯的,現在分享給大家,幫大家做個參考.
ArrayList是Java List類型的集合類中最常使用的，本文基于Java1.8，對于ArrayList的實現原理做一下詳細講解。
（Java1.8源碼：http://docs.oracle.com/javase/8/docs/api/）
一、ArrayList實現原理總結
ArrayList的實現原理總結如下：
①數據存儲是基于數組實現的，默認初始容量為10；
②添加數據時，首先需要檢查元素個數是否超過數組容量，如果超過了則需要對數組進行擴容；插入數據時，需要將插入點k開始到數組末尾的數據全部向后移動一位。
③數組的擴容是新建一個大容量（原始數組大小+擴充容量）的數組，然后將原始數組數據拷貝到新數組，然后將新數組作為擴容之后的數組。數組擴容的操作代價很高，我們應該盡量減少這種操作。
④刪除數據時，需要將刪除點+1位置開始到數組末尾的數據全部向前移動一位。
⑤獲取數據很快，根據數組下表可以直接獲取。
二、ArrayList的實現原理詳解
（轉自：http://zhangshixi.iteye.com/blog/674856）
1. ArrayList概述：
?? ArrayList是List接口的可變數組的實現。實現了所有可選列表操作，并允許包括 null 在內的所有元素。除了實現 List 接口外，此類還提供一些方法來操作內部用來存儲列表的數組的大小。
?? 每個ArrayList實例都有一個容量，該容量是指用來存儲列表元素的數組的大小。它總是至少等于列表的大小。隨著向ArrayList中不斷添加元素，其容量也自動增長。自動增長會帶來數據向新數組的重新拷貝，因此，如果可預知數據量的多少，可在構造ArrayList時指定其容量。在添加大量元素前，應用程序也可以使用ensureCapacity操作來增加ArrayList實例的容量，這可以減少遞增式再分配的數量。
?? 注意，此實現不是同步的。如果多個線程同時訪問一個ArrayList實例，而其中至少一個線程從結構上修改了列表，那么它必須保持外部同步。
?
2. ArrayList的實現：
?? 對于ArrayList而言，它實現List接口、底層使用數組保存所有元素。其操作基本上是對數組的操作。下面我們來分析ArrayList的源代碼：
???1) 底層使用數組實現：
Java代碼 ? ????2) 構造方法：
?? ArrayList提供了三種方式的構造器，可以構造一個默認初始容量為10的空列表、構造一個指定初始容量的空列表以及構造一個包含指定collection的元素的列表，這些元素按照該collection的迭代器返回它們的順序排列的。
????3) 存儲：
?? ArrayList提供了set(int index, E element)、add(E e)、add(int index, E element)、addAll(Collection<? extends E> c)、addAll(int index, Collection<? extends E> c)這些添加元素的方法。下面我們一一講解：
????4) 讀取：
Java代碼 ? ??? 5) 刪除：
?? ArrayList提供了根據下標或者指定對象兩種方式的刪除功能。如下：
??? 注意：從數組中移除元素的操作，也會導致被移除的元素以后的所有元素的向左移動一個位置。
???6) 調整數組容量：
?? 從上面介紹的向ArrayList中存儲元素的代碼中，我們看到，每當向數組中添加元素時，都要去檢查添加后元素的個數是否會超出當前數組的長度，如果超出，數組將會進行擴容，以滿足添加數據的需求。數組擴容通過一個公開的方法ensureCapacity(int minCapacity)來實現。在實際添加大量元素前，我也可以使用ensureCapacity來手動增加ArrayList實例的容量，以減少遞增式再分配的數量。
?? 從上述代碼中可以看出，數組進行擴容時，會將老數組中的元素重新拷貝一份到新的數組中，每次數組容量的增長大約是其原容量的1.5倍。這種操作的代價是很高的，因此在實際使用時，我們應該盡量避免數組容量的擴張。當我們可預知要保存的元素的多少時，要在構造ArrayList實例時，就指定其容量，以避免數組擴容的發生。或者根據實際需求，通過調用ensureCapacity方法來手動增加ArrayList實例的容量。
?? ArrayList還給我們提供了將底層數組的容量調整為當前列表保存的實際元素的大小的功能。它可以通過trimToSize方法來實現。代碼如下：
???7) Fail-Fast機制：
ArrayList也采用了快速失敗的機制，通過記錄modCount參數來實現。在面對并發的修改時，迭代器很快就會完全失敗，而不是冒著在將來某個不確定時間發生任意不確定行為的風險。具體介紹請參考我之前的文章深入Java集合學習系列：HashMap的實現原理中的Fail-Fast機制。
???8) 關于其他的一些方法的實現都很簡單易懂，讀者可參照API文檔和源代碼，一看便知，這里就不再多說。
/*****************************************************************************************************************************/
ArrayList是List里面使用率最高的。
package collection.lession7;
| ? | import?java.util.ArrayList; import?java.util.Arrays; import?java.util.Collection; import?java.util.Iterator; import?java.util.List; public?class?Lession7 { public?static?void?main(String[] args) { testNormal(); testSpecial(); // 一個最常見的錯誤 testForProblem(); } public?static?void?testNormal() { // ------------------------------------------------------- // 聲明一個列表 // 允許放入任何數據 // ------------------------------------------------------- ArrayList list =?new?ArrayList(); // 放入整數 // 當然你用 new Integer(1)也可以 list.add(1); // 放入字符串 list.add("abc"); // 放入浮點數 list.add(new?Float(1.11)); // add會將數據保存到列表的尾部 showList(list);?// 1, abc, 1.11] // 下面我們在列表的頭部增加數據 list.add(0,?2); list.add(0,?"bcd"); list.add(0,?new?Double(2.34)); // 列表可以指定插入的位置 // 0 是頭部第一個位置，所以數據都逐個放到最前面了 showList(list);?// [2.34, bcd, 2, 1, abc, 1.11] // 下面我們插入到我們希望的任何位置 // 當然不能越界，(0 到 list.size()-1)范圍內才可以 list.add(1,?3); list.add(4,?"xyz"); // 數據被放到了正確的位置 showList(list);?// [2.34, 3, bcd, 2, xyz, 1, abc, 1.11] // ------------------------------------------------------- // 我們有了數據，我們來測試讀取數據 // ------------------------------------------------------- // 我們可以通過指定索引的位置，來拿到我們希望的數據 System.out.println(list.get(0));?// 2.34 System.out.println(list.get(4));?// xyz // ------------------------------------------------------- // 測試是否存在某個數據 // ------------------------------------------------------- System.out.println(list.contains("xyz"));?// true // 測試是否包含一組數據 Collection c =?new?ArrayList(); c.add(1); c.add(2); System.out.println(list.containsAll(c));?// true c.add(3); c.add(4); // containsAll_1234=false System.out.println(list.containsAll(c));?// false // ------------------------------------------------------- // 查找某個數據所在的索引位置 // 如果不存在，返回-1 // ------------------------------------------------------- System.out.println(list.indexOf(3));?// 1 System.out.println(list.indexOf("xyz"));?// 4 System.out.println(list.indexOf("abcd"));?// -1 // ------------------------------------------------------- // 測試刪除數據 // 請注意， // 如果你使用整數(int)數字，則默認調用的是remove(int index); // 如果你用 long,則會調用 remove(Object obj); // 所以如果你要刪除整數，請使用 remove(new Integer(int)); // ------------------------------------------------------- // 刪除索引為1的數據 list.remove(1); // 索引為1的數據被干掉了 showList(list);?// [2.34, bcd, 2, xyz, 1, abc, 1.11] // 刪除數字1 和字符串 abc list.remove(new?Integer(1)); list.remove("xyz"); showList(list);?// [2.34, bcd, 2, abc, 1.11] // ------------------------------------------------------- // 迭代器的使用 // ------------------------------------------------------- Iterator it = list.iterator(); while?(it.hasNext()) { System.out.print(it.next() +?" ");?// 2.34 bcd 2 abc 1.11 } System.out.println(); // ------------------------------------------------------- // 轉化為數組 // ------------------------------------------------------- Object[] objs = list.toArray(); for?(Object obj : objs) { System.out.print(obj +?" ");?// 2.34 bcd 2 abc 1.11 } System.out.println(); } public?static?void?testSpecial() { // ------------------------------------------------------- // 測試重復和null // ------------------------------------------------------- // List<Integer> list =?new?ArrayList<Integer>(); list.add(123); list.add(456); list.add(123); list.add(456); // 數據允許重復 showList(list);?// [123, 456, 123, 456] list.add(null); list.add(789); list.add(null); list.add(999); // 允許放入多個null showList(list);?// [123, 456, 123, 456, null, 789, null, 999] // ------------------------------------------------------- // 測試一下查找最后一次出現的位置 // ------------------------------------------------------- System.out.println(list.indexOf(123));?// 0 System.out.println(list.lastIndexOf(123));?// 2 // ------------------------------------------------------- // 轉化為數組 // 記得要轉化為Inerger. // ------------------------------------------------------- Integer[] nums = (Integer[]) list.toArray(new?Integer[0]); // 注意數據里面有null,所以循環變量不要用int 要用Integer for?(Integer num : nums) { System.out.print(num +?" ");?// 123 456 123 456 null 789 null 999 } System.out.println(); } public?static?void?testForProblem() { // 一些朋友在向循環里向列表增加對象的時候 // 經常忘記初始化，造成最終加入的都是同一個對象 List<MyObject> list =?new?ArrayList<MyObject>(); MyObject obj =?new?MyObject(); for?(int?i =?1; i <=?5; i++) { obj.setName("Name"?+ i); list.add(obj); } // 里面的數據都是最后一個 showList(list);?// [Name5, Name5, Name5, Name5, Name5] // 正確的做法 List<MyObject> list2 =?new?ArrayList<MyObject>(); MyObject obj2 =?null; for?(int?i =?1; i <=?5; i++) { obj2 =?new?MyObject(); obj2.setName("Name"?+ i); list2.add(obj2); } // 里面的數據都是最后一個 showList(list2);?// [Name1, Name2, Name3, Name4, Name5] } /** * 顯示List里面的數據。 * * @param list */ private?static?void?showList(List list) { System.out.println(Arrays.toString(list.toArray())); } } class?MyObject { private?String name; public?String getName() { return?name; } public?void?setName(String name) { this.name = name; } /** * 重寫toString方法，輸出name */ public?String toString() { return?name; } } |
輸出結果
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 | [1, abc,?1.11] [2.34, bcd,?2,?1, abc,?1.11] [2.34,?3, bcd,?2, xyz,?1, abc,?1.11] 2.34 xyz true true false 1 4 -1 [2.34, bcd,?2, xyz,?1, abc,?1.11] [2.34, bcd,?2, abc,?1.11] 2.34?bcd?2?abc?1.11 2.34?bcd?2?abc?1.11 [123,?456,?123,?456] [123,?456,?123,?456,?null,?789,?null,?999] 0 2 123?456?123?456?null?789?null?999 [Name5, Name5, Name5, Name5, Name5] [Name1, Name2, Name3, Name4, Name5] |
創作挑戰賽新人創作獎勵來咯，堅持創作打卡瓜分現金大獎
總結
以上是生活随笔為你收集整理的Java ArrayList的实现原理详解的全部內容，希望文章能夠幫你解決所遇到的問題。
- 上一篇： Java基础知识——Java数组详解
- 下一篇： 青柠檬的功效与作用、禁忌和食用方法