Java集合總覽

jopen 10年前發布 | 34K 次閱讀 Java集合 Java開發

這篇文章總結了所有的Java集合（Collection）。主要介紹各個集合的特性和用途，以及在不同的集合類型之間轉換的方式。

Arrays

Array是Java特有的數組。在你知道所要處理數據元素個數的情況下非常好用。java.util.Arrays 包含了許多處理數據的實用方法：

  • Arrays.asList：可以從 Array 轉換成 List。可以作為其他集合類型構造器的參數。

  • Arrays.binarySearch：在一個已排序的或者其中一段中快速查找。

  • Arrays.copyOf：如果你想擴大數組容量又不想改變它的內容的時候可以使用這個方法。

  • Arrays.copyOfRange：可以復制整個數組或其中的一部分。

  • Arrays.deepEquals、Arrays.deepHashCode：Arrays.equals/hashCode的高級版本，支持子數組的操作。

  • Arrays.equals：如果你想要比較兩個數組是否相等，應該調用這個方法而不是數組對象中的 equals方法（數組對象中沒有重寫equals()方法，所以這個方法之比較引用而不比較內容）。這個方法集合了Java 5的自動裝箱和無參變量的特性，來實現將一個變量快速地傳給 equals() 方法——所以這個方法在比較了對象的類型之后是直接傳值進去比較的。

  • Arrays.fill：用一個給定的值填充整個數組或其中的一部分。

  • Arrays.hashCode：用來根據數組的內容計算其哈希值（數組對象的hashCode()不可用）。這個方法集合了Java 5的自動裝箱和無參變量的特性，來實現將一個變量快速地傳給 Arrays.hashcode方法——只是傳值進去，不是對象。

  • Arrays.sort：對整個數組或者數組的一部分進行排序。也可以使用此方法用給定的比較器對對象數組進行排序。

  • Arrays.toString：打印數組的內容。
    • </ul>

    如果想要復制整個數組或其中一部分到另一個數組，可以調用 System.arraycopy方法。此方法從源數組中指定的位置復制指定個數的元素到目標數組里。這無疑是一個簡便的方法。（有時候用 ByteBuffer bulk復制會更快。可以參考這篇文章）.

    最后，所有的集合都可以用T[] Collection.toArray( T[] a ) 這個方法復制到數組中。通常會用這樣的方式調用：

    return coll.toArray( new T[ coll.size() ] );

    這個方法會分配足夠大的數組來儲存所有的集合，這樣 toArray 在返回值時就不必再分配空間了。

    單線程集合

    這一部分介紹的是不支持多線程的集合。這些集合都在java.util包里。其中一些在Java 1.o的時候就有了（現在已經棄用），其中大多數在Java 1.4中重新發布。枚舉集合在Java 1.5中重新發布，并且從這個版本之后所有的集合都支持泛型。PriorityQueue也在Java 1.5中加入。非線程安全的集合架構的最后一個版本是ArrayDeque ，也在Java 1.6中重新發布了。

    List

    • ArrayList：最有用的List集合實現。由一個整形數字或數組存儲了集合的大小（數組中第一個沒有使用的元素）。像所有的List集合一樣，ArrayList可以在必要的時候擴展它的大小。ArrayList訪問元素的時間開銷固定。在尾部添加元素成本低（為常數復雜度），而在頭部添加元素成本很高（線性復雜度）。這是由ArrayList的實現原理——所有的元素的從角標為0開始一個接著一個排列造成的。也就是說，從要插入的元素位置往后，每個元素都要向后移動一個位置。CPU緩存友好的集合是基于數組的。（其實也不是很友好，因為有時數組會包含對象，這樣存儲的只是指向實際對象的指針）。

    • LinkedList：Deque實現：每一個節點都保存著上一個節點和下一個節點的指針。這就意味著數據的存取和更新具有線性復雜度（這也是一個最佳化的實現，每次操作都不會遍歷數組一半以上，操作成本最高的元素就是數組中間的那個）。如果想寫出高效的LinkedList代碼可以使用 ListIterators 。如果你想用一個Queue/Deque實現的話（你只需讀取第一個和最后一個元素就行了）——考慮用ArrayDeque代替。

    • Vector：一個帶有線程同步方法的ArrayList版本。現在直接用ArrayList代替了。
      • </ul>

      Queues/deques

      • ArrayDeque：Deque是基于有首尾指針的數組（環形緩沖區）實現的。和LinkedList不同，這個類沒有實現List接口。因此，如果沒有首尾元素的話就不能取出任何元素。這個類比LinkedList要好一些，因為它產生的垃圾數量較少（在擴展的時候舊的數組會被丟棄）。

      • Stack：一種后進先出的隊列。不要在生產代碼中使用，使用別的Deque來代替（ArrayDeque比較好）。

      • PriorityQueue：一個基于優先級的隊列。使用自然順序或者制定的比較器來排序。他的主要屬性——poll/peek/remove/element會返回一個隊列的最小值。不僅如此，PriorityQueue還實現了Iterable接口，隊列迭代時不進行排序（或者其他順序）。在需要排序的集合中，使用這個隊列會比TreeSet等其他隊列要方便。
        • </ul>

        Maps

        • HashMap：最常用的Map實現。只是將一個鍵和值相對應，并沒有其他的功能。對于復雜的hashCode method，get/put方法有固定的復雜度。

        • EnumMap：枚舉類型作為鍵值的Map。因為鍵的數量相對固定，所以在內部用一個數組儲存對應值。通常來說，效率要高于HashMap。

        • HashTable：舊HashMap的同步版本，新的代碼中也使用了HashMap。

        • IdentityHashMap：這是一個特殊的Map版本，它違背了一般Map的規則：它使用 “==” 來比較引用而不是調用Object.equals來判斷相等。這個特性使得此集合在遍歷圖表的算法中非常實用——可以方便地在IdentityHashMap中存儲處理過的節點以及相關的數據。

        • LinkedHashMap ：HashMap和LinkedList的結合，所有元素的插入順序存儲在LinkedList中。這就是為什么迭代LinkedHashMap的條目（entry）、鍵和值的時候總是遵循插入的順序。在JDK中，這是每元素消耗內存最大的集合。

        • TreeMap：一種基于已排序且帶導向信息Map的紅黑樹。每次插入都會按照自然順序或者給定的比較器排序。這個Map需要實現equals方法和Comparable/Comparator。compareTo需要前后一致。這個類實現了一個NavigableMap接口：可以帶有與鍵數量不同的入口，可以得到鍵的上一個或者下一個入口，可以得到另一Map某一范圍的鍵（大致和SQL的BETWEEN運算符相同），以及其他的一些方法。

        • WeakHashMap：這種Map通常用在數據緩存中。它將鍵存儲在WeakReference中，就是說，如果沒有強引用指向鍵對象的話，這些鍵就可以被垃圾回收線程回收。值被保存在強引用中。因此，你要確保沒有引用從值指向鍵或者將值也保存在弱引用中m.put(key, new WeakReference(value))。
          • </ul>

          Sets

          • HashSet：一個基于HashMap的Set實現。其中，所有的值為“假值”（同一個Object對象具備和HashMap同樣的性能。基于這個特性，這個數據結構會消耗更多不必要的內存。

          • EnumSet：值為枚舉類型的Set。Java的每一個enum都映射成一個不同的int。這就允許使用BitSet——一個類似的集合結構，其中每一比特都映射成不同的enum。EnumSet有兩種實現，RegularEnumSet——由一個單獨的long存儲（能夠存儲64個枚舉值，99.9%的情況下是夠用的），JumboEnumSet——由long[]存儲。

          • BitSet：一個比特Set。需要時常考慮用BitSet處理一組密集的整數Set（比如從一個預先知道的數字開始的id集合）。這個類用 long[]來存儲bit。

          • LinkedHashMap：與HashSet一樣，這個類基于LinkedHashMap實現。這是唯一一個保持了插入順序的Set。

          • TreeSet：與HashSet類似。這個類是基于一個TreeMap實例的。這是在單線程部分唯一一個排序的Set。
            • </ul>

            java.util.Collections

            就像有專門的java.util.Arrays來處理數組，Java中對集合也有java.util.Collections來處理。

            第一組方法主要返回集合的各種數據：

            • Collections.checkedCollection / checkedList / checkedMap / checkedSet / checkedSortedMap / checkedSortedSet：檢查要添加的元素的類型并返回結果。任何嘗試添加非法類型的變量都會拋出一個ClassCastException異常。這個功能可以防止在運行的時候出錯。//fixme

            • Collections.emptyList / emptyMap / emptySet ：返回一個固定的空集合，不能添加任何元素。

            • Collections.singleton / singletonList / singletonMap：返回一個只有一個入口的 set/list/map 集合。

            • Collections.synchronizedCollection / synchronizedList / synchronizedMap / synchronizedSet / synchronizedSortedMap / synchronizedSortedSet：獲得集合的線程安全版本（多線程操作時開銷低但不高效，而且不支持類似put或update這樣的復合操作）

            • Collections.unmodifiableCollection / unmodifiableList / unmodifiableMap / unmodifiableSet / unmodifiableSortedMap / unmodifiableSortedSet：返回一個不可變的集合。當一個不可變對象中包含集合的時候，可以使用此方法。
              • </ul>

              第二組方法中，其中有一些方法因為某些原因沒有加入到集合中：

              • Collections.addAll：添加一些元素或者一個數組的內容到集合中。

              • Collections.binarySearch：和數組的Arrays.binarySearch功能相同。

              • Collections.disjoint：檢查兩個集合是不是沒有相同的元素。

              • Collections.fill：用一個指定的值代替集合中的所有元素。

              • Collections.frequency：集合中有多少元素是和給定元素相同的。

              • Collections.indexOfSubList / lastIndexOfSubList：和String.indexOf(String) / lastIndexOf(String)方法類似——找出給定的List中第一個出現或者最后一個出現的子表。

              • Collections.max / min：找出基于自然順序或者比較器排序的集合中，最大的或者最小的元素。

              • Collections.replaceAll：將集合中的某一元素替換成另一個元素。

              • Collections.reverse：顛倒排列元素在集合中的順序。如果你要在排序之后使用這個方法的話，在列表排序時，最好使用Collections.reverseOrder比較器。

              • Collections.rotate：根據給定的距離旋轉元素。

              • Collections.shuffle：隨機排放List集合中的節點，可以給定你自己的生成器——例如 java.util.Random / java.util.ThreadLocalRandom or java.security.SecureRandom。

              • Collections.sort：將集合按照自然順序或者給定的順序排序。

              • Collections.swap：交換集合中兩個元素的位置（多數開發者都是自己實現這個操作的）。
                • </ul>

                并發集合

                這一部分將介紹java.util.concurrent包中線程安全的集合。這些集合的主要屬性是一個不可分割的必須執行的方法。因為并發的操作，例如add或update或者check再update，都有一次以上的調用，必須同步。因為第一步從集合中組合操作查詢到的信息在開始第二步操作時可能變為無效數據。

                多數的并發集合是在Java 1.5引入的。ConcurrentSkipListMap / ConcurrentSkipListSet 和 LinkedBlockingDeque是在Java 1.6新加入的。Java 1.7加入了最后的 ConcurrentLinkedDeque 和 LinkedTransferQueue

                Lists

                • CopyOnWriteArrayList：list的實現每一次更新都會產生一個新的隱含數組副本，所以這個操作成本很高。通常用在遍歷操作比更新操作多的集合，比如listeners/observers集合。
                  • </ul>

                  Queues/deques

                  • ArrayBlockingQueue：基于數組實現的一個有界阻塞隊，大小不能重新定義。所以當你試圖向一個滿的隊列添加元素的時候，就會受到阻塞，直到另一個方法從隊列中取出元素。

                  • ConcurrentLinkedDeque / ConcurrentLinkedQueue：基于鏈表實現的無界隊列，添加元素不會堵塞。但是這就要求這個集合的消費者工作速度至少要和生產這一樣快，不然內存就會耗盡。嚴重依賴于CAS(compare-and-set)操作。

                  • DelayQueue：無界的保存Delayed元素的集合。元素只有在延時已經過期的時候才能被取出。隊列的第一個元素延期最小（包含負值——延時已經過期）。當你要實現一個延期任務的隊列的時候使用（不要自己手動實現——使用ScheduledThreadPoolExecutor）。

                  • LinkedBlockingDeque / LinkedBlockingQueue：可選擇有界或者無界基于鏈表的實現。在隊列為空或者滿的情況下使用ReentrantLock-s。

                  • LinkedTransferQueue：基于鏈表的無界隊列。除了通常的隊列操作，它還有一系列的transfer方法，可以讓生產者直接給等待的消費者傳遞信息，這樣就不用將元素存儲到隊列中了。這是一個基于CAS操作的無鎖集合。

                  • PriorityBlockingQueue：PriorityQueue的無界的版本。

                  • SynchronousQueue：一個有界隊列，其中沒有任何內存容量。這就意味著任何插入操作必須等到響應的取出操作才能執行，反之亦反。如果不需要Queue接口的話，通過Exchanger類也能完成響應的功能。
                    • </ul>

                    Maps

sesese色