秒懂Java – 『容器』是个什么鬼?

J008

经常听到别人说『容器』,这东西是个啥,和集合又有什么关系呢?

容器和集合

数组的弊端和优势

在编程中,我们经常需要把一些对象放起来,并且贴好“标签”,便于之后快速找到。

最基础的就是数组Array,其中的每一个元素都会有一个下标index,它有专门的语法糖[] ,用起来的速度也很快。但是它的唯一缺点就是大小是固定的,如果要调整的话很麻烦。

所以如果你经常要往里面插入和删除对象的话,那用起来简直就是令人崩溃的。

Array的基础上,Java库中又提供了一些功能更强大的对象存放方式。

他们合称为容器Container,和Array的最大区别就是它们的长度都是自动变化的,根本无需你干预。

当然,根据不同的用途,还有很多细分的种类,高效满足各式各样的特殊需求。

而数组的优势就是“快”,如果你存储的对象数目是确定的,那么可以直接使用数组,方便高效。

容器与集合

Container 从总体上来看分为两类,一类叫做集合Collection ,另一类则叫做映射Map

➣ 集合映射之间有什么区别呢?

区别很简单在Map中,对象必须是成对存放的,这个对就叫做key-value,而集合则不是。

集合又分为集Set序列List队列Queue

Map中添加元素的方法是put(K key, V value),而向Collection中添加则是add(E e)

集合 Collection

基本结构

集Set序列List队列Queue 之所以说他们属于Collection,是因为他们都实现了Collection这个interface。并且他们也不是“实现类”,而是interface,他们并不能直接使用。

➣那么什么是实现类?

集Set序列List队列Queue 下面的类基本上就是实现类了,最常用的是

List:ArrayList LinkedList

Set:HashSet TreeSet LinkedHashMap

Queue:ArrayDeque PriorityQueue

Collection结构图(摘自《Java Core》)

➣Collection中规定了什么方法?

最常用的就是这些方法:

添加:add(E e)   移除:remove(Object o)   返回元素数:size()   清空:clear()   返回迭代器:iterator()   返回数组:toArray()   询问是否包含某元素:contains(Object o)  

iterator是迭代器的意思,主要是用来遍历集合中的元素。

三种Collection的区别

➣三种不同的Collection之间有什么区别呢?

List是和另外两个非常不同的,它就是用Array实现的,几乎唯一的区别就是可以动态变化数组大小。

所以其中的每个元素都有index,我们就可以通过add(int index, E element)get(int index) 等等方法,准确的在某个具体位置操作元素。

但是另外两个就不一样了,他们中的元素并没有index。

➣那我们如何从其中获得元素呢?

Set在英语中的意思是“集合(数学用语)”,我们都知道数学上的集合是无序的,并且其中的元素还不能重复,Set也是类似的。不过这里要特别说明的是“无序”(只是其基本形式HashSet,之后会说到),只是相对于我们使用者而言,计算机在内部实现的时候还是有顺序的,不过这个顺序不是我们规定的,对我们来说没有意义。

没有index,就不能指定某一个位置的具体元素,我们只能使用迭代器来进行遍历。迭代器和遍历之后立即会说到。

Queue是“队列”的意思,它的特点就是只能从最顶上存取,你可以把它想象成一个窄口小桶,你能接触到的只是上面的一个而已。

Queue

PriorityQueue来举例子吧,除了遍历之外,还可以用两种方法来获取其中的元素,一种是peek(),他在英文里的意思就是“看一眼”,另一种是poll(),他的意思就是“剪短”。顾名思义,第一种就是只是获取上面的元素,而第二种则是获取之后把那个元素给删除。

初始化

在建立集合之后就想,立即把一些元素放在里面,该怎么办呢?

想要加进去的元素,往往已经存在了,那么无非就存在于三种地方:一个是存在了数组里;另外可能存在的其他集合中;还有可能非常简单,只是存在你的脑袋里。

在脑子里(数列)

➣方法1:匿名内部类

Collection <Integer> c = new ArrayList(){{add(1);add(2);add(3);add(4);}};

➣方法2:Arrays.asList(T... elements)

Collection <Integer> c = Arrays.asList(1,2,3,4,5);

➣方法3:Collections.addAll(Collection<? super T> c, T... elements)

Collection <Integer> c;Collections.addAll(c,1,2,3,4);

Collections工具类中,还有很多实用的方法,比如排序/互换/替换/打乱顺序等等等。

在另一个集合中

➣方法4:构造方法

集合的构造方法可以接受另一个集合,这里用ArrayList(Collection<? extends E> c) 为例。

Collection<Integer>c = new ArrayList<Integer>(Arrays.asList(1,2,3,4,5));

➣方法5: Collection.addAll(Collection)

集合中的成员方法,可以直接把另一个集合加进去

在数组中

因为, T... elements 这种可变参数的实现机制其实就是数组,所以也可以直接传递数组咯。

下面说的这些方法都只支持对象数组,而不支持基本类型数组,因为集合是持有对象的,不能直接持有基本类型。(因为泛型是容器的基础,泛型不能所以容器也不能,具体可以看泛型系列的三篇文章)

➣方法6:Arrays.asList(T... elements)

Integer  [] a = {1,2,3,4}; c = Arrays.asList(a);

Arrays.asList(strArray)返回值是java.util.Arrays类中一个私有静态内部类java.util.Arrays.ArrayList,它并非java.util.ArrayList类。java.util.Arrays.ArrayList类具有 set(),get(),contains() 等方法,但是不具有添加add()或删除remove()方法, 所以调用add()方法会报错。[1]

不过,可以这么来补救。

 Collection<Integer> c = new ArrayList<>(Arrays.asList(a)) ;

➣方法7:Collections.addAll(Collection<? super T> c, T... elements)

Integer  [] a = {1,2,3,4};  Collections.addAll(arrayList, a);

遍历和迭代器

之前我们对数组进行遍历的时候可以直接用循环,这是因为我们知道Array里面的元素都是有Index的,但是到了Collection就不一样了,除了List,其他的没有Index。

解决这个问题的办法就是使用iterator,它就像一个领航员一样,你可以通过他的next()方法一步一步的在集合元素中移动。要注意的是iterator中并没有back()方法,也就是说,并不能后退。

为了保证移动的时候,不会因为元素已经没有了而出现Exception,需要先使用hasNext()方法检查一下。

 public class ArrayListTest {     public static void main(String[] args) {         Collection <Integer> c = new ArrayList(){{add(1);add(2);add(3);add(4);}};         Iterator iterator = c.iterator();          while (iterator.hasNext()) {             System.out.println(iterator.next());         } 

输出结果

如果想删掉某一个元素的话,也可以在通过next()获取之后,紧跟着调用remove()方法,remove()只能删去next()刚刚获取到的东西,如果连续调用两次remove()是会出错的。

向前移动的Iterator(《Java Core》)

不过在不删除元素的情况下,大多时候并不会直接使用iterator,Java里面有很多的基于iterator的方法和语法糖,用起来更加便捷。

在数组中,我们会使用foreach关键字来进行遍历,Collection也是可以的,仔细的看看,刚刚贴上去的Java容器结构图,你会发现Collection实现了Iterableinterface,只要实现了Iterable都是可以用foreach的。

    for (int arg : c) {             System.out.println(arg);         }

Java在SE8之后开始支持函数式编程,所以我们也可以通过,传递一个lambda表达式来进行遍历,这就更简洁了,只需要一行。

c.forEach((e)->System.out.println(e));

当然,你也可以更"丧心病狂"一点,直接用“方法引用”,和lambda是一个效果的,但是更简单。

c.forEach( System.out::println);

如果你仔细看的话还会发现,迭代器里面有一个方法叫做forEachRemaining(),它也是接收一个lambda,不过唯一的区别就在于它是Iterator的一个方法,和Iteratornext()效果是完全一样的,是“一去不回头”的。如下操作,还是只能遍历一次。

        iterator.forEachRemaining(System.out::println);         iterator.forEachRemaining(System.out::println);

Collection实现类

List的实现类

首先谈一下List,常用的就只有两个,一个是ArrayList,另一个是LinkedList

ArrayList是用数组实现的,只不过他把数组的size调整,给自动化罢了

LinkedList 是用“链表”实现的,它的出现主要是为了解决ArrayList“插入和删除元素”效率低的问题。

为什么效率会很低呢?如果你在Array中插入过你就会知道,这种插入是牵一发动全身的。比如,如果在index==5的位置,插入一个新的元素,那么当前index大于等于5的元素,全都要向后挪动一位。

对于一个很长的数组来说,这种挪动带来的损失实在是太大了。

化学实验室

你可以设想这么一个场景,在化学实验室里,摆放着一排试剂,每个试剂从上都贴了一个标签,一共是30个瓶子,标签分别是从0到29。这个时候突然要加入一个新的5号瓶子,那你只能把后面的瓶子上的标签纸,挨个撕掉,重新写好,重新再贴上。简直是太繁琐了。

➣LinkedList 是如何解决这个问题的呢?

它采用了一种叫做“链表”的形式,你可以想象成是一群人手拉手站在一起,这样的话,如果想在中间的某个部位加入一个人,并不需要整个队列移动,只需要让其中两个人把手松开,另外一个人握住他们的手就行了(队列不一定是笔直的)。所以说插入元素和删除元素简直是太方便。

手拉手的队列

那么我们该如何知道每个人的序号呢?这就稍微麻烦一点,对某一个具体序号进行操作的时候,只要先清点一下就行了,清点数量总比大范围移动要快的多得多。[2]

也就是说,在访问某个具体元素的时候ArrayList占有优势;频繁增删元素的时候,LinkedList占有优势。

Set的实现类

这几个实现类中最基础的是HashSet,所以先从这个说起。

➣什么叫做 Hash 呢?

之前谈到过Set的最大特点就是“元素不能重复”,所以元素添加过程中,最重要的一个步骤就是进行对比。

对比运算需要耗费大量的资源,必然会导致效率下降。

Hash就是为了解决“查重”而诞生的。

Hash的大致原理是怎么样的?

Hash是一种函数,它能够把任意长度的数据,计算成固定长度的短小字符串。

不管是1KB还是100GB的数据,计算之后,他们的字符串长度都是一致的。

这个字符串的长度是非常短的,所以对比起来速度飞快。

比如说最常见的MD5 算法,生成的HashCode只有16个字节。

这种算法广泛的应用于计算机中,我们在使用百度网盘的时候,上传文件经常会出现“秒传”原理就是首先在本地计算MD5值,然后去服务器进行对比,如果发现资源已经存在,那么也就不用上传了,直接建立快捷方式就行了。

Hash有唯一性吗?

一定是没有的,Hash可以看作把一个,无限集合映射到一个有限集合中,所以存在多对一的情况是不可避免的。

但作为一个单值函数,它不会存在一对多的情况。

所以依照该函数的数学原理,我们就可以保证,如果两个文件的HashCode是不同的,那么他们两个一定不是同一个文件;但反过来,我们并不是百分之百确定。

HashCode 只是信息的一部分,他从信息中通过一定的算法,抽取出一定的特征进行比较。其实这种事情我们在生活中经常做,比如我们想比较两个物品是否一样,那么我们只需要看一个特征就行了,只要发现有不一样的地方,那就一定不是同一种物品;反之,如果发现其中有个地方是一样的,那么我们不能断定他们就是一样的。

比如你在街上看见了一个人,他的身高和容貌和你的一个朋友很相似,那你不敢断定,他一定是你的朋友;但如果他的身高比你朋友矮很多,那你就知道他一定不是。

一句话总结就是,Hash的原理就是“先比较一点再说”。

HashCode如果真的出现了一致的情况,那么为了严谨考虑,会对两个对象进行完全比较,如果真的出现了冲突情况,那就在这个位置再分出一条链来,可以理解成在那个位置建立一个数组(一般叫做bucket/桶),然后把他们两个一起放进去。

Hash冲突的示意图(《疯狂Java讲义》)

所以,当我们向Set,中添加元素的时候,首先会调用对象的hashCode() 方法计算HashCode,如果发现HashCode重复,则调用equals(Object o)方法。

TreeSetLinkedHashMap主要解决了什么问题?

TreeSetLinkedHashMap是在HashCode的基础上发展来的,他们主要是解决Set无序的问题。

前者就是调用Object.compareTo(Object o)方法(有时候对象并没有实现Comparable ,也可以“定制排序”,也就是另外传入一个Comparator ),对元素进行排序;而后者就是使用了“链表”,记住了元素的插入顺序。

由于他们仍然使用HashCode,所以在保证不重复的看清下,都依然能够快速的存取元素。

➣我们怎么知道是否add成功了?

add()函数是返回布尔值的,这种做法貌似是违反了《Clean Code》中“询问和操作分离”的倡议,不过在如此基础的操作上,似乎也很难有两全其美的方法。

       Integer  [] a = {1,2,3,4};         Collection<Integer> c = new LinkedHashSet<>() ;         Collections.addAll(c, a);         System.out.println(c);         System.out.println(c.add(4));         System.out.println(c.add(5));         System.out.println(c);
[1, 2, 3, 4] false true [1, 2, 3, 4, 5]

Queue实现类

主要就是有两个,第一个是ArrayDeque,第二个是PriorityQueue

第一个是一种“双端队列”,也就是可以两头存取删除;第二个则是“优先级队列”,最小的那个永远在顶上,排序的时候依然可以使用“自然”和“定制”两种方法,不过他只是保证最小的在顶上而已,并不是全部排序,这一点要注意。

映射 Map

Map的实现类主要有三个,分别是:

HashMap 一种存储键/值关联的数据结构
TreeMap 一种键值有序排列的映射表
LinkedHashMap 一种可以记住键/值项添加次序的映射表

Set和Map是一家人

你会发现,和Set可以说是一模一样的。为什么会这样呢?

之前说过Map存储的是key-value,其中的key一定是不能重复的,如果重复了之后,那就没法查找value了,数组的index也是一样,它们是一样的道理。

Map-Value(《疯狂Java讲义》)

所以,对于任意的Map单独看它的Key部分,不就是一个Set吗?其实它们是完全一样的,因为Set就是用Map实现的,可以说SetMap的一种特殊应用。Map中也有一个叫做KeySet()的方法,直接返回一个Set

Map操作中的空指针异常

但是如果从整体上来看Map又和List有相似的地方,他的每个对象都有一个唯一的Key,如果换成数字,那么也就是类似ListIndex了,不过Key是任意对象,而不是int

不过,Map中的Key就算全都是数字,也不是稠密的,在类似数组的结构之中,我们可以先看一下数组的长度,就知道index是否存在,但是在Map中是不行的。

所以在存取元素的时候,非常重要的一个工作,就是检查一下,这个位置到底有没有Key-Value对,如果没有的话,对null操作,就容易造成空指针异常。

另外需要注意的一点是,通过put替换掉一个value时,put会把那个value返回。

    public static void main(String[] args) {         HashMap <String,Integer> hashMap =new HashMap<String,Integer>({{put("一",1);}};         hashMap.put("一", hashMap.get("一") + 1);         hashMap.put("二", hashMap.get("二") + 1);     }
Exception in thread "main" java.lang.NullPointerException     at MapTest.main(MapTest.java:13)  Process finished with exit code 1

在之前的时候,这个工作比较繁琐,JavaSE8之后,专门增加了一些方法来解决这一问题,比如compute、merge、和getOrDefault。这些方法自带null判断。

注释

[1] https://blog.csdn.net/x541211...

[2] “知道序号”的具体的实现,我不知道,我这里只是给出一种合理猜测。

End

秒懂Java

更多文章:

版权声明

该文章版权系“心如止水”所有,欢迎分享、转发,但如需转载,请联系QQ:2531574300,得到许可并标明出处和原链接后方可转载。未经授权,禁止转载。版权所有 ©心如止水 保留一切权利。

心如止水

脚本宝典为你提供优质服务
脚本宝典 » 秒懂Java – 『容器』是个什么鬼?

发表评论

提供最优质的资源集合

立即查看 了解详情