Java List的remove()方法陷阱以及性能優(yōu)化
Java List在進行remove（）方法是通常容易踩坑，主要有一下幾點
循環(huán)時：問題在于，刪除某個元素后，因為刪除元素后，后面的元素都往前移動了一位，而你的索引+1，所以實際訪問的元素相對于刪除的元素中間間隔了一位。
幾種常見方法
1.使用for循環(huán)不進行額外處理時（錯誤）
//錯誤的方法
for(int i=0;i<list.size();i++) {
if(list.get(i)%2==0) {
list.remove(i);
}
}
2.使用foreach循環(huán)（錯誤）
for(Integer i:list) {
if(i%2==0) {
list.remove(i);
}
}
拋出異常：java.util.ConcurrentModificationException；
foreach的本質(zhì)是使用迭代器實現(xiàn)，每次進入for (Integer i:list) 時，會調(diào)用ListItr.next()方法；
繼而調(diào)用checkForComodification()方法， checkForComodification()方法對操作集合的次數(shù)進行了判斷，如果當前對集合的操作次數(shù)與生成迭代器時不同，拋出異常
public E next() {
checkForComodification();
if (!hasNext()) {
throw new NoSuchElementException();
}
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
// checkForComodification()方法對集合遍歷前被修改的次數(shù)與現(xiàn)在被修改的次數(shù)做出對比
final void checkForComodification() {
if (modCount != expectedModCount) {
throw new ConcurrentModificationException();
}
}
使用for循環(huán)，并且同時改變索引；（正確）
//正確
for(int i=0;i<list.size();i++) {
if(list.get(i)%2==0) {
list.remove(i);
i--;//在元素被移除掉后，進行索引后移
}
}
使用for循環(huán)，倒序進行；（正確）
//正確
for(int i=list.size()-1;i>=0;i--) {
if(list.get(i)%2==0) {
list.remove(i);
}
}
使用while循環(huán)，刪除了元素，索引便不+1，在沒刪除元素時索引+1（正確）
//正確
int i=0;
while(i<list.size()) {
if(list.get(i)%2==0) {
list.remove(i);
}else {
i++;
}
}
4.使用迭代器方法（正確,推薦）
只能使用迭代器的remove()方法，使用列表的remove()方法是錯誤的
//正確，并且推薦的方法
Iterator<Integer> itr = list.iterator();
while(itr.hasNext()) {
if(itr.next()%2 ==0)
itr.remove();
}
性能分析
下面來談談當數(shù)據(jù)量過大時候，需要刪除的元素較多時，如何用迭代器進行性能的優(yōu)化，對于ArrayList這幾乎是致命的，從一個ArrayList中刪除批量元素都是昂貴的時間復雜度為O（n²），那么接下來看看LinkeedList是否可行。LinkedList暴露了兩個問題，一個：是每次的Get請求效率不高，而且，對于remove的調(diào)用同樣低效，因為達到位置I的代價是昂貴的。
是每次的Get請求效率不高
需要先get元素，然后過濾元素。比較元素是否滿足刪除條件。
remove的調(diào)用同樣低效
LinkedList的remove（index），方法是需要先遍歷鏈表，先找到該index下的節(jié)點，再處理節(jié)點的前驅(qū)后繼。
以上兩個問題當遇到批量級別需要處理時時間復雜度直接上升到O（n²）
使用迭代器的方法刪除元素
對于LinkedList，對該迭代器的remove（）方法的調(diào)用只花費常數(shù)時間，因為在循環(huán)時該迭代器位于需要被刪除的節(jié)點，因此是常數(shù)操作。對于一個ArrayList，即使該迭代器位于需要被刪除的節(jié)點，其remove（）方法依然是昂貴的，因為數(shù)組項必須移動。下面貼出示例代碼以及運行結果
public class RemoveByIterator {
public static void main(String[] args) {
List<Integer> arrList1 = new ArrayList<>();
for(int i=0;i<100000;i++) {
arrList1.add(i);
}
List<Integer> linList1 = new LinkedList<>();
for(int i=0;i<100000;i++) {
linList1.add(i);
}
List<Integer> arrList2 = new ArrayList<>();
for(int i=0;i<100000;i++) {
arrList2.add(i);
}
List<Integer> linList2 = new LinkedList<>();
for(int i=0;i<100000;i++) {
linList2.add(i);
}
removeEvens(arrList1,"ArrayList");
removeEvens(linList1,"LinkedList");
removeEvensByIterator(arrList2,"ArrayList");
removeEvensByIterator(linList2,"LinkedList");
}
public static void removeEvensByIterator(List<Integer> lst ,String name) {//利用迭代器remove偶數(shù)
long sTime = new Date().getTime();
Iterator<Integer> itr = lst.iterator();
while(itr.hasNext()) {
if(itr.next()%2 ==0)
itr.remove();
}
System.out.println(name+"使用迭代器時間:"+(new Date().getTime()-sTime)+"毫秒");
}
public static void removeEvens(List<Integer> list , String name) {//不使用迭代器remove偶數(shù)
long sTime = new Date().getTime();
int i=0;
while(i<list.size()) {
if(list.get(i)%2==0) {
list.remove(i);
}else {
i++;
}
}
System.out.println(name+"不使用迭代器的時間"+(new Date().getTime()-sTime)+"毫秒");
}
}
原理 重點看一下LinkedList的迭代器
另一篇博客Iterator簡介 LinkedList使用迭代器優(yōu)化移除批量元素原理
調(diào)用方法：list.iterator();
重點看下remove方法
private class ListItr implements ListIterator<E> {
//返回的節(jié)點
private Node<E> lastReturned;
//下一個節(jié)點
private Node<E> next;
//下一個節(jié)點索引
private int nextIndex;
//修改次數(shù)
private int expectedModCount = modCount;
ListItr(int index) {
//根據(jù)傳進來的數(shù)字設置next等屬性，默認傳0
next = (index == size) ? null : node(index);
nextIndex = index;
}
//直接調(diào)用節(jié)點的后繼指針
public E next() {
checkForComodification();
if (!hasNext())
throw new NoSuchElementException();
lastReturned = next;
next = next.next;
nextIndex++;
return lastReturned.item;
}
//返回節(jié)點的前驅(qū)
public E previous() {
checkForComodification();
if (!hasPrevious())
throw new NoSuchElementException();
lastReturned = next = (next == null) ? last : next.prev;
nextIndex--;
return lastReturned.item;
}
/**
* 最重要的方法，在LinkedList中按一定規(guī)則移除大量元素時用這個方法
* 為什么會比list.remove效率高呢;
*/
public void remove() {
checkForComodification();
if (lastReturned == null)
throw new IllegalStateException();
Node<E> lastNext = lastReturned.next;
unlink(lastReturned);
if (next == lastReturned)
next = lastNext;
else
nextIndex--;
lastReturned = null;
expectedModCount++;
}
public void set(E e) {
if (lastReturned == null)
throw new IllegalStateException();
checkForComodification();
lastReturned.item = e;
}
public void add(E e) {
checkForComodification();
lastReturned = null;
if (next == null)
linkLast(e);
else
linkBefore(e, next);
nextIndex++;
expectedModCount++;
}
}
LinkedList 源碼的remove(int index)的過程是
先逐一移動指針，再找到要移除的Node，最后再修改這個Node前驅(qū)后繼等移除Node。如果有批量元素要按規(guī)則移除的話這么做時間復雜度O（n²）。但是使用迭代器是O（n）。
先看看list.remove（idnex）是怎么處理的
LinkedList是雙向鏈表，這里示意圖簡單畫個單鏈表
比如要移除鏈表中偶數(shù)元素，先循環(huán)調(diào)用get方法，指針逐漸后移獲得元素，比如獲得index = 1；指針后移兩次才能獲得元素。
當發(fā)現(xiàn)元素值為偶數(shù)是。使用idnex移除元素，如list.remove(1)；鏈表先Node node(int index)返回該index下的元素，與get方法一樣。然后再做前驅(qū)后繼的修改。所以在remove之前相當于做了兩次get請求。導致時間復雜度是O（n）。
繼續(xù)移除下一個元素需要重新再走一遍鏈表（步驟忽略當index大于半數(shù)，鏈表倒序查找）
以上如果移除偶數(shù)指針做了6次移動。
刪除2節(jié)點
get請求移動1次，remove（1）移動1次。
刪除4節(jié)點
get請求移動2次，remove（2）移動2次。
迭代器的處理
迭代器的next指針執(zhí)行一次一直向后移動的操作。一共只需要移動4次。當元素越多時這個差距會越明顯。整體上移除批量元素是O（n），而使用list.remove(index)移除批量元素是O（n²）
到此這篇關于Java List的remove()方法陷阱以及性能優(yōu)化的文章就介紹到這了,更多相關Java List的remove() 內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關文章希望大家以后多多支持腳本之家！
相關文章
代號Che的下一代Eclipse IDE將運行在云端，可以在任何機器上打開瀏覽器寫代碼。項目的建立、編輯、debug、部署可以都在一個倉庫中進行，需要的朋友可以參考下2015-12-12
這篇文章主要介紹了IDEA生成可運行jar包（包含第三方jar包）流程詳解,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-11-11
springBoot集成redis(jedis)的實現(xiàn)示例
Redis是我們Java開發(fā)中,使用頻次非常高的一個nosql數(shù)據(jù)庫,本文主要介紹了springBoot集成redis(jedis)的實現(xiàn)示例,具有一定的參考價值,感興趣的可以了解一下2023-09-09
分析java并發(fā)中的wait notify notifyAll
一個線程修改一個對象的值，而另一個線程則感知到了變化，然后進行相應的操作，這就是wait()、notify()和notifyAll()方法的本質(zhì)。本文將詳細來介紹它們概念實現(xiàn)以及區(qū)別2021-06-06
這篇文章主要介紹了java中的異常,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2021-08-08
Java使用CompletableFuture進行非阻塞IO詳解
這篇文章主要介紹了Java使用CompletableFuture進行非阻塞IO詳解,CompletableFuture是Java中的一個類,用于支持異步編程和處理異步任務的結果,它提供了一種方便的方式來處理異步操作,并允許我們以非阻塞的方式執(zhí)行任務,需要的朋友可以參考下2023-09-09
這篇文章主要介紹了maven中多個子模塊的構建順序，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-09-09
使用java實現(xiàn)各種數(shù)據(jù)統(tǒng)計圖（柱形圖，餅圖，折線圖）
用Jfree實現(xiàn)條形柱狀圖表，java代碼實現(xiàn)?？山?jīng)常用于報表的制作，代碼自動生成后可以自由查看?？梢宰杂膳渲脠D表的各個屬性，用來達到自己的要求和目的。本文給大家介紹使用java實現(xiàn)各種數(shù)據(jù)統(tǒng)計圖（柱形圖，餅圖，折線圖），需要的朋友可以參考下2015-10-10
一不小心就讓Java開發(fā)踩坑的fail-fast是個什么鬼？(推薦)
這篇文章主要介紹了Java fail-fast，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2019-04-04
這篇文章主要介紹了Netty通道的容器屬性Attribute詳解,Netty中的Channel通道類,有類似于Map的容器功能,可以通過鍵值對的形式來保存任何Java Object的值,一般來說可以存放一些與通道實例相關聯(lián)的屬性,比如說服務期端的ServerSession會話實例,需要的朋友可以參考下2023-12-12