Java-集合进阶1-单列集合

Collection 集合

Collection 集合是所有单列集合的父接口，所有的单列集合都实现了 Collection 接口，可以分为 List 、Set 两类（这里的 List 和 Set 也是接口，是继承自 Collection 的）

Collection 集合的常见成员函数如下（这里使用 ArrayList 的对象进行演示）：

public static void main(String[] args) {
    Collection<String> strings = new ArrayList<();
    boolean addSuccess = strings.add("123");                // 添加元素
    boolean removeSuccess = strings.remove("123");      // 移除元素
    boolean isContain = strings.contains("234");            // 是否包含元素
    boolean isEmpty = strings.isEmpty();                    // 是否为空
    strings.clear();                                     // 清空集合
    int size = strings.size();                            // 返回集合大小
}

注意： 如果在集合中添加了自定义类的对象（如 person ），则需要在 person 类中重写 equals() 方法
这是因为 contains() 方法是依赖于 equals() 方法的，如果不重写， contains() 方法可能失效

遍历

有三种方法遍历 Collection 集合：

迭代器对象遍历

public static void main(String[] args) {
    Collection<String> strings = new HashSet<>();
    for (int i = 0; i < 15; i++) {
        strings.add(String.valueOf(i));
    }

    Iterator<String> setIterator = strings.iterator();
    while (setIterator.hasNext()) {
        System.out.println(setIterator.next());
    }
}

增强的 for 循环遍历

public static void main(String[] args) {
    Collection<String> strings = new HashSet<>();
    for (int i = 0; i < 15; i++) {
        strings.add(String.valueOf(i));
    }

    for (String string : strings) {
        System.out.println(string);
    }
}

lambda 表达式

public static void main(String[] args) {
    Collection<String> strings = new HashSet<>();
    for (int i = 0; i < 15; i++) {
        strings.add(String.valueOf(i));
    }

    strings.forEach(s -> System.out.println(s));
    strings.forEach(System.out::println);        // lambda表达式的另一种写法
}

注意：

在迭代器遍历中，每一个迭代器对象都是一次性的。也就是说，一个迭代器对象遍历完成后，需要重新获取一个迭代器对象
在迭代器遍历过程中，不能使用集合提供的方法添加或删除集合中的元素，但可以使用迭代器提供的 remove() 方法移除元素
在增强 for 循环中，为循环变量（如 string ）赋值，不会改变原集合中元素的值

List 集合

List 集合是从 Collection 集合中继承得来的，它的集合元素有如下特点：有序、可重复、有索引

List 集合除了从 Collection 集合继承得到的成员方法，它还有一些特有方法，而这些方法都是关于 List 的索引的操作：

public static void main(String[] args) {
    List<String> strings = new ArrayList<>();
    for (int i = 0; i < 15; i++) {
        strings.add("" + i);
    }

    strings.add(4, "four");                     // 在指定位置插入元素
    String remove12 = strings.remove(12);       // 删除指定位置的元素，并返回被删除的元素
    String set5 = strings.set(5, "five");           // 修改指定位置的元素，并返回被修改的元素
    String get9 = strings.get(9);                   // 获得指定位置的元素
}

遍历

除了继承自Collection 的三种迭代方式（迭代器、增强 for 遍历、 lambda 表达式），List 集合还有以下两种遍历方式：

直接使用 for 循环遍历

public static void main(String[] args) {
    List<String> strings = new ArrayList<>();
    for (int i = 0; i < 15; i++) {
        strings.add("" + i);
    }
    // for循环遍历
    for (int i = 0; i < strings.size(); i++) {
        System.out.println(strings.get(i));
    }

列表迭代器遍历

public static void main(String[] args) {
    List<String> strings = new ArrayList<>();
    for (int i = 0; i < 15; i++) {
        strings.add("" + i);
    }
    // 列表迭代器
    ListIterator<String> iterator = strings.listIterator()
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

注意：

列表迭代器提供了 add() 和 remove() 方法，用于在遍历过程中添加或删除元素
列表迭代器也提供了 previous() 和 hasPrevious() 方法，用于倒序遍历列表（需要注意指针位置问题）

List 集合的两个实现类

List 作为接口，自然有实现类。下面是 List 集合的两个实现类：

ArrayList 集合

ArrayList 集合基于数组，所以它也具有数组的特性：

查找快：可以直接通过索引查找数据
修改慢：增删元素时，需要移动其他元素

在创建 ArrayList 集合时，系统会进行以下操作：

以空参创建 ArrayList 的时候，系统会创建一个长度为0的 elementData 数组，并将 ArrayList 的成员变量 size 的值设置为0
添加第一个元素时，系统会再创建一个长度为10的新数组
每次添加一个元素，size 就加一
当数组被填满时，系统会创建一个长度为原来1.5倍的数组，并将原数组复制进去
如果一次添加的元素太多，以至于数组扩容后仍然无法容纳所有元素，那么系统会直接创建一个长度为“原数组长度”+“添加元素个数”的新数组，并容纳所有元素

ArrayList 适用于“查找多、修改少”的场景

LinkedList 集合

LinkedList 集合基于双向链表，所以它也具有链表的特性：

查找慢：需要遍历整个链表才能查找数据
修改快：增删元素时，不需要移动其他元素，只需要修改结点的指针域
可能断链：一般不发生（除非手写增删元素的方法）

LinkedList 的结点中包含三个部分：前驱指针域 prev 、数据域 data 、后继指针域 next

在创建 LinkedList 对象时，系统会做出以下操作：

以空参创建 LinkedList 集合对象时，系统会直接调用空参构造
添加元素时，系统会创建 Node 结点对象，并直接添加到链表的尾部（第一个元素则作为头结点）

LinkedList 集合有两个方法用于获取头节点和尾结点：

public static void main(String[] args) {
    LinkedList<String> strings = new LinkedList<>();
    for (int i = 0; i < 5; i++) {
        strings.add("string" + i);
    }

    System.out.println(strings.getFirst());     // 获取头节点 string0
    System.out.println(strings.getLast());      // 获取尾结点 string4
}

当然，LinkedList 也可以直接通过索引获取元素：

public static void main(String[] args) {
    LinkedList<String> strings = new LinkedList<>();
    for (int i = 0; i < 5; i++) {
        strings.add("string" + i);
    }

    System.out.println(strings.get(4);        // 获取下标为4的元素
}

LinkedList 适用于“修改多、查找少”的场景

Set 集合

Set 集合也是由 Collection 集合派生得到的，在 Set 中添加的元素则是无序、不重复、没有索引的

这也就引出 Set 的一些特性：

存取顺序不一致
可以去除重复的元素
不能使用索引获取元素

Set 集合的成员方法与 Collection 集合基本相同：

public static void main(String[] args) {
    Set<String> strings = new HashSet<>();
    boolean addSuccess = strings.add("123");                // 添加元素，返回false的时候说明存在重复元素
    boolean removeSuccess = strings.remove("123");      // 移除元素
    boolean isContain = strings.contains("234");            // 是否包含元素
    boolean isEmpty = strings.isEmpty();                    // 是否为空
    strings.clear();                                     // 清空集合
    int size = strings.size();                            // 返回集合大小
}

set 集合可以使用迭代器、增强for循环和lambda表达式进行遍历：

迭代器对象遍历

public static void main(String[] args) {
    Set<String> strings = new HashSet<>();
    for (int i = 0; i < 15; i++) {
        strings.add(String.valueOf(i));
    }

    Iterator<String> setIterator = strings.iterator();
    while (setIterator.hasNext()) {
        System.out.println(setIterator.next());
    }
}

增强的 for 循环遍历

public static void main(String[] args) {
    Set<String> strings = new HashSet<>();
    for (int i = 0; i < 15; i++) {
        strings.add(String.valueOf(i));
    }

    for (String string : strings) {
        System.out.println(string);
    }
}

lambda 表达式

public static void main(String[] args) {
    Set<String> strings = new HashSet<>();
    for (int i = 0; i < 15; i++) {
        strings.add(String.valueOf(i));
    }

    strings.forEach(s -> System.out.println(s));
    strings.forEach(System.out::println);        // lambda表达式的另一种写法
}

Set 集合的三个实现类

Set 作为集合，也有实现类，以下是它的三个实现类：

HashSet 集合

HashSet 集合基于哈希表，哈希表的数据存储原理如下：

定义哈希函数H(x)
通过哈希函数，将对象转换为哈希值（如将对象的某个属性值经转换得到的值作为哈希值）
将哈希值作为数组的索引，将数据存储到数组中

因为哈希函数的局限性，可能出现两个对象的哈希值相同的情况（冲突）。解决冲突的方法有：

拉链法：在出现冲突的索引创建一个链表，然后将冲突的元素添加进链表中
开地址法：将冲突的元素按一定规律添加到数组的空闲位置
双散列法：使用两个哈希函数生成哈希值

JAVA的 HashSet 使用拉链法解决冲突，添加元素步骤如下：

创建一个默认长度16，装填因子为0.75的数组
计算元素哈希值，并基于数组长度计算索引
如果索引位置为空，存入元素
如果索引位置不为空，先比较属性值，属性值相同则不存入元素，否则使用拉链法解决冲突
当哈希表装填因子大于0.75时，扩容哈希表

TreeSet 集合

TreeSet 基于红黑树，其中的元素不重复、无索引且可排序

向 TreeSet 中添加的元素会被自动排序，默认从小到大排序

排序规则如下：

数值类型：按照数值大小排序
字符类型：按照 ASCLL 码表排列
字符串类型：先比较高位字符，再比较低位字符，如果前n位字符均相同但是字符串长度不同（比如“abc”与“abcd”），较长的字符串更大
自定义引用类型：需要在类中定义比较规则或向 TreeSet 传递比较器 Comparator 才可以排序

定义比较规则

定义比较规则首先需要让类实现 Comparable 接口，并重写 compareTo() 方法

import java.util.Objects;

public class Class1 implements Comparable<Class1> {
    String name;
    int age;

    /*类中的其他成员方法*/

    @Override
    public int compareTo(Class1 o) {
        int r = this.age - o.age;
        return r;
    }
}

对于 compareTo() 方法，需要知道以下几点：

传入参数中的 o ：表示 TreeSet 中存在的元素
方法体中的 this ：表示当前向 TreeSet 添加的元素
返回值 r ：表示比较的结果，返回正数说明 this 大于 o ，需要添加到 o 的右边；返回负数说明 this 小于 o ，需要添加到 o 的左边；返回0说明两者相等，this 与 o 重复，不添加

传递比较器

在创建 TreeSet 对象时，也可以向构造方法中传递比较器 Comparator 对象，此时就可以在对象中定义比较方法：

public static void main(String[] args) {
    Random rand = new Random();
    TreeSet<String> strs = new TreeSet<>(new Comparator<String>() {
        @Override
        public int compare(String o1, String o2) {
            return o1.length() == o2.length() ? o1.compareTo(o2) : o1.length() - o2.length();
        }
    });
    for (int i = 0; i < 20; i++) {
        if (!strs.add("test" + rand.nextInt(100))) {
            i--;
        }
    }
    System.out.println(strs);
}

当然，它也可以使用 lambda 表达式书写：

public static void main(String[] args) {
    Random rand = new Random();
    TreeSet<String> strs = new TreeSet<>((o1, o2) -> o1.length() == o2.length() ? o1.compareTo(o2) : o1.length() - o2.length());
    for (int i = 0; i < 20; i++) {
        if (!strs.add("test" + rand.nextInt(100))) {
            i--;
        }
    }
    System.out.println(strs);

注意： 比较器对象的优先级高于 compareTo() 方法，两者共存时，系统会优先使用比较器对象的排序规则