詳細介紹Java容器相關知識全面總結（圖）

Java實用類別庫提供了一套相當完整的容器來幫助我們解決許多具體問題。因為我本身就是Android開發者，包括我在內很多安卓開發，最拿手的就是ListView(RecycleView)+BaseAdapter+ArrayList三劍客, 平時接觸使用的容器也只有ArrayList和HashMap。導致整個Java容器系統的掌握和使用仍停留在很淺的層面。省不足而思改進，那麼就跟著我來總結一下Java容器的相關知識吧。

結構

• java容器類別的繼承結構

• ##具體介紹

• #List

• Set

• #Queue

##迭代器
Collection
Map

一些建議
進階·並發容器
CopyOnWriteArrayList與Copy-On-Write策略
ConcurrentLinkedQueue
ConcurrentHashMap與鎖定分段技術
#阻塞佇列

java容器類別的繼承結構

Java容器類別庫定義了兩個不同概念的容器，Collection和Map

• #Collection

   一個獨立元素的序列，這些元素都服從一條或多條規則。 List必須按照插入的順序保存元素。 Set不能有重複元素。 Queue依照排隊規則來決定物件產生的順序。

(文中Jdk原始碼版本無特殊說明皆為jdk1.8.0_101)

    public interface Collection<E> extends Iterable<E> {
        int size();

        boolean isEmpty();

        boolean contains(Object o);

        Iterator<E> iterator();

        Object[] toArray();

        <T> T[] toArray(T[] a);

        boolean add(E e);

        boolean remove(Object o);

        boolean containsAll(java.util.Collection<?> c);

        boolean addAll(java.util.Collection<? extends E> c);

        boolean removeAll(java.util.Collection<?> c);

        ... //省略了其他方法
    }

可以看到，java定義了Collection介面和內部集合的基本操作方法，Collection預設可以進行對集合末端新增元素，刪除指定元素等操作。 List、Set、Queue介面都繼承自Collection並定義了各自不同的方法。

• Map

   一組成對的」鍵值對」對象，允許我們使用鍵來找出值。

      public interface Map<K,V> {
          int size();
  
          boolean containsKey(Object key);
  
          boolean containsValue(Object value);
  
          V get(Object key);
  
          V put(K key, V value);
  
          V remove(Object key);
  
          void putAll(java.util.Map<? extends K, ? extends V> m);
  
          void clear();
  
          Set<K> keySet();
  
          Collection<V> values();
  
          Set<java.util.Map.Entry<K, V>> entrySet();
  
          interface Entry<K,V> {
              K getKey();
  
              V getValue();
  
              V setValue(V value);
  
              boolean equals(Object o);
  
              int hashCode();
  
              ...
          }
  
          boolean equals(Object o);
  
          int hashCode();
  
      }

Map內部介面Entryb77a8d9c3c319e50d4b02a976b347910對應著Map的鍵值對。

具體介紹

迭代器

先介紹迭代器。迭代器本身也是一種

設計模式，設計的初衷在於：容器的實作由很多種，而我們想對容器進行遍歷操作的話，首先不應該關心容器實現的細節，其次遍歷操作應該是輕量級的。迭代器統一了對容器的存取方式，同時創建它的代價很小。值得注意的是，Iterator只能單向移動。

    public interface Iterator<E> {
        boolean hasNext();

        E next();

        default void remove() {
            throw new UnsupportedOperationException("remove");
        }

        default void forEachRemaining(Consumer<? super E> action) {
            Objects.requireNonNull(action);
            while (hasNext())
                action.accept(next());
            }
    }

透過容器的iterator()方法拿到容器的迭代器

迭代器的next()取得下一個元素

hasNext()判斷是否還有元素
remove()刪除指定元素

ListIterator

ListIterator是Iterator的擴展之內，用於各種List類別訪問，支援雙向移動。

Collection

List

List 承諾可以將元素維護在特定的序列中.List介面在Collection的基礎上加入了大量的方法，使得可以再List中間插入和移除元素。

    public interface List<E> extends Collection<E> {

        ...

        boolean add(E e);

        boolean remove(Object o);

        boolean containsAll(Collection<?> c);

        boolean addAll(Collection<? extends E> c);

        boolean addAll(int index, Collection<? extends E> c);

        boolean removeAll(Collection<?> c);

        boolean retainAll(Collection<?> c);

        E get(int index);

        E set(int index, E element);

        void add(int index, E element);

        E remove(int index);

        int indexOf(Object o);

        int lastIndexOf(Object o);

        java.util.List<E> subList(int fromIndex, int toIndex);

        ...

    }

有兩種類型的List，ArrayList和LinkedList

#List類型##優點底層實作ArrayList#隨機存取元素較快中間元素的插入與刪除較慢LinkedList

		陣列

中間元素的插入與刪除，順序存取的最佳化隨機存取元素較慢

雙向鍊錶

#SetSet類型使用場景底層實作HashSet快速尋找，元素必須定義hashCode()鍊錶

		Set不保存重複的元素，通常用於快速尋找元素。值得一提的是，Set具有與Collection完全一樣的接口，沒有任何額外的功能。 存入的元素必須定義equals()方法
##TreeSet	#保持順序，元素必須實作Comparable介面	紅-黑樹結構

LinkedHashSet#####維護順序的HashSet, 元素必須定義hashCode ()######鍊錶############

Queue

除了并发应用，Queue仅有的两个实现是LinkedList和PriorityQueue, 其中LinkedList同时实现了List, Deque接口。它们的差异在于排序行为而不是性能。

    public interface Queue<E> extends Collection<E> {
        boolean add(E e);

        boolean offer(E e);

        E remove();

        E poll();

        E element();

        E peek();
    }

Map

Map类型	使用场景	底层实现
HashMap	快速查询	散列表
LinkedHashMap	迭代遍历具有顺序(插入顺序 or 最近最少使用)	链表
TreeMap	具有排序，唯一可以返回子树的Map(subMap())	红-黑树结构
WeakHashMap	弱键映射，映射之外无引用的键，可以被垃圾回收	散列表
ConcurrentHashMap	线程安全的Map	链表
IdentityHashMap	使用==代替equals()对键进行排序，专位解决特殊问题	链表

我們可以手動調整HashMap來調整效能，涉及如容量、初始容量、尺寸、負載因子等概念。有興趣的話可以看一些相關資料。

一些建議

• 不要使用過時的容器如Vector Enumeration Hashtable Stack(沒錯，這就是java最初的糟糕設計，實際中使用堆疊的話推薦LinkedList)

進階·並發容器

這裡不會討論的太細緻的實現，僅僅簡單介紹一下基礎知識，感興趣的可以閱讀《Java 並發編程的藝術》這本書。

CopyOnWriteArrayList與Copy-On-Write策略

Copy-On-Write簡稱COW，是一種用於程式設計中的最佳化策略。其基本想法是，從一開始大家都在共享同一個內容，當某個人想要修改這個內容的時候，才會真正把內容Copy出去形成一個新的內容然後再改，這是一種延時懶惰策略。從JDK1.5開始Java並發包裡提供了兩個使用CopyOnWrite機制實現的並發容器,它們是CopyOnWriteArrayList和CopyOnWriteArraySet。 CopyOnWrite容器非常有用，可以在非常多的並發場景中使用。

CopyOnWrite容器即時複製的容器。通俗的理解是當我們往一個容器添加元素的時候，不直接往當前容器添加，而是先將當前容器進行Copy，複製出一個新的容器，然後新的容器裡添加元素，添加完元素之後，再將原容器的引用指向新的容器。這樣做的好處是我們可以對CopyOnWrite容器進行並發的讀取，而不需要加鎖，因為當前容器不會添加任何元素。所以CopyOnWrite容器也是一種讀寫分離的思想，讀寫不同的容器。

CopyOnWrite容器只能保證資料的最終一致性，無法保證資料的即時一致性。所以如果你希望寫入的數據，馬上能讀到，請不要使用CopyOnWrite容器。

ConcurrentLinkedQueue

在並發程式設計中，有時候需要使用執行緒安全的佇列或清單。通常實作執行緒安全有兩種方式，一種是使用阻塞演算法，一種是使用非阻塞演算法。非阻塞演算法實作基礎為循環CAS(Compare and Swipe 比較與交換)。

ConcurrentLinkedQueue技術上的實作與CopyOnWriteArrayList與Copy類似，但是容器只有部分內容而不是整個容器可以被複製和修改。 ConcurrentLinkedQueue有head節點和tail節點組成，每個節點由節點元素(item)和指向下一個結點(next)的引用組成。節點之間透過next關聯起來，形成一張鍊錶結構的隊列。

ConcurrentHashMap與鎖定分段技術

ConcurrentHashMap是線程安全且高效的HashMap。多線程環境下，使用非線程安全的HashMap會導致死循環，而如文章中建議的那樣，HashTable這種過時容器效率低下(使用synchronized來保證線程安全)。 ConcurrentHashMap使用鎖定分段技術，大大提高了並發使用的效率。

鎖定分段技術: 假設容器有多把鎖，每一把鎖用於鎖容器其中一部分數據，當多執行緒存取容器不同資料段資料時，執行緒間就不存在鎖競爭，從而提高並發存取效率。

阻塞佇列

JDK7 提供了7個阻塞佇列，實作原理都是基於生產-消費模式的等待通知機制。

LinkedBlockingQueue由鍊錶結構組成的有界阻塞佇列PriorityBlockingQueue 支援排序的無界阻塞佇列#DelayQueue使用優先權佇列實作的無界阻塞佇列SynchronousQueue不儲存元素的阻塞佇列

阻塞佇列類型
##ArrayBlockingQueue
	##由陣列結構組成的有界阻塞佇列
	優先權

##LinkedTransferQueue######由鍊錶結構組成的無界阻塞佇列############LinkedBlockingQueue######由鍊錶結構組成的雙向阻塞佇列############

以上是詳細介紹Java容器相關知識全面總結（圖）的詳細內容。更多資訊請關注PHP中文網其他相關文章！