Java 集合学习笔记【一】

集合导论

集合 Collection

用来存储数据使用，对应着不同类型的需求，拥有着不同的集合来处理它。Collection 是一个顶层接口，下面继承他的还有两个接口，分别是 List 接口和 Set 接口，其中 List 接口实现的是有序可重复的列表，Set 接口实现的是无序不可重复的列表。剩下的就是实现 List 和 Set 接口的各种类了，这些类五花八门，可以根据需要选择使用。

Collection 接口

Collection 的定义

首先我们看 Collection 接口的定义：

public interface Collection<E> extends Iterable<E> 

继承了一个 Iterable 的接口，并使用了泛型，泛型用于定义此集合存储的数据类型，而继承的接口 Iterable 可以先不管，一会再看它。接口里面定义了所有实现这个接口的类所必须要有的方法，因为 Collection 接口是所有集合都要实现的接口，因此所有的集合都有 Collection 接口里面的方法，下面是一些主要的方法：

int size(); // 返回集合元素数量
boolean isEmpty(); // 返回集合是否为空
boolean contains(Object o); // 返回是否包含某个元素
boolean add(E e); // 加入某个元素并返回是否加入成功
boolean remove(Object o); // 删除某个元素并判断是否删除成功
void clear(); // 删除所有的元素
Iterator<E> iterator(); // 返回此集合的一个迭代器

研究 Collection 接口里面的方法是因为这些方法在所有集合里面都是通用的，无论我们拿到一个什么样的集合，都可以使用 Collection 接口里面定义的方法来对此集合进行操作，而 Collection 接口的存在，除了方便规定集合以外，还可以用来玩多态，无论是啥集合，统一向上转型，然后当作 Collection 实例处理。

Iterator 迭代器

仔细观察 Collection 接口的主要方法，里面是没有用来返回元素的，这是因为有些集合，是没有索引的，比如 set 接口下面实现的几种集合。他们不能通过对下标的遍历来遍历整个集合。面对千万种不同的集合，一种统一的用于集合的迭代接口就必不可少了，把具体的迭代细节封装起来，留下统一的方法接口，只管调用即可。

而 Iteratior 接口就是这种标准的迭代接口，在 Collection 接口种就规定了一个方法用来返回用于此集合遍历的迭代器 Iterator<E> iterator();。而 Iteratior 接口规定了实现迭代统一而必不可少的方法：

public interface Iterator<E> {
    boolean hasNext(); // 返回是否还有下一个元素
    E next(); // 返回下一个元素并移动指针指向
}

没错，只有这两个方法就够了，判断还有下一个元素没有了，如果有就取出来，如果没有那就迭代完成！我们不需要关心集合是啥，只要 hasNext 和 next ，闭着眼都能遍历它。

增强 For 循环

对于数组和集合来说，可以使用普通 for 循环和迭代器来迭代它，首先建立一个集合并添加元素：

ArrayList<String> Tempest=new ArrayList<>();
Tempest.add("Xorex");
Tempest.add("Asuna");
Tempest.add("Yukino");
Tempest.add("Megumi");

然后对集合进行遍历：

for(Iterator<String> Ti =Tempest.iterator();Ti.hasNext();) {
    String i=Ti.next();
    System.out.println(i);
}

这就是利用了普通 for 循环和迭代器实现了集合的遍历。

那么这样的写法一般是比较固定的，于是 Java 就加入了一个语法糖，增强 for 循环。使用格式就是 for(集合元素类型 变量名 : 集合实例名); ，然后遍历代码就可以简化如下：

for(String i:Tempest) {
    System.out.println(i);
}

本质上还是用了迭代器，只不过这部分代码是编译器帮助我们生成的，我们只写语法糖部分即可。

List 接口及其实现

List 接口

上面说了 Collection 接口被 List 和 Set 两个接口继承，从而将集合分为了两大结构，这里我们就开始讨论一下这个 List 接口，以及 List 接口的一些实现。首先我们看一下官方给 List 的介绍：

* An ordered collection (also known as a <i>sequence</i>).  The user of this
* interface has precise control over where in the list each element is
* inserted.  The user can access elements by their integer index (position in
* the list), and search for elements in the list.<p>

首先 List 是一个 ordered collection 即有序列表，这意味着元素的取出顺序和放入顺序是相同的。并且可以 precise control over where 精确的控制元素的插入位置，使用元素 integer index 坐标来访问和搜索。

然后我们来看看 List 区别与 Collection 的主要方法：

E get(int index); // 获取在某坐标的元素
E set(int index, E element); // 在某坐标替换元素（删除原元素），并返回原元素
void add(int index, E element);// 在某坐标插入元素，原元素后移一位
E remove(int index); // 移除某坐标的元素
int indexOf(Object o);// 获取某元素第一次出现的坐标值
int lastIndexOf(Object o);// 获取某元素最后一次出现的坐标值

不同的地方自然是有序列表和坐标的引入了，那么就会有上面针对于坐标的操作。

List 和 Array 互换

第一种是从 List 转换为 Array，方法自然是使用 List 接口里面的 toArray(T[]) 传入一个和元素类型相同的数组，然后返回一个将 List 元素转化过的数组。当然如果我们传入的数组大小和 List 元素数量不一样的话，它也会自动处理的，小的话它会新建一个刚刚好的数组复制之后返回回来，大的话它会把没有容纳 List 元素的位置填成 null。当然我们可以直接写个大小刚刚好的：

String[] array = Tempest.toArray(new String[Tempest.size()]);

ArrayList 集合

ArrayList 是对 List 接口的一个实现类，而它的实现方法是使用数组，数组的缺点就是在插入元素的时候，后面的元素都要全部后移，造成了性能消耗比较大：

执行请求	资源消耗
获取指定元素	速度很快
添加元素到末尾	速度很快
在指定位置添加/删除	需要移动元素
内存占用	少

LinkedList 集合

LinkedList 也同样是对 List 接口的一个实现类，而它的实现方法是使用链表，链表的缺点就是查询的时候，需要遍历一边链表才能查到，造成了性能消耗比较大：

执行请求	资源消耗
获取指定元素	需要从头开始查找元素
添加元素到末尾	速度很快
在指定位置添加/删除	不需要移动元素
内存占用	较大

Set 接口及其实现

Set 接口

讨论完 List 接口之后来看看 Set 接口，同样作为继承于 Collection 的好孩子，Set 接口有什么特点呢，看看官方文档吧：

* A collection that contains no duplicate elements.  More formally, sets
* contain no pair of elements {@code e1} and {@code e2} such that
* {@code e1.equals(e2)}, and at most one null element.  As implied by
* its name, this interface models the mathematical <i>set</i> abstraction.

no duplicate elements 表示 Set 里面没有重复的元素，也就是两个 equals() 能判断相等的两个元素，null 也只能有一个。并且此集合没有索引，也就不存在了各种有关索引操作的方法了。

至于这个接口规定的一些方法，其实没啥好讲的，和 Collection 差不多，下面直接研究实现 Set 接口的两个重要的类，分别是 HashSet 和 LinkedHashSet 。

HashSet 集合

HashSet内部实现

HashSet 是 Set 的一个实现类，故名思意，实现 Set 的方法就是用了 Hash，确切的说，使用了 Hash 实现的 Map，即 HashMap。这可是个好东西，通过 Map 构建了键值对映射之后，就意味着我们对于 List 的查询和添加效率不可得兼的问题就得到了解决。使用 HashMap 可以高效的完成添加和查询，但是牺牲就是里面无法存储重复的元素。

这里对上面的名词进行解释一下， Hash，哈希表，又叫做散列表，是用来计算唯一特征值的一种算法，每一个实例都可以计算出来自己独一无二的 Hash 值，我们将这个 Hash 值作为键，将实例作为值，然后用 Map 结构来存储两者，通过 Map 结构可以用 Hash 值作为键值快速获得实例。

因此我们总结出来了，使用 HashSet 有两个必须要的条件：

1. 可以计算一个实例的 Hash 值，并且尽可能地独一无二。
2. 拥有判断两个实例是否相等地算法，保证集合元素不会重复。

第一个在 Java 里面，需要自己在写类的时候就重写继承于 Object 的方法 hashCode()，第二个则需要重写 Object 的 equals() 方法。

重写 hashCode()

首先我们看看 Object 里面的 hashCode() 是怎么写的：

public native int hashCode();

使用了 native 关键词，说明是调用了系统来返回一个十进制整数，作为这个实例的 Hash 值。

而我们的重写就需要自己计算 Hash 值了，这个算法需要保证两点

• 如果两个对象相等，则两个对象的hashCode()必须相等；
• 如果两个对象不相等，则两个对象的hashCode()尽量不要相等。

Java 为我们提供了一个利器来实现 Hash 的计算，因为不同的实例本质上是字段的值不同，所以我们就根据字段来计算 Hash 值，而计算的方法则是利用 Objects.hash()，它使用是可变参数，往里面把所有的字段都填进去即可返回一个合适的 Hash 值。

public static int hash(Object... values);

简单的重写代码：

class Tempest {
    int age;
    String name;
    public int hashCode() {
        return Objects.hash(age,name);
    }
}

重写 equals()

编写 equals() 当然也有一些原则，不过我认为这些原则都没啥用，只要能合理的重写 equals 方法即可。我们比较 两个实例是否相等的方式就是依次比较它的字段值，如果每个字段值都相等，那么就认为这两个实例是相等的，字段值有两种，一种是基本类型，一种是引用类型。对于基本类型，我们可以直接用 == 进行判断，但是引用类型就不可以了。

引用类型使用 == 判断比较的是引用地址是否相同，假使两个实例的所有字段都相同，但是由两个 new 语句建立的，那么引用地址就肯定不相同，导致使用 == 判断也不相同。所以对于引用类型的字段来说，我们使用它自带的 equals() 进行比对，但是，如果比对 equals() 的一方的引用类型字段为 null，那么调用它的 equals() 就会抛出异常，所以我们还需要单独判断是否为 null，这就太麻烦了。

麻烦的东西自然有人帮助我们处理，直接使用 Objects 类种的静态方法 equals() 传入两个引用类型，它会自动返回是否相等。因此我们就可以得到重写 equals() 的步骤了。

1. 首先判断传入的 Object 是不是此类的实例，如果是则开始下一步。
2. 然后将传入的 Object 向下转型为当前类的实例，方便比较字段。
3. 然后比较字段，引用类型使用 Objects.equals(Object a,Object b)，基本类型直接使用 == 。

简单的重写代码：

class Tempest {
    int age;
    String name;
    public boolean equals(Object o) {
        if(o instanceof Tempest) {
            Tempest P=(Tempest)o;
            return Objects.equals(this.name,P.name)&&this.age==P.age;
        }
        return false;
    }
}

使用 HashSet 集合

这里就可以看出来 Set 和 List 的使用区别了，如果需要存储重复的元素，那么只能使用 List ，如果没必要存储重复元素，则使用 Set 。 Set 虽然有着无序和无法通过下标访问的缺点，但是因为使用了映射机制，实现了 List 的无法全部获得的优点：同时实现插入和查询的高效。

因此如果没有必须要重复存储一些元素，那我们直接使用 Set 类。

LinkedHashSet 集合

LinkedHashSet 集合和 HashSet 集合之间的区别仅仅就是在前者比后者内部多了一个链表用来记录存储元素的先后顺序，这个链表仅仅只在迭代器工作的时候使用，它可以保证迭代的顺序和插入元素的顺序是相同的。而 HashSet 因为只有一个哈希表，所以迭代顺序可能会随着插入了元素而变化。

Collections 集合工具

集合工具，故名思意，就是用于操作集合的工具，这个类里面拥有很多直接操作集合的方法，帮助我们更好使用集合。

1. 排序

对一个集合进行排序的时候，如果集合里面拥有排序方法，那么就可以调用集合里面的排序方法对集合进行排序。如果没有的话，则可以利用 Collections 类的静态方法 sort() 对集合进行排序操作，需要注意的是，这里的排序只能用于列表 List ，而不能用于 Set 。

实现排序最根本的要求就是知道如何比较集合里面两个元素的大小，对于 Collections 类里面有两种排序方法，一种是 sort(List<T> list) ，直接传入一个列表既可，但需要列表的元素类实现 interface Comparable<T> 接口并重写 compareTo() 方法。另外一种则是使用 sort(List<T> list, Comparator<? super T> c) 里面传入列表和对应元素类型需要的比较器 Comparator 。

• 首先我们介绍第一种，在类中实现 interface Comparable<T> 接口，并重写里面的 compareTo() 方法。public int compareTo(T o); ，如果返回零则表示两者相等，返回正数表示自己大于比较对象 o ，返回负数表示自己小于比较对象。
• 第二种的优势在于可以定义临时的比较方法，不在类中将比较方法写死了，使用匿名类传入参数 Comparator<? super T> c ，只需要重写 public int compare(T o1, T o2); 方法即可。下面展示一下：

这里代码的主要思路就是对一个元素类型是 Tempest 类的列表进行排序，而我们的类 Tempest 考虑到不同的用途有不同的比较方法，就没有实现 compareTo() ，因此这里使用 Collections 里面的 sort(List<T> list, Comparator<? super T> c) ，其中第二个参数就是我们临时生成的匿名类，里面实现了 compare 方法。这个比较规则是首先按照年龄排序，如果年龄相同，则按照姓名排序。

package Java;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;

public class test {
    public static void main(String[] args) {
        ArrayList<Tempest> list=new ArrayList<>();
        list.add(new Tempest("Xorex",19));
        list.add(new Tempest("Asuna",20));
        list.add(new Tempest("Yukino",18));
        list.add(new Tempest("Megumi",18));
        list.add(new Tempest("Origami",17));
        Collections.sort(list,new Comparator<Tempest>() {
            @Override
            public int compare(Tempest o1,Tempest o2) {
                if(o1.getAge()==o2.getAge()) {
                    return o1.getName().compareTo(o2.getName());
                }
                else {
                    return o1.getAge()-o2.getAge();
                }
            }
        });
        System.out.println(list);
    }
}

class Tempest {
    
    private int age;
    private String name;
    
    Tempest(String name,int age) {
        this.name=name;
        this.age=age;
    }

    public int getAge() {
        return age;
    }

    public String getName() {
        return name;
    }

    @Override
    public String toString() {
        return name+':'+age;
    }
}

洗牌 shuffle

洗牌故名思意，就是将列表里面的元素顺序打乱，这种打乱是随机的，每次都不同的打乱。这种方法则是使用 Collections 中的静态方法：Collections.shuffle(List<?> list) 。

不可变集合

再 Collections 中，可以封装三种类型非不可变集合：

• 封装成不可变 List：List<T> unmodifiableList(List<? extends T> list)
• 封装成不可变 Set：Set<T> unmodifiableSet(Set<? extends T> set)
• 封装成不可变 Map：Map<K, V> unmodifiableMap(Map<? extends K, ? extends V> m)

调用这些方法，传入集合，然后返回一个不可变集合。需要注意的是，原来的集合实例还是可以修改的，而且修改之后，也同样会会修改返回的不可变实例。因此我们如果想要把一个集合变成不可变的，那么应该直接扔掉可变实例的引用，只留下来返回的不可变实例。

Map 容器

基本 Map 的概念

需要注意的是，这里的 Map 并不是地图的意思，而是映射。我们看看 Map 的定义：

public interface Map<K, V>

这里接口 Map 并没有继承与 Collection 或者 Iterator，而是作为默认继承了 Object，说明它并不是 “集合” 的一个下属，而是和 Collection 同级别的存在。我们一般的集合指的都是 Collection 实现的子类，而 Map，我认为被叫做容器更为合适一点，但是大家都叫做它集合。

Map 映射，从它的定义就能看出来，拥有两个泛型 <K, V> 表示 key 和 value 的一个键值对的映射。这种映射是拥有一定要求的，最重要的一点就是 Key 是不允许重复的，我们通过键访问值，键因此不能重复。

Map 集合里面拥有一些方法可以使用：

int size(); //返回Map中拥有的映射数量
boolean isEmpty(); //返回Map是否为空
boolean containsKey(Object key); //返回是否存在键key
boolean containsValue(Object value); //返回是否存在值value
V get(Object key); //输入key返回value
V put(K key, V value); //输入一个键值对，建立一个null,如果key不存在返回null,存在返回原来value
V remove(Object key); //输入键，移除此键值对映射
void putAll(Map<? extends K, ? extends V> m); //将一个现成Map存入当前Map
void clear(); //清空Map
Set<K> keySet(); //返回一个Set集合，里面为Map的键
Collection<V> values(); //返回一个集合，里面为Map的值
Set<Map.Entry<K, V>> entrySet(); //返回一个Set集合，里面元素为Map.Entry<K,V>实例，每个实例保存了一个键值对映射。

上面的方法中，需要注意的是 V put(K key, V value); ，因为 key 的唯一性，当我们使用 put 方法传入一个 key 已经存在 Map 里面的 key-value2 映射的时候，这个 key 映射的 value1 会被新的 value2 覆盖，并且 put 方法会把这个 value1 给返回回来。如果 key 不存在与 Map 的时候，新添加一个 key-value 只会返回 null。

迭代 Map

因为 Map 没有继承 Iterator 接口，所以自然不存在 iterator() 来返回迭代器，所以如果想要迭代 Map 的话，有两种方法可以实现：

• 第一种是使用 Set<K> keySet(); 方法，获取一个 装满 key 的 Set 集合，用 Set 的迭代器迭代出来 Map 所有的 key ，再通过 key 和 V get(Object key); 方法获取 value。
• 第二种是使用 Set<Map.Entry<K, V>> entrySet(); 返回一个装满 Map.Entry<K,V> 实例的 Set 集合，然后迭代这个集合，对于集合中的每个 Map.Entry<K,V> 实例，使用它的 K getKey(); 和 V getValue(); 来获取键值对信息即可。

Map 接口实现 HashMap

HashMap 是使用哈希算法来实现 Map 接口的一种集合，这里 HashMap 和 HashSet 使用的技术是一模一样的，都为哈希，不同之处就是 Map 为存储键值对的映射容器，而 Set 为存储单一元素的集合，Map 对于单个元素的访问可以通过键或者值，而 Set 对于单个元素的访问只能通过值。

我们使用 Map 的时候都是通过 HashMap 来实现的，不过因为采用了 Hash 技术，和前面的 HashSet 一样，想要存储自定义数据类型，必须实现 key 类自己的 equals() 和 hashCode() ，两者的实现方法在上面已经写过了。而 value 无需实现两者，因为其实现是针对 key 进行计算位置的以及是否哈希冲突的。

LinkedHashMap

首先观察此类的定义，发现它是继承于 HashMap 的：

public class LinkedHashMap<K,V> extends HashMap<K,V>

这意味着这个类拥有 HashMap 所有的方法，他们之间的不同之处就是 LinkedHashMap 自己内部通过链表实现了一个加入顺序的记录，也就是说，我们如果直接输出 LinkedHashMap 的实例，发现里面的元素顺序和我们添加的顺序是相同的，这就是 Linked 的意义所在。而且这个输出顺序同样体现在： Set<K> keySet(); 方法和Set<Map.Entry<K, V>> entrySet(); 方法返回的 Set 集合里元素的顺序，同样是按照输入的顺序保留下来的。（其实返回来的本质上是 LinkedHashSet 来保证顺序的）

TreeMap

我们来看看 TreeMap 在 Map 家族里面的关系：

       ┌───┐
       │Map│
       └───┘
         ▲
    ┌────┴─────┐
    │          │
┌───────┐ ┌─────────┐
│HashMap│ │SortedMap│
└───────┘ └─────────┘
               ▲
               │
          ┌─────────┐
          │ TreeMap │
          └─────────┘

这里 TreeMap 是实现了 SortedMap 接口里面的内容，表示它通过了树结构，实现了可排序的 Map。因为本身 HashMap 这样的类一是不像 ArrayList 一样内置了 sort() 方法，二是不像 Collection 大家族拥有 Collections 类来对其进行排序操作。因此 Map 家族就直接搞了一个 TreeMap 来实现 Map 的排序。

TreeMap 内部实现是利用红黑树实现查询和排序的，因此相对于 HashMap，他获得了 Key 排好顺序的同时，失去了 O(1) 复杂度的查询，变成了O(Logn) 。因此，如果没有必须的排序要求，还是建议使用 HashMap。因为实现方法不是哈希算法，所以自然不需要对 key 类进行实现 hashCode() 和 equals() 。

使用 TreeMap 的时候，因为要排序，所以需要 key 类实现接口 comparable 的 compareTo()，或者在建立 TreeMap 实例的时候，直接给构造方法传入一个比较器 Comparator ，这里原理都和 Collections 排序集合一样。

---

集合的内容好多啊，所以就又拆分出来了一篇文章，第二篇的内容就比较少了，而且体系化相对来说比较弱一点，都是一些零零散散的工具集合，加油吧少年！