开发: C++知识库 Java知识库 JavaScript Python PHP知识库人工智能区块链大数据移动开发嵌入式开发工具数据结构与算法开发测试游戏开发网络协议系统运维
教程: HTML教程 CSS教程 JavaScript教程 Go语言教程 JQuery教程 VUE教程 VUE3教程 Bootstrap教程 SQL数据库教程 C语言教程 C++教程 Java教程 Python教程 Python3教程 C#教程
数码: 电脑笔记本显卡显示器固态硬盘硬盘耳机手机 iphone vivo oppo 小米华为单反装机图拉丁

-> 数据结构与算法 -> Java中的常用集合，包括List系列和Map系类、以及正则表达式的简单应用和红黑树原理 -> 正文阅读

[数据结构与算法]Java中的常用集合，包括List系列和Map系类、以及正则表达式的简单应用和红黑树原理

集合

概述

📔 集合数组都是容器

📔 数组定义后类型确定，长度确定；

📔 集合可以动态调整；

📔 集合的泛型只能是引用类型 – 对象容器，因此8种基本类型得使用包装类；

Collection集合常用API

方法名	说明
public boolean add(E e)	把给定的对象添加到当前集合中
public void clear()	清空集合中所有的元素
public boolean remove(E e)	把给定的对象在当前集合中删除
public boolean contains(Object obj)	判断当前集合中是否包含给定的对象
public boolean isEmpty()	判断当前集合是否为空
public int size()	返回集合中元素的个数。
public Object[] toArray()	把集合中的元素，存储到数组中

Collection集合的遍历

迭代器遍历：

遍历就是一个一个的把容器中的元素访问一遍；
迭代器在Java中的代表是Iterator，迭代器是集合的专用遍历方式；

foreach遍历/增强for：

既可以遍历数组，又可以遍历集合；
它是JDK5之后出现的，其内部原理是一个Iterator迭代器，遍历集合相当于是迭代器的简化手法；
实现Iterator接口的类才可以使用迭代器和增强for，Collection接口已实现该接口；

Lambda表达式遍历：JDK8之后开始有；

package cn.edu.njust.collection;

import java.util.*;
import java.util.function.Consumer;

public class Demo01 {
    public static void main(String[] args) {
        Collection<String> list = new ArrayList<>();

        list.add("c");
        list.add("c++");
        list.add("Java");
        list.add("Python");
        list.add("HTML+CSS");
        list.add("JavaScript");

        // 使用迭代器遍历
        System.out.println("--------使用迭代器遍历--------");
        Iterator<String> it = list.iterator();
        while (it.hasNext()) {
            System.out.println(it.next());
        }

        // foreach\增强for循环遍历
        System.out.println("----foreach\\增强for循环遍历----");
        for (String s : list) {
            System.out.println(s);
        }

        // Lambda表达式遍历
        System.out.println("-------Lambda表达式遍历-------");
        // 匿名内部类
        list.forEach(new Consumer<String>() {
            @Override
            public void accept(String s) {
                System.out.println(s);
            }
        });

        // 化成Lambda表达式简
        System.out.println("-------化成Lambda表达式-------");
        list.forEach(s -> System.out.println(s));

        // 新技术
        System.out.println("-------新技术-------");
        list.forEach(System.out::println);
    }
}
/*
--------使用迭代器遍历--------
c
c++
Java
Python
HTML+CSS
JavaScript
----foreach\增强for循环遍历----
c
c++
Java
Python
HTML+CSS
JavaScript
-------Lambda表达式遍历-------
c
c++
Java
Python
HTML+CSS
JavaScript
-------化成Lambda表达式-------
c
c++
Java
Python
HTML+CSS
JavaScript
-------新技术-------
c
c++
Java
Python
HTML+CSS
JavaScript

*/

集合的体系结构

Collection（单列/接口）

简介：collection单列集合，每个元素只包含一个值；

List系列（接口）

📔 添加元素有序、可重复、有索引；

📔 List集合常用的是：ArrayList 和 LinkedList;

List集合特有的方法：List集合因为支持索引，所以多了很多索引操作的独特API，其他Collection的功能List也都继承了；

方法名	说明
void add(int index,E element)	在此集合中的指定位置插入指定的元素
E remove(int index)	删除指定索引处的元素，返回被删除的元素
E set(int index,E element)	修改指定索引处的元素，返回被修改的元素
E get(int index)	返回指定索引处的元素

List集合实现类的底层原理：

ArrayList底层是基于数组实现的，根据查询元素快，增删相对慢；
LinkedList底层基于双链表实现的，查询元素慢，增删元素相对较快；

List集合的遍历方式：

Collection支持的遍历方式List集合都适用；
根据List的特点，还能根据索引来遍历元素（常见的就是for循环根据索引遍历）；

ArrayList底层原理：

ArrayList底层是基于数组实现的：根据索引定位元素快，增删需要做元素的移位操作。
第一次创建集合并添加第一个元素的时候，在底层创建一个默认长度为10的数组。
当长度不够的时候，每次扩容1.5倍；

LinkedList底层原理：

底层数据结构是双链表，查询慢，首尾操作的速度是极快的，所以多了很多首尾操作的特有API。
特有功能：

方法名	说明
`public void addFirst(E e)`	在该列表开头插入指定的元素
`public void addLast(E e)`	将指定的元素追加到此列表的末尾
`public E getFirst()`	返回此列表中的第一个元素
`public E getLast()`	返回此列表中的最后一个元素
`public E removeFirst()`	从此列表中删除并返回第一个元素
`public E removeLast()`	从此列表中删除并返回最后一个元素

可以用来实现栈和队列：内置有压栈、出栈、入队、出队的操作等等；

注意事项：使用迭代器删除元素的时候，用it.remove；

Set系列（接口）

📔 添加元素无序、不可重复、无索引；

📔 Set系列常用：HashSet、LinkedHashSet和TreeSet；

? 📄 HashSet：无序、不重复、无索引；

? 📄 LinkedHashSet：有序、不重复、无索引；

? 📄 TreeSet：默认升序排列、不重复、无索引；

特点：

无序：存取顺序不一致，即第一次放进去的元素不是按照放发次序存储的；
不重复：可以去除重复；
无索引，不能使用普通for循环遍历元素；

功能：与Collection的API基本一致，没有扩展很多的API，主要是有更多的特点；

去重复的原因：先判断HashCode再判断equals，如果是自定义类型，需要重写这两个方法；

HashSet底层原理：

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

哈希表的储存：

在JDK8之前采用数组+链表+哈希算法（链地址法）；
在JDK8之后采用数组+链表+红黑树+哈希算法+红黑树；
- 在JDK8之后，链表长度超过8之后，自动转换成为红黑树；
- 其实就是在链地址法的基础上，当链表长度超过8时，将链表转换成红黑树；

实现类LinkedHashSet：

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

实现类TreeSet：

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

Map（双列/接口）

简介：

Map集合是一种双列集合，每个元素包含两个数据。
Map集合的每个元素的格式：key=value(键值对元素)。
Map集合也被称为**“键值对集合”**。

整体格式：

Collection集合的格式: [元素1,元素2,元素3..];
Map集合的完整格式：{key1=value1 , key2=value2 , key3=value3 , ...};

集合体系：

在这里插入图片描述

Map集合体系特点：

Map集合的特点都是由键决定的。
Map集合的键是无序,不重复的，无索引的，值不做要求（可以重复）。
Map集合后面重复的键对应的值会覆盖前面重复键的值。
Map集合的键值对都可以为null。

Map集合实现类特点：

HashMap:元素按照键是无序，不重复，无索引，值不做要求。（与Map体系一致）
LinkedHashMap:元素按照键是有序，不重复，无索引，值不做要求。
TreeMap：元素按照建是排序，不重复，无索引的，值不做要求。

示例：

package cn.edu.njust.map;

import java.util.HashMap;
import java.util.LinkedHashMap;
import java.util.Map;

public class Demo01 {
    public static void main(String[] args) {
        // 经典语句
        Map<String, Integer> map = new HashMap<>();
        map.put("c", 1);
        map.put("c++", 2);
        map.put("Java", 3);
        map.put("Python", 4);
        // 键值对不能重复，后面会覆盖前面的
        map.put("c", 5);
        // 允许用null
        map.put(null, null);

        System.out.println(map);
        /* 输出
         * {null=null, Java=3, c++=2, c=5, Python=4}
         * 说明HashMap是无序的
         * */

        Map<String, Integer> map1 = new LinkedHashMap<>();
        map1.put("c", 1);
        map1.put("c++", 2);
        map1.put("Java", 3);
        map1.put("Python", 4);
        // 键值对不能重复，后面会覆盖前面的
        map1.put("c", 5);
        // 允许用null
        map1.put(null, null);

        System.out.println(map1);
        /* 输出
         * {c=5, c++=2, Java=3, Python=4, null=null}
         * 说明LinkedHashMap是有序的
         * */
    }
}

Map集合常用的`API`

方法名	说明
`V put(K key,V value)`	添加元素
`V remove(Object key)`	根据键删除键值对元素
`void clear()`	移除所有的键值对元素
`boolean containsKey(Object key)`	判断集合是否包含指定的键
`boolean containsValue(Object value)`	判断集合是否包含指定的值
`boolean isEmpty()`	判断集合是否为空
`int size()`	集合的长度，也就是集合中键值对的个数

Map常用的遍历方式

方式一：键找值

过程：

先获取Map集合的全部键的Set集合。
遍历键的Set集合，然后通过键提取对应值。

方法名	说明
`Set<K> keySet()`	获取所有键的集合
`V get(Object key)`	根据键获取值

方式二：键值对

过程：

先把Map集合转换成Set集合，Set集合中每个元素都是键值对实体类型了。
遍历Set集合，然后提取键以及提取值。

方法名	说明
`Set<Map.Entry<K,V>> entrySet()`	获取所有键值对对象的集合
`K getKey()`	获得键
`V getValue()`	获取值

方式三：Lambda表达式

概述：得益于JDK 8开始的新技术Lambda表达式，提供了一种更简单、更直接的遍历集合的方式。

方法名	说明
`default void forEach(BiConsumer<? super K, ? super V> action)`	结合lambda遍历Map集合

代码演示

package cn.edu.njust.map;

import java.util.HashMap;
import java.util.Map;
import java.util.Set;
import java.util.function.BiConsumer;

public class Demo02 {
    public static void main(String[] args) {
        Map<String, Integer> map = new HashMap<>();
        map.put("c", 1);
        map.put("c++", 2);
        map.put("Java", 3);
        map.put("Python", 4);
        // 遍历测试
        System.out.println(map);
        /* 输出
         * {Java=3, c++=2, c=1, Python=4}
         * */

        // 方式一遍历：键找值
        System.out.println("----------方式一----------");
        // 1.首先获取全部的键
        Set<String> keys = map.keySet();
        // 2.遍历每个键，根据键值提取value
        for (String key : keys) {
            int value = map.get(key);
            System.out.println(key + " --> " + value);
        }
        /* 输出
         * Java --> 3
         * c++ --> 2
         * c --> 1
         * Python --> 4
         * */

        // 遍历方式二：键值对
        System.out.println("----------方式二----------");
        // 1.将Map转化成Set
        Set<Map.Entry<String, Integer>> entries = map.entrySet();
        // 2.通过ForEach遍历
        for (Map.Entry<String, Integer> entry : entries) {
            String key = entry.getKey();
            int value = entry.getValue();
            System.out.println(key + " --> " + value);
        }
        /* 输出
         * Java --> 3
         * c++ --> 2
         * c --> 1
         * Python --> 4
         * */

        // 方式三：Lambda表达式
        System.out.println("----------方式三----------");
        // 匿名内部类
        /*map.forEach(new BiConsumer<String, Integer>() {
            @Override
            public void accept(String key, Integer value) {
                System.out.println(key + " --> " + value);
            }
        });*/

        // Lambda表达式简化
        map.forEach((key, value) -> System.out.println(key + " --> " + value));

    }
}

`HashMap`详细

特点：

HashMap是Map里面的一个实现类。特点是由键决定的：无序、不重复、无索引；
没有额外需要学习的特有方法，直接使用Map里面的方法就可以了；
HashMap跟HashSet底层原理是一模一样的，都是哈希表结构，只是HashMap的每个元素包含两个值而已；

底层原理：

由键决定：无序、不重复、无索引。HashMap底层是哈希表结构的。
依赖hashCode方法和equals方法保证键的唯一。
如果键要存储的是自定义对象，需要重写hashCode和equals方法。
基于哈希表。增删改查的性能都较好。

`linkedHashMap`详细

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

`TreeMap`详解

特点：

由键决定特性：不重复、无索引、可排序
可排序：按照键数据的大小默认升序（有小到大）排序。只能对键排序。
注意：TreeMap集合是一定要排序的，可以默认排序，也可以将键按照指定的规则进行排序
TreeMap跟TreeSet一样底层原理是一样的。

TreeMap集合自定义排序规则有2种

类实现Comparable接口，重写比较规则。
集合自定义Comparator比较器对象，重写比较规则。

红黑树

概述：

红黑树是一种自平衡的二叉树找树，是计算机科学中用到的一种数据结构；
1972年出现，当时称为平衡二叉B树；1978年被修改为如今的”红黑树“；
每一个节点可以是红或者黑；不同于平衡二叉树，红黑树不通过高度平衡，是通过”红黑规则“进行平衡的；

在这里插入图片描述

红黑规则：

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

添加节点：

添加的节点的颜色，可以是红色，也可以是黑色的；
默认用红色效率高；即有新节点的时候，将该节点的颜色默认为红色进行调整；

规则：

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

泛型

概述：是JDK5中引入的特性，可以在编译阶段约束操作的数据类型，并进行检查；

格式：<数据类型>；

注意：

泛型只能支持引用数据类型；
集合体系的全部接口和实现类都是支持泛型的使用的；

泛型可以在很多地方进行定义：

类后面 --> 泛型类
方法申明 --> 泛型方法
接口后面 --> 泛型接口

分类

泛型类

概述：定义类的同时定义了泛型；

格式：修饰符 class 类名<泛型变量>{}

泛型方法

概述：定义方法的同时定义泛型；

格式：修饰符 <泛型变量> 方法返回值方法名称(形参列表){}

public<T> void show(T t){}

泛型接口

概述：定义了泛型的接口就是泛型接口；

格式：修饰符 interface 接口名<泛型变量>{}

功能：可以在实现类实现接口的时候，向接口传递自己实现的类型，从而约束实现类；

通配符

概述：?

?可以在”使用泛型“的时候代表一切类型；
E T K V是在定义泛型的时候使用的；

泛型的上下限

泛型上限：? extends Car： ? --> 必须是Car或者是其子类；
泛型下限：? super Car：? --> 必须是Car或者其父类

代码示例

package cn.edu.njust.generic;


import java.util.ArrayList;

/**
 * 研究通配符 ？ 的使用
 */
public class Demo02 {
    public static void main(String[] args) {
        ArrayList<BMW> bmws = new ArrayList<>();
        bmws.add(new BMW());
        bmws.add(new BMW());
        bmws.add(new BMW());
        go(bmws);

        ArrayList<BENZ> benzs = new ArrayList<>();
        benzs.add(new BENZ());
        benzs.add(new BENZ());
        benzs.add(new BENZ());
        go(benzs);

        ArrayList<Dog> dogs = new ArrayList<>();
        dogs.add(new Dog());
        // go(dogs);
    }

/*    // 显然这样会出错
    public static void go(ArrayList<BMW> cars) {

    }*/

    /*
     * 这样定义，也会出错，原因是：
     * 尽管BENZ和BMW都是Car的子类，但是他们的集合之间并没有继承上的关系
     * */
/*    public static void go(ArrayList<Car> cars) {

    }*/

    // 使用通配符 --> ?
    // 新问题：这样使用通配符，即使不是Car的子类，依然可以使用该方法 --> 代码23--25行
    // 于是退出新方法
    /*public static void go(ArrayList<?> cars){

    }*/

    /* 上限和下限
     * ? extends 类名
     * 此时25行代码报错
     * */
    public static void go(ArrayList<? extends Car> cars) {

    }

}


// 父类
class Car {

}

// 子类--宝马
class BMW extends Car {

}

// 子类--奔驰
class BENZ extends Car {

}

class Dog {

}

补充知识

可变参数

简介：

形参中可以接收多个数据；
可变参数的格式：数据类型...参数名称；

作用：

接收参数非常灵活，方便。可以不接收参数，可以接收1个或者多个参数，也可以接收一个数组
可变参数在方法内部本质上就是一个数组。

注意事项：

一个形参列表中可变参数只能有一个；
可变参数必须放在形参列表的最后面；

package cn.edu.njust.params;

public class Demo01 {
    public static void main(String[] args) {
        // 可变参数
        // 1.不传参数
        System.out.println(sum());
        // 2.传1个参数
        System.out.println(sum(12));
        // 3.传多个参数
        System.out.println(sum(1, 4));
        // 4.传一个数组
        System.out.println(sum(new int[]{13, 23, 43, 12}));

    }

    public static int sum(int... nums) {
        int sum = 0;
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
        }
        return sum;
    }
}
/*
0
12
5
91

*/

集合工具类

Collection集合工具类：

java.utils.Collections：是集合工具类；
作用：Collections并不属于集合，是用来操作集合的工具类；

方法名	说明
`public static <T> boolean addAll(Collection<? super T> c, T... elements)`	给集合对象批量添加元素
`public static void shuffle(List<?> list)`	打乱List集合元素的顺序
`public static <T> void sort(List<T> list)`	将集合中元素按照默认规则排序
`public static <T> void sort(List<T> list，Comparator<? super T> c)`	将集合中元素按照指定规则排序