Java-集合框架

发表于 更新于 分类于

Java-集合框架

概述

Java集合框架继承结构
Java集合框架继承结构详细

  1. 集合接口：6个接口（短虚线表示），表示不同集合类型，是集合框架的基础。
  2. 抽象类：5个抽象类（长虚线表示），对集合接口的部分实现。可扩展为自定义集合类。
  3. 实现类：8个实现类（实线表示），对接口的具体实现。
  4. Collection 接口是一组允许重复的对象。
  5. Set 接口继承 Collection，集合元素不重复。
  6. List 接口继承 Collection，允许重复，维护元素插入顺序。
  7. Map接口是键－值对象，与Collection接口没有什么关系。
    集合框架的核心是对各种数据结构和算法的封装，我希望在此只列出容器的线程安全等性质，以后有时间再深入源码。

如何对集合框架进行分类

  1. 实现的接口
    Java使用接口来区分不同的数据接口。
  2. 是否ordered
    ordered容器可以利用排序算法进行排序并按顺序读写。
  3. 是否允许元素重复
    容器的基础是一些经典的数据结构，比如Java的HashMap的底层数据结构是散列表，不允许重复元素，而ArrayList的底层——数组——就没有这个限制。
  4. 按是否可插入null值
    是否能插入null值一般和容器的并发安全性有关，因为如果需要对key加锁的话，key就必须不能为null了。

按实现接口

  1. Collection接口
    表示内容元素构成一组相同类型的集合，它们可能是1对1的关系或没有关系，集合主要包含添加、删除、判断、清空、大小等基本操作。
    List，按照插入顺序保存元素
    Set，插入元素不能重复且无序
    Queue，先进先出
  2. Map接口
    键值对的一组映射，内容元素是1对多的关系。
    Map接口有一个内部接口Entry,对集合中的元素定义了一组通用的操作，维护这键值对，可以对键值对进行相应的操作，通过Map接口的entrySet可以返回集合对象的视图集，方便对集合对象进行遍历等操作。Map同样包含添加、删除、判断、清空、大小等基本操作。

按是否ordered

顺序容器指的是元素按链式组织的容器，比如数组、链表（List , RandomAccessList）、队列。还有一种是关联容器，包含Set、Map、Graph，也可以根据没有关系、一对一、一对多、多对多再进行细分。

按是否允许重复

除了Map之外的容器显而易见都是允许重复元素存在的，Set仅仅是将Map的Value替换为了Boolean，而Map按照散列表的原理是不允许重复的。

按是否允许插入null对象

集合框架的设计都是尽可能通用的，所以每个容器都是尽可能地容纳null对象地插入的，但是需要注意：

  • 像PriorityQueue这种插入时需要比较元素之间大小的容器不能插入null；
  • 并发安全容器一般不允许插入null对象，因为操作需要对元素进行加锁等操作；
  • 插入null后，对容器调用查找排序等方法可能会抛出空指针异常；

Collections

搜索

binarySearch
使用二分搜索法搜索指定列表，以获得指定对象，根据二分搜索的要求，该输入列表必须事先排过序，且元素必须实现Comparable接口，它们必须是可比较的，因此基本类型、没有实现Comparable接口的自定义类型都是不能进行排序的。

排序

排序的前提是知道元素之间的大小顺序，一般比较大小顺序时会使用Comparable或Comparator接口，它们在使用方式上有点区别；在比较元素是否相等时会使用equals方法
sort
对容器进行排序，其基本操作和Arrays.sort差不多，只不过Arrays.sort是对数组排序，Collections.sort是对容器内元素进行排序。
它使用什么算法？

容器线程安全化

synchronizedList/Map/Set 相当于一个包装器，为原来不具备线程安全特性的容器添加上线程安全的特性

容器遍历

Iterator

优点：Iterator可以屏蔽不同数据集合的特点，统一遍历集合的接口，而且对于链式存储的容器来说，for循环遍历时间复杂度为O(n^2)，而Iterator只需O(n)
缺点：代码量颇大，特别是Iterator设计模式有很多变体需要考虑，还有fail-fast、fail-safe的问题 

1
2
3
4
5
Iterator iterator = list.iterator();
while (iterator.hasNext()) {
    ...
    iterator.next();
}

fail-fast、fail-safe
是Java集合框架的两种错误机制，注意这样的条件：在使用迭代器扫描的时候，容器中的元素不应该变化。
fail-fast在下面两种情况下会抛出ConcurrentModificationException异常：

  • 单线程中，使用除了ite.remove()之外的方法修改容器结构
  • 多线程中，在一个线程使用迭代器遍历时，另一个线程对这个容器的结构进行了修改 
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    private class Itr implements Iterator<E> {
        int cursor;
        int lastRet = -1;
        int expectedModCount = ArrayList.this.modCount; // 在创建迭代器时的容器大小
        public boolean hasNext() {
            return (this.cursor != ArrayList.this.size);
        }
        public E next() {
            // 检查是否发生了修改
            checkForComodification();
            /** 省略此处代码 */
        }
        public void remove() {
            if (this.lastRet < 0) {
                throw new IllegalStateException();
            }
            // 检查是否发生了修改
            this.checkForComodification();
            // 在迭代器中remove不会抛出异常，因为同时修改了expectedModCount和modCount
            checkForComodification();
            /** 省略此处代码 */
        }
        final void checkForComodification() {
            // 如果链表中剩余元素数和创建迭代器时的不同，抛出异常
            if(ArrayList.this.modCount != this.expectedModCount) {
                throw new ConcurrentModificationException();
            }
        }
    }
    fail-safe 修改前复制一次集合，在复制出的集合上进行修改，虽然不会抛出异常，但是效率也会低很多，而且在频繁修改的时候根本不知道自己在读哪个版本的数据
    现在已知的是一些原本的容器都是fail-fast，包括Collections包装出来的容器（用的是包装的容器的迭代器），在juc包下的容器是fail-safe的（没有仔细验证）。

for循环遍历

优点：按位置读取，比较简单
缺点：效率与容器内部实现相关，如果是链式存储的效率就特别低，这种情况下更好的选择是Iterator，因为Iterator内部维护了当前遍历的位置，所以每次遍历，读取下一个位置并不需要从集合的第一个元素开始查找，只要把指针向后移一位就行了 

1
2
3
for (int i = 0; i < list.size(); i++) {
    list.get(i);
}

foreach

foreach内部也是使用了Iterator，只是编译器帮我们生成了这些代码，可以反编译class文件查看，但是要注意的是容器若没实现Iterator是不能使用foreach遍历的。
优点：屏蔽了显式声明的Iterator和计数器，代码简洁，不易出错
缺点：只能做简单的遍历，不能在遍历过程中操作（删除、替换）数据集合，并且因为每次都要做 类型转换检查 ，所以花费的时间比Iterator略长 

1
2
3
for (ElementType element : list) {
    ...
}

最佳实践

Java数据集合框架中，提供了一个RandomAccess接口，该接口没有方法，只是一个标记。通常被List接口的实现使用，用来标记该List的实现是否支持Random Access。
如果一个数据集合实现了该接口，就意味着它支持Random Access，按位置读取元素的平均时间复杂度为O(1)。
有时候代码中会更改集合的实现，如果想要使用集合的代码总是保持较高的遍历效率，最好进行一次类型判断来选择使用for循环遍历还是Iterator遍历。 

1
2
3
4
5
if (list instanceof RandomAccess) {
    //使用传统的for循环遍历。
} else {
    //使用Iterator或者foreach。
}

性能测试

在性能方面，关注的主要是不同的集合对象在相同的场景下的性能对比状况，场景设计上分为单线程场景和多线程场景。
在单线程下，按照如下场景测试：

  • 测试在不同的集合大小（分别为10、100、1000、10000）下增加、查找及删除100个元素的性能变化情况；

在多线程下，按照如下场景进行测试：

  • 测试在不同的集合大小（分别为10、100、1000、10000）及不同的线程数（分别为10、50、100）的情况下，增加、查找及删除100个元素的性能变化情况；

对需要测试的集合对象，都进行以上场景的性能测试，每个场景均运行10次，取平均值，以尽量保证测试能充分地体现集合对象的性能状况。

List

ArrayList

ArrayList的实现和vector差不多，它的底层是一个数组，相对LinkedList来说随机访问列表的速度较快，同时缺点在于插入删除的效率相对较低，使用capacity域来标志分配的空间大小，如果add的时候发现不够了就会重新分配一次空间。

  • 线程安全：NO
  • null：YES
  • 重复：YES
  • 时间复杂度
    • size O(1) add操作会更新size
    • isEmpty O(1) 只需要判断size==0?
    • get O(1) 因为是数组容器
    • set O(1) 同上
    • add O(n) 需要移动元素
    • remove O(n) 同上

Vector

实现上和ArrayList区别不大，但是由于给增删改查操作添加了synchronized关键字，Vector是线程安全的。

  • 线程安全：YES

LinkedList

  1. 当实现Queue接口的时候，添加了element()/peek()/poll()/offer()/remove()方法
  2. getFirst()/element()和peek()
    • 获取列表第一个元素
    • 列表为空时，element()抛出NoSuchElementException异常,peek()返回null
  3. removeFirst()/remove()和poll()
    • 删除列表第一个元素
    • 列表为空时remove()抛出异常，poll()返回null

LinkedList的底层是一个双向链表，还可以当作栈、队列等，但是实现栈或队列更好的还是ArrayDeque

  • 线程安全：NO
  • null：YES
  • 重复：YES
  • 时间复杂度
    • size O(1)
    • isEmpty O(1)
    • get O(n)
    • set O(n)
    • add O(n) 这里仅讨论任意位置插入的情况
    • remove O(n)

Map

Hashtable

Hashtable原本是过时的一个容器，在Java4中被重写了，实现了Map接口，所以归到集合框架中来了。
这个容器的核心实现和HashMap几乎是一样的，除了两点：它实现了同步、不可以插入null值。
Hashtable也是fail-fast，它并不是使用Iterator实现迭代，而是Enumerator，但是本质上是差不多的，即发现迭代过程中数据被修改即抛出异常。

  • 同步：YES
  • null：NO
  • 重复：NO

HashMap

HashMap是使用分离链接法实现的哈希容器，使用一个大数组存储键值对，靠hash函数计算key来确定键值对的存储位置。 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
/**
 * Constructs an empty <tt>HashMap</tt> with the specified initial
 * capacity and load factor.
 *
 * @param  initialCapacity the initial capacity
 * @param  loadFactor      the load factor
 * @throws IllegalArgumentException if the initial capacity is negative
 *         or the load factor is nonpositive
 */
public HashMap(int initialCapacity, float loadFactor) {
    if (initialCapacity < 0)
        throw new IllegalArgumentException("Illegal initial capacity: " +
                                           initialCapacity);
    if (initialCapacity > MAXIMUM_CAPACITY)
        initialCapacity = MAXIMUM_CAPACITY;
    if (loadFactor <= 0 || Float.isNaN(loadFactor))
        throw new IllegalArgumentException("Illegal load factor: " +
                                           loadFactor);
    this.loadFactor = loadFactor;
    this.threshold = tableSizeFor(initialCapacity);
}

inital capacity（初始容量）初始table大小，当initialCapacity > MAXIMUM_CAPACITY，取最大值MAXIMUM_CAPACITY = 1 << 30 = 1073741824
load factor（负载系数）每个哈希槽（或者说桶）的平均存储元素个数，当存储的元素个数超过capacity * load_factor时将触发容器执行rehash

负载因子能表示一个散列表的空间使用程度，initialCapacity * loadFactory = HashMap的容量，负载因子越大则散列表的装填程度越高，也就是能容纳更多的元素，元素多了，链表大了，所以此时索引效率就会降低；反之，负载因子越小则链表中的数据量就越稀疏，此时会对空间造成浪费，但是索引效率相对的就会高一些。
设置inital_capacity和load_factor需要考虑当前场景下是读频繁还是写频繁，若读频繁，不妨把inital_capacity设置得小一些，迭代遍历时能快一些，若写频繁，不妨设置得大一些，以免经常需要rehash。
hashCode哈希表数据结构需要hash函数来计算出一个key应该被插入到哪个位置，在Java中这个函数是每个类重写的hashCode方法
equalsHash容器不允许重复，当发生冲突时需要使用equals方法来判断key是否重复
红黑树优化，每个哈希槽长度增长到一定程度(8)后会自动转换为红黑树，以提升查询效率。

  • 同步：NO
  • null：YES
  • 重复：NO
  • 时间复杂度
    • get O(n)/Θ(a)/Θ(a/2 + 1) 分别表示最坏、查找失败的平均情况、查找成功的平均情况，其中a代表负载因子，即每个链表中的平均元素个数
    • 其他操作与get类似
    • printAll O(l * a) 其中l表示哈希表的长度
    • resize() 即rehash扩容，initialCapacity和loadFactory会影响到HashMap的扩容，HashMap在每次put操作时都会检查一边size(当前对象数量) > initialCapacity * loadFactor是否成立，如果不成立则HashMap扩容为以前的两倍（数组扩成两倍），然后重新计算每个元素在数组中的位置，然后再进行存储。可见这个过程是比较耗时的，所以最好根据业务预估出HashMap的适当容量，尽量避免频繁的resize()。

      HashMap中的扩容是直接扩容，ConcurrentHashMap中的扩容是渐进式的。

Hashtable 与 HashMap 的简单比较

HashTable 基于 Dictionary 类，而 HashMap 是基于 AbstractMap。
Dictionary 是任何可将键映射到相应值的类的抽象父类，而 AbstractMap 是基于 Map 接口的实现，它以最大限度地减少实现此接口所需的工作。
HashMap 的 key 和 value 都允许为 null，而 Hashtable 的 key 和 value 都不允许为 null。HashMap 遇到 key 为 null 的时候，调用 putForNullKey 方法进行处理，而对 value 没有处理；Hashtable遇到 null，直接返回 NullPointerException。
Hashtable 方法是同步，而 HashMap 则不是。我们可以看一下源码，Hashtable 中的几乎所有的 public 的方法都是 synchronized 的，而有些方法也是在内部通过 synchronized 代码块来实现。
所以有人一般都建议如果是涉及到多线程同步时采用 HashTable，没有涉及就采用 HashMap，但是在 Collections 类中存在一个静态方法：synchronizedMap()，该方法创建了一个线程安全的 Map 对象，并把它作为一个封装的对象来返回。

hashmap 并发下有什么缺点？

HashMap 是非线程安全的，多个线程 put 的时候造成了某个 key 值 Entry key List 的死循环，问题就这么产生了。
Hashcode 是一个 native 方法，是用非 java 语言开发。
哈希表的两大特点：直接定址（locate），解决冲突（散列） 为什么散列时要对 16 取余（h%length），因为这样等价于 a 和（lenth-1）的按位与运算，也就是 h%length<==>h&（length-1），位运算效率高于取余运算效率。
Hashmap 在 1.8 增加了红黑树，主要用于解决链表深度太大，降低查询效率，所以当链表长达大于 8 时会产生红黑树
hashmap 如何扩容？ 当 HashMap 中的元素个数超过数组大小(数组总大小 length，不是数组中个数 size）* loadFactor 时，就会进行数组扩容，loadFactor 的默认值为 0.75，这是一个折中的取值。
也就是说，默认情况下，数组大小为 16，那么当 HashMap 中元素个数超过 16 * 0.75 = 12（这个值就是代码中的 threshold 值，也叫做临界值）的时候，就把数组的大小扩展为 2 * 16 = 32，即扩大一倍，然后重新计算每个元素在数组中的位置，而这是一个非常消耗性能的操作，所以如果我们已经预知 HashMap 中元素的个数，那么预设元素的个数能够有效的提高 HashMap 的性能。

HashSet

HashSet和TreeSet的思路一样，它仅仅对HashMap的接口加了一层包装。

Properties

Properties是Hashtable的子类，主要用于加载配置文件（load()），也可以运行时动态修改配置文件（store()）。

LinkedHashMap

LinkedHashMap是HashMap的子类，它将所有Entry按插入顺序连接起来，主要目的是为了使迭代顺序跟插入顺序相同，保证迭代的时间复杂度只和元素个数相关。
因此实现上和HashMap的差别不大，唯一需要注意的是新增的链表头尾引用header和tail。

WeakHashMap

WeakHashMap使用哈希表来存储弱引用，弱引用的概念在垃圾收集器中出现过，主要用于引用一些有用但不必要的对象，在垃圾回收时会被回收掉，这个特性特别适合于缓存场景。

WeakHashSet

WeakHashSet是不存在的，但是可以通过Collections.newSetFromMap来包装出一个WeakHashSet

Queue

Stack

Java中的Stack类不推荐使用，因为它是一个先进先出的容器，使用链表实现会更好，而设计时却继承了Vector，主要有两点问题：

  • Vector底层是由数组实现的，用add和remove操作来实现push和pop虽然很方便，但是数组是静态的，在容量超出elementData.length后需要重新分配，对效率产生影响
  • 栈本身应该只允许访问栈顶元素，但实现Vector后可以访问任意位置元素，和栈的理念违背
    鉴于此，在使用到栈的地方，最好使用别的比如ArrayDeque来代替

ArrayQueue

ArrayDeque底层是使用循环数组实现的

  • 线程安全：NO
  • null：NO
  • 重复：YES
  • 时间复杂度
    • 都是O(1)
    • 扩容操作没有实现

PriorityQueue

PriorityQueue是使用完全二叉树实现的一个小项堆（小顶堆/最小堆…）
完全二叉树 可以理解为一层一层、从左往右向树上堆节点，可以使用数组实现，区别于完美二叉树

  • 线程安全：NO
  • null：NO 无法比较null和其他元素大小
  • 重复：YES
  • 时间复杂度
    • peek O(1) 取堆顶元而不删除，不需要修改堆结构
    • offer/poll O(log(n)) 需要对堆进行一次上滤/下滤操作调整堆结构
    • remove O(n) remove可以删除任意一个元素，删除前需要遍历一遍定位目标位置

参考

  1. HashMap和ArrayList有什么区别？
    而ArrayList是通过equals来比较的，HashMap是通过hashCode来比较两个对象是否相等的。
    ArrayList允许重复，而HashMap不允许重复。

参考

  1. Why there is no ConcurrentHashSet against ConcurrentHashMap
  2. 《深入理解Java集合框架》系列文章（已全部更新完毕）
  3. 类 Collections
  4. Java中遍历集合的几种方法
  5. 【目录】集合框架目录