亚洲中字慕日产2020,大陆极品少妇内射AAAAAA,无码av大香线蕉伊人久久,久久精品国产亚洲av麻豆网站

資訊專欄INFORMATION COLUMN

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

xietao3 / 658人閱讀

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

1.LinkedList源碼分析

LinkedList的是基于鏈表實(shí)現(xiàn)的java集合類，通過index插入到指定位置的時(shí)候使用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分別為列表，隊(duì)列功能的相關(guān)接口，即此LinkedList支持列表、隊(duì)列的相關(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;
        }
    }

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

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

 transient Node first;
 transient Node last;

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

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

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

  void linkLast(E e) {
      //保存鏈表插入之前的最后一個(gè)節(jié)點(diǎn)
      final Node l = last;
      //將新節(jié)點(diǎn)的preNode指向鏈表最后一個(gè)節(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ù)的時(shí)候，頭節(jié)點(diǎn)和尾節(jié)點(diǎn)指向同一個(gè)節(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)多個(gè)線程同時(shí)執(zhí)行此方法的時(shí)候，其實(shí)會(huì)出現(xiàn)線程安全問題。具體的線程安全問題后面分析。

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

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

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

在指定index插入元素的時(shí)候會(huì)先查詢出index位置的元素，然后調(diào)用linkBefore將此元素插入到查詢到的元素的前一個(gè)位置。其中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)。同樣會(huì)出現(xiàn)并發(fā)安全問題，下面對(duì)此問題進(jìn)行分析。

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

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

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

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

轉(zhuǎn)載請(qǐng)注明本文地址：http://www.ezyhdfw.cn/yun/67637.html

相關(guān)文章

  • Java 常用List集合使用場(chǎng)景分析

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

    godruoyi 評(píng)論0 收藏0

  • LinkedList 基本示例及源碼解析

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

    senntyou 評(píng)論0 收藏0

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

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

    chengjianhua 評(píng)論0 收藏0

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

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

    bigdevil_s 評(píng)論0 收藏0

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

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

    VPointer 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<