Java进阶_03_集合

程序本质上是对数据的处理，而为了更好的处理数据，设计了很多种数据结构。Java为了方便编程，提供了典型数据结构的实现类及其扩展类，本文介绍相关的类，统称为集合，注意，接口以及类后面的尖括号涉及到泛型的知识，暂且记住。java.util.Collection是集合接口，提供了很多数据结构的实现类；java.util.Collections是集合工具类，提供集合之间的操作，比如将集合不安全转换成集合安全等等。

1. 集合概述

集合实际上就是一个容器，可以用来容纳其他类型的数据，比如说数组其实就是一个集合。

为什么说集合在开发中使用较多？

集合是一个容器，是一个载体，可以一次容纳多个对象。在实际开发中，假设连接数据库，数据库当中有10条记录，那么假设把这10条记录查询出来，在Java程序中共会将10条数据封装成10个Java对象，然后将10个Java对象放到某一个集合当中，将集合传到前端，然后遍历集合，将一个个数据展现出来。

集合不能直接存储基本数据类型，也不能直接存储Java对象，只能存储Java对象的内存地址，或者说存储的是引用。即使在语法上存储了基本数据类型，底层一定进行了自动装箱操作。集合在Java中本身是一个容器，是一个对象，所以集合也可以存储集合引用。

Java中每一个不同的集合，实际上对应不同的数据结构。往不同的集合中存储元素，等于将数据放到了不同的数据结构中。不同的数据结构，数据存储方式不同。例如：数组、二叉树、链表、哈希表等等。 本质上说，集合就是数据结构的具体实现。所有的集合类和集合接口都在java.util包下。Java中的集合分为两大类：单个方式存储元素和键值对方式存储元素。

1.1 单个方式存储元素

这类集合中的超级父接口是：java.util.Collection，该接口继承了java.lang.Iterable接口，该接口表示可迭代的，可遍历的。Iterable接口中有iterator()方法，负责产生对应集合的迭代器Iterator对象，用于访问集合中的元素。继承Iterable的集合都是可迭代的。

该接口下有很多子接口以及子类，帮助文档中的详细展示如下：

该接口下需要注意的两个子接口是List和Set，这两个接口下的实现类用的比较多。

1.1.1 List

List集合存储元素的特点是：有序可重复，存储元素有下标。

List接口下面需要注意的类有：ArrayList、LinkedList、Vector、Stack。

• ArrayList底层采用了数组这种数据结构（非线程安全）；
• LinkedList底层采用了双向链表这种数据结构；
• Vector底层采用了数组这种数据结构（线程安全，效率较低，现在保证线程安全有其他方法，用的较少）；
• Stack就是Java实现的栈数据结构。

可以将ArrayList和LinkedList分别看做是数组和链表，只不过二者封装了一些常用的方法。

1.1.2 Set

注意，Set中的元素不可重复，对于Integer类型来说，指的是值不可重复，并不是对象不可重复，即Integer it1 = new Integer(12345)和Integer it2 = new Integer(12345)虽然是两个不同的对象，但是值是一样的，所以存储的是第一个元素，之后再添加相同的元素即使不报错，也没存进去。看了看源码，和contains一样，似乎底层也是调用的equals方法，通过equals方法来判断是否相等，是否添加。所以根本上还是看是否重写equals方法和hashCode方法，比较内存地址还是值。

Set集合存储元素的特点是：无序不可重复，存储元素没有下标。

Set接口下面需要注意的类有：HashSet、SortedSet(TreeSet)。

• HashSet底层实际上是HashMap集合，HashMap底层采用了哈希表这种数据结构。
• TreeSet类实现了SortedSet接口，SortedSet接口继承了Set接口。TreeSet底层实际上是TreeMap集合，TreeMap底层采用了二叉树这种数据结构。注意，SortedSet接口的实现类中元素可以自动排序，这里的排序是数值内容排序。而Set说的无序指的是存储和取出的时候顺序对应不上。

1.2 键值对方式存储元素

这类集合中的超级父接口是：java.util.Map，该接口没有父接口，说明Map和Collection是没有关系的。以键值对方式存储元素，key和value都是存储Java对象的内存地址，所有的key都是无序不可重复的。

该接口下有很多子接口和子类，帮助文档中的详细展示如下：

该接口下需要注意的类及接口有：**HashMap、Hashtable和SortedMap(TreeMap)**，其中：

• HashMap底层采用了哈希表这种数据结构（非线程安全）；
• Hashtable底层采用了哈希表这种数据结构（线程安全，但是保证线程安全有其他方法，该类效率较低，用的较少）；
• TreeMap实现SortedMap接口，SortedMap接口继承了Map接口。TreeMap底层采用了二叉树这种数据结构。SortedMap集合下的子类，存储元素会自动按照key元素的大小顺序排序。

补充：Hashtable下有一个Properties子类，该类是线程安全的，要求key和value必须是String类型，不支持其他类型。该类也被称为属性类。

当然，其实Collection和Map中还有其他类型的接口和类，只不过上述列举出来的是常用的。上述集合的总体继承结构如下所示：

2. Collection及其子类介绍

没有使用“泛型”之前，Collection中可以存储Object的所有子类型；使用了“泛型”之后，Collection中只能存储某个具体的类型。注意，集合中不能直接存储基本数据类型。

Collection是所有单个方式存储元素类的父接口，首先要了解该接口中的常用方法。该接口中的方法均为public abstract修饰，所以均省略了修饰符列表。

2.1 Collection接口中的常用方法

方法名	描述
boolean add(Object o)	向集合中添加元素
int size()	获取集合中的元素个数
void clear()	移除集合中的所有元素
boolean contains(Object o)	判断集合中是否包含元素o
boolean remove(Object o)	删除集合中的元素o（只删除1个）
boolean isEmpty()	判断集合是否为空
Object[] toArray()	将集合转换成Object数组
Iterator iterator()	返回该集合的迭代器对象

2.2 迭代器Iterator

可以看到，集合中并没有提供遍历集合的方法，但提供了迭代器对象方法（也可以用增强for循环foreach来遍历）。Collection中的Iterator iterator()方法，返回集合的迭代器对象，迭代器主要的作用就是遍历集合，这里着重讲解一下，注意，调用方法获取迭代器的时候，一定要在添加元素之后获取，就是说获取迭代器只能获取当前集合中所包含的元素所形成的迭代器，类似快照。注意，集合结构只要发生改变（无论是删除还是添加元素），迭代器必须重新获取，迭代器常用的方法有如下三个：

• booelan hasNext()

  判断迭代器中是否有元素可以迭代，有则返回true。

• Object next()

  返回迭代的下一个元素。

• void remove()

  从迭代器指向的Collection中移除迭代器返回的最后一个元素。

利用迭代器测试ArrayList（有序可重复）和HashSet（无需不可重复）：

import java.util.ArrayList;
import java.util.Collection;
import java.util.HashSet;
import java.util.Iterator;

public class CollectionTest03 {

    public static void main(String[] args) {
        Collection c = new ArrayList();

        c.add(123);
        c.add(24);
        c.add(35);
        c.add(24);
        c.add(1234);
        c.add(1234);

        Iterator it = c.iterator();	// 获取当前上面所有元素形成的迭代器。

        while(it.hasNext()){
            System.out.println(it.next());  // 输出顺序和添加顺序一致
        }

        System.out.println("============");

        Collection c2 = new HashSet();

        c2.add(100);
        c2.add(50);
        c2.add(10);
        c2.add(50);
        c2.add(90);
        c2.add(50);
        c2.add(0);

        Iterator its = c2.iterator();

        while(its.hasNext()){
            System.out.println(its.next());     // 输出顺序和添加顺序不一样
        }
    }
}

测试不可重复，添加的元素到底是哪一个：实际上是第一次添加的，后续添加相同的元素，其实没存进去。

Collection c3 = new HashSet();

Integer ints1 = new Integer(12345);
Integer ints2 = new Integer(12345);

System.out.println(ints1 == ints2);

c3.add(ints1);
c3.add(ints2);

Iterator its = c3.iterator();

Object obj = its.next();

System.out.println(obj == ints1);	// true
System.out.println(obj == ints2);	// false

2.3 contains方法

注意，contains方法底层调用了参数的equals方法。所以就是比较的是内存地址还是值取决于参数是否重写了equals方法以及hashCode方法，add()方法也是如此，这样构成了HashSet的不重复特性。测试代码如下：

class Animal {

    private String color;

    public Animal(){}

    public Animal(String color){

        this.color = color;
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Animal animal = (Animal) o;
        return Objects.equals(color, animal.color);
    }

    @Override
    public int hashCode() {
        return Objects.hash(color);
    }
}

public class CollectionTest04 {

    public static void main(String[] args) {
        Collection c = new HashSet();

        Animal a1 = new Animal("blue");
        Animal a2 = new Animal("blue");

        c.add(a1);
        
        System.out.println(c.contains(a2));	// 重写之后，true，重写之前为false。
        
        Animal a3 = new Animal("blue");
        c.add(a3);
        
        System.out.println(c.size());	// 重写之后，size=1，重写之前为2；
    }
}

所以，存放在集合中的类型，一定要重写equals方法以及hashCode方法。

2.4 remove方法

remove方法底层也是调用了参数的equals方法，所以删除某个参数的时候，如果没有重写equals方法，则比较内存地址删除，如果重写了，则比较内容删除。

另外，此处验证集合结构发生改变之后，迭代器必须重新获取，否则报错。

因此，如果想要删除集合中的元素，要么在此操作之后重新获取迭代器，要么就采用迭代器中提供的删除方法（底层实际上通知了集合删除元素，使得迭代器和集合同步删除）。

Collection c = new ArrayList();

c.add("hello");
c.add("world");
c.add(123);
c.add(3.14);

// 方法1，删除操作之后重新获取迭代器
Iterator it = c.iterator();

while(it.hasNext()){
    Object o = it.next();
    System.out.println(o);
    c.remove(o);
    it = c.iterator();
}

System.out.println(c.size());

// 方法2，采用迭代器提供的删除方法，删除迭代器当前指向的元素
it = c.iterator();
while(it.hasNext()){
    Object o = it.next();
    System.out.println(o);
    it.remove();
}

System.out.println(c.size());

2.5 List

讲解了Collection典型方法，下面讲解一下子接口List特有方法，List接口也有上述Collection中的方法，这里不再赘述。

List集合存储元素特点：有序可重复。有序意味着List集合中的元素有下标，所以可以通过下标来获取元素，这样就不需要迭代器来遍历了。可重复意味着可以重复存储相同的元素。List特有方法如下所示（注意，E指的是泛型，目前可以看成是Object）：

方法名	描述
void add(int index, E element)	在指定index处插入元素element（效率较低）
E get(int index)	获取指定index上的元素
int indexOf(Object o)	获取元素o在List中第一次出现的index
int lastIndexOf(Object o)	获取元素o在List中最后一次出现的index
E remove(int index)	移除指定index上的元素，并返回该元素
E set(int index, E element)	修改指定index处的元素为element

2.5.1 ArrayList（用的较多）

ArrayList集合底层是一个Object[] 数组，默认初始化容量是10（底层先创建了一个长度为0的数组，当添加第一个元素的时候，初始话容量为10），也可以手动设置容量。

ArrayList会自动扩容，增长当前容量的一半，即扩容到之前的1.5倍。数组扩容效率比较低，建议在使用ArrayList集合的时候预估计元素的个数，给定一个初始化容量

这么多集合中，哪个用的比较多？

回答：ArrayList，因为平时使用过程中，经常向数组末尾添加元素，检索次数较多。插入删除较少，所以采用数组结构的ArrayList集合使用的比较多。

ArrayList集合在创建的时候，可以将某个集合传入构造方法，即将该集合转换成ArrayList类型集合。

常用的方法基本上就是Collection和List接口中的方法，这里不再赘述，非线程安全。

2.5.2 LinkedList

LinkedList集合底层是双向链表，有指向头结点和尾结点的指针。LinkedList和ArrayList的常用方法类似，只不过二者底层一个是链表一个是数组。另外，LinkedList没有初始化容量，链表不需要初始化容量。

2.5.3 Vector

Vector底层也是数组，初始容量是10，扩容之后是原容量的2倍。Vector是线程安全的，效率较低，使用较少。

2.6 Set

Set中的HashSet和TreeSet底层都是Map中的HashMap和TreeMap，所以这里就不再讲解Set相关知识，简单描述一下即可。不过Set集合的遍历方式只有两种：迭代器和foreach，没有下标遍历方式。

2.6.1 HashSet

• 存储时顺序和取出的顺序不同；
• 不可重复；
• 放到HashSet集合中的元素实际上是放到HashMap集合的key部分了。

public class HashSetTest01 {
    public static void main(String[] args) {

        Set<String> mySet = new HashSet<>();

        mySet.add("zhangSan");
        mySet.add("liSi");
        mySet.add("wangWu");
        mySet.add("zhaoLiu");

        for (String strs: mySet) {
            System.out.println(strs);
        }
    }
}

// 输出结果为：
liSi
zhaoLiu
wangWu
zhangSan

2.6.2 TreeSet

• 无序可不重复，但是存储的元素可以自动按照大小顺序排序。

public class TreeSetTest01 {
    public static void main(String[] args) {

        Set<String> mySet = new TreeSet<>();

        mySet.add("zhangSan");
        mySet.add("liSi");
        mySet.add("wangWu");
        mySet.add("zhaoLiu");

        for (String strs: mySet) {
            System.out.println(strs);
        }
    }
}

// 输出结果为：
liSi
wangWu
zhangSan
zhaoLiu

3. Map及其子类介绍

Map集合和上述的Collection集合没有关系，它是以key和value这种键值对的方式存储元素，并且key和value是存储java对象的内存地址，所有Map集合的key特点：无序不可重复。另外，Set集合存储元素特点和Map集合的key是一样的。key起到主导地位，value是key的一个附属品。

Map支持泛型，因为Map包括key和value两个字段，所以二者都可以指定具体的类型。

3.1 Map接口中的常用方法

方法名	描述
void clear()	清空Map集合
boolean containsKey(Object key)	判断Map中是否包含某个Key
boolean containsValue(Object value)	判断Map中是否包含某个value
V get(Object key)	通过key获取value
boolean isEmpty()	判断Map中元素个数是否为0
Set<key> keySet()	获取Map集合所有的key，返回Set集合
V put(K key, V value)	向Map集合中添加键值对
int size()	获取Map集合中键值对的个数
Collection<V> values()	获取Map集合中所有的value，返回一个Collection
Set<Map.Entry<K, V>> entrySet()	将Map集合转换成Set集合，集合中的元素是key=value这种形式，类型就是尖括号中的泛型。
V remove(Object key)	通过key删除对应的键值对

备注，Entry是Map中的静态内部类，也是一种类型，所以该类型完整的类型名是Map.Entry，创建对应的对象就是采用全名创建的。此时后面再加上泛型，说明该类支持泛型，另外泛型是可以嵌套的，即一层又一层。

同样，contains相关方法底层调用的是equals方法，如果自定义的类，需要实现equals方法。

3.2 Map集合的遍历

遍历Map集合有以下几种方式，

1. 获取所有的key，通过遍历key来遍历value。

   public class MapTest02 {
   
       public static void main(String[] args) {
   
           Map<Integer, String> myMap = new HashMap<>();
   
           myMap.put(1, "zhangSan");
           myMap.put(2, "liSi");
           myMap.put(3, "wangWu");
           myMap.put(4, "zhaoLiu");
   
           Set<Integer> mySet = myMap.keySet();
   
           System.out.println("增强for循环遍历key：");
           for (Integer i: mySet) {
               System.out.println(i + "=" + myMap.get(i));
           }
   
           System.out.println("迭代器遍历key：");
           Iterator<Integer> it = mySet.iterator();
           while(it.hasNext()){
               Integer key = it.next();
               System.out.println(key + "=" + myMap.get(key));
           }
       }
   }

2. 通过entrySet方法将Map集合转换成Set集合，遍历集合即可（效率较高）。

   Set<Map.Entry<Integer, String>> sets = myMap.entrySet();
   Iterator<Map.Entry<Integer, String>> it2 = sets.iterator();
      
   while(it2.hasNext()){
       Map.Entry<Integer, String> entry = it2.next();
       System.out.println(entry.getKey() + "=" + entry.getValue());
   }
      
   for (Map.Entry<Integer, String> entry: sets) {
       System.out.println(entry.getKey() + "=" + entry.getValue());
   }

3.3 HashMap

HashMap底层是哈希表，其源码大致如下所示：

public class HashMap{
    
    // HashMap底层实际上是一个数组。（一维数组）
    transient HashMap.Node<K, V>[] table;
    
    // 静态内部类
    static class Node<K, V> {
        // hash值，属性key的hashCode()方法的执行结果，哈希值可以通过算法转换成数组的下标。即找到该节点（元素）在数组中存储的链表位置。
        final int hash;
        
        // 存储在Map集合中的key
        final K key;
        
        // 存储在Map集合中的value
        V value;
        
        // 下一个节点的引用
        HashMap.Node<K, V> next;
    }
}

HashMap集合的默认初始化容量是16，默认加载因子是0.75，另外初始化容量必须是2的倍数，这也是Java官方推荐的，这是因为达到散列均匀，为了提高HashMap集合的存取效率所必须的。默认加载因子指的是当HashMap集合底层数组的容量达到75%的时候，数组开始扩容。

注意，在JDK8及之后，如果链表的长度超过了8，则会将链表变成红黑树，当红黑树上的节点数量小于6时，会重新把红黑树变成单向链表数据结构。这种做法是为了提高检测效率，因为二叉树的检索会再次缩小扫描范围。

一定要掌握put(k, v)和get(k)方法的实现原理。

3.3.1 put(k, v)方法

map.put(k, v)方法原理如下：

第一步：先将 k,v 封装到Node对象当中；

第二步：底层会调用k的hashCode()方法得出hash值，然后通过哈希函数/哈希算法，将hash值转换成数组的下标，下标位置上如果没有任何元素，就把Node添加到这个位置上了。如果说下标对应的位置上有元素（链表），此时会将k和链表上每一个节点中的k进行equals，如果所有的equals方法返回都是false，表明该节点没有存储在链表中，那么这个新节点将会被添加到链表的末尾，如果其中有一个equals返回了true，此时会将旧节点的value替换为新节点的value（即更新节点值）。

3.3.2 get(k)方法

map.get(k)方法原理如下：

第一步：先调用k的hashCode()方法得出哈希值，通过哈希算法转换成数组下标，通过数组下标快速定位到某个位置上（某个链表上），如果这个位置上什么也没有，返回null。如果这个位置上有单向链表，那么会拿着参数k和单向链表上的每个节点中的k进行equals，如果所有equals方法返回false，那么get方法返回null；如果其中有一个节点的k和参数k equals的时候返回true，那么此时这个节点的value就是我们要找的value，get方法最终返回这个要找的value。

上述两个方法都调用了key对象的hashCode()和equals()方法，key对象的这两个方法需要重写，否则采用的是Object中的方法（比较的是内存地址）。并且放在HashSet集合存储元素的时候是存储在HashMap中的key部分了，所以HashSet存储的元素也需要重写hashCode()和equals()方法。

equals()方法返回true表示两个对象(值)相同，在同一个单向链表上，所以其哈希值是相同的，所以hashCode()方法的返回值也应该相同。所以重写方法时需要注意这些（直接使用IDEA生成即可）。

通过这两个方法可以看出：

• 从链表的角度来看，结合数组和哈希算法，一定程度上减少了扫描范围，使得检索效率有了一定的提升，即根据哈希算法可以直接定位到某一条子链表中。
• 从数组的角度来看，结合链表和哈希算法，一定程度上减少了元素的移动，使得随机增删效率有了一定的提升，即根据哈希值计算出节点所在的链表后，在链表上进行元素的增删。

3.4 Properties

Properties是一个Map集合，该类也被称为属性类，继承Hashtable类。它的key和value都是String类型。了解一下常用方法即可。

方法名	描述
Object setProperty(String key, String value)	向集合中存储元素
String getProperty(String key)	从集合中取元素

3.4 TreeMap

TreeMap底层是一个二叉树，存储元素无序不可重复，但是可根据元素（key）大小进行排序，元素类需实现comparable接口或者传入comparator接口实现类对象。所以当需要对数据进行排序的时候，可以将其添加到TreeMap或者TreeSet中，取出来就是有顺序的。所以，存进去的元素必须是可排序的，即必须是继承 java.lang.Comparable 接口的，并制定了比较规则。

注意，放在TreeSet和TreeMap的key中的元素类需要实现java.lang.Comparable接口，并且实现compareTo()方法，equals()方法可以不写。

在添加数据的时候，compareTo()方法的返回值很重要：

• 返回0表示相同，value会覆盖
• 返回 > 0，会在右子树上添加或者覆盖
• 返回 < 0，会在左子树上添加或者覆盖

TreeMap底层是二叉树，所以在存储元素的时候，是按照左右子树比较进行排序的，所以二者相比小于0，则放在左子树，大于0则放在右子树。规则可以自己编写。

comparable接口实现简单代码测试如下：

import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapTest01 {

    public static void main(String[] args) {

        TreeMap<Customer, String> tm = new TreeMap<>();

        tm.put(new Customer(19), "zhangSan");
        tm.put(new Customer(10), "liSi");
        tm.put(new Customer(23), "wangWu");

        Set<Map.Entry<Customer, String>> sme = tm.entrySet();

        for ( Map.Entry<Customer, String> me: sme) {
            System.out.println(me.getKey() + "-->" + me.getValue());
        }

    }
}

class Customer implements Comparable<Customer> {
    int age;

    public Customer(int age){
        this.age = age;
    }

    @Override
    public int compareTo(Customer customer) {

        // 如果小于0，customer放在左子树位置上，即升序排列
//        return this.age - customer.age;

        // 如果小于0，customer放在右子树上，即降序排列
        return customer.age - this.age;
    }

    public String toString(){
        return Integer.toString(this.age);
    }
}

comparator接口比较器实现简单代码测试如下：

import java.util.Comparator;
import java.util.Map;
import java.util.Set;
import java.util.TreeMap;

public class TreeMapTest01 {

    public static void main(String[] args) {

        // 传入比较器实现类对象
        TreeMap<Vip, String> vips = new TreeMap<>(new VipComparator());

        vips.put(new Vip(19), "zhangSan");
        vips.put(new Vip(14), "liSan");
        vips.put(new Vip(21), "wangSan");
        vips.put(new Vip(20), "zhaoSan");

        Set<Map.Entry<Vip, String>> smes = vips.entrySet();

        for(Map.Entry<Vip, String> ssme : smes){
            System.out.println(ssme.getKey() + "--->" + ssme.getValue());
        }

    }
}

class Vip{
    int age;

    public Vip(int age){
        this.age = age;
    }

    public String toString(){
        return "小乌龟[" + this.age + "]";
    }

}

// 定义比较器实现类
class VipComparator implements Comparator<Vip> {
    @Override
    public int compare(Vip vip, Vip t1) {
        return vip.age - t1.age;
    }
}

3.4.1 TreeMap关键

放到TreeSet或者TreeMap集合key部分的元素要想做到排序，包括以下两种方式：

• 元素类实现java.lang.Comparable接口；
• 在构造TreeSet或者TreeMap集合的时候给它传一个比较器对象，即java.util.Comparator接口实现类。（也可直接匿名内部类传参）

那么这两种方式如何选择呢？当比较规则不会发生改变的时候，或者说当比较规则只有1个的时候，建议采用第一种方法元素类实现Comparable接口。如果比较规则有多个，并且需要多个比较规则之间频繁切换，建议采用第二种方法实现Comparator接口传参。

4. 集合工具类Collections

注意，java.util.Collection是集合接口；java.util.Collections是集合工具类，方便集合的操作。一些方法如下所示：

方法名	描述
static <T> void sort(List<T> list)	对集合中的内容进行排序
static <T> List<T> SynchronsizedList(List<T> list)	将非线程安全的转换成线程安全的

5. 备注

参考B站《动力节点》。