Collection

什么是 Collection

Collection 是 Java 世界中最重要的类库，是这个类库的顶级接口。它的实现有 Set，List。而 Set 的实现又有 HashSet，TreeSet……。List 的实现有 ArrayList，LinkedList ……。也就是说我们日常使用的集合类都基本是 Collection 接口的实现。

Collction 常用方法

C：new ArrayList() / new LinkedList() / new HashSer() /…
R：size() / isEmpty() / contains() / for() /stream
U：add() / addAll() / retainAll()
D：clear() / remove() / removeAll()

• 其中 contains() 判断 collection 是否包含某一元素
• retainAll() 表示当前集合只保留与指定集合的公共元素，比如下面的代码：

public void updateCollection() {
    Collection collection1 = new ArrayList();

    collection1.add(1);
    collection1.add(2);
    collection1.add(3);

    Collection collection2 = new ArrayList();

    collection2.add(2);
    collection2.add(3);
    collection2.add(3);

    collection2.retainAll(collection1);
}

这样 collection2 进行 retainAll() 操作之后得到的结果就是与** collection1** 相同的元素，即：2，3。

• removeAll() 正好与 retinAll() 相反，表示**移除当前集合移除与指定集合相同的元素，比如下面代码：

public void deleteCollection() {
     Collection collection1 = new ArrayList();
     collection1.add(1);
     collection1.add(2);
     collection1.add(3);

     Collection collection2 = new ArrayList();

     collection2.add(2);
     collection2.add(3);
     collection2.add(4);

     collection2.removeAll(collection1);
 }

collection2 进行 removeAll() 操作之后，collection2 中的元素为：4。

List

List 是有序且元素可重复的集合

ArrayList

ArrayList 底层是个数组实现，具有动态扩容的特点。说到数组，我们印象中的数组都是有容量限制的，都有一个固定大小，那 ArrayList 的动态扩容是怎么实现的呢？

ArrayList 动态扩容原理：当 ArrayList 满了的时候，会自动扩容。ArrayList 会创建一个新的更大的空间的 List ，把原来满了的 List 的数据，复制到新的 List 中，并把原来满的 List 丢弃。

LinkedList

LinkedList 底层是链表实现，LinkedList 在日常使用中很少使用到。

ArrayList 和 LinkedList

ArrayList 是 Java 世界中，最常用的实现。既然是最常用的实现，为什么我们还需要 LinkedList? 既然有两种实现方式，那么两者的的区别和优缺点又是什么？

通过两者的底层实现可以发现他们各自的优势和区别。

因为 ArrayList 底层是数组实现，根据数组这一数据结构的特点，可以知道，数组用于查询，速度非常快。但是，数组做增删的操作就很比较慢。

而 LinkedList 的底层是链表实现，根据链表这一数据结构的特点，也很容易知道，链表的增删速度非常快，而对于查询来说就比较慢。

因此，综上所诉。对于查询需求较多的，我们可以使用 ArrayList 的实现，对于增删需求较多的，就使用 LinkedList

ArrayList 的扩容机制

我们经常往 ArrayList 中添加元素，在们看来 ArrayList 好像是一个无限容量的空间一样，可以一直往里面丢东西。实际上是 ArrayList 的扩容机制在搞鬼，每当容量不足的时候，他就会在背后帮我们自动扩容，而我们是感知不到这个过程的，扩容机制给我们造成了无限容量的假象。

我们直接查看 ArrayList 的 add 方法源代码，如下。

可以发现在添加元素前，使用了 ensureCapacityInternal 方法，来确保可以添加。我们可以在 ensureCapacityInternal 的实现方法中找到 grow 方法，这个方法就是 ArrayList 扩容的秘密。

可以看到代码中的 newCapacity = oldCapacity + (oldCapacity >> 1)，表示的扩容后，新容量等于旧容量加上旧容量右移一位。右移可以理解为除以 n^2，此处就是旧容量除以1的2次方，相加之后新容量就是旧容量的1.5倍。ArrayList 扩容机制简述就是：创建一个更大的空间，空间容量为原来容量的1.5倍，然后把所有元素拷贝过去，完成扩容。

说到这里还有个问题没有解决，既然 ArrayList 容量是有限的，那么我们直接 new 一个 ArrayList 的初始容量是多少呢？其实源代码已经给出答案了。

构造方法注释中标明，初始化容量是10。但我用 debug 调试的时候，发现初始容量并不是我们 new 的时候就创建好了，而是当我们往里面添加第一个元素时，触发了 ArrayList 的扩容机制，扩容成一个容量是10的新空间，再把我们要添加的元素放进新空间中。这属于懒加载机制，当我们需要添加元素时，才真正开辟空间。

Set

Set 是无序且元素不可重复的集合。在 java 世界中，判断两个元素是否相同使用 equals  方法。

简单的 Set 实现

我们可以顺着 List 的特性，以及 Collection 的 Contains() 方法来简单实现一个 Set。因为 Set 不包含重复元素，而且 Contains 方法就是判断元素是否重复。因此，只要往 List 中添加元素时，进行 Contains 判断，元素不重复就往 List 中添加，这样就能得到一个不包含重复元素的 List，也就是一个手写的简单 Set 实现。

Java 世界的高效 Set 实现 HashSet

虽然我们手写的 Set 也能用，但是相比 Java 中其它的 Set 实现，性能差距不知差了多少。Java 世界中最高效的 Set 实现当属于 HashSet 。

一、HashSet 实现简述

HashSet 之所以高效是因为他的背后是 HashBucket，即：哈希桶。每个哈希桶对应一个 hashCode。因此，每次往 HashSet 中添加元素的时候，首先通过 hash 运算，计算出它的 hashCode，再与哈希桶的 hashCode 进行比对，相同就把元素加入该哈希桶中。

二、hashCode

在了解 HashCode 之前，先了解下 Hash 运算。Hash 运算就是把我们数据变成一个哈希值，是一个单向映射操作。例如：假设 Hash 运算把名字变成姓氏，于是就是有「张三」->「张」、「李四」-> 「李」，以此类推。Java 世界中的 Hash 运算有它自己的一套运算规则，我们只需要知道经过 Hash 运算会返回一个 int 值就行了。

hashCode 是数据通过 Hash 运算得到的值。我们可以通过 hashCode 来初步判断是否同一元素。

在 Java 世界中对象返回的 HashCode 都遵守以下约定：

• 同一个对象得到的 hashCode 相等
• 两个对象 equals 为 true，hashcode 相等
• 两个对象不等，hashcode 可能相等

判断对象是否相等

假设存在一个 Person 对象，它有 name 属性。现在我们要使得名字相同的对象为同一对象，应该怎么做呢？

public class Person {
    private final String name;

    public Person(String name) {
        this.name = name;
    }

    public String getName() {
        return name;
    }
}

在上面提到过判断是否重复我们可以使用 equals 方法，因此我们可以该方法来解决。假如我们初始化 person1，person2，他们的名字都是「张三」。然后我们再调用 equals 方法判断 person1.equals(perons2) ，结果返回的却是 false，为什么？

在我们看来，名字相同的人就是同一个对象，可是计算机却不是这么认为的，我们查看 Object 的 equals 方法发现，它比较的实际上是内存地址。因为是两个对象，所以他们指向的内存地址不同。尽管内存中的值相等，也没用。

因此，我们就需要重写 equals，hashCode 方法来达到相同名字为同一对象的目的。

@Override
public int hashCode() {
    return name.hashCode();
}

@Override
public boolean equals(Object obj) {
    if (this == obj) {
        return true;
    }
    if (obj instanceof Person) {
        Person person = (Person) obj;
        return this.name.equals(person.getName());
    }
    return false;
}

我们在 equals 中比较两个对象的名字是否相等，相等返回 true。同时遵守「两个对象 equals 为 true，hashcode 相等」的约定，所以我们再 hashCode 方法中根据 name 来返回 HashCode，当 name 相同时就会返回相等的 HahsCode。