Java 集合之 Collection

集合就是一组数的集合,就像是一个容器,但是我们应该清楚的是集合中存放的都是对象的引用,而不是真正的实体。而我们常说的集合中的对象其实指的就是对象的引用。

我们可以把集合理解为一个小型数据库,用于存放数据,我们对集合的操作也就是数据的增删改查,在 Java 中有两个顶层接口 Collection 和 Map 用于定义和规范集合的相关操作。这篇文章主要说一下集合框架中的 Collection 部分。

Collection 表示一组对象,这些对象可以是有序也可以是无序的,它提供了不同的子接口满足我们的需求。我们主要看看 List 和 Set 。

List 整体的特征就是有序可重复。我们需要研究的是上图中具体的实现类都有什么特性。底层的实现原理是什么,首先来看一看 List 的古老的实现类 Vector ,说是古老是因为在 JDK 1.0 的时候就出现了,都走开,我要开始看源码了!这些源码来自于 JDK 1.7。

就以上源码分析就可以知道关于 Vector 的特征。1 底层实现是使用数组来存储数据,所以相应的查找元素和添加元素速度较快,删除和插入元素较慢。2 数组的初始长度为 10 ,当长度不够时,增长量也为 10 使用变量 capacityIncrement 来表示。3 方法的声明中都加入了 synchronized 关键字,线程安全的,所以效率相应降低了。 4 没分析出来的再看一遍。

下面开始看 ArrayList 的源码。

因为源码和 Vector 类似,所以有些就不贴了,但是不耽误我们继续分析 ArrayList 。1 底层存储数据使用的还是数组,长度依旧为 10 ,但是进步了,没有在刚开始创建的时候就初始化,而是在添加第一个元素的时候才初始化的。2 方法的声明少了 synchronized 关键字,线程不安全,但性能提高了。3 数组长度不够时,会自动增加为原长度的 1.5 倍。

以上分析也能体现出 Vector 和 ArrayList 的差别。主要就是想说 Vector 已经不用了。使用 ArrayList 即可,关于线程安全问题,后面再说。

接着看 LinkedList 的实现,上源码 ~

重点就是 LinkedList 的底层实现是双链表。这样就会有以下特性,1 查找元素较慢,但是添加和删除较快。2 占内存,因为每一个节点都要维护两个索引。3 线程不安全 。4 对集合长度没有限制。

以上,List 的几个实现已经分析完成,以后再谈到 Vector ,ArrayList ,LinkedList 之间的区别应该不会不知所云了吧!还要接着看 Collection 的另一个子接口 Set 。首先有个大前提,Set 中存储的元素是无序不可重复的。然后我们再来看实现类是如何实现的。下面开始 HashSet 的表演。

看了源码才发现,1 原来 HashSet 就是对 HashMap 的封装啊,底层实现是基于 hash 表的,回头有必要再好好的介绍一下 hash 相关的知识。2 Set 集合中的值,都会以 key 的形式存放在 Map 中,所以说 Set 中的元素不能重复。3 线程不安全。4 允许存放空值,因为 Map 的键允许为空。

今天要说的最后一个实现类终于出现啦,他就是 TreeSet ,这个实现类中的元素是有序的!注意这里说的有序是指按照一定的规则排序,而我们说 Set 集合中的元素无序是因为添加进集合的顺序和输出的顺序不保证一致。TreeSet 是怎么保证有序我们待会再说,还是一样的套路,是对 TreeMap 的封装,线程依旧不安全。

我们可以看到 TreeSet 中构造函数上方的注释,TreeSet 要保证元素有序,保证有序的思路是在添加元素的时候进行比较。

Java 中提供了两种方式,第一种方法,需要我们所添加对象的类实现 Comparable 接口,进而实现 compareTo 方法,这种方式也叫自然排序,我们并没有传入什么排序规则。这种方式对应 TreeSet 的空参构造器。而另一种方式就是定制排序,即我们自己定义两个元素的排序规则,在实例化 TreeSet 的时候传入对应的排序规则即可,对应于TreeSet 中带有Comparator 接口的构造器,这里面需要实现 compare 方法 。有点迷糊了是吧,举个例子看看 ~

上面就是自然排序和定制排序的应用。要说明几点:

1 定制排序和自然排序同时存在的话,优先执行定制排序。可以看看上面的 put 方法的实现 。

2 自然排序对应 Comparable 接口,定制排序对应 Comparator 接口。

3 String ,包装类,日期类都已经实现了 Comparable 接口的 comparaTo 方法,所以我上面的例子中都偷懒了,没有自己实现具体比较,而是直接调用现成的。

看到这里,也算是对 Collection 有了整体的认识,但是这里我并没有说到具体的 API ,我现在日常也用不到几个方法,就放一张 Collection 接口的结构图吧,方法也比较简单,看个名字就大概知道什么意思了。

还是要重点说一下 iterator 方法。这个方法定义在 Iterable 接口中(Collection 继承了Iterable接口),方法返回的是 iterator 接口对象。iterator 中定义了迭代器的操作规则,而 Collection 的实现类中是具体的实现。Iterator 接口中定义了 next ,hasNext 和 remove 方法。看一下在ArrayList 中是如何实现的吧。

应用起来还是比较简单的,使用一个 while 循环即可。看下面这个例子。

不知道你有没有发现,除了 Vector 以外,保存集合元素的那个变量都定义为 transient 不管你是数组,Node 或是 Map ,不由得我又要想一想为什么这样设计?

先看一下transient 的作用吧!Java 的 serialization 提供了一种持久化对象实例的机制。当持久化对象时,可能有一个特殊的对象数据成员,我们不想用 serialization 机制来保存它。为了在一个特定对象的一个域上关闭 serialization,可以在这个域前加上关键字 transient 。当一个对象被序列化的时候,transient 型变量的值不包括在序列化的表示中,非 transient 型的变量是被包括进去的。

那么为什么要这么做呢,好好的标准序列化不用,原因如下:

对于 ArrayList 来说,底层实现是数组,而数组的长度和容量不一定相等,可能容量为 10 ,而我们的元素只有 5 。此时序列化的时候就有点浪费资源,序列化和反序列化还是要的,故 ArrayList 自己实现了两个方法,分别是 writeObject 和 readObject ,用于序列化和反序列化。

对于 HashSet 和 HashMap 来说,底层实现都是依赖于 hash 表,而不同的 JVM 可能算出的 hashCode 值不一致,这样在跨平台的时候就会导致序列化紊乱。故也重写了那两个方法。借用一句似懂非懂的话:

当一个对象的物理表示方法与它的逻辑数据内容有实质性差别时,使用默认序列化形式有 N 种缺陷,所以应该尽可能的根据实际情况重写序列化方法。

对应于 Collection ,有一个 Collections 工具类,其中提供很多方法,比如说集合的排序,求子集合,最大值,最小值,交换,填充,打乱集合等等,还记得上面说到的实现类中存在线程不安全的情况吧,这个工具类中提供很多对应的 synchronized 的方法。

后记 :不知不觉中扩展了这么多知识点,实话说,肯定还有遗漏的地方,就我现在能想到的依然还有很多,除去 Hash 表和 Hash 算法这一部分之外,我还没有对底层的数据结构进一步分析,数组,链表,二叉树等等,现在是分析不动了,本文已经很长了。

  • 发表于:
  • 原文链接:https://kuaibao.qq.com/s/20180817G1M9PE00?refer=cp_1026
  • 腾讯「云+社区」是腾讯内容开放平台帐号(企鹅号)传播渠道之一,根据《腾讯内容开放平台服务协议》转载发布内容。

扫码关注云+社区

领取腾讯云代金券