Java 性能调优指南之 Java 集合概览

这篇文章总结了所有的Java集合(Collection)。主要介绍各个集合的特性和用途,以及在不同的集合类型之间转换的方式。

【编者按】本文作者为拥有十年金融软件开发经验的 Mikhail
Vorontsov,文章主要概览了所有标准
Java 集合类型。文章系国内
ITOM 管理平台
OneAPM
编译呈现,以下为正文:

Arrays

Array是Java特有的数组。在你知道所要处理数据元素个数的情况下非常好用。java.util.Arrays
包含了许多处理数据的实用方法:

  • Arrays.asList:可以从 Array 转换成
    List。可以作为其他集合类型构造器的参数。
  • Arrays.binarySearch:在一个已排序的或者其中一段中快速查找。
  • Arrays.copyOf:如果你想扩大数组容量又不想改变它的内容的时候可以使用这个方法。
  • Arrays.copyOfRange:可以复制整个数组或其中的一部分。
  • Arrays.deepEqualsArrays.deepHashCode:Arrays.equals/hashCode的高级版本,支持子数组的操作。
  • Arrays.equals:如果你想要比较两个数组是否相等,应该调用这个方法而不是数组对象中的
    equals方法(数组对象中没有重写equals()方法,所以这个方法之比较引用而不比较内容)。这个方法集合了Java
    5的自动装箱和无参变量的特性,来实现将一个变量快速地传给 equals()
    方法——所以这个方法在比较了对象的类型之后是直接传值进去比较的。
  • Arrays.fill:用一个给定的值填充整个数组或其中的一部分。
  • Arrays.hashCode:用来根据数组的内容计算其哈希值(数组对象的hashCode()不可用)。这个方法集合了Java
    5的自动装箱和无参变量的特性,来实现将一个变量快速地传给
    Arrays.hashcode澳门新葡亰网站注册,方法——只是传值进去,不是对象。
  • Arrays.sort:对整个数组或者数组的一部分进行排序。也可以使用此方法用给定的比较器对对象数组进行排序。
  • Arrays.toString:打印数组的内容。

如果想要复制整个数组或其中一部分到另一个数组,可以调用
System.arraycopy方法。此方法从源数组中指定的位置复制指定个数的元素到目标数组里。这无疑是一个简便的方法。(有时候用
ByteBuffer
bulk复制会更快。可以参考这篇文章).

最后,所有的集合都可以用T[] Collection.toArray( T[] a )
这个方法复制到数组中。通常会用这样的方式调用:

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

这个方法会分配足够大的数组来储存所有的集合,这样 toArray
在返回值时就不必再分配空间了。

本文将概览所有标准的 Java
集合类型。我们将按照它们可区分的属性与主要用例进行分类。除此之外,我们还将穷举在不同集合类型之间进行数据转换的方法。

单线程集合

这一部分介绍的是不支持多线程的集合。这些集合都在java.util包里。其中一些在Java
1.o的时候就有了(现在已经弃用),其中大多数在Java
1.4中重新发布。枚举集合在Java
1.5中重新发布,并且从这个版本之后所有的集合都支持泛型。PriorityQueue也在Java
1.5中加入。非线程安全的集合架构的最后一个版本是ArrayDeque ,也在Java
1.6中重新发布了。

数组(Arrays)

数组是 Java
语言内置的唯一集合类型,尤其擅长处理预先知道数量上限的元素集。java.util.Arrays
包含了许多用于处理数组的方法,列举如下:

  • Arrays.asList ——将 array(数组) 转变为
    List(列表),后者可以传值给其他标准的集合构造函数。
  • Arrays.binarySearch ——对有序数组或其分段进行快速查找。
  • Arrays.copyOf ——如果想在扩展数组的同时保存其内容,可调用该方法。
  • Arrays.copyOfRange ——如果需要拷贝整个数组或其分段,可调用该方法。
  • Arrays.deepEquals, Arrays.deepHashCode ——支持嵌套子数组的
    Arrays.equals 或 Arrays.hashCode 版本。
  • Arrays.equals
    ——如果需要比较两个数组是否相等,可调用此方法(不可调用数组自身的
    equals 方法,array.equals
    方法未被重写,因此只会比较对数组的引用,而非其内容。)此方法可以与
    Java 5 中的 boxing(装箱)与 varargs(可变参数)特性并用,以编写类
    equals 方法的简单实现——在比较对象类型之后,将所有类字段都传给
    Arrays.equals 即可。
  • Arrays.fill ——将整个数组或其分段赋值为给定的值。
  • Arrays.hashCode ——计算数组内容的 hashcode 值(数组自身的 hashcode
    方法无法实现此功能。)此方法可以与 Java 5 中的 boxing(装箱)与
    varargs(可变参数)特性并用,以编写类 hashcode
    方法的简单实现——将所有类字段都传给 Arrays.hashcode 即可。
  • Arrays.sort ——根据自然排序(natural
    ordering)规则,对整个数组或其分段进行排序。若要利用已知的 Comparator
    对 Object[] 进行排序,也有一对 Arrays.sort 方法。
  • Arrays.toString ——打印数组的具体内容。

如果需要将部分数组(或整个数组)拷贝到另一个已有数组,你需要调用
System.arraycopy
方法,后者会将源数组中指定位置的给定数量的元素拷贝到目的数组的指定位置。通常,这是在
Java 中拷贝数组内容的最快方式(不过,在某些情况下,你也可以检查一下
ByteBuffer
批量拷贝的速度是否更快)。

最后,还有一点,任何 Collection(集合) 都可以使用 T[]
Collection.toArray( T[] a )
方法拷贝到数组中。此方法调用的常见模式如下:

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

此方法调用会分配足够大的数组以存储整个集合,因此 toArray
不必要分配很大的数组用于返回。

List

  • ArrayList:最有用的List集合实现。由一个整形数字或数组存储了集合的大小(数组中第一个没有使用的元素)。像所有的List集合一样,ArrayList可以在必要的时候扩展它的大小。ArrayList访问元素的时间开销固定。在尾部添加元素成本低(为常数复杂度),而在头部添加元素成本很高(线性复杂度)。这是由ArrayList的实现原理——所有的元素的从角标为0开始一个接着一个排列造成的。也就是说,从要插入的元素位置往后,每个元素都要向后移动一个位置。CPU缓存友好的集合是基于数组的。(其实也不是很友好,因为有时数组会包含对象,这样存储的只是指向实际对象的指针)。
  • LinkedList:Deque实现:每一个节点都保存着上一个节点和下一个节点的指针。这就意味着数据的存取和更新具有线性复杂度(这也是一个最佳化的实现,每次操作都不会遍历数组一半以上,操作成本最高的元素就是数组中间的那个)。如果想写出高效的LinkedList代码可以使用
    ListIterators
    。如果你想用一个Queue/Deque实现的话(你只需读取第一个和最后一个元素就行了)——考虑用ArrayDeque代替。
  • Vector:一个带有线程同步方法的ArrayList版本。现在直接用ArrayList代替了。

单线程集合(Single-threaded collections)

本部分将重点介绍非线程安全(non-thread-safe)集合。这些集合全都存储于
java.util 包中。其中一些集合类型从 Java 1.0
开始就有了,现在已经不再建议使用(deprecated),但大多数集合类型从 Java
1.4 开始启用。枚举集合(Enum collections)自 Java 1.5
开始出现,同时具备所有集合类的泛型支持。PriorityQueue 也是从 Java 1.5
开始启用的。非线程安全集合框架的最新成员是自 Java 1.6 起推出的
ArrayDeque。

Queues/deques

  • ArrayDeque:Deque是基于有首尾指针的数组(环形缓冲区)实现的。和LinkedList不同,这个类没有实现List接口。因此,如果没有首尾元素的话就不能取出任何元素。这个类比LinkedList要好一些,因为它产生的垃圾数量较少(在扩展的时候旧的数组会被丢弃)。
  • Stack:一种后进先出的队列。不要在生产代码中使用,使用别的Deque来代替(ArrayDeque比较好)。
  • PriorityQueue:一个基于优先级的队列。使用自然顺序或者制定的比较器来排序。他的主要属性——poll/peek/remove/element会返回一个队列的最小值。不仅如此,PriorityQueue还实现了Iterable接口,队列迭代时不进行排序(或者其他顺序)。在需要排序的集合中,使用这个队列会比TreeSet等其他队列要方便。

Lists(列表)

  • ArrayList
    ——用处最大的 List 实现。包含一个数组与一个 int
    类型,后者代表了数组中首个未使用元素所在的位置。与其他 List
    一样,ArrayList
    可以在需要的时候进行扩展。此外,元素读取时间固定,在列表尾部更新时成本很小(复杂度是固定的),而在头部更新时成本很高(复杂度是线性增长的),这是因为
    ArrayList
    不变量——所有元素在底层数组中从索引(index)为0处开始,这意味着在插入元素时,插入位置右边的所有元素都要往右移;在移除元素时,移除位置右边的所有元素都要往左移。由于包含数组,该集合类型易于
    CPU 缓存。(不过,也不是特别容易。因为其包含
    Objects,而后者其实是指向实际对象的指针)。
  • LinkedList
    ——Deque 实现,每个 Node(结点)由一个值,以及 prev 与 next
    指针构成。这意味着,元素读取或更新的复杂度是线性增长的(得益于一些优化,这些方法遍历的范围不会超过列表长度的一半,因此,读取或更新成本最高的元素位于列表的中间位置)。如果打算编写运行更快的
    LinkedList 代码,则需要使用 ListIterators。如果想要编写 Queue/Deque
    实现(只需读取首尾两个元素),请转而使用 ArrayDeque。
  • Vector —— ArrayList 先前的版本,包含所有同步方法。请尽量使用
    ArrayList。

Maps

  • HashMap:最常用的Map实现。只是将一个键和值相对应,并没有其他的功能。对于复杂的hashCode methodget/put方法有固定的复杂度。
  • EnumMap:枚举类型作为键值的Map。因为键的数量相对固定,所以在内部用一个数组储存对应值。通常来说,效率要高于HashMap
  • HashTable:旧HashMap的同步版本,新的代码中也使用了HashMap
  • IdentityHashMap:这是一个特殊的Map版本,它违背了一般Map的规则:它使用
    “==”
    来比较引用而不是调用Object.equals来判断相等。这个特性使得此集合在遍历图表的算法中非常实用——可以方便地在IdentityHashMap中存储处理过的节点以及相关的数据。
  • LinkedHashMap
    HashMapLinkedList的结合,所有元素的插入顺序存储在LinkedList中。这就是为什么迭代LinkedHashMap的条目(entry)、键和值的时候总是遵循插入的顺序。在JDK中,这是每元素消耗内存最大的集合。
  • TreeMap:一种基于已排序且带导向信息Map的红黑树。每次插入都会按照自然顺序或者给定的比较器排序。这个Map需要实现equals方法和Comparable/ComparatorcompareTo需要前后一致。这个类实现了一个NavigableMap接口:可以带有与键数量不同的入口,可以得到键的上一个或者下一个入口,可以得到另一Map某一范围的键(大致和SQL的BETWEEN运算符相同),以及其他的一些方法。
  • WeakHashMap:这种Map通常用在数据缓存中。它将键存储在WeakReference中,就是说,如果没有强引用指向键对象的话,这些键就可以被垃圾回收线程回收。值被保存在强引用中。因此,你要确保没有引用从值指向键或者将值也保存在弱引用中m.put(key, new WeakReference(value))

Queues(队列)/deques(双队列)

  • ArrayDeque – Deque implementation based on the array (circular
    buffer) with head/tail pointers. Unlike LinkedList, this class does
    not implement List interface, which means that you can not access
    anything except the first and the last elements. This class is
    generally preferable to LinkedList for queues/deques due to a
    limited amount of garbage it generates (old array will be discarded
    on the extensions).
  • ArrayDeque
    ——基于数组(循环缓冲)的 Deque 实现,带有头/尾(head/tail)指针。与
    LinkedList 不同,该类并不实现 List
    接口,这意味着除了首尾元素,无法读取其他元素。由于该类生成的垃圾较少,在实现队列或双队列时,该类比
    LinkedList 更加适合(老数组在扩展时会被抛弃)。
  • Stack ——后进先出(LIFO)队列。不要在生产代码中使用该类。可用任意 Deque
    实现替代之(ArrayDeque 优先)。
  • PriorityQueue ——基于priority(优先级)堆的队列。采用自然排序或已知的
    Comparator。其主要属性—— poll/peek/remove/element
    方法总是返回队列中最小的余留元素。尽管如此,该队列实现了
    Iterable,不会按照排好的次序(或任何特定次序)迭代队列。如果只需要队列中的最小元素,该队列往往比
    TreeSet
    之类的其他排序集合更可取。

Sets

  • HashSet:一个基于HashMapSet实现。其中,所有的值为“假值”(同一个Object对象具备和HashMap同样的性能。基于这个特性,这个数据结构会消耗更多不必要的内存。
  • EnumSet:值为枚举类型的Set。Java的每一个enum都映射成一个不同的int。这就允许使用BitSet——一个类似的集合结构,其中每一比特都映射成不同的enumEnumSet有两种实现,RegularEnumSet——由一个单独的long存储(能够存储64个枚举值,99.9%的情况下是够用的),JumboEnumSet——由long[]存储。
  • BitSet:一个比特Set。需要时常考虑用BitSet处理一组密集的整数Set(比如从一个预先知道的数字开始的id集合)。这个类用
    long[]来存储bit
  • LinkedHashMap:与HashSet一样,这个类基于LinkedHashMap实现。这是唯一一个保持了插入顺序的Set
  • TreeSet:与HashSet类似。这个类是基于一个TreeMap实例的。这是在单线程部分唯一一个排序的Set

Maps(映射)

  • HashMap
    ——最常见的一种映射实现,将键(key)映射至对应的值(value),仅此而已。如果想要高效率的
    hashcode
    方法,可以考虑
    get/put 方法,它们的复杂度是固定的。
  • EnumMap
    ——带有 enum 键的映射。由于已知最大键数量以及内置的 enum 至 int
    映射,此类的运行速度往往高于 HashMap。
  • Hashtable —— HashMap 先前的同步化版本,在新产品的代码中尽量用
    HashMap 替代之。
  • IdentityHashMap
    —— Map 的超特殊版本,违背了 Map 的通用约定:在比较引用时使用 ==
    而非调用 Object.equals 方法。这一属性使得 IdentityHashMap
    在各种图遍历算法中大显神通——你可以在 IdentityHashMap
    中轻易地存储已经处理过的节点,连同一些无关数据。
  • LinkedHashMap —— HashMap 与 LinkedList
    的结合体,所有元素的插入次序都存储在 LinkedList
    中,也因此,LinkedHashMap
    的条目,键以及值都以插入次序迭代。就每个元素的内存消耗量而已,这是成本最高的
    JDK 集合类型。
  • TreeMap ——基于有序导航型 Map 的红黑树。按照自然次序或给定的键
    Comparator 对条目进行排序。此映射类要求 equals 与
    Comparable/Comparator.compareTo 的实现必须一致。此类实现了一个
    NavigableMap 接口:它允许获得少于或多于给定键的映射;允许获得一个
    prev/next 条目(基于键的排序);允许获得给定范围内的键的映射(这与
    SQL
    的 BETWEEN 操作符基本对应)以及此方法的许多变体。
  • WeakHashMap ——此映射通常用于数据缓存的实现。它将所有键都保存于
    WeakReference,这意味着,如果没有指向这些键对象的强引用,这些键就会被垃圾回收。另一方面,值却用强引用保存。因此,你需要确保不存在从值指向键的引用,或者将值也保存在弱引用中:m.put(key,
    new WeakReference(value))。

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:获得集合的线程安全版本(多线程操作时开销低但不高效,而且不支持类似putupdate这样的复合操作)
  • Collections.unmodifiableCollection / unmodifiableList /
    unmodifiableMap / unmodifiableSet / unmodifiableSortedMap /
    unmodifiableSortedSet:返回一个不可变的集合。当一个不可变对象中包含集合的时候,可以使用此方法。

第二组方法中,其中有一些方法因为某些原因没有加入到集合中:

  • 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:交换集合中两个元素的位置(多数开发者都是自己实现这个操作的)。

Sets(集合)

  • HashSet ——基于带有虚值(每个值的 Object 均相同) HashMap 的 set
    实现。与 HashMap
    的属性相同。也因为这种实现方式,此类消耗的内存比该数据类型实际需要的内存要多。
  • EnumSet
    —— enum 值的集合。在 Java 中,每个 enum 都映射至一个 int 类型:每个
    enum 值映射的 int 都互不相同。这使得 BitSet
    之类的集合结构成为可能,每个 bit 都映射到一个不同的 enum
    值。此类还存在两种实现——包含单个 long 类型(可存储64个 enum
    值,足够覆盖99.9%的用例)的 RegularEnumSet 与包含 long[] 类型的
    JumboEnumSet。
  • BitSet —— bit
    集合。请牢记,可以使用 BitSet 表示整型的稠密集(比如从已知起点开始的
    id)。此类使用 long[] 类型存储 bit。
  • LinkedHashSet ——与 HashSet 类似,此类基于 LinkedHashMap
    类实现。这是以插入次序保存元素的唯一集合类。
  • TreeSet ——与 HashSet 类似,此类基于 TreeMap 实例。这是标准 JDK
    的单线程阵营中唯一的有序集合。

并发集合

这一部分将介绍java.util.concurrent包中线程安全的集合。这些集合的主要属性是一个不可分割的必须执行的方法。因为并发的操作,例如addupdate或者checkupdate,都有一次以上的调用,必须同步。因为第一步从集合中组合操作查询到的信息在开始第二步操作时可能变为无效数据。

多数的并发集合是在Java
1.5引入的。ConcurrentSkipListMap / ConcurrentSkipListSet
LinkedBlockingDeque是在Java 1.6新加入的。Java 1.7加入了最后的
ConcurrentLinkedDequeLinkedTransferQueue

java.util.Collections

就像针对数组的 java.util.Arrays 包一样,java.util.Collections
包提供了许多处理集合的好方法。

本文将要介绍的第一组方法会返回集合的各种视图:

  • Collections.checkedCollection / checkedList / checkedMap /
    checkedSet / checkedSortedMap / checkedSortedSet ——
    会返回集合的视图,在运行时检查所添加元素的类型。如果试图添加类型不兼容的元素,会抛出
    ClassCastException 异常。该功能能有效防止运行时造型(runtime casts)。
  • Collections.emptyList / emptyMap / emptySet
    ——当你需要返回不可变的空集合,而又不想分配任何对象时,此类方法便能派上用场。
  • Collections.singleton / singletonList / singletonMap ——
    返回带有单个条目的不可变 set/list/map。
  • Collections.synchronizedCollection / synchronizedList /
    synchronizedMap / synchronizedSet / synchronizedSortedMap /
    synchronizedSortedSet ——
    返回包含所有同步方法的集合视图(低成本又低效率的多线程方法,仍然不支持put-or-update之类的复合动作)。
  • Collections.unmodifiableCollection / unmodifiableList /
    unmodifiableMap / unmodifiableSet / unmodifiableSortedMap /
    unmodifiableSortedSet——返回集合的不可变视图。当需要实现包含任意集合的不可变对象时尤其有用。

本文介绍的第二组方法都因为相同的原因被排除在集合之外:

  • Collections.addAll
    ——如果要往一个集合添加一定数量的元素或一个数组的内容,调用此方法。
  • Collections.binarySearch —— 与 Arrays.binarySearch 对于
    arrays(数组)的作用相同。
  • Collections.disjoint —— 检查2个集合之间不存在共同的元素。
  • Collections.fill —— 用给定值替换某个列表中的所有元素。
  • Collections.frequency —— 给定集合中有多少元素与给定对象相等。
  • Collections.indexOfSubList / lastIndexOfSubList —— 这些方法与
    String.indexOf(String) / lastIndexOf(String)
    相似,它们会找出给定列表中给定子列表首次或末次出现的情况。
  • Collections.max / min —— 基于自然排序或 Comparator
    找出集合中的最大或最小元素。
  • Collections.replaceAll —— 在给定列表中用某个元素替代另一个元素。
  • Collections.reverse ——
    颠倒给定列表中的元素次序。如果你打算在列表排序之后立即调用此方法,不如在进行元素排序时使用
    Collections.reverseOrder 比较器。
  • Collections.rotate —— 根据给定距离旋转列表中的元素。
  • Collections.shuffle
    ——打乱列表的排序。注意,你可以为此方法提供自己的随机生成器,可以是
    java.util.Random,java.util.ThreadLocalRandom 或
    java.security.SecureRandom。
  • Collections.sort —— 根据自然排序或给定的 Comparator 对列表进行排序。
  • Collections.swap ——
    根据给定的位置交换列表中的2个元素(许多开发者都亲自编写此方法)。