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中规定了什么方法？

最常用的就是这些方法：

添加：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是“队列”的意思，它的特点就是只能从最顶上存取，你可以把它想象成一个窄口小桶，你能接触到的只是上面的一个而已。

拿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里面有很多的基于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的一个方法，和iterator的next()效果是完全一样的，是“一去不回头”的。如下操作，还是只能遍历一次。

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/桶)，然后把他们两个一起放进去。

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

➣TreeSet 和LinkedHashMap主要解决了什么问题？

TreeSet 和LinkedHashMap是在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单独看它的key部分，不就是一个Set吗？其实它们是完全一样的，因为Set就是用Map实现的，可以说Set是Map的一种特殊应用。Map中也有一个叫做KeySet()的方法，直接返回一个Set。

Map操作中的空指针异常

但是如果从整体上来看Map又和List有相似的地方，他的每个对象都有一个唯一的key，如果换成数字，那么也就是类似List的Index了，不过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 - 泛型数组的问题是「体制」问题
• 秒懂Java - 红警思维看"泛型"
• 秒懂Java - 『资本家老板』的协议与回调
• 秒懂Java - 内部类与lambda表达式
• 秒懂Java -「林彪」教你"通配符泛型"

版权声明

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