Java入门学习笔记(6)：集合进阶 – 上

前言

前面学习过了 ArrayList 的基本使用，但依旧有许多需要学习。

由于这一部分许多知识我现阶段并不会用到，所以直接略过。

集合分类

分为单列集合 Collection 与双列 Map 集合。

字面意思即可理解。单列集合一次添加一个数据，而双列集合一次添加两个相对应的数据。

集合体系结构

Collection 分为 List 和 Set，都是接口。

List 系添加元素有序、可重复、可索引；Set 无序、不重复、不索引。

Collection 系集合

Collection 基本操作

如下示例：

package test;

import java.util.ArrayList;
import java.util.Collection;

public class test {
    public static void main(String[] args) {
        Collection<String> coll = new ArrayList<>();
        coll.add("a");
        coll.add("b");
        coll.add("c");
        System.out.println(coll);

        coll.remove("a");
        System.out.println(coll);

        coll.clear();
        System.out.println(coll);
    }
}

package test;

import java.util.ArrayList;
import java.util.Collection;

public class test {
    public static void main(String[] args) {
        Collection<String> coll = new ArrayList<>();
        coll.add("a");
        coll.add("b");
        coll.add("c");
        System.out.println(coll);

        coll.remove("a");
        System.out.println(coll);

        coll.clear();
        System.out.println(coll);
    }
}

应当输出：

[a, b, c]
[b, c]
[]

[a, b, c]
[b, c]
[]

*contain 方法依赖的 equals 方法默认继承自 Object 类的 equals，比较的是地址值，而不是属性值。

Collection 通用遍历方法

迭代器遍历

迭代器不依赖索引。依靠创建并移动指针来读出所有元素。

public class collection {
    public static void main(String[] args) {
        // 创建集合，添加元素
        Collection<String> coll = new ArrayList<>();
        coll.add("a");
        coll.add("b");
        coll.add("c");
        coll.add("d");

        //获取迭代器对象
        Iterator<String> it = coll.iterator();
        //循环
        while (it.hasNext()) {
            String str = it.next();
            System.out.println(str);
        }
    }
}

public class collection {
    public static void main(String[] args) {
        // 创建集合，添加元素
        Collection<String> coll = new ArrayList<>();
        coll.add("a");
        coll.add("b");
        coll.add("c");
        coll.add("d");

        //获取迭代器对象
        Iterator<String> it = coll.iterator();
        //循环
        while (it.hasNext()) {
            String str = it.next();
            System.out.println(str);
        }
    }
}

其它注意事项：

指针不再指向任何元素时调用 next 方法，会报错 NoSuchElementException
遍历结束后，指针不会复位
循环中只能使用一次使用 next 方法

增强 for 循环（foreach）遍历

增强 for 底层就是迭代器，可以简化书写
JDK5 后出现
单列集合和数组才可以增强 for 遍历

package com.CollctionForEach;

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

public class Demo1 {
    public static void main(String[] args) {
        Collection<String> names = new ArrayList<>();
        names.add("张三");
        names.add("李四");
        names.add("王五");
        names.add("赵六");

        for (String s : names) {
            System.out.println(s);
        }
    }
}

package com.CollctionForEach;

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

public class Demo1 {
    public static void main(String[] args) {
        Collection<String> names = new ArrayList<>();
        names.add("张三");
        names.add("李四");
        names.add("王五");
        names.add("赵六");

        for (String s : names) {
            System.out.println(s);
        }
    }
}

lambda 表达式遍历

package com.CollctionForEach;

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

public class Demo1 {
    public static void main(String[] args) {
        Collection<String> names = new ArrayList<>();
        names.add("张三");
        names.add("李四");
        names.add("王五");
        names.add("赵六");

        names.forEach(name -> System.out.println(name));
    }
}

package com.CollctionForEach;

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

public class Demo1 {
    public static void main(String[] args) {
        Collection<String> names = new ArrayList<>();
        names.add("张三");
        names.add("李四");
        names.add("王五");
        names.add("赵六");

        names.forEach(name -> System.out.println(name));
    }
}

List 系集合

继承了 Collection 方法。因为 Collection 是 List 的超级接口。

由于 List 集合拥有索引，所以多了很多索引操作。

List 常用方法：

add() - 将元素添加到列表
addAll() - 将一个列表的所有元素添加到另一个
get() - 有助于从列表中随机访问元素
iterator() - 返回迭代器对象，该对象可用于顺序访问列表的元素
set() - 更改列表的元素
remove() - 从列表中删除一个元素
removeAll() - 从列表中删除所有元素
clear() - 从列表中删除所有元素（比removeAll()效率更高）
size() - 返回列表的长度
toArray() - 将列表转换为数组
contains() - 如果列表包含指定的元素，则返回true

add() 方法包含两个参数，一个 index，一个 element。如果索引上已存在数据，则后面所有元素都后移。

remove() 可以删除指定索引的元素，同时返回删除的元素。

List 遍历方式

由于继承了 Collection，所以可以使用上面提到的通用遍历方法。

多了个索引，就可以用普通 for 循环了：

for (int i = 0; i < list.size(); i++) {
  String item = list.get(i);
  sout(item);
}

for (int i = 0; i < list.size(); i++) {
  String item = list.get(i);
  sout(item);
}

数据结构（一）

栈

后进先出，先进后出。

队列

先进先出，后进后出。

数据从后端进队列的过程，叫作入队列。

数据从前端出队列的过程，叫作出队列。

数组

由于添加、删除元素都需要移动一批元素，所以增删速度慢。

但是查询速度快，因为元素在内存中是连续存储的。

链表

链表种的每一个元素，成为结点，每个结点都是一个独立的对象，拥有自己的地址值。每个结点中，不仅会存储自己的数据，还会存储下一个结点的地址值。与链条结构很相似。

创建的第一个结点，叫作头结点。

添加数据：创建新结点，在头节点存储新结点的地址值，即可将结点串联起来。“^”表示空地址值。

所以，链表的查找速度较慢。数组在内存中是一篇连续的空间，本质上只需要一个数组的地址值，随后就可以使用索引找到元素。链表查找数据则必须从头结点开始查找，一个个向后。

不过，链表插入数据并不需要像数组那样将一大批的元素后后移，直接修改地址值就可以完成数据的插入。因此，链表的增删速度较快。

我们可以像每个结点中塞入两个地址值，这样它就可以完成双向查找，效率大幅提升，称为双向链表。

泛型

概述

JDK5 引入的新特性，可以在编译阶段约束操作数据的类型，并进行检查。

格式：<数据类型>。

泛型只支持引用数据类型。

如果不设定泛型，集合中所有数据类型都是 Object 类。

泛型的好处：

统一数据类型
将运行时会出现的问题提前至编译阶段检查，可以规避一系列数据类型错误

Java 中的泛型，是伪泛型。意思就是，这个泛型，只在编译时期有效。

泛型类

例如：

public class ArrayList<E>{

}

public class ArrayList<E>{

}

不确定成员数据类型时，可以使用泛型。

任意字母都可以，比如 Type，Element，Key，Value。

泛型方法

一个方法的形参不确定的话，可以在类添加泛型，也可以单独给一个方法加上泛型。例如 public static<E> void method(E e){}。

其它

泛型本身不可继承，但数据具备继承性。

数据结构（二）

二叉树

由父节点、左/右子节点构成。

每个节点都是独立的对象，不仅存储当前数据，还会按需存储父节点、左/右子节点的地址值。

一些术语

度

每个节点的子节点数量，叫作度。任意节点度 <= 2 的，叫作二叉树。

二叉搜索树树的数据规律

遵守一个规则：小在左，大在右，一样就跳过。

二叉树的遍历方式

前序遍历：根结点 ---> 左子树 ---> 右子树

中序遍历：左子树---> 根结点 ---> 右子树

后序遍历：左子树 ---> 右子树 ---> 根结点

层次遍历：只需按层次遍历即可

平衡二叉树

任意节点的左右子树高度差不超过一。

平衡二叉树的旋转机制

确定支点：不断向父节点寻找不平衡的节点。

以不平衡的点为支点
将支点左旋降级，使其成为左子节点
晋升原本的右子节点

右旋同理。

二叉树需要旋转的四种情况

一、左左

当根节点左子树的左子树点有节点插入，导致二叉树不平衡时。

右旋一次可以保持平衡。

二、左右

根节点的左子树的右子树有节点插入。

先将左子树局部左旋使其成为“左左”的情况，然后右旋即可恢复平衡。

三、右右

与“左左相反”。左旋一次恢复平衡。

四、右左

同理，局部右旋，随后左旋。

红黑树

概述

红黑树是一种自平衡的二叉查找树，是计算机科学中用到的一种数据结构
1972 年出现，当时被称之为平衡二叉B树。后来，1978 年被修改为如今的“红黑树"
它是一种特殊的二叉查找树，红黑树的每一个节点上都有存储位表示节点的颜色
每一个节点可以是红或者黑；红黑树不是高度平衡的，它的平衡是通过”红黑规则”进行实现的

是一个二叉查找树。

并不高度平衡，平衡靠红黑规则保证，比二叉树的“任意节点的左右子树高度差不超过一”的要求宽松一些。

红黑规则

每一个节点或是红色的，或者是黑色的
根节点必须是黑色
如果一个节点没有子节点或者父节点，则该节点相应的指针属性值为Nil，这些Nil视为叶节点，每个叶节点（Nil)是黑色的
如果某一个节点是红色，那么它的子节点必须是黑色（不能出现两个红色节点相连的情况）
对每一个节点，从该节点到其所有后代叶节点的简单路径上，均包含相同数目的黑色节点

红黑树的节点中，会多存储一个颜色属性，即黑或红。

添加的节点默认为红色。因为如果添加黑色的话，会违反第五条规则，还需要更换一下颜色。

Set 类集合

概述

无序：存取顺序不一致
不重复：可以去除重复
无索引：没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取元素

Set 类集合的实现类

HashSet：无序、不重复、无索引
LinkedHashSet：有序、不重复、无索引
TreeSet:可排序、不重复、无索引

Set 集合的方法与 Collection 方法基本一致。

HashSet 概述

没有什么新方法，直接了解一下原理即可。

不从 0 索引开始向后存储，而是依据一定计算得到整数索引。

int index = (数组长度 - 1) & HashCode;

int index = (数组长度 - 1) & HashCode;

哈希值

对象的整数表现形式。

根据hashCode方法算出来的int类型的整数
该方法定义在Object类中，所有对象都可以调用，默认使用地址值进行计算
一般情况下，会重写hashCode方法，利用对象内部的属性值计算哈希值

对象的哈希值属性：

如果没有重写 hashCode 方法，不同对象计算出的哈希值是不同的
如果已经重写 hashCode 方法，不同的对象只要属性值相同，计算出的哈希值就是一样的
在小部分情况下，不同的属性值或者不同的地址值计算出来的哈希值也有可能一样。（哈希碰撞——概率极小，但确有可能）

我们来演示一下，这里创建两个对象并获取其哈希值。

public class demo {
    public static void main(String[] args) {
        Student s1 = new Student("zhangsan",23);
        Student s2 = new Student("zhangsan",23);
        System.out.println(s1.hashCode());
        System.out.println(s2.hashCode());
    }
}

public class demo {
    public static void main(String[] args) {
        Student s1 = new Student("zhangsan",23);
        Student s2 = new Student("zhangsan",23);
        System.out.println(s1.hashCode());
        System.out.println(s2.hashCode());
    }
}

输出：

26697217
3022630

26697217
3022630

对于哈希碰撞，我们也可以模拟：

public class demo {
    public static void main(String[] args) {
        System.out.println("abc".hashCode());
        System.out.println("acD".hashCode());
    }
}

public class demo {
    public static void main(String[] args) {
        System.out.println("abc".hashCode());
        System.out.println("acD".hashCode());
    }
}

输出：

96354
96354

96354
96354

HashSet 底层原理

HashSet集合底层采取哈希表存储数据
哈希表是一种对于增删改查数据性能都较好的结构

Hash 表的组成

JDK8之前：数组+链表
JDK8开始：数组+链表+红黑树

模拟一下：

创建一个默认长度16，默认加载因为0.75的数组，数组名table
根据元素的哈希值跟数组的长度计算出应存入的位置
判断当前位置是否为null，如果是null直接存入
如果位置不为null，表示有元素，则调用equals方法比较属性值
一样：不存
不一样：存入数组，形成链表——JDK8以前：新元素存入数组，老元素挂在新元素下面；JDK8以后：新元素直接挂在老元素下面

同时，当链表长度大于 8 且数组长度大于 64 时，该链表自动转换为红黑树以提高查改效率。

这时，就会出现三种数据结构：table[] 数组，链表，还有转换后的红黑树。也就是上面说的”数组+链表+红黑树“。

如果集合中存储的是自定义对象，必须要重写 hashcode 和 equals 方法。

关于 HashSet 的三个问题

问题一：为什么 HashSet 的存取的顺序不一样？

既然索引是计算而来，就有可能出现后添加的数据存储在前边的情况了。

问题二：为什么 HashSet 没有索引？

首先，HashSet 是不重复的（HashCode 与 equals 方法）。

而且，有索引的是数组，链表会挂许多元素。我们不能够根据链表头结点所在的索引去找到链表里的元素。所以，是不索引的。

问题三：如何保证去重？

HashCode 与 equals 方法。

一样的会跳过不存。不存在重复数据的情况。

综上，我们书写如下代码：

import java.util.HashSet;

public class demo {
    public static void main(String[] args) {
        Student s1 = new Student("zhangsan",23);
        Student s2 = new Student("lisi",24);
        Student s3 = new Student("wangwu",25);
        Student s4 = new Student("zhangsan",23);

        HashSet<Student> hs = new HashSet<>();
        System.out.println(hs.add(s1));
        System.out.println(hs.add(s2));
        System.out.println(hs.add(s3));
        System.out.println(hs.add(s4));

        System.out.println(hs);
    }
}

// 输出：
// true
// true
// true
// false
// [Student@42ca5bd9, Student@62365a6, Student@a8e9e1e4]
// 打印地址值是因为没有重写 toString

import java.util.HashSet;

public class demo {
    public static void main(String[] args) {
        Student s1 = new Student("zhangsan",23);
        Student s2 = new Student("lisi",24);
        Student s3 = new Student("wangwu",25);
        Student s4 = new Student("zhangsan",23);

        HashSet<Student> hs = new HashSet<>();
        System.out.println(hs.add(s1));
        System.out.println(hs.add(s2));
        System.out.println(hs.add(s3));
        System.out.println(hs.add(s4));

        System.out.println(hs);
    }
}

// 输出：
// true
// true
// true
// false
// [Student@42ca5bd9, Student@62365a6, Student@a8e9e1e4]
// 打印地址值是因为没有重写 toString

并且在 Student 类中重写 hashCode() 和 equals()，基于 name 和 age 来定义相等的逻辑。不然会返回四个 true：

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Student student = (Student) obj;
        return age == student.age && Objects.equals(name, student.name);
    }

    @Override
    public int hashCode() {
        return Objects.hash(name, age);
    }

    @Override
    public boolean equals(Object obj) {
        if (this == obj) return true;
        if (obj == null || getClass() != obj.getClass()) return false;
        Student student = (Student) obj;
        return age == student.age && Objects.equals(name, student.name);
    }

LinkedHashSet 概述

有序、不重复、无索引。
这里的有序指的是保证存储和取出的元素顺序一致
原理：底层数据结构是依然哈希表，只是每个元素又额外的多了一个双链表的机制记录存储的顺序。

每一个结点都会同相邻存储的数据建立一个双向链表。这样，取出时，顺序就是一样的了。

由于我们需要观察去除顺序，这里顺手重写一下 Student 类的 toString 方法：

public String toString () { return "Student{name =" + name + ", age =" + age + "}"; }

public String toString () { return "Student{name =" + name + ", age =" + age + "}"; }

import java.util.LinkedHashSet;

public class demo {
    public static void main(String[] args) {
        Student s1 = new Student("zhangsan",23);
        Student s2 = new Student("lisi",24);
        Student s3 = new Student("wangwu",25);
        Student s4 = new Student("zhangsan",23);

        LinkedHashSet<Student> hs = new LinkedHashSet<>();
        System.out.println(hs.add(s1));
        System.out.println(hs.add(s2));
        System.out.println(hs.add(s3));
        System.out.println(hs.add(s4));

        System.out.println(hs);
    }
}
// input：
// true
// true
// true
// false
// [Student{name =zhangsan, age =23}, Student{name =lisi, age =24}, Student{name =wangwu, age =25}]

import java.util.LinkedHashSet;

public class demo {
    public static void main(String[] args) {
        Student s1 = new Student("zhangsan",23);
        Student s2 = new Student("lisi",24);
        Student s3 = new Student("wangwu",25);
        Student s4 = new Student("zhangsan",23);

        LinkedHashSet<Student> hs = new LinkedHashSet<>();
        System.out.println(hs.add(s1));
        System.out.println(hs.add(s2));
        System.out.println(hs.add(s3));
        System.out.println(hs.add(s4));

        System.out.println(hs);
    }
}
// input：
// true
// true
// true
// false
// [Student{name =zhangsan, age =23}, Student{name =lisi, age =24}, Student{name =wangwu, age =25}]

可以观察到，数据的取出确实是有序的。

TreeSet 概述

不重复、无索引、可排序
可排序：按照元素的默认规则（有小到大）排序
TreeSet集合底层是基于红黑树的数据结构实现排序的，增删改查性能都较好

// import java.util.LinkedHashSet;

import java.util.TreeSet;

public class demo {
    public static void main(String[] args) {
        // Student s1 = new Student("zhangsan",23);
        // Student s2 = new Student("lisi",24);
        // Student s3 = new Student("wangwu",25);
        // Student s4 = new Student("zhangsan",23);

        TreeSet<Integer> hs = new TreeSet<>();
        hs.add(5);
        hs.add(2);
        hs.add(3);
        hs.add(4);
        hs.add(1);
        System.out.println(hs);
    }
}
// 输出：
// [1, 2, 3, 4, 5]
// 这是因为 TreeSet 默认从小到大自动排序

// import java.util.LinkedHashSet;

import java.util.TreeSet;

public class demo {
    public static void main(String[] args) {
        // Student s1 = new Student("zhangsan",23);
        // Student s2 = new Student("lisi",24);
        // Student s3 = new Student("wangwu",25);
        // Student s4 = new Student("zhangsan",23);

        TreeSet<Integer> hs = new TreeSet<>();
        hs.add(5);
        hs.add(2);
        hs.add(3);
        hs.add(4);
        hs.add(1);
        System.out.println(hs);
    }
}
// 输出：
// [1, 2, 3, 4, 5]
// 这是因为 TreeSet 默认从小到大自动排序

TreeSet 集合默认的规则

对于数值类型：Integer，Double，默认按照从小到大的顺序进行排序。
对于字符、字符串类型：按照字符在ASCII码表中的数字升序进行排序。

TreeSet 比较器排序

Student 类：

public class Student {
	private String name;
	private int age;
	
	public Student(String name, int age) {
		super();
		this.name = name;
		this.age = age;
	}
	
	@Override
	public String toString() {
		return "Student [name=" + name + ", age=" + age + "]";
	}
}

public class Student {
	private String name;
	private int age;
	
	public Student(String name, int age) {
		super();
		this.name = name;
		this.age = age;
	}
	
	@Override
	public String toString() {
		return "Student [name=" + name + ", age=" + age + "]";
	}
}

测试类：

public class DemoTreeSet {
	public static void main(String[] args) {
		TreeSet<Student> ts = new TreeSet<>();
		ts.add(new Student("张廷玉",43));
		ts.add(new Student("纳兰明珠",80));
		ts.add(new Student("索额图",79));
		System.out.println(ts);
	}
}

public class DemoTreeSet {
	public static void main(String[] args) {
		TreeSet<Student> ts = new TreeSet<>();
		ts.add(new Student("张廷玉",43));
		ts.add(new Student("纳兰明珠",80));
		ts.add(new Student("索额图",79));
		System.out.println(ts);
	}
}

如果没有自定义比较器，TreeSet 集合存储的对象元素必须实现 Comparable 接口。这里我们的 Student 类既没有定义比较器，没有实现 Comparable 接口，所以会报 java.lang.ClassCastException 异常，意思就是这里存的元素不是 Comparable 类型的。

实现 Comparable 接口：

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

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

按照这个规则，就可以实现依照 age 属性进行升序排序了。

光 · 昭

前言