天天看點

聊聊集合

日前,網絡流傳“治療罕見病‘脊髓性肌萎縮症’特效藥物需‘70萬元一支’天價,且國内價格遠高于國外”,引發社會關注。

讓我突然想到了“我不是藥神”,一個抗癌藥物讓外國人賺到了暴利,國内那些所謂的黃牛也從中牟利,這也就讓很多外國人說中國人沒有信仰。的确,從馬斯洛的需求理論來說,的确大部人還在下層。

聊聊集合

談談技術吧

 ArrayList和 Vector 的差別。

這兩個類都實作了 List 接口(List 接口繼承了Collection 接口),他們都是有序集合,即存儲在這兩個集合中的元素的位置都是有順序的,相當于一種動态的數組,我們以後可以按位置索引号取出某個元素,并且其中的資料是允許重複的,這是 HashSet 之類的集合的最大不同處,HashSet 之類的集合不可以按索引号去檢索其中的元素,也不允許有重複的元素(本來題目問的與 hashset 沒有任何關系,但為了說清楚 ArrayList 與 Vector 的功能,我們使用對比方式,更有利于說明問題)。接着才說ArrayList 與 Vector 的差別,這主要包括兩個方面。

  • 同步性:

Vector 是線程安全的,也就是說是它的方法之間是線程同步的,而 ArrayList 是線程式不安全的,它的方法之間是線程不同步的。如果隻有一個線程會通路到集合,那最好是使用 ArrayList,因為它不考慮線程安全,效率會高些;如果有多個線程會通路到集合,那最好是使用 Vector,因為不需要我們自己再去考慮和編寫線程安全的代碼。

備注:對于 Vector&ArrayList、Hashtable&HashMap,要記住線程安全的問題,記住 Vector 與 Hashtable 是舊的,是 java 一誕生就提供了的,它們是線程安全的,ArrayList 與 HashMap 是 java2 時才提供的,它們是線程不安全的。是以,我們講課時先講老的。

  • 資料增長:

ArrayList 與Vector 都有一個初始的容量大小,當存儲進它們裡面的元素的個數超過了容量時,就需要增加 ArrayList與 Vector 的存儲空間,每次要增加存儲空間時,不是隻增加一個存儲單元,而是增加多個存儲單元,每次增加的存儲單元的個數在記憶體空間利用與程式效率之間要取得一定的平衡。Vector 預設增長為原來兩倍,而 ArrayList 的增長政策在文檔中沒有明确規定(從源代碼看到的是增長為原來的 1.5 倍)。ArrayList 與Vector 都可以設定初始的空間大小,Vector 還可以設定增長的空間大小,而 ArrayList 沒有提供設定增長空間的方法。

總結:即 Vector 增長原來的一倍,ArrayList 增加原來的 0.5 倍。

ArrayList

ArrayList底層是由動态數組實作的。動态數組就是長度不固定,随着資料的增多而變長。當執行個體化ArrayList時(比如:List<Integer> intList = new ArrayList<>();),如果不指定它的長度,則預設為10,如下圖:

聊聊集合

當ArrayList增加元素時,它是按照順序從頭部開始往後添加,它是有順序的。如下圖

聊聊集合

如果當添加的元素超過目前數組的長度時,它會新建立一個數組,長度為目前數組的1.5倍,然後将目前數組的元素複制到新的數組,目前數組的記憶體被釋放。如下圖

聊聊集合

根據上圖我們可以發現新的數組由原來的長度10變為現在的15.

    我們知道,數組是用來存儲固定大小的同類型元素,數組存放位置是在jvm的堆中。當有新的元素需要存儲時,都會存儲在最前面,是以每次存儲,所有的元素都會向後移動位置。同理,如果删除一個元素,後面的元素都會向前移動一個位置。是以,ArrayList在存儲和删除的時候效率比較低。

    但是由于每個元素占用的記憶體相同且是連續排列的,是以在查找的時候,根據元素的下标可以迅速通路數組中的任意元素,查詢效率非常高。

LinkedList

LinkedList底層是由雙向連結清單的資料結構實作的。

聊聊集合

由上圖可以看到:雙向連結清單是由三個部分組成:prev、data、next.

prev:由用來存儲上一個節點的位址;

data:是用來存儲要存儲的資料;

next:是用來存儲下一個節點的位址。

聊聊集合

上圖可以看出雙向連結清單每個元素之間的聯系。我故意将每個連結清單畫的分布不均勻是因為它不像數組一樣是連續排列的,雙向連結清單是可以占用一段不連續的記憶體空間。

當我們有新元素插入時,隻需要修改所要插入位置的前一個元素的next值和後一個元素的prev值即可。比如我們在資料2與資料6之間插入一個資料4的元素,那麼隻需要修改資料2的next值和資料6的prev值。如下圖

聊聊集合

删除也是同理,比如要删除資料8的元素,隻需要修改資料7的next值和資料9的prev值即可,然後資料8沒有元素指向它,它就成了垃圾對象,最後被回收。是以在增加和删除的時候隻需要更改前後元素的next和prev值,效率非常高。但是在查詢的時候需要從第一個元素開始查找,直到找到我們需要的資料為止,是以查詢的效率比較低。