摘要:類庫中提供了一套相當完整的容器類來解決這個問題,其中基本類型有,,,,這些對象類型被稱為集合類。但是,類庫中使用了來指代集合類中的子集,,,所以集合類也被稱為容器。五類型是能夠將對象映射到其他對象的一種容器,有區別于的方法。
引言
如果一個程序只包含固定數量的且其生命周期都是已知對象,那么這是一個非常簡單的程序——《think in java》
了解容器前,先提出一個問題,ArrayList和LinkedList誰的處理速度更快呢?
一 持有對象的方式在Java中,我們可以使用數組來保存一組對象。但是,數組是固定大小的,在一般情況下,我們寫程序時并不知道將需要多少個對象,因此數組固定大小對于編程有些受限。
java類庫中提供了一套相當完整的容器類來解決這個問題,其中基本類型有List,Queue,Set,Map,這些對象類型被稱為集合類。但是,Java類庫中使用了Collection來指代集合類中的子集{List,Queue,Set},所以集合類也被稱為容器。容器提供了完善的方法來保存對象。
二 類型安全的容器java采用泛型保證我們不會向容器中插入不正確的類型,但是java的泛型只存在于程序源碼中,在經過編譯器編譯就會將類型擦除。舉一個例子:
//經過編譯前 Listlist = new ArrayList<>(); list.add("ok"); System.out.println(list.get(0)); //經過編譯后 List list = new ArrayList(); list.add("ok"); System.out.println((String)list.get(0));
這樣做的好處是:在編寫程序的時候,不會將其他非導出類型的對象添加到容器中。
三 List數組存儲多個對象的原因是它提前聲明了能存儲多少對象。那容器又是如何實現存儲不定多對象的呢?
//ArrayList部分源碼 private static final int DEFAULT_CAPACITY = 10; private static final Object[] EMPTY_ELEMENTDATA = {}; private transient Object[] elementData; private int size; public ArrayList(int initialCapacity) { super(); if (initialCapacity < 0) throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity); this.elementData = new Object[initialCapacity]; } public ArrayList() { super(); this.elementData = EMPTY_ELEMENTDATA; } public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; } private void ensureCapacityInternal(int minCapacity) { if (elementData == EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } private void ensureExplicitCapacity(int minCapacity) { modCount++; // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); } private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
我們可以看到,在ArrayList類中有一個elementData數組。當使用無參構造函數時數組長度默認為空,當向ArrayList加入對象時,會調用一個方法來判斷數組是否能放下這個對象。當數組為空時設置數組長度為10并申請相應大小空間,當數組已滿時,最少重新申請原數組大小1.5倍的空間(除非達到int類型最大值-8)。而在LinkedList中卻沒有采用這種方式,而是采用鏈表方式。
//LinkedList add方法 void linkLast(E e) { final Nodel = last; final Node newNode = new Node<>(l, e, null); last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; }
在LinkedList中,他的add方法調用了linkLast方法,直接在鏈表后邊加入一個新的節點。
四 SetSet類型不保存重復的元素。判斷對象元素是否相等采用的是equals方法,所以在存入自定義的對象時,如果重寫equals方法依賴于可變屬性,將會導致一些問題。
五 MapMap類型是能夠將對象映射到其他對象的一種容器,有區別于List的get方法。HashSet類中包含了一個HashMap對象,HashSet的實現依靠HashMap。
HashMap的實現采用了數組鏈表的方式,即數組的每一個位置都存放的是鏈表頭。查找會先通過key的hash找到對應數組下標,再在該數組下標所對應的鏈表中找到是否有對應對象,查找方式為equals方法。
HashMap如果存儲的鍵值對大于設定值,會自動進行擴容并且對已經存入的鍵值對進行重排序,一次擴容的大小是當前數組長度的兩倍。
//HashMap擴容 public V put(K key, V value) { //other... addEntry(hash, key, value, i); return null; } void addEntry(int hash, K key, V value, int bucketIndex) { if ((size >= threshold) && (null != table[bucketIndex])) { resize(2 * table.length); hash = (null != key) ? hash(key) : 0; bucketIndex = indexFor(hash, table.length); } //other... }六 Queue
隊列是一種典型的先進先出的容器,LinkedList實現了Queue接口。PriorityQueue實現了優先級隊列。ArrayDeque是一個用數組實現雙端隊列的類,我們來看一下ArrayDeque類中的一些方法。
//ArrayDeque構造方法 public ArrayDeque() { elements = (E[]) new Object[16]; } public ArrayDeque(int numElements) { allocateElements(numElements); } private void allocateElements(int numElements) { int initialCapacity = MIN_INITIAL_CAPACITY; if (numElements >= initialCapacity) { initialCapacity = numElements; initialCapacity |= (initialCapacity >>> 1); initialCapacity |= (initialCapacity >>> 2); initialCapacity |= (initialCapacity >>> 4); initialCapacity |= (initialCapacity >>> 8); initialCapacity |= (initialCapacity >>> 16); initialCapacity++; if (initialCapacity < 0) // Too many elements, must back off initialCapacity >>>= 1;// Good luck allocating 2 ^ 30 elements } elements = (E[]) new Object[initialCapacity]; }
上邊的代碼是ArrayDeque的構造方法,可以看到,當沒有定義大小時,ArrayDeque默認數組大小為16,而定義大小后,會調用allocateElements方法,這個方法的作用是:當給定長度小于最小長度8時,使用最小長度。若大于等于最小長度,則找到比給定長度大的最小的2的冪數。為什么要是2的冪數呢?原因有以下兩點:
操作系統分配內存的方法使用伙伴系統的話,每一塊的大小都是2的冪數,如果分配的內存大小為2的冪數,可以減少內存分配的時間。
伙伴系統在百度百科中的解釋:http://baike.baidu.com/view/4...
在ArrayDeque的addFirst方法中不固定將頭放在數組的第一位,而是循環移位。使用2的冪數能夠有效判斷頭部所在的地址。
同樣在第二點中,如果隊列滿了,數組擴充是將容量capacity值左移一位即可擴充一倍。
public void addFirst(E e) { if (e == null) throw new NullPointerException(); elements[head = (head - 1) & (elements.length - 1)] = e; if (head == tail) doubleCapacity(); } private void doubleCapacity() { assert head == tail; int p = head; int n = elements.length; int r = n - p; // number of elements to the right of p int newCapacity = n << 1; if (newCapacity < 0) throw new IllegalStateException("Sorry, deque too big"); Object[] a = new Object[newCapacity]; System.arraycopy(elements, p, a, 0, r); System.arraycopy(elements, 0, a, r, p); elements = (E[])a; head = 0; tail = n; }七 List的選擇
在文章開頭提出了一個問題,數組實現的List快還是鏈表實現的List快。模擬一下試試:
public static void add() { long start = 0; long end = 0; Listalist = new ArrayList<>(); List llist = new LinkedList<>(); System.out.println("ArrayList添加1000萬數據所需毫秒數"); start = System.currentTimeMillis(); for (int i=0; i<10000000; i++) { alist.add(i); } end = System.currentTimeMillis(); System.out.println(end-start); System.out.println("LinkedList添加1000萬數據所需毫秒數"); start = System.currentTimeMillis(); for (int i=0; i<10000000; i++) { llist.add(i); } end = System.currentTimeMillis(); System.out.println(end-start+" "); System.out.println("ArrayList從1000萬數據刪除數據所需毫秒數"); start = System.currentTimeMillis(); alist.remove(0); alist.remove(2000000); alist.remove(4000000); alist.remove(6000000); alist.remove(8000000); alist.remove(9999994); end = System.currentTimeMillis(); System.out.println(end - start); System.out.println("LinkedList從1000萬數據刪除數據所需毫秒數"); start = System.currentTimeMillis(); llist.remove(0); llist.remove(2000000); llist.remove(4000000); llist.remove(6000000); llist.remove(8000000); llist.remove(9999994); end = System.currentTimeMillis(); System.out.println(end - start+" "); System.out.println("ArrayList從1000萬數據查找數據所需毫秒數"); start = System.currentTimeMillis(); alist.contains(0); alist.contains(2000000); alist.contains(4000000); alist.contains(6000000); alist.contains(8000000); alist.contains(10000000); end = System.currentTimeMillis(); System.out.println(end - start); System.out.println("LinkedList從1000萬數據查找數據所需毫秒數"); start = System.currentTimeMillis(); llist.contains(0); llist.contains(2000000); llist.contains(4000000); llist.contains(6000000); llist.contains(8000000); llist.contains(10000000); end = System.currentTimeMillis(); System.out.println(end - start+" "); }
可以看到,無論在何種情況下,數組實現的list都比鏈表快。當我在ArrayList構造方法中設置數組初始大小1000萬時,ArrayLIst添加數據的速度慢了下來,降到5000毫秒左右,所以一般情況下不需要優化。
簡單容器類圖:
Java的容器分為兩類,一類是Collection,一類是Map。collection中包含三種集合類型:Set,List,Queue。
如果想要set中的數據有序,請使用TreeSet。
HashTable和Vector是線程安全的,但是不建議使用,請使用java.util.concurrent包下的容器。
HashMap允許key/value值為null。
更多文章:http://blog.gavinzh.com
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/64423.html
摘要:允許從任一方向來遍歷對象,并在遍歷迭代過程中進行修改該對象,還能獲得迭代器的當前位置。這個構造函數是將返回了一個對象給,這也是的存儲實現原理。 一、容器產生的原因 1.數組的缺點:大小一旦給定就無法更改,除非復制到一個新的數組中,開銷大;而容器類都可以自動地調整自己的尺寸。 2.容器功能的多樣性:容器可以實現各種不同要求,如按不同依據將元素進行排序或者保證容器內無重復元素等等。關...
摘要:誕生之初,是單線程的。當接收到服務端的響應之后,便通過回調函數執行之后的操作。沖鋒基于事件驅動。擁有攔截請求消息推送靜默更新地理圍欄等服務。控制時處于兩種狀態之一終止以節省內存監聽獲取和消息事件。支持的所有事件五銷毀瀏覽器決定是否銷毀。 這次體驗一種新的博客風格,我們長話短說,針針見血。 showImg(https://segmentfault.com/img/remote/14600...
摘要:動態編程使用場景通過配置生成代碼,減少重復編碼,降低維護成本。動態生成字節碼操作字節碼的工具有,其中有兩個比較流行的,一個是,一個是。 作者簡介 傳恒,一個喜歡攝影和旅游的軟件工程師,先后從事餓了么物流蜂鳥自配送和蜂鳥眾包的開發,現在轉戰 Java,目前負責物流策略組分流相關業務的開發。 什么是動態編程 動態編程是相對于靜態編程而言的,平時我們討論比較多的靜態編程語言例如Java, 與動態...
摘要:如果一個程序只包含固定數量且其生命周期都是已知的對象,那么這是一個非常簡單的程序。 如果一個程序只包含固定數量且其生命周期都是已知的對象,那么這是一個非常簡單的程序。 1.泛型和類型安全的容器 通過使用泛型,可以在編譯期防止將錯誤類型的對象放置到容器中. 2.基本概念 Java容器類庫的用途是保存對象,并將其劃分為兩個不同的概念:Collection,Map. Collection...
閱讀 2097·2023-04-26 00:09
閱讀 3115·2021-09-26 10:12
閱讀 3481·2019-08-30 15:44
閱讀 2863·2019-08-30 13:47
閱讀 922·2019-08-23 17:56
閱讀 3226·2019-08-23 15:31
閱讀 475·2019-08-23 13:47
閱讀 2508·2019-08-23 11:56