Java 容器 接口

Java 中容器框架的内容可以分为三层: 接口(模型), 模板和具体实现。

在开发中使用容器正常的流程是,首先根据需求确定使用何种容器模型,然后选择一个符合性能要求的容器实现类或者自己实现一个容器类。例如:

// 这是我们最经常用的方式了
List stringList = new ArrayList<String>();

这种方式的好处在于:

  1. 模型与实现分开可以复用一部分实现类;
  2. 屏蔽了实现逻辑的细节,可以更专注模型的操作;
  3. 接口为操作添加了约束,避免误操作。

上面所说的模型在容器框架中对应的是接口。在容器框架中根据它的特征可以作如下划分。

  1. Collection, Map 高度抽象的容器接口。可以作为构造函数的参数,实现一个容器到另一个容器的复制
  2. Iterator, ListIterator, Enumeration 迭代器接口
  3. List, Set, Queue, SortedSet, NavigatorSet,SortedMap,NavigatorMap 容器模型
  4. Comparator, Comparable 比较器接口
  5. RandomAccess 标记接口,没有操作

他们之间的关系如下:

Java 容器接口类图

接口的所有操作都包含在类图当中了。 下面我们按照分类讲一下它们的具体功能

高度抽象的容器接口


Collection

它是整个集合系容器的 Root(尽管它继承了Iterable)。代表一系列元素的‘集合’,JDK中没有它的直接实现类。一般情况下要求它的子类有两个标准构造函数:一个不带参数的构造函数,一个只有Collection类型参数的构造函数。不强制要求,但它是所有JDK中容器类已经遵守的规范。

如果Collection子类中不支持某种操作,要抛出UnSupportedOperationException异常。所以收到这个异常的时候先检查选用的实现类是否支持特定的操作。

由于它高度抽象,所以很多的约束都没有定义。包括是否线程安全,是否有类型约束,是否支持null值等,这些约束需要根据子类实现方式确定。

Map

Map系容器类的Root。它保存的是key到value的映射,所有的key不能重复。替代了JDK之前版本的Dictionary类。 提供了三个获取视图的操作,分别用来查看key,value,Entry,遍历顺序由具体的实现决定。

需要注意的是,在某些类型的对象中如果修改一些属性会影响到equals方法的结果的时候,修改key对象的属性可能会产生意料之外的影响。当一个Map使用自己的实例做key的时候,hash和equals都有可能不再正常。

这两个类的代码都比较简单,这里就不提供了。

容器模型


List

列表 特征:

  1. 可以通过位置访问
  2. 支持重复元素。
  3. ListIterator类辅助。
  4. 支持顺序查找,复杂度O(n)
  5. 如果自己持有自己,equals和hashCode会失效

列举几个不常用的方法:

// 这两个方法是返回listIterator的,它在移动指针方面要比Iterator灵活
ListIterator<E> listIterator();
ListIterator<E> listIterator();
// 这里会产生一个子列表,不过所有对它的操作都会映射到父列表中。它仅仅是个View而已。
List<E> subList(int fromIndex, int to Index);

Set

Set 与List类似,只是不支持重复元素。它的所有操作都是Collection接口中定义的方法。

你可能会发现Set系的接口与Map系的接口是类似的。他们的确是类似的,只是名字不同而已。从Set的源码可以发现,Set是使用Map来实现的。Set相当与做了一层封装,Set是一类特殊的Map。源码的开发者也有偷懒的时候。不过这里使用Map造成的多余开销影响不大。

SortedSet

这个列表对所有元素提供了全排序。所以它的元素要么实现了Comparable接口,要么在Set中指定一个Comparator对象。它跟SortedMap是类似的。

NavigableSet

它提供了四个查询操作要区分一下:

/**
 * 下面的操作中,没有对应的值都返回null
 */
// 返回集合中 小于 e 的最大元素
E lower(E e);
// 返回集合中 小于或等于 e 的最大元素
E floor(E e);
// 返回集合中 大于或等于 e 的最小元素
E celing(E e);
// 返回集合中 大于 e 的最小元素
E higher(E e);

它还提供了逆序操作:

// 返回一个逆序的集合,但它是本集合的view而已。对结果集合所做的任何操作都会反馈到本集合上。反之亦然。
NavigableSet<E> descendingSet();
// 一个逆序的迭代器;等同于desendingSet().iterator();
Iterator<E> descendingIterator();

还有很多求子集的方法,大家自己了解,这里不列举了

Queue

满足 先进先出 模式 的有序队列。 除了从Collection类继承来的方法外,有几个方法需要加以区别:

// 向队列中添加一个元素,如果队列中空间不够,抛出一个异常
boolean add(E e);
// 向队列中添加一个元素,如果队列空间不够,返回false
boolean offer(E e);
// 删除队列中的首个元素,如果队列为空,抛出异常
E remove();
// 删除队列中的首个元素,如果队列为空,返回null
E poll();
// 返回队列首个元素的值,但不删除它,如果队列为空,抛出异常
E element();
// 返回队列中首个元素的值,但不删除它,如果队列为空,返回null
E peek();
Deque

全称:"Double End Queue" 两端都可以插入和删除队列。在Queue的基础上添加了两端都可以插入和删除的操作。

// xxx对应queue中的操作
boolean xxxFirst() // 队首操作
boolean xxxLasst() // 队尾操作

然而设计者对它的操作设计不止于此(个人感觉这样设计功能不再单一, 不是很好。但源码中确实是这样做的), Deque中还可以当作 来使用:

// 下面两个操作是栈的操作
E pop();
void push(E e);

还有两个普通的操作, 根据方法名就可以理解方法的含义.

boolean removeFirstOccurrence(Object o);
boolean removeLastOccurrence(Object o);

比较器接口


如果一个类实现了 Comparable那么它就是有自然顺序的。如果一个类的对象没有实现Comparable接口,那当把它放到有顺序的容器中排序的时候,就需要为容器添加一个Comparator接口的对象。

在实现这两个接口的时候需要注意 比较与相等一致 的问题。当c1.compareTo(c2) == 0的时候, 必须要有c1.equals(c2)。不然在使用一些有序容器的时候,例如SortedSet, SortedMap,这类对象的行为很难预料。

标记接口


RandomAccess接口在容器框架中的接口,它的作用类似于一种标记。它是一个空接口,并没有方法。 凡是实现它容器随机访问都是O(1)的时间复杂度。例如ArrayList

这里常用的一个例子就是:

List<String> list1 = new ArrayList();
List<String> list2 = new LinkedList();
for(int i = 0; i < list1.size(); i++) String s = list1.get(i);
for(int i = 0; i < list2.size(); i++) String s = list2.get(i);

由于实现方式的不同,两个列表的访问效率相差很大。前一个是O(n), 后一个是O(n ^ 2)。

接口这一部分就分享这些内容了。后面会对具体的实现做一些分析。

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏开发与安全

数据结构:双向链表实现队列与循环链表

一、双向链表(double linked list)如图26.5,是在单链表的每个结点中,再设置一个指向其前驱结点的指针域。双向链表的基本操作与单链表基本一样,...

28180
来自专栏Linyb极客之路

Java开发者易犯错误Top10

Arrays.asList()将返回一个数组内部是私有静态类的ArrayList,这不是java.util.ArrayList类,java.util.Array...

13040
来自专栏服务端技术杂谈

Java编码规范

命名 类名使用UpperCamelCase风格。 领域模型相关命名:DO / DTO / VO / DAO等。 方法名,参数名,成员变量,局部变量都统一使用lo...

35140
来自专栏androidBlog

归并排序 递归版和非递归版的实现(java)

版权声明:本文为博主原创文章,未经博主允许不得转载。 https://blog.csdn.net/gdutxiaoxu/article/details/...

29910
来自专栏北京马哥教育

Python高级编程技巧

正文: 本文展示一些高级的Python设计结构和它们的使用方法。在日常工作中,你可以根据需要选择合适的数据结构,例如对快速查找性的要求、对数据一致 性的要求或...

50650
来自专栏黑泽君的专栏

异常中要了解的Throwable类中的几个方法

*   public String getMessage()   获取异常的信息,返回的是字符串

82610
来自专栏专注 Java 基础分享

堆结构的优秀实现类----PriorityQueue优先队列

     之前的文章中,我们有介绍过动态数组ArrayList,双向队列LinkedList,键值对集合HashMap,树集TreeMap。他们都各自有各自的优...

26360
来自专栏haifeiWu与他朋友们的专栏

System方法总结

最近在研究Android源码,突然看到有很多和System有关,什么System.arraycopy、System.nanoTime(),所以专门花时间看了一下...

11420
来自专栏小勇DW3

LinkedHashMap 源码分析

LinkedHashMap 继承自 HashMap,在 HashMap 基础上,通过维护一条双向链表,解决了 HashMap 不能随时保持遍历顺序和插入顺序一致...

21530
来自专栏Coding迪斯尼

Reactjs开发自制编程语言Monkey的编译器:语法解析

16120

扫码关注云+社区

领取腾讯云代金券