Java集合架構
Java集合類存放于Java.util包中,主要有3種:List(清單包含Queue)、Set(集)、Map(映射)
List是有序的Collection。是線性資料結構的主要表現,存儲的元素是有序的,可重複的。
一共三個實作類: 分别是ArrayList、Vector和LinkedList。
ArrayList底層使用數組實作,元素存儲有序可重複,線程不安全,查詢快增删慢,支援快速随機通路,擴容1.5倍。
ArrayList的自動擴容機制
ArrayList是一個數組結構的存儲容器,預設情況下,數組的長度是10,當然我們可以在建構ArrayList對象的時候自己指定初始化長度。随着在程式裡面不斷的往ArrayList中添加資料,當添加的資料達到10個的時候,ArrayList就沒有多餘的容量可以存儲後續的資料。
這個時候ArrayList就會自動觸發擴容。擴容的具體流程很簡單:
首先,建立一個新的數組,這個數組的長度是原來數組長度的1.5倍。
然後使用Arrays.copyOf方法把老數組裡面的資料拷貝到新的數組裡面。
擴容完成後再把目前要添加的元素加入到新的數組裡面,進而完成動态擴容的過程。
LinkedList底層使用雙向連結清單實作,元素存儲排序有序可重複,線程不安全,查詢慢增删快,不支援随機通路。
Vector1.0就存在,1.2出現在集合架構中。和ArrayList一樣也是數組結構,是線程安全的,是以運作效率慢,每次擴容100%。
ArrayList與LinkedList差別
1.資料結構
ArrayList是基于動态數組實作的,它内部維護一個可變長度的數組,當元素數量增加時,會根據需要自動擴容。
LinkedList則是基于連結清單實作的,它内部維護一個雙向連結清單。
2.通路效率
ArrayList是基于數組實作的,是以它能夠随機通路集合中的元素,時間複雜度為O(1),但在插入和删除元素時,需要将後續的元素向前或向後移動,時間複雜度為O(n)。
LinkedList則是基于連結清單實作的,是以在通路元素時需要從頭或尾開始周遊連結清單,時間複雜度為O(n),但在插入和删除元素時,由于隻需要修改前後節點的引用,時間複雜度為O(1)。
3.空間占用
ArrayList需要維護一個動态數組,是以在一定程度上比LinkedList占用更多的空間。
但在實際應用中,ArrayList更常用,因為它能夠提供更快的随機通路和更好的緩存性能。
4.線程安全
ArrayList和LinkedList都不是線程安全的,如果需要在多線程環境中使用,需要使用線程安全的集合類或者在通路時進行同步控制。
ArrayList與Vector差別
1.線程安全性
Vector是線程安全的,而ArrayList是非線程安全的。是以,在多線程的情況下,ArrayList的性能更好,而Vector的線程安全性可能會導緻性能損失。
2.擴容機制
ArrayList和Vector在擴容時都會增加容量大小,不同之處在于,ArrayList擴容時會增加原始容量的一半,而Vector擴容時會将容量翻倍。是以,ArrayList相對于Vector更加靈活,可以更快地适應容量變化。
3.資料增删效率
ArrayList和Vector在資料增删時的效率也有所不同。由于Vector是線程安全的,在進行資料操作時需要進行同步,這會導緻效率降低。而ArrayList不需要同步,是以資料操作效率更高。
4.性能
由于ArrayList不是線程安全的,是以其性能要比Vector高。
Iterator和ListIterator都是Java集合架構中的疊代器,用于周遊集合中的元素。Iterator可以周遊所有Collection接口的實作類,如List、Set等。但是隻能單向周遊,即隻能從前向後周遊,不能向後回退。Iterator提供的方法有:
hasNext():判斷是否還有下一個元素。
next():傳回下一個元素。
remove():移除上一個元素(如果未調用next()方法則沒有元素可删,如果連續調用兩次remove()方法也會報錯)。
ListIterator隻能周遊List接口的實作類,而且是雙向周遊。即可以從前向後周遊,也可以從後向前周遊。ListIterator提供的方法有:
hasNext():判斷是否還有下一個元素。
next():傳回下一個元素。
hasPrevious():判斷是否還有上一個元素。
previous():傳回上一個元素。
remove():移除上一個元素(如果未調用next()或previous()方法則沒有元素可删,如果連續調用兩次remove()方法也會報錯)。
add(E e):在目前元素位置後添加一個元素。
set(E e):修改目前元素。