成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

LinkedList源碼和并發(fā)問題分析

xietao3 / 620人閱讀

摘要：在次操作中其實(shí)即尾節(jié)點(diǎn)是共享資源，當(dāng)多個線程同時執(zhí)行此方法的時候，其實(shí)會出現(xiàn)線程安全問題。同樣會出現(xiàn)并發(fā)安全問題，下面對此問題進(jìn)行分析。

1.LinkedList源碼分析

LinkedList的是基于鏈表實(shí)現(xiàn)的java集合類，通過index插入到指定位置的時候使用LinkedList效率要比ArrayList高，以下源碼分析是基于JDK1.8.

1.1 類的繼承結(jié)構(gòu)

LinkedList類的繼承結(jié)構(gòu)如如下所示：

從以上繼承結(jié)構(gòu)圖中可以看到，最頂層接口為Iterable接口，實(shí)現(xiàn)此接口的類支持通過迭代器遍歷集合中的元素。其他相關(guān)接口如Collection、List、Queue、Deque分別為列表，隊列功能的相關(guān)接口，即此LinkedList支持列表、隊列的相關(guān)操作。Serializable接口為序列化標(biāo)志接口，即所有需要序列化的類都需要實(shí)現(xiàn)此接口。

1.2 LinkedList數(shù)據(jù)結(jié)構(gòu)說明

首先我們來看下LinkedList中保存數(shù)據(jù)的內(nèi)部類定義源碼如下：

private static class Node {
        E item;
        Node next;
        Node prev;

        Node(Node prev, E element, Node next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

通過以上定義可以看出來每個節(jié)點(diǎn)中除了保存元素的值之外還保存了前后節(jié)點(diǎn)的引用。即使用了鏈表的數(shù)據(jù)接口保存數(shù)據(jù)元素。數(shù)據(jù)結(jié)構(gòu)如下圖所示：

在LinkedList類中，只是定義了兩個Node類型的屬性，定義如下：

 transient Node first;
 transient Node last;

這兩個屬性分別表示頭節(jié)點(diǎn)和尾節(jié)點(diǎn)，始終指向鏈表的第一個節(jié)點(diǎn)和最后一個節(jié)點(diǎn)。

1.3 關(guān)鍵方法源碼分析

當(dāng)不指定index往LinkedList中添加元素的時候默認(rèn)是在鏈表的尾部添加數(shù)據(jù)，源代碼如下

  void linkLast(E e) {
      //保存鏈表插入之前的最后一個節(jié)點(diǎn)
      final Node l = last;
      //將新節(jié)點(diǎn)的preNode指向鏈表最后一個節(jié)點(diǎn)
      final Node newNode = new Node<>(l, e, null);
      last指向插入后的尾節(jié)點(diǎn)
      last = newNode;
      if (l == null)
          //當(dāng)?shù)谝淮尾迦霐?shù)據(jù)的時候，頭節(jié)點(diǎn)和尾節(jié)點(diǎn)指向同一個節(jié)點(diǎn)
          first = newNode;
      else
          //插入之前的尾節(jié)點(diǎn)的nextNode指向新插入的節(jié)點(diǎn)
          l.next = newNode;
      size++;
      modCount++;
  }

插入節(jié)點(diǎn)的詳細(xì)操作如上面代碼注釋。在次操作中其實(shí)last即尾節(jié)點(diǎn)是共享資源，當(dāng)多個線程同時執(zhí)行此方法的時候，其實(shí)會出現(xiàn)線程安全問題。具體的線程安全問題后面分析。

當(dāng)指定index插入數(shù)據(jù)的時候，源代碼如下所示：

public void add(int index, E element) {
       checkPositionIndex(index);

       if (index == size)
           linkLast(element);
       else
           linkBefore(element, node(index));
   }

在指定index插入元素的時候會先查詢出index位置的元素，然后調(diào)用linkBefore將此元素插入到查詢到的元素的前一個位置。其中l(wèi)inkBefore源碼如下所示：

void linkBefore(E e, Node succ) {
       // assert succ != null;
       final Node pred = succ.prev;
       //新建節(jié)點(diǎn)，并將preNode指向idnex-1節(jié)點(diǎn)
       final Node newNode = new Node<>(pred, e, succ);
       //插入前的index節(jié)點(diǎn)的prev指向新節(jié)點(diǎn)
       succ.prev = newNode;
       if (pred == null)
           first = newNode;
       else
          //index-1節(jié)點(diǎn)的nextNode指向新節(jié)點(diǎn)
           pred.next = newNode;
       size++;
       modCount++;
   }

在指定節(jié)點(diǎn)插入的方式如上注釋所示。此操作中共享資源是插入之前index節(jié)點(diǎn)。同樣會出現(xiàn)并發(fā)安全問題，下面對此問題進(jìn)行分析。

2.LinkedList并發(fā)插入時節(jié)點(diǎn)覆蓋的問題

在指定index插入或者addLast的時候都是在鏈表的尾部插入數(shù)據(jù)，當(dāng)并發(fā)插入的時候如果出現(xiàn)以下執(zhí)行順序的時候，會出現(xiàn)插入的數(shù)據(jù)被覆蓋的問題。

當(dāng)多個線程同時獲取到相同的尾節(jié)點(diǎn)的時候，然后多個線程同時在此尾節(jié)點(diǎn)后面插入數(shù)據(jù)的時候會出現(xiàn)數(shù)據(jù)覆蓋的問題。

文章版權(quán)歸作者所有，未經(jīng)允許請勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請注明本文地址：http://systransis.cn/yun/67637.html

相關(guān)文章

  • Java 常用List集合使用場景分析

    摘要：常用集合使用場景分析過年前的最后一篇，本章通過介紹，，，底層實(shí)現(xiàn)原理和四個集合的區(qū)別。和都是線程安全的，不同的是前者使用類，后者使用關(guān)鍵字。面試官會認(rèn)為你是一個基礎(chǔ)扎實(shí)，內(nèi)功深厚的人才到這里常用集合使用場景分析就結(jié)束了。 Java 常用List集合使用場景分析 過年前的最后一篇，本章通過介紹ArrayList，LinkedList，Vector，CopyOnWriteArrayList...

    godruoyi 評論0 收藏0

  • LinkedList 基本示例及源碼解析

    摘要：對于不可修改的列表來說，程序員需要實(shí)現(xiàn)列表迭代器的和方法介紹這個接口也是繼承類層次的核心接口，以求最大限度的減少實(shí)現(xiàn)此接口的工作量，由順序訪問數(shù)據(jù)存儲例如鏈接鏈表支持。 一、JavaDoc 簡介 LinkedList雙向鏈表，實(shí)現(xiàn)了List的 雙向隊列接口，實(shí)現(xiàn)了所有l(wèi)ist可選擇性操作，允許存儲任何元素(包括null值) 所有的操作都可以表現(xiàn)為雙向性的，遍歷的時候會從首部到尾部進(jìn)行...

    senntyou 評論0 收藏0

  • 【備戰(zhàn)春招/秋招系列】美團(tuán)Java面經(jīng)總結(jié)進(jìn)階篇 （附詳解答案）

    摘要：我在前面的文章中也提到了應(yīng)該怎么做自我介紹與項目介紹，詳情可以查看這篇文章備戰(zhàn)春招秋招系列初出茅廬的程序員該如何準(zhǔn)備面試。因此基于事件消息對象驅(qū)動的業(yè)務(wù)架構(gòu)可以是一系列流程。 showImg(https://user-gold-cdn.xitu.io/2018/11/14/16711ac29c2ae52c?w=928&h=531&f=png&s=798562); 一 消息隊列MQ的...

    chengjianhua 評論0 收藏0

  • 這幾道Java集合框架面試題在面試中幾乎必問

    摘要：若遇到哈希沖突，則將沖突的值加到鏈表中即可。之后相比于之前的版本，之后在解決哈希沖突時有了較大的變化，當(dāng)鏈表長度大于閾值默認(rèn)為時，將鏈表轉(zhuǎn)化為紅黑樹，以減少搜索時間。有序，唯一紅黑樹自平衡的排序二叉樹。 本文是最最最常見Java面試題總結(jié)系列第三周的文章。主要內(nèi)容： Arraylist 與 LinkedList 異同 ArrayList 與 Vector 區(qū)別 HashMap的底層...

    bigdevil_s 評論0 收藏0

  • 學(xué)習(xí)Java Collection Framework的Iterator實(shí)現(xiàn)

    摘要：源碼，由于的結(jié)構(gòu)并不是順序的，在執(zhí)行方法時不能通過指針或下標(biāo)的方式直接找到下一個元素，為了能達(dá)到這個目的，在構(gòu)造函數(shù)和方法中預(yù)先做了處理。 繼續(xù)研讀JDK的源碼，在比較HashMap和ConcurrentHashMap的不同之處發(fā)現(xiàn)了一個細(xì)節(jié)——關(guān)于Iterator的實(shí)現(xiàn)的不同，其實(shí)HashMap和ConcurrentHashMap還有更多不同的地方，這也是面試經(jīng)常問到的問題，有一篇文...

    VPointer 評論0 收藏0

發(fā)表評論

0條評論

xietao3

男|高級講師

TA的文章

閱讀更多
最新活動
閱讀需要支付1元查看
<