【Java高级】Java常用集合特性及查找大全

本文为原创文章，转载请注明出处
查看[Java]系列内容请点击：https://www.jianshu.com/nb/45938443

java.util 中的常用集合

类型	类	父类	存储数据类型	存储算法	扩容策略	线程安全性	特点
列表	ArrayList	List	数组	顺序存储	数组满则扩容为原来1.5倍长度数组	不安全	随机查找效率高，修改效率低
列表	LinkedList	List/Deque(双端队列)	链表	顺序存储，带头尾指针	实时扩容	不安全	随机查找效率低，修改效率高
列表	Vector	List	数组	顺序存储	数组满则扩容为原来2倍长度数组	安全	各方面效率低于ArrayList，已不建议使用
集	HashSet	Set	HashMap（key为该集合的值，value为固定值）	直接存储到HashMap	与HashMap扩容一致	不安全	值允许为null，存储结果无序
集	TreeSet	Set/SortedSet	默认为TreeMap，可自定义排序Map	树形存储，红黑树结构	实时扩容	不安全	不允许值为null，存储结果根据比较器排序
队列	ArrayDeque	Deque	数组	数组顺序存储，带头尾指针	数组满则扩展为原来的2倍	不安全	由于只能对首尾进行操作，效率较高
队列	PriorityQueue	Queue	数组	最小堆(根据比较器比较排序)	数组满则扩展为原来的2倍	不安全	一般用于实现优先算法
映射	HashMap	Map	Node<K,V>[] table(数组)	1:根据hashCode计算存储在数组中的位置; 2:使用链表存储hashCode冲突的Node; 3:当链表长度超过7转为红黑树存储冲突的Node	数组内容填充程度达到负载因子(默认0.75)则扩充2倍，并重新散列	不安全	查找效率较高，内容无序，根据hashCode+equals确定唯一的key
映射	TreeMap	SortedMap	树形	红黑树存储(可自定义比较器)	实时扩容	不安全	查找效率高，内容有序，根据hashCode+equals+comparator确定唯一的key
映射	Hashtable	Map/Dictionary	数组	同HashMap	同HashMap	安全	已经不建议使用
映射	EnumMap	Map	定容量数组	以枚举类型下标为hash值存储	不扩容	不安全	专门针对枚举类型的key
映射	LinkedHashMap	Map/HashMap	用HashMap实现，与HashMap一致	在HashMap基础上增加了链表，按顺序链接先后存储的数据	与HashMap一致	不安全	由于每次访问、新增之后都会将最近被访问的内容移到链表的头部，所以可以通过复写removeEldestEntry来实现LRU算法，在缓存管理中非常有用
映射	WeakHashMap	Map	弱引用数组	与HashMap一致	与HashMap一致	不安全	存储数据在一次内存回收之后将不可达(会存储到弱引用队列中并等待回收)

看不清没关系，看图：

点击查看大图

与线程相关的常用集合(java.util.concurrent)

下面的所有类都是线程安全的

BlockingQueue家族

主要用于【生产者-消费者】模式，有线程负责生产，有线程负责消费，可以根据策略选择队列满了生产线程或者队列空了消费线程是否等待等。

BlockingQueue具有一些公共方法来对队列实现读写：

	不可读写时抛出异常	不可读写时返回特定值	不可读写时阻塞	不可读写时超时阻塞
插入	add(e)	offer(e)	put(e)	offer(e,time,unit)
删除	remove()	poll()	take()	poll(time,unit)
查询	element()	peek(e)

相关的子类：

类	父类	存储数据类型	存储算法	特点
ArrayBlockingQueue	BlockingQueue	数组	先入先出队列	使用一个ReentrantLock锁控制队列的读写，必须指定队列容量，一般在多线程使用(见程序-1)
LinkedBlockingQueue	BlockingQueue	链表	先入先出链表队列	分别使用两个锁控制加入和删除数据操作，比ArrayBlockingQueue的吞吐量高
PriorityBlockingQueue	BlockingQueue	数组	最小堆（可指定比较器）	使用一个锁控制读写，优先队列，出队列顺序已排序
DelayQueue	BlockingQueue	数组（PriorityQueue）	最小堆（通常使用延迟时间比较）	使用一个锁控制读写，优先队列，出队列顺序已排序，但是这个是一个让线程先延迟后执行的队列，需要的等待时间越短越靠近堆顶

还有一个是LinkedBlockingDeque与LinkedBlockingQueue类似，只不过是双端队列。

点击查看大图

程序-1：

import java.util.Random;
import java.util.concurrent.ArrayBlockingQueue;

public class Main {
    public static void main(String[] args) throws Exception {
        ArrayBlockingQueue<Integer> queue = new ArrayBlockingQueue<Integer>(5); // 容量最大5个

        // 制造一个消费线程
        new Thread(() -> {
            while (true) {
                try {
                    Integer i = queue.take();
                    System.out.println("get value: " + i);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
            }
        }).start();

        Thread.sleep(1000); // 先让上面线程跑一会儿

        // 在本线程生产
        Random random = new Random();
        for (int i = 0; i < 10; i++) {
            queue.put(random.nextInt(1000));
            Thread.sleep(1000);
        }
    }
}

Concurrent家族

Concurrent家族还有ConcurrentHashMap(高并发线程安全HashMap)、ConcurrentLinkedQueue、ConcurrentLinkedDeque、ConcurrentSkipListSet、ConcurrentSkipListMap等，这里需要特别说明的是，ConcurrentSkipListSet、ConcurrentSkipListMap使用跳表而不是红黑树来建立数据结构，跳表可以有效加快大量并发的情况下的查找效率。

写时复制的集合

写时复制大家都知道什么意思，这里就不再赘述，列出来两个集合：

CopyOnWriteArrayList: 写时复制列表
CopyOnWriteArraySet: 写时复制集