java面試基礎篇-List
- 2020 年 4 月 5 日
- 筆記
一.ArrayList:
底層為數組實現,執行緒不安全,查詢,修改快,增加刪除慢,
數據結構:數組以0為下標依次連續進行存儲
數組查詢元素：根據下標查詢就行
數組增加元素：如果需要給index為10的位置添加，則從index為11的位置開始右移
數組刪除元素：如果需要刪除index為10的位置，則從index為11的位置開始左移
執行緒: 如果判斷執行緒安不安全只需要了解到是否進行加鎖,如果沒有加鎖的話,多個執行緒操作同一個對象時就會出現執行緒不安全的情況.
源碼:
1.new一個arraylist,調用add方法
2.查看add方法的源碼可以看出,並沒有任何加鎖操作,這就是執行緒不安全的 ,這裡首先會確認數組的容量,對其進行增加,並將新的元素加入到數組中
使用場景:查詢 修改多
二.LikedList:
底層為鏈表實現,執行緒不安全,查詢修改慢,增加刪除快
數據結構:鏈表的每個元素都存儲了下一個元素的地址，從而使一系列的隨機的記憶體地址串在了一起，只要有足夠的記憶體空間，就可以為鏈表分配記憶體
鏈表查：當同時讀取所有元素時，鏈表的效率很高，讀第一個，讀第二個，以此類推。如果需要找到某個節點時,就需要遍歷整個節點,才可以找到需要的元素
鏈表增加元素：只需要修改它前面的那個元素指針指向的地址即可
鏈表刪除元素:只需要將前一個元素指針指向的地址更改即可
執行緒: 如果判斷執行緒安不安全只需要了解到是否進行加鎖,如果沒有加鎖的話,多個執行緒操作同一個對象時就會出現執行緒不安全的情況.
源碼:
1.new一個likedlist
2.可以看到likedlist源碼中也無任何的加鎖操作,其中add又調用了linklast
3.linklast里會吧新加元素設置為尾節點，所以創建了一個新的Node(節點)存起來,然後再新建一個節點,把之前的node指向鏈表的最後一個節點,然後再判斷一下l是否為空也就是之前的鏈表裡是否為空,如果為空則吧新的節點設為頭節點,否則就把next改為newnode,同時size和modcound自增
同樣的 也沒看到任何加鎖的操作
使用場景:增加刪除多
三,Vector
底層是數組實現，執行緒安全的，操作的時候使用synchronized進行加鎖
因為是數組實現的,curd方面可以參考arraylist,由於是加鎖的,所以比前兩個list效率更低的
源碼
1.new一個Vector,
2. 可以看到這個方法使用了 synchronized來進行修飾,對此方法進行加鎖,因此這個方法對元素操作時是效率安全的,但效率相對較低,
同樣的首先確認元素,擴容+1,把新的元素放進去
題外話.怎樣來保證list的執行緒安全
方式一:自己寫一個包裝類,根據業務,一般在進行add/update/remove操作時加鎖
方式二:collections調用 synchronizedlist方法,
源碼:
1.創建一個list,會返回一個執行緒安全的list給你
2.可看到這個方法里首先是一個list集合,mutex是一個加鎖的對象
3.在繼續打開synchronizedrandomaccesslist
4,打開super,這裡可以看到這裡返回了一個同步的synchronizedlist,同樣也繼承了一個list方法
5.在synchronizedlist里可以找到常用的一些方法,同樣也是加鎖的,所以這個就變成執行緒安全了
方式三:CopyOnWriteArrayList
源碼:
1.new CopyOnWriteArrayList 使用ReentrantLock加鎖
2. CopyOnWriteArrayList 在使用get操作時沒有加鎖的 這個與synchronizedlist對比來說性能要更好一點
3,在add方法時可以看到用了ReentrantLock來進行加鎖,再用object數組獲取老的數組,並將老的數組獲取保存在len,
下面再用Arrays.copyof進行拷貝,將老的數組拷貝到新的數組newElements,並將長度+1,+1的原因就是為了存放新的元素,
目前記憶體里有兩個空間,一個空間是新的空間,另一個是舊的空間
setarray是為了將新的拷貝到舊的里,也就是改變了他的引用地址
最終unlock,把鎖釋放
