Java集合框架之Collection

1.Collection的类结构

输入图片说明

Collection接口定义了增加元素、删除元素、包含判断、获取元素个数、交集、获取元素分离器、转成流、转成数组等操作。但是注意它没有包含获取元素的方法,这是因为有的实现类可以随机访问,有的不可以随机访问(只能靠逐个遍历获取)。记住Collection的接口定义,就基本掌握了集合的大部分能力。下图是Collection接口中定义的方法:

输入图片说明

在Java 8之前,Collection提供了获取外部迭代器方法(iterator),利用外部迭代器,就可以遍历集合里面的元素,然后对每个元素进行操作。到了Java 8,Collection又提供了内部迭代方法(forEach),利用内部迭代器,我们只要告诉内部迭代器要对每个元素做什么操作,怎么遍历就完全交给集合自己了,此时遍历对于使用者是透明的。这两个方法都是定义在Collection的父接口——Iterable。利用外部迭代器Iterator遍历集合有两个问题,一是使用者要写一堆业务无关的遍历代码,二是只能单线程处理任务。而内部迭代只要写业务代码,还可以充分利用多线程并行处理任务,最大限度利用现代的多核处理器。下面是两段对比代码(提供一个点的集合,让每个点都向右向上各平移1个单位的距离):

外部迭代(for-each语法糖,取代先获取Iterator再遍历的写法):

List pointList = Arrays.asList(new Point(1,2),new Point(2,3));
for(Point p:pointList) {
	p.translate(1,1);
}

内部迭代(只要写业务代码,不需要写迭代代码):

List pointList = Arrays.asList(new Point(1,2),new Point(2,3));
pointList.forEach(p -> p.translate(1,1));

看上面的类结构图,可以看到Collection分为三大类:

  • List:有序集合,元素可重复。可以随机访问(增删改查都叫访问)。
  • Set:无序集合,元素不可重复。更像数学概念中的集合,可以进行复杂的集合运算,比如交集、并集、差集……但是不能随机访问。
  • Queue:队列,满足广泛存在的生产者-消费者业务模型。子接口Deque是双向队列,除了可以实现队列模型,还可以实现栈模型。

下面我们再逐一分析常用的实现类。


2.List实现类

List是有序集合,元素可重复。可以随机访问(增删改查都叫访问)。应用场景非常广泛。

List较常用的实现类有ArrayList、LinkedList、Vector、Stack、CopyOnWriteArrayList……

ArrayList是基于数组实现的。基于数组实现的容器一定会涉及到容量(capacity)问题。ArrayList有确定的容量,它的默认初始容量是10,实例化的时候也可以自己指定。等到需要扩容的时候,容量变为原来两倍。所以在初始化的时候,要充分考虑扩容带来的性能问题。ArrayList基于数组实现,可以通过索引访问数据,所以随机访问效率很高。但是如果要往中间增加或删除一个元素,后面的元素下标全部要改变(本质上是重建索引),这时效率很低。所以它非常适合处理那种只顺序添加数据的场景。ArrayList没有进行同步,是线程不安全的。

LinkedList是基于双向链表实现的。因此它的容量不会受到限制。因为缺少索引,必须逐个遍历比对,所以它的随机访问性能比较差。但是如果往中间插一个元素或删一个元素,只要更改前后两个元素的指针即可,此时性能比ArrayList高。LinkedList也没有进行同步,是线程不安全的。

Vector也是基于数组实现的,提供的接口能力和ArrayList差不多。默认初始容量是10,扩容之后变为原来容量的1.5倍。Vector有个扩展类Stack,Stack提供了实现栈模型的方法。这两个类都是同步的,也就是线程安全的。具有很大的同步开销,一般很少用。

CopyOnWriteArrayList是Java并发包下的一个实现类,是支持高并发的线程安全实现类。看名称就知道,它也是基于数组实现的。但是它进行了读写分离,当要修改集合中的数据时,先copy一份数据出来,然后在备份数据中修改,修改好了再合并。读数据的时候没有同步,所以有可能读到的是老数据,但是最终能读到最新数据。这个类适合要求高性能,但是不要求严格一致性的场景。

再介绍两个知识点:

  1. 利用Collections这个工具类可以实现基本的线程安全集合:
List list = Collections.synchronizedList(new ArrayList());
  1. 在 Java 9 中,Java 标准类库提供了一系列的静态工厂方法,比如,List.of()、Set.of(),大大简化了构建小的容器实例的代码量。
List simpleList = List.of("Hello","world");

3.Set实现类

Set是无序集合,元素不可重复。主要实现类有HashSet、TreeSet、LinkedHashSet……

学习Set只要记住一点,HashSet是由HashMap实现的,TreeSet是由TreeMap实现的,LinkedHashSet是由LinkedHashMap实现的。也就是说,Set是基于Map这种封装了一次的数据结构实现的,Map的Key就是Set里的元素,Map的Value是一个虚拟对象“PRESENT”。要理解Set各种不同实现的特性,就要先了解Map的各种不同实现的特性。可以参考:Java集合框架之Map

另外,Java 并发包中也有适合高并发场景的线程安全的实现类CopyOnWriteArraySet。原理和CopyOnWriteArrayList差不多。


4.Queue实现类

Queue 队列,满足广泛存在的生产者-消费者业务模型。子接口Deque是双向队列,除了可以实现队列模型,还可以实现栈模型。在Java并发包里面还定义了BlockingQueue,也就是线程安全的阻塞队列。下面两个表分别是Queue和BlockingQueue的主要方法(插入、移除、检查):

Queue接口主要方法(两组方法,不同步):

| -- | Throws exception | Returns special value | | :---- | :---- | : ---- | | Insert | add(e) | offer(e) | | Remove | remove() | poll() | | Examine | element() | peek() |

BlockingQueue接口主要方法(增加了一组会等待超时的方法,三组方法都是同步的):

亚博竞猜APPwww.yabox3.com亚博yabo线上投注| -- | Throws exception |Special value Blocks | Times out | | :---- | :---- | : ---- | :------- | | Insert | add(e) | offer(e) | put(e) | |offer(e, time, unit) | | Remove | remove() | poll() | take() | |poll(time, unit) | | Examine | element() | peek() | not applicable | not applicable |

比较常用的实现类有PriorityQueue、PriorityBlockingQueue、ArrayBlockingQueue、ConcurrentLinkedQueue……

PriorityQueue优先队列跟普通队列比起来,多了一个比较器,如果实例化的时候没有指定比较器,就会使用自然排序。PriorityQueue的存储结构是个数组,但是逻辑结构是一颗完全二叉树。优先级最高的元素(用比较器比出来最大的元素)会成为根节点,每次消费的都是根节点,根节点被消费后,会根据比较器选出新的根节点。这里不展开论述,可以参考:Java堆结构PriorityQueue完全解析

阻塞队列都是用ReentrantLock实现同步,所以性能方面不会好,主要在并发环境下使用。

ConcurrentLinkedQueue的实现原理可以类比ConcurrentHashMap,在Java 8以前是分段,之后用CAS等手段实现。具体可以参考:Java集合框架之Map

转载于:https://my.oschina.net/leaforbook/blog/1821461