国产xxxx99真实实拍_久久不雅视频_高清韩国a级特黄毛片_嗯老师别我我受不了了小说

資訊專欄INFORMATION COLUMN

Week 2 - Java 容器 - 詳細剖析 List 之 ArrayList, Vector,

MartinDai / 3043人閱讀

摘要:底層使用的是雙向鏈表數據結構之前為循環鏈表,取消了循環。快速隨機訪問就是通過元素的序號快速獲取元素對象對應于方法。而接口就是用來標識該類支持快速隨機訪問。僅僅是起標識作用。,中文名為雙端隊列。不同的是,是線程安全的,內部使用了進行同步。

前言

學習情況記錄

時間:week 2

SMART子目標 :Java 容器

記錄在學習Java容器 知識點中,關于List的需要重點記錄的知識點。

知識點概覽:

ArrayList 與 LinkedList對比

ArrayList 中的 RandomAccess 接口 是什么?

LinkedList 中的 Deque 接口 是什么?

老調常談 之 ArrayList 擴容機制

ArrayList 與 Vector 對比

ArrayList 與 LinkedList對比

底層數據結構:

ArrayList 底層使用的Object數組,默認大小 10

**

LinkedList 底層使用的是雙向鏈表數據結構(JDK1.6之前為循環鏈表,JDK1.7取消了循環。注意雙向鏈表和雙向循環鏈表的區別)。LinkedList 包含了3個重要的成員:sizefirstlastsize是雙向鏈表中節點的個數,firstlast分別指向第一個和最后一個節點的引用。

插入和刪除是否受元素位置的影響:

由于底層實現的影響,ArrayList 采用數組存儲,所以插入和刪除元素的時間復雜度受元素位置的影響。比如:執行add(E e)方法的時候, ArrayList 會默認在將指定的元素追加到此列表的末尾,這種情況時間復雜度就是O(1)。但是如果要在指定位置 i 插入和刪除元素的話(add(int index, E element))時間復雜度就為 O(n-i)。因為在進行上述操作的時候集合中第 i 和第 i 個元素之后的(n-i)個元素都要執行向后位/向前移一位的操作。實際就是近似O(n)

而LinkedList 采用鏈表存儲,所以插入,刪除元素時間復雜度不受元素位置的影響,都是近似 O(1)

是否支持快速隨機訪問:這個也是由底層實現決定的,LinkedList 不支持高效的隨機元素訪問,而 ArrayList 支持。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應于get(int index)方法)。

內存空間占用:ArrayList的空間浪費主要體現在在list列表的結尾會預留一定的容量空間,而LinkedList的空間花費則體現在它的每一個元素都需要消耗比ArrayList更多的空間(因為要存放prev 指針和next 指針以及數據)。

ArrayList 中的 RandomAccess 接口 是什么?

前面的圖中我們可以看到ArrayList 繼承了三個接口,后面兩個都是比較熟悉的,分別是標識對象可復制和可序列化。

那么RandomAccess 接口代表什么呢?

前面的關于ArrayList 與 LinkedList 的對比當中,有一點就是,

是否支持快速隨機訪問:這個也是由底層實現決定的,LinkedList 不支持高效的隨機元素訪問,而 ArrayList 支持。快速隨機訪問就是通過元素的序號快速獲取元素對象(對應于get(int index)方法)。

RandomAccess 接口 就是用來 標識該類支持快速隨機訪問。 查看源碼可以發現,這個接口內部沒有任何的定義。僅僅是起標識作用。

比如在Collections.binarySearch()方法中,

實現了RandomAccess接口的List使用索引遍歷,而未實現RandomAccess接口的List使用迭代器遍歷。

總結一句話:實現RandomAccess接口的List可以通過for循環來遍歷數據比使用iterator遍歷數據更高效,未實現RandomAccess接口的List可以通過iterator遍歷數據比使用for循環來遍歷數據更高效。當然對于ArrayList來說,for循環遍歷和Iterator方式遍歷差距不大,但是對于LinkedList這種沒有實現的來說,兩種遍歷方式效率差距就有點大了。這主要是因為底層實現不同。

LinkedList 中的 Deque 接口是什么?

與 ArrayList 相對應的,LinkedList 中也有一個值得好好研究的接口,那就是Deque 接口。

Deque - double-ended queue,中文名為雙端隊列。

我們都知道 Queue 是一個隊列,遵循 FIFO 準則,我們也知道 Stack 是一個棧結構,遵循 FILO 準則。 而Deque 這個雙端隊列就厲害了,它既可以實現棧的操作,也可以實現隊列的操作,換句話說,實現了這個接口的類,既可以作為棧使用也可以作為隊列使用

如何作為隊列使用呢? Deque 實現了 Queue,所以 Queue 所有的方法 Deque 都有,下面比較的是Deque區別 Queue 的方法:

Queue Deque
add(e) addLast()
offer(e) offerLast()
remove() removeFirst()
poll() pollFirst()
element() getFirst()
peek() peekFirst()

如何作為棧使用呢? 下面我們來看看下雙端隊列作為棧 Stack使用的時候方法對應關系。

Stack Deque
push(e) addFirst(e)
pop() removeFirst()
peek() peekFirst()

因為篇幅有限,具體實現源碼就不帶大家去分析了。

引一篇好文:搞懂 Java LinkedList 源碼

老調常談 之 ArrayList 擴容機制

這是一個很頻繁的面試點,故記錄一下。

以下是源碼部分。

add()方法開始入手

ensureCapacityInternal(size + 1) 確認當前數組可否容納 size + 1 個元素,如果不夠進行擴容

grow(minCapacity) 這就是具體擴容的邏輯

新容量的大小為 oldCapacity + (oldCapacity >> 1),也就是舊容量的1.5

擴容操作 需要 調用 Arrays.copyOf()這個方法,把原數組整個復制到新數組中,這個操作代價很高,所以 很多地方包括阿里開發手冊上也會建議 在集合初始化的時候就指定好大概的容量大小,減少擴容的次數

ArrayList 與 Vector 對比

ArrayList 與 Vector 的底層實現都是 Object 數組,所以兩者使用和特性上非常類似。

不同的是,

Vector 是線程安全的,內部使用了synchronized 進行同步。這導致了 Vector 性能非常不好。相比較的話,推薦用ArrayList,然后自己控制同步。

Vector 每次擴容都是2 倍大小,而不是1.5

如果是想要達到線程安全的目的,Vector 有其他的替代方案:

使用 Collections.synchronizedList() 得到一個線程安全的ArrayList(這類的Collections.synchronized*() 就是一層Wrapper,看源碼就知道了)

也可以使用J.U.C中的 CopyOnWriteArrayList 讀寫分離,后面的內容會有詳細介紹

參考

搞懂 Java LinkedList 源碼

《碼出高效》

《瘋狂Java講義》

github cs-note

java guide

文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。

轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/75364.html

相關文章

  • Java集合總結【面試題+腦圖】,將知識點一網打盡!

    摘要:而在集合中,值僅僅是一個對象罷了該對象對本身而言是無用的。將這篇文章作為集合的總結篇,但覺得沒什么好寫就回答一些面試題去了,找了一會面試題又覺得不夠系統。 前言 聲明,本文用的是jdk1.8 花了一個星期,把Java容器核心的知識過了一遍,感覺集合已經無所畏懼了!!(哈哈哈....),現在來總結一下吧~~ 回顧目錄: Collection總覽 List集合就這么簡單【源碼剖析】 Ma...

    yearsj 評論0 收藏0
  • 帶你了解集合世界的fail-fast機制 和 CopyOnWriteArrayList 源碼詳解

    摘要:體現的就是適配器模式。數組對象集合世界中的機制機制集合世界中比較常見的錯誤檢測機制,防止在對集合進行遍歷過程當中,出現意料之外的修改,會通過異常暴力的反應出來。而在增強循環中,集合遍歷是通過進行的。 前言 學習情況記錄 時間:week 2 SMART子目標 :Java 容器 記錄在學習Java容器 知識點中,關于List的重點知識點。 知識點概覽: 容器中的設計模式 從Array...

    young.li 評論0 收藏0
  • CopyOnWriteArrayList你都不知道,怎么拿offer?

    摘要:今天主要講解的是本文力求簡單講清每個知識點,希望大家看完能有所收獲一和回顧線程安全的和我們知道是用于替代的,是線程安全的容器。使用迭代器遍歷時不需要顯示加鎖,看看與方法的實現可能就有點眉目了。 前言 只有光頭才能變強 showImg(https://segmentfault.com/img/remote/1460000016931828?w=1120&h=640); 前一陣子寫過一篇C...

    noONE 評論0 收藏0
  • List集合就這么簡單【源碼剖析

    摘要:線程不安全底層數據結構是鏈表。的默認初始化容量是,每次擴容時候增加原先容量的一半,也就是變為原來的倍刪除元素時不會減少容量,若希望減少容量則調用它不是線程安全的。 前言 聲明,本文用得是jdk1.8 前一篇已經講了Collection的總覽:Collection總覽,介紹了一些基礎知識。 現在這篇主要講List集合的三個子類: ArrayList 底層數據結構是數組。線程不安全 ...

    cpupro 評論0 收藏0
  • Java集合問題大匯總

    摘要:集合中成員很豐富,常用的集合有,,等。實現接口的集合主要有。集合中不能包含重復的元素,每個元素必須是唯一的。而以作為實現的構造函數的訪問權限是默認訪問權限,即包內訪問權限。與接口不同,它是由一系列鍵值對組成的集合,提供了到的映射。 原文地址 Java集合 Java集合框架:是一種工具類,就像是一個容器可以存儲任意數量的具有共同屬性的對象。 Java集合中成員很豐富,常用的集合有Arra...

    894974231 評論0 收藏0

發表評論

0條評論

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