JAVA

Java Collection框架概述

[TOC]

JAVA集合框架可以是说是JAVA开发中使用次数最高的一套类，是JAVA对各种数据结构的实现。一个集合代表一组对象，使用集合框架可以独立于实现细节来操作这一组对象，而不用自己再造轮子。

集合接口概要：

集合接口

再加上并发库中的集合接口：

所有集合接口

在下面的标题中用concurrent标记这个类是java.util.concurrent包中的集合

List （since 1.2）

有序列表，代表一组有序可重复对象。

实现类：

List实现类

Vector（since 1.0）：

与ArrayList实现基本类似，都是用Object数组存储，区别在于Vector是线程安全的，而且Vector扩容策略也比较老式：

newCapacity = oldCapacity + ((capacityIncrement > 0) ? capacityIncrement : oldCapacity) (容量成倍增加)

如果构造时指定了capacityIncrement 扩容增量，则每次增加capacityIncrement (线性增加)。

该类完全可以使用Collections.synchronizedList(new ArrayList())代替。

JDK1.0当初的集合设计主要模仿C++的STL，可惜1.0的时候没有泛型(Java泛型与C++的模板本质上是不同的，不可相提并论)，同时又为了线程安全加了synchronized锁，重点是当初没有面向接口设计整个集合框架，最终导致了这个不伦不类的设计。

Stack（since 1.0）：

“后进先出(LIFO)”的栈式结构，继承自Vector，这也决定了它被淘汰的命运：因为Deque接口的实现类可以作为栈使用

查看Deque接口

ArrayList（since 1.2）：

数组实现的List，自动扩容，Java8.0中一般扩容策略为newCapacity = oldCapacity + (oldCapacity >> 1)，也就是说每次扩容新容量为原始容量的1.5倍，另外在第一次添加元素的时候才申请内存(默认初始容量为10)。

ArrayList绝对是集合框架中使用次数最多的类。

LinkedList（since 1.2）：

双向链表实现的List，在后续Java版本中又相继实现了Queue，Deque接口，所以该类可以当作链表、队列、栈使用。

因为LinkedList使用双向链表实现，所以作为List使用其查找元素效率不如ArrayList，但是在中间插入元素的效率比ArrayList高。

更多内容查看Queue和Deque接口。

CopyOnWriteArrayList（since 1.5，concurrent）：

通过拷贝数组来保证写线程不会影响到读线程(实现所谓的读写分离)，所以该类允许读写同时进行；

同时使用ReentrantLock来实现多线程执行写操作的同步。

但是拷贝数组毕竟耗时，因此该类不适合用在写操作频繁的情况。

Map （since 1.2）

把Map放在前面是因为，Set的实现类是基于Map或List实现的。

表示一系列键值对映射(Key-Value)的集合，由于Map通过Key来查找Value，所以Key不能重复。

实现类：

Map实现类

Hashtable（since 1.0）：

哈希表，与HashMap实现原理相同，都是使用链式地址法解决哈希碰撞的。

与HashMap的区别：

  • Hashtable使用synchronize关键字实现线程安全的，而HashMap不能保证线程安全；这一点与Vector相同
  • Hashtable不允许Key为null(会抛空指针异常)，而HashMap允许。

Hashtable基本被淘汰，Java的后续版本都没有对其升级。

更多相关内容可以查看HashMap

Propreties（since 1.0）：

严格的说，这个类不能算是容器类。这个类一般用于存取属性配置文件的，该类实际上是一个Hashtable<Object,Object>对象。

1
public class Properties extends Hashtable<Object,Object>

HashMap（since 1.2）：

HashMap在集合框架中的地位举足轻重，所以Java在每个版本中都对它进行了大大小小的性能优化。

HashMap对计算hash值的优化

哈希表，根据Key生成hashCode从而确定存储位置，时间复杂度为1，获取哈希值方法如下：

1
2
3
4
5
static final int hash(Object key) {
        int h;
        // 低位与高位异或，目的是让HashMap的bucket较小时，高位也能参与哈希取余
        return (key == null) ? 0 : (h = key.hashCode()) ^ (h >>> 16);
}

对于hash相同的元素(也就是哈希碰撞)使用链表(拉链法)进行延伸存储，拉链使用头插法。

当总体容量达到数组长度的0.75倍这个默认阈值后，重新定容，将数组长度扩大到原来的两倍，并将原来的数据重新计算hash存入新表中，这个过程叫做rehash。

HashMap重新定容耗时耗资源，所以如果能确定存取元素的最大容量，最好在构造时通过initialCapacity参数来指定容量，**默认初始容量为16($2^4$)**。

同时也可以通过构造方法中的loadFactor参数来自定义扩容因子，默认扩容因子为0.75。

另外，**HashMap的容量始终保持为$2^n$**。这样设计为了方便直接根据哈希值定位索引(用&位运算取代%取余运算)：

index = (length - 1) & hash

当$length=2^n$时，length-1的二进制为全1，(length-1) & hash​可以达到取余的效果。

所以在通过initialCapacity参数指定构造时的容量，会有下面这个运算：

1
2
3
4
5
6
7
8
9
10
11
12
// initialCapacity指定为5，6，7的时候，实际容量都为8
static final int tableSizeFor(int cap) {
    int n = cap - 1;
    // 从最高位的1开始，后面的全是1
    n |= n >>> 1;
    n |= n >>> 2;
    n |= n >>> 4;
    n |= n >>> 8;
    n |= n >>> 16;
    // 最后在全1的数上加1，从而得到2^n
    return (n < 0) ? 1 : (n >= MAXIMUM_CAPACITY) ? MAXIMUM_CAPACITY : n + 1;
}

官方文档中将这个延伸的链表称为桶，个人觉得还是叫“拉链”更为形象。下面当拉链进化成红黑树的时候，叫“拉链”就有点不合适了。

Java8中使用红黑树对拉链法进行优化

当出现所有的元素都集中在一条拉链上的极端情况时，HashMap就退化成链表，导致查找性能下降。

我们知道红黑树能够实现$log_2(N)$级别的查找速度，所以Java8使用红黑树对拉链进行了优化。

在HashMap中有这么几个常量：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
/**
 * 当拉链长度增长到8的时候，HashMap会将这条拉链转成红黑树
 */
static final int TREEIFY_THRESHOLD = 8;

/**
 * 当拉链长度缩短到6的时候，HashMap又会把红黑树转换回拉链
 */
static final int UNTREEIFY_THRESHOLD = 6;

/**
 * 只有当HashMap的数量达到64的时候才会进行红黑树转换
 *
 * 以避免数量较少的时候刚转成红黑树添加几个元素后又需要rehash
 */
static final int MIN_TREEIFY_CAPACITY = 64;

WeakHashMap（since 1.2）：

使用上与HashMap类似，区别在于这里的Entry对象(Key-Value对)继承自WeakReference。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
public class WeakHashMap<K,V> extends AbstractMap<K,V> implements Map<K,V> {
    // GC回收key之后，会把key对应的Entry放到这个队列中
    // WeakHashMap每次都会检查这个队列，把被GC回收的Entry清除掉
    private final ReferenceQueue<Object> queue = new ReferenceQueue<>();
    ...
    private static class Entry<K,V> extends WeakReference<Object> implements Map.Entry<K,V> {
        V value;  // 节点存储的值
        final int hash; // 缓存hash值,避免重复计算hash值
        Entry<K,V> next; // 下一个节点,主要用于拉链
        Entry(Object key, V value, ReferenceQueue<Object> queue, // 这里传入引用队列
              int hash, Entry<K,V> next) {
            super(key, queue); // 引用的对象和队列
            ...
        }
        ...
    }
}

也就是说Entry中持有Key的弱引用，从而不影响GC的垃圾回收，Key被系统回收后会自动将Entry放入引用队列。WeakHashMap每次读写操作都会遍历这个引用队列，从而把已过期的Entry对象从表中删除。

另外WeakHashMap与HashMap计算hash的算法也略有不同：

1
2
3
4
5
final int hash(Object k) {
    int h = k.hashCode();
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

WeakHashMap也进行了二次幂优化：hash & (length-1)

IdentityHashMap（since 1.4）：

与HashMap功能相同，区别在于IdentityHashMap使用k1 == k2判断key是否相同，也就是k1和k2是同一个对象的引用才认为是同一个key；

而HashMap则是(k1 == null ? k2 == null ：k1.equals(k2) )，也就是两个对象满足内容相同就认为是同一个key。

根据上述特性，IdentityHashMap允许Key重复。

所以IdentityHashMap允许两个内容相同的对象作为Key，另外获取与HashMap获取哈希值的方式不同：

1
2
3
4
private static int hash(Object x, int length) {
	int h = System.identityHashCode(x); // 使用的是对象的地址(暂且理解为地址)
	return ((h << 1) - (h << 8)) & (length - 1);
}

LinkedHashMap（since 1.4）：

LinkedHashMap继承自HashMap，在HashMap的基础上，通过维护一个双向链表来保存元素插入的顺序。

根据该双向链表就可以知道哪些数据是存入时间较长的，所以LinkedHashMap可以用作数据的LRU缓存(可以通过重载removeEldestEntry方法来定义缓存策略)。

下面是一个使用LinkedHashMap实现的最简单Least recently used缓存。

1
2
3
4
5
6
7
public class LruCache extends LinkedHashMap {
    private static final int MAX_ENTRIES = 100;

    protected boolean removeEldestEntry(Map.Entry eldest) {
      return size() > MAX_ENTRIES;
    }
}

EnumMap（since 1.5）：

元素只能是枚举类，构造EnumMap时指定枚举类型。底层使用数组实现存储，所以数据比较紧凑。Key不允许为null。使用相对比较少。

TreeMap（since 1.2）：NavigableMap的实现类。查看NavigableMap接口实现类。

ConcurrentHashMap（since 1.5，concurrent）：ConcurrentMap的实现类。查看ConcurrentMap接口实现类。

ConcurrentSkipListMap（since 1.6，concurrent）：ConcurrentNavigableMap的实现类。查看ConcurrentNavigableMap接口实现类。

Android中还提供了一个数组实现的ArrayMap。HashMap将Key-Value包装成一个类对象，然后使用该类的数组。而ArrayMap直接将Key-Value放在一个Object数组中，通过2*n，2*n+1来对Key-Value进行区分，这和EnumMap在一定程度有有点相似。

SortedMap(since 1.2)与NavigableMap(since 1.6)

SortedMap在Map的基础上对Key自动排序

方法方法说明
Comparator<? super K> comparator()返回该Map中Key使用的比较器
SortedMap<K,V> headMap(K toKey)头：小于toKey的所有Key-Value对，不包括toKey
SortedMap<K,V> tailMap(K fromKey)尾：大于fromKey的所有Key-Value对，包括fromKey
SortedMap<K,V> subMap(K fromKey, K toKey)fromKey到toKey之间的所有Key-Value对，包括fromKey，不包括toKey。
K firstKey()第一个Key，也就是最小的Key
K lastKey()最后一个Key，也就是最大的Key

SortedMap实现类：

SortMap实现类

NavigableMap在SortedMap的基础上添加了更多的有序Map的操作。下图是NavigableMap增加的操作，更多细节可以查看Java官方文档。

NaviableMap增加的操作

NavigableMap实现类：

NavigableMap实现类

TreeMap（since 1.2）：

通过红黑树（一种自平衡二叉查找树树）实现的有序Map映射，因为红黑树的元素查找类似于二分查找，所以保证了增删改查等方法的时间复杂度$log_2(N)$。

因为元素是有序存储，所以需要实现Comparable接口或者在构造方法中指定Comparator比较器。

因为元素之间需要进行比较，所以TreeMap不允许元素为null(会抛空指针异常)。

ConcurrentSkipListMap可以查看ConcurrentNavigableMap接口的实现类。

ConcurrentMap （since 1.5）与ConcurrentNavigableMap （since 1.6）

在Map的基础上添加了一些原子操作，从而实现无锁数据结构，具有多线程高并发特性，更多内容可以查看这篇文章。

方法等价操作
V putIfAbsent(K key, V value)
if (!map.containsKey(key))
    return map.put(key, value);
 else
    return map.get(key);
boolean remove(Object key, Object value)
if (map.containsKey(key) && Objects.equals(map.get(key), value)) {
    map.remove(key);
    return true;
 } else
    return false;
boolean replace(K key, V oldValue, V newValue)
if (map.containsKey(key) && Objects.equals(map.get(key), oldValue)) {
    map.put(key, newValue);
    return true;
 } else
    return false;
V replace(K key, V value)
if (map.containsKey(key)) {
    return map.put(key, value);
 } else
    return null;

ConcurrentMap 实现类：

ConcurrentMap实现类

ConcurrentNavigableMap是ConcurrentMap与NavigableMap的结合体：既有序又高并发。

ConcurrentHashMap（since 1.5，concurrent）：

该类用来代替Hashtable实现多线高并发操作。与Hashtable相比支持高并发的读取操作，Hashtable由于所有的方法都加上了同步锁(包括读取操作)，而ConcurrentHashMap对读取操作不加锁，对写入操作的关键部分加同步锁，进而降低锁粒度，所以在多线程操作的效率上ConcurrentHashMap比Hashtable更加高效。

ConcurrentSkipListMap（since 1.6，concurrent）：

ConcurrentNavigableMap接口的唯一实现类。该数据结构使用跳跃链表实现，跳跃链表是一种查找速度与二叉查找树相当的数据结构，基于多级并联的链表实现，相较二叉查找树要消耗更多的内存资源，但实现起来比二叉查找树简单的多。关于跳跃链表的更多细节可以查看维基百科。

Set （since 1.2）

无序集合，代表一组无序不可重复的对象。与数学中的集合特性类似：无序性，互异性。

Set 实现类：

Set的实现类

HashSet（since 1.2）：

一个底层由HashMap实现的无序集合。只使用了HashMap的Key，而没有使用Value，HashSet的所有元素的Value都是一个Object常量：private static final Object PRESENT = new Object();。因为HashMap允许Key为null，所以HashSet中的元素也允许为null。

LinkedHashSet（since 1.4）：

底层由LinkedHashMap实现。LinkedHashSet继承自HashSet，该类只有四个构造函数，这四个构造函数都是调用HashSet的这个构造函数(该构造方法包内私有)：

1
2
3
HashSet(int initialCapacity, float loadFactor, boolean dummy) {
    map = new LinkedHashMap<>(initialCapacity, loadFactor);
}

EnumSet（since 1.5）：

只存储枚举类型的Set。根据具体的枚举类型，可以得到枚举类中的所有枚举值，进一步就确定这个集合最大的容量了。EnumSet就直接把所有枚举值放到一个数组，然后通过类似于BitSet的位图算法并借助枚举类值的ordinal作为索引来标记集合中是否有对应的枚举值。按照枚举类的大小它分成了两种实现，枚举值个数小于64的直接用一个long进行标记，这就是RegularEnumSet的实现；枚举值个数大于64的，则用long[]进行标记，这就是JumboEnumSet的实现。

EnumSet的静态方法

CopyOnWriteArraySet（since 1.5，concurrent）：

基于CopyOnWriteArraySet实现的无序集，与CopyOnWriteArrayList一样不适合写操作频繁的场合。由于底层使用数组实现，所以它的查找速度不如HashSet。

ConcurrentSkipListSet可以查看NavigableSet接口。

SortedSet （since 1.2）与NavigableSet （since 1.6）

SortedSet ：有序集合，在Set基础上提供排序功能，由于Set基本上都是使用Map实现的(除了上面提到的EnumSet)，所以SortedSet的排序功能也来自于SortedMap。

方法方法说明
Comparator<? super K> comparator()返回该Set元素使用的比较器
SortedSetheadSet(E toElement)头：小于toElement的所有元素，不包括toElement
SortedSettailSet(E fromElement)尾：大于fromElement的所有元素，包括fromElement
SortedSetsubSet(E fromElement, E toElement)fromElement到toElement之间的所有元素对，包括fromElement，不包括toElement。
E first()第一个元素，也就是最小的元素
E last()最后一个元素，也就是最大的元素

NavigableSet： 在SortedSet的基础上添加了更多的有序Set的操作。下图是NavigableSet增加的操作，更多细节可以查看Java官方文档。

NavigableSet增加的操作

NavigableSet实现类：

SortSet的实现类

TreeSet（since 1.2）：

底层由TreeMap实现，与HashSet一样只使用Key不使用Value，Value都是同一个对象：private static final Object PRESENT = new Object();

ConcurrentSkipListSet（since 1.6，concurrent）：

基于ConcurrentSkipListMap实现的有序集，因为ConcurrentSkipListMap支持并发操作，ConcurrentSkipListSet也支持并发操作。

Queue （since 1.5）

队列示意图
在普通集合的基础上添加了一些队列操作：

操作失败抛出异常失败返回false
入队add(e)offer(e)
出队remove()poll()
检查element()peek()

看Queue的实现类之前，先来看一张Queue的继承图

Queue继承图

Queue这个接口仿佛就是为了并发库而设计的，所以Queue的实现类也几乎都是支持多线程的。

Queue实现类：

Queue的实现类

PriorityQueue（since 1.5）：

优先级队列，使用数组实现二叉堆(完全二叉树)，从而对元素进行排序，队列中的元素需要实现Comparable接口或者在构造方法中指定Comparator比较器。

ConcurrentLinkedQueue（since 1.5，concurrent）：

无界限非阻塞的并发队列，使用了非阻塞同步算法(CAS)实现无锁数据结构，该类与BlockingQueue接口的实现类不同，BlockingQueue通过线程阻塞来实现生产者与消费者的同步，而无锁数据结构不会导致线程阻塞。关于CAS的内容可以参考这篇文章。

BlockingQueue （since 1.5，concurrent）

阻塞队列。在Queue的基础上进行阻塞扩展，如果队列为空读取元素会阻塞，如果队列已满添加元素会阻塞。用生产者消费者模式来解释就是：当生产者向队列添加元素但队列已满时，生产者会被阻塞；当消费者从队列移除元素但队列为空时，消费者会被阻塞。阻塞队列是线程间通信常用的手段。

BlockingQueue方法的总结
抛出异常返回false阻塞超时
入队add(e)offer(e)put(e)offer(e, time, unit)
出队remove()poll()take()poll(time, unit)
检查element()peek()无需该操作无需该操作

实现类：

BlockingQueue实现类

ArrayBlockingQueue（since 1.5，concurrent）：

数组实现的阻塞队列，数组大小不会自动增长。队列已满，生产者线程阻塞。元素不允许为null。

DelayQueue（since 1.5，concurrent）：

使用PriorityQueue与ReentrantLock实现的延时阻塞队列，该集合存储的元素需要实现Delayed接口，该集合通过Delayed接口来获取元素对应的延时时长。元素不能为null。

LinkedBlockingQueue（since 1.5）：

单向链表实现的阻塞队列，该集合功能上类似与ArrayBlockingQueue。LinkedBlockingQueue可以在构造方法中指定最大容量，如果没有指定则为Integer.MAX_VALUE，相当于不限容，所以LinkedBlockingQueue相比ArrayBlockingQueue有更大的吞吐量。元素不允许为null。

PriorityBlockingQueue（since 1.5）：

在PriorityQueue的基础上对读写操作加重入锁(ReentrantLock)来达到多线程的同步。

SynchronousQueue（since 1.5）：

这个类是一个比较奇葩的容器，或许不能称其为容器，因为它是一个0容量的队列，不像ArrayBockingQueue和LinkedBlockingQueue那样有缓冲区，SynchronousQueue没有缓冲区，内部直接通过TransferQueue(公平模式)或TransferStack(不公平模式)来进行生产者与消费者的数据传递（这是Java6之后的实现方式），公平模式使生产者(或消费者)线程排队依次添加(或取出)，而费公平模式允许恶性竞争，使用SynchronousQueue可以让生产者线程与消费者线程之间的同步：生产者生产一个消费者就消费一个。SynchronousQueue不允许添加null元素。
公平模式下的SynchronousQueue示意图

Deque （since 1.6）

Deque示意图
双端队列，两端都支持插入删除。既可以把它当Queue用又可以把它当Stack用。

第一元素（头）最后元素（尾）
抛出异常返回false抛出异常返回false
插入addFirst(e)offerFirst(e)addLast(e)offerLast(e)
删除removeFirst()pollFirst()removeLast()pollLast()
检查getFirst()peekFirst()getLast()peekLast()

实现类：

Deque实现类

LinkedList（since 1.2）：双向链表实现双端队列，前面已经提过了。

ArrayDeque（since 1.6）：

数组实现的双端队列。容量按两倍的方式自动增长。不允许元素为null。双端队列既可以当栈用又可以当队列用，作为栈使用速度比Stack类更快，作为队列用速度比LinkedList类更快。

ConcurrentLinkedDeque（since 1.5，concurrent）：

无界限非阻塞的并发双端队列，与ConcurrentLinkedQueue一样使用非阻塞同步算法实现。

LinkedBlockingDeque（since 1.7，concurrent）：

BlockingDeque接口的实现类。查看BlockingDeque接口

BlockingDeque （since 1.6）

BlockingDeque与Deque的关系类似于BlcokingQueue与Queue的关系。

BlockingDeque方法的总结
第一元素（头）
抛出异常返回false阻塞超时
插入addFirst(e)offerFirst(e)putFirst(e)offerFirst(e, time, unit)
删除removeFirst()pollFirst()takeFirst()pollFirst(time, unit)
检查getFirst()peekFirst()无需该操作无需该操作
最后元素（尾）
抛出异常返回false阻塞超时
插入addLast(e)offerLast(e)putLast(e)offerLast(e, time, unit)
删除removeLast()pollLast()takeLast()pollLast(time, unit)
检查getLast()peekLast()无需该操作无需该操作

实现类：

  • java.util.concurrent包
    • LinkedBlockingDeque（since 1.7）：双向链表实现的双端阻塞队列。与LinkedBlockingQueue类似，只是说这个类还可以当作栈使用。

TransferQueue （since 1.7）

在BlockingQueue的基础上更进一步，生产者会一直阻塞直到所添加到队列的元素被某一个消费者所消费（不仅仅是添加到队列里就完事）。这个和SynchronousQueue有点类似，但区别在于SynchronousQueue只允许一个生产者线程将数据传递给一个消费者线程，其他线程想要添加或取出数据就会阻塞；而TransferQueue可以允许多个生产者线程同时与多个消费者线程进行数据传递，所以当我们把TransferQueue的容量设为0时TransferQueue就等价于SynchronousQueue了。

返回值方法说明
intgetWaitingConsumerCount()
返回调用BlockingQueue.take()或BlockingQueue.poll消费者方法而阻塞的消费者的数量
booleanhasWaitingConsumer()
true是否有消费者正在调用BlockingQueue.take()或BlockingQueue.poll消费者方法
voidtransfer(E e)
将元素e转交给消费者，如有必要该方法阻塞以等待消费者将元素e消费。
booleantryTransfer(E e)
如果可以立即将元素e转交给等待的消费者返回true，否则返回false。
booleantryTransfer(E e, long timeout, TimeUnit unit)
如果可以在指定时间内将元素转交给消费者返回true，否则返回false。
**实现类：**
  • java.util.concurrent包
    • LinkedTransferQueue（since 1.7）：TransferQueue接口唯一的一个实现类，相关功能可以查看TransferQueue接口的定义。注意的是LinkedTransferQueue.size()方法与大多数集合不一样，该类没有成员变量中没有保存容器的size，size()方法会临时性的去遍历整个链表来计算元素个数，所以这是个非常耗时的操作，而且由于遍历过程中可能有另外的线程操作，所以该方法获取的size可能是不准确的。

Collections工具类

Collections工具类中的包装类

Collections.unmodifiable 不可修改包装类

经过unmodifiable方法包装的集合对象将成为只读对象，对只读的集合进行add，remove等修改操作将会抛出异常。这个方法使用场景比较广泛。比如说一个公司(Company)有一个字段为员工表(employeeList)，同时有一个获取员工表的方法List getEmployeeList()，我们希望员工的删减只能通过Company类中的指定方法来修改，List getEmployeeList()方法返回员工表但是不能被外部修改，此时就需要使用unmodifiableList对employeeList进行包装了。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public class Company {
	private List<Employee> employeeList;

	// 增加员工
	public void addEmployee(Employee newEmployee) {
		employeeList.add(newEmployee);
	}
	// 删除员工
	public void removeEmployee(Employee fireEmployee) {
		employeeList.remove(fireEmployee);
	}
	// 该方法返回的员工表只读，不允许外部对员工表进行修改。
	public List<Employee> getEmployeeList() {
		return Collections.unmodifiableList(employeeList);
	}
}

public class Employee {
	private String name;
	private int age;

	...
}

Collections中的unmodified方法有以下几个：

  • public static <T> Collection<T> unmodifiableCollection(Collection<? extends T> c)
  • public static <T> List<T> unmodifiableList(List<? extends T> list)
  • public static <T> Set<T> unmodifiableSet(Set<? extends T> s)
  • public static <T> SortedSet<T> unmodifiableSortedSet(SortedSet<T> s)
  • public static <T> NavigableSet<T> unmodifiableNavigableSet(NavigableSet<T> s)
  • public static <K,V> Map<K,V> unmodifiableMap(Map<? extends K, ? extends V> m)
  • public static <K,V> SortedMap<K,V> unmodifiableSortedMap(SortedMap<K, ? extends V> m)
  • public static <K,V> NavigableMap<K,V> unmodifiableNavigableMap(NavigableMap<K, ? extends V> m)

这与Google Guava中的Immutable集合工具类有点类似。

Collections.synchronized 同步包装类

synchronized包装后的集合是线程同步的，比如ArrayList对象可以经过synchronizedList方法进行包装从而达到线程同步的目的，有了这个线程同步的包装类，ArrayList可以完全替代Vector。

  • public static <T> Collection<T> synchronizedCollection(Collection<T> c)
  • public static <T> List<T> synchronizedList(List<T> list)
  • public static <T> Set<T> synchronizedSet(Set<T> s)
  • public static <T> SortedSet<T> synchronizedSortedSet(SortedSet<T> s)
  • public static <T> NavigableSet<T> synchronizedNavigableSet(NavigableSet<T> s)
  • public static <K,V> Map<K,V> synchronizedMap(Map<K,V> m)
  • public static <K,V> SortedMap<K,V> synchronizedSortedMap(SortedMap<K,V> m)
  • public static <K,V> NavigableMap<K,V> synchronizedNavigableMap(NavigableMap<K,V> m)

Collections.checked 动态类型检查包装类

这主要归咎于Java的类型擦除(Java的泛型与C++的泛型不同，准确的说C++应该叫做“模板”，C++在编译后会根据模版的使用情况生成多套可执行代码，而Java使用同一套代码)。Java集合实际存储的时候都是使用Object数组，集合中不保存集合元素的数据类型，所以在源代码中你会看到类似下面的代码：

1
2
3
4
@SuppressWarnings("unchecked")
E elementData(int index) {
    return (E) elementData[index];
}

因此Java对于List list = new ArrayList<String>()这样的赋值也不会报错。而此时我们往list中添加任何类型的数据都没有影响list.add(1) list.add(true)，但是我们本意是想往该集合中添加String类型的数据。这个时候就可以使用checked动态类型检查了。拿上面的那个公司与员工表的例子，现在我们可以通过getEmployeeList获取员工表并对员工表进行修改。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
public class Company {
	private List<Employee> employeeList = new ArrayList<>();

	// 直接返回员工表对象，外部能够添加删除员工
	public List<Employee> getEmployeeList() {
		return employeeList;
	}
}

public class Employee {
	private String name;
	private int age;
	...
}

客户调用时可能会做出这样的操作

1
2
3
4
5
6
7
8
public class Client {
	public static void main(String[] args) {
		Company alibaba = new Company();
		List list = alibaba.getEmployeeList();
		list.add(1);  	// 这明显是错误的操作，但是程序照样能正常运行
		list.add(true);
	}
}

上面的用户很显然执行了一个不正确的操作，但是程序照样能够运行，不会报错。此时我们就可以进行动态类型检查。

1
2
3
4
5
6
7
public class Company {
	private List<Employee> employeeList = new ArrayList<>();

	public List<Employee> getEmployeeList() {
		return Collections.checkedList(employeeList, Employee.class);
	}
}

这样就能确保用户只能往员工表中添加员工，而不能添加其他元素了。

Collections中的checked方法有以下几个：

  • public static <E> Collection<E> checkedCollection(Collection<E> c, Class<E> type)
  • public static <E> List<E> checkedList(List<E> list, Class<E> type)
  • public static <E> Set<E> checkedSet(Set<E> s, Class<E> type)
  • public static <E> SortedSet<E> checkedSortedSet(SortedSet<E> s, Class<E> type)
  • public static <E> NavigableSet<E> checkedNavigableSet(NavigableSet<E> s, Class<E> type)
  • public static <K, V> Map<K, V> checkedMap(Map<K, V> m, Class<K> keyType, Class<V> valueType)
  • public static <K,V> SortedMap<K,V> checkedSortedMap(SortedMap<K, V> m, Class<K> keyType, Class<V> valueType)
  • public static <K,V> NavigableMap<K,V> checkedNavigableMap(NavigableMap<K, V> m, Class<K> keyType, Class<V> valueType)
  • public static <E> Queue<E> checkedQueue(Queue<E> queue, Class<E> type)

Collections类中的简单工具方法

  1. 列表逆序

    1
    public static void reverse(List<?> list)

  2. 列表填充

    1
    public static <T> void fill(List<? super T> list, T obj)

  3. 列表拷贝

    1
    public static <T> void copy(List<? super T> dest, List<? extends T> src)

  4. 列表元素交换

    1
    public static void swap(List<?> list, int i, int j)

  5. 计算集合中元素出现次数

    1
    public static int frequency(Collection<?> c, Object o)

  6. 集合元素是否相交

    1
    public static boolean disjoint(Collection<?> c1, Collection<?> c2)

  7. 集合最大值，最小值

    1
    2
    3
    4
    public static <T extends Object & Comparable<? super T>> T min(Collection<? extends T> coll)
    public static <T extends Object & Comparable<? super T>> T max(Collection<? extends T> coll)
    public static <T> T max(Collection<? extends T> coll, Comparator<? super T> comp)
    public static <T> T min(Collection<? extends T> coll, Comparator<? super T> comp)

  8. 集合元素替换

    1
    public static <T> boolean replaceAll(List<T> list, T oldVal, T newVal)

  9. 添加若干元素

    1
    public static <T> boolean addAll(Collection<? super T> c, T... elements)

  10. 查找子列表

    1
    2
    public static int indexOfSubList(List<?> source, List<?> target)
    public static int lastIndexOfSubList(List<?> source, List<?> target)

Collections类中的算法

排序算法

Collections直接调用list.sort方法，该方法底层调用Arrays类中的排序算法。

1
2
public static <T extends Comparable<? super T>> void sort(List<T> list)
public static <T> void sort(List<T> list, Comparator<? super T> c)

关于排序算法可以先参考常见排序算法及Java实现和SinglePivotQuickSort与DualPivotQuickSort及其JAVA实现。

二分查找算法

1
2
int binarySearch(List<? extends Comparable<? super T>> list, T key)
public static <T> int binarySearch(List<? extends T> list, T key, Comparator<? super T> c)

洗牌算法

1
2
public static void shuffle(List<?> list)
public static void shuffle(List<?> list, Random rnd)

列表旋转算法

1
2
3
// 列表的旋转可能不好理解，你把list想象成一个环。
// 环的旋转就相当于把list的尾部放到头部，头部放到尾部，注意这和列表的逆序不一样。
public static void rotate(List<?> list, int distance)

Collections中的适配器

Collections集合中使用对象的适配器模式实现并提供了两个适配器，分别可以将Map适配成Set，Deque适配成Stack。

1
2
public static <E> Set<E> newSetFromMap(Map<E, Boolean> map)    // 将Map适配成Set (SetFromMap)
public static <T> Queue<T> asLifoQueue(Deque<T> deque)    // 将Deque适配成Stack (AsLIFOQueue)

本作品采用 知识共享署名 4.0 国际许可协议 进行许可。

转载时请注明原文链接：https://blog.hufeifei.cn/2017/05/Java/JavaCollection/

鼓励一下
支付宝微信