[数据结构与算法]学习Java中集合

目录

1.集合概述

2.Collection 集合概述和使用

3.Collection 集合的遍历

4.增强for循环——foreach

5.List 集合

6.数据结构

7.LinkedList 集合

8.泛型

9.Set 集合

10.TreeSet 集合

11.树的数据结构

12.红黑树

13.HashSet 集合

14.Map 集合

15.HashMap 集合

16.TreeMap 集合

1.集合概述

集合概念
????????一种容器，可以保存多个对象

集合类为什么有这么多
? ? ? ? 需求不一样

CRUD 增删改查：? ? （体系，CRUD，遍历，特点）
????????增加(Create)、检索(Retrieve)、更新(Update)和删除(Delete)：

2.Collection 集合概述和使用

Collection 集合概述
? ? ? ? 是单列集合的顶层接口，它表示一组对象，这些对象也称未Collection的元素
? ? ? ? JDK不提供此接口的任何直接实现，它提供个更具体的子接口（如Set、List）实现

创建Collection 集合的对象
? ? ? ? 多态的方式
? ? ? ? 具体的实现类ArrayList

特点：
? ? ? ? 是单列集合的顶层接口，拥有单列集合的共性功能，只有增删

public class Main {
    public static void main(String[] args) {
        Collection<Integer> cl = new ArrayList<>();
        cl.add(1);
        cl.add(22);
        cl.add(333);
        cl.add(4444);
        System.out.println(cl);
        cl.removeIf(integer -> integer < 300);
        System.out.println(cl);
    }
}

执行结果：

3.Collection 集合的遍历

Iterator?：迭代器，集合的专用遍历方式（集合自带的方法，不常用）
????????Iterator <E> iterator()：返回集合中的迭代器对象，该对象默认指向当前集合的0索引。

Iterator 中的常用方法
? ? ? ? boolean hasNext ()：判断当前位置是否有元素可以被取出
? ? ? ? E next ()：获取当前位置的元素
? ? ? ? ? ? ? ? ? ? ? ? ?将迭代器对象移向下一个索引位置

public class Main {
    public static void main(String[] args) {
        Collection<Integer> cl = new ArrayList<>();
        cl.add(1);
        cl.add(22);
        cl.add(333);
        cl.add(4444);
        Iterator<Integer> iterator = cl.iterator();
        while (iterator.hasNext()) {
            Integer s =  iterator.next();
            if (s <= 22){
                //不直接通过集合删除
                iterator.remove();
            }
        }
        System.out.println(cl);
    }
}

执行结果：

4.增强for循环——foreach

增强for：简化数组和Collection 集合的遍历? ? ? ? （常用遍历）
? ? ? ? 它是JDK 5之后出现的，其内部原理是一个Iterator迭代器
? ? ? ? 实现Iterable 接口的类才可以使用迭代器和增强for （Collection和数组可以，Map不行）

增强for 的格式
? ? ? ? for（元素数据类型? 变量名 ： 数组或者Collection集合）{
? ? ? ? ? ? ? ? //在此出使用变量即可，该变量就是元素
? ? ? ? }

public class Main {
    public static void main(String[] args) {
        Collection<Integer> cl = new ArrayList<>();
        cl.add(1);
        cl.add(22);
        cl.add(333);
        cl.add(4444);
        for (Integer n : cl) {
            System.out.println(n);
        }
    }
}

执行结果：

5.List 集合

List 集合概述? ? ? ? (比Collection 多一种遍历，因为有索引，可以普通for遍历)
? ? ? ? 有序集合，这里的有序指的是存取顺序
? ? ? ? 用户可以精确控制列表中每个元素的插入位置。用户可以通过整数索引访问元素，并搜索列表中的元素
? ? ? ? 与Set集合不同，列表通常允许重复的元素

List 集合的特点
? ? ? ? 有序（非排序）：存储和取出的元素顺序一致
? ? ? ? 有索引：可以通过索引操作元素
? ? ? ? 可重复：存储的元素可以重复

6.数据结构

数据结构是计算机存储，组织数据的方式。是指互相之间存在的一种或多种特定关系的数据元素的集合，通常情况下，精心选择的数据结构可以带来更高的运行或者存储效率

栈? ? ? ? ? ?（先进后出）?
队列? ? ? ?（先进先出）
数组：? ? ? (是一种查询快，增删慢的模型)
? ? ? ? 查询数据通过地址值和索引定位，查询任意数据耗时相同，查询速度快
? ? ? ? 删除数据时，要将原始数据删除，同时后面每个数据前移，删除效率低
? ? ? ? 添加数据时，添加位置后的每个数据后移，再添加元素，添加效率极低
链表? ? ? ? ?(是一种查询慢，增删快的模型，对比数组)

List 集合常用子类：ArrayList 、 LinkedList
? ? ? ? ArrayList：底层数据结构是数组，查询快，增删慢? （常用就不说了）
? ? ? ? LinkedList：底层数据结构是链表，查询慢，增删快

7.LinkedList 集合

LinkedList 成员方法? (实现了栈、队列)
? ? ? ? 栈? ? ? ? push()? ? ? ? pop()
? ? ? 队列? ? ? ?offer()? ? ? ? poll()

8.泛型

泛型：是JDK 5中引入的特性，参数化类型，它提供了编译时类型安全检测机制

泛型的好处：
? ? ? ? 把运行时期的问题提前到了编译时间
? ? ? ? 避免了强制类型转换

泛型的定义格式：
? ? ? ? <类型>：指定一种类型的格式。
? ? ? ? ? ? ? ? ? ? ? ? 尖括号里面可以任意书写，按照变量的定义规则即可。一般只写一个字母。
? ? ? ? ? ? ? ? ? ? ? ? 比如：<E> <T> <Q> <M>? ? ? ? (如T，E，K，V常用于表示泛型)

? ? ? ? <类型1，类型2>：指定多种类型的格式，多种类型之间用逗号隔开。
? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 比如：<E，T> <Q，M> <K，V>

泛型可以使用的地方：
? ? ? ? 类后面? ? ? ? ? ? ? ? ——>? ? ? ? 泛型类
? ? ? ? 方法声明上? ? ? ? ?——>? ? ? ? 泛型方法
? ? ? ? 接口后面? ? ? ? ? ? ?——>? ? ? ? 泛型接口?

泛型类：
? ? ? ? 格式：修饰符 class 类名 <类型> {}
? ? ? ? 范例：public class Generic <T> {}

泛型方法
? ? ? ? 格式：修饰符 <类型> 返回值类型 方法名 (类型 变量名) {}
? ? ? ? 范例：public <T> void show (T t) {}

泛型接口
? ? ? ? 格式：修饰符 interface 接口名 <类型> {}
? ? ? ? 范例：public interface Generic <T> {}

泛型通配符：<？>
? ? ? ? ArrayList<?>：表示元素类型位置的ArrayList，它的元素可以匹配任何的类型
? ? ? ? 但时并不能把元素添加到ArrayList中了，获取出来的也是父类类型

通配符上限：<？ extends 类型>
? ? ? ? 比如 ArrayList <？extendes Number> ：它表示的类型时Number或者其子类型

通配符下限：<？super 类型>
????????

泛型类的总结：? ? ? ? (泛型擦除)
? ? ? ? 如果一个类的后面有<E>，表示这个类是一个泛型类
? ? ? ? 创建泛型类的对象时，必须要给这个泛型确定具体的数据类型

9.Set 集合

Set 集合特点? ? ? ? ? ? ? ? ? ? ?(可以使用Collection下所用方法)
? ? ? ? 可以去除重复
? ? ? ? 存取顺序不一致
? ? ? ? 没有带索引的方法，所以不能使用普通for循环遍历，也不能通过索引来获取、删除Set集合里面的元素

10.TreeSet 集合

TreeSet 集合特点? ? ? ? ? ? ? ? （底层红黑树）
? ? ? ? 不包含重复元素的集合
? ? ? ? 没有带索引的方放
? ? ? ? 可以将元素按照规则进行排序? ? ? ? (需要指定排序规则)

自然排序Comparable
? ? ? ? 使用空参构造创建TreeSet集合
? ? ? ? 自定义的Student 类实现Comparable 接口
? ? ? ? 重写里面的comparableTo 方法

自然排序简单原理图
? ? ? ? 如果返回值为负数，表示当前存入的元素是较小值，存左边
? ? ? ? 如果返回值为0，表示当前存入的元素更集合中元素重复了，不存
? ? ? ? 如果返回值为正数，表示当前存入的元素是较大值，存右边

比较器排序Comparator
? ? ? ? TreeSet 的带参构造方法使用的是比较器排序对元素进行排序的
? ? ? ? 比较器排序，就是让集合构造方法接受Comparator 的实现类对象，重写compare 方法
? ? ? ? 重写方法是，一i的那个注意排序规则必须按照要求的主要条件和次要条件来写

两种比较方式小结
? ? ?自然排序：自定义类实现Comparable 接口，重写compareTo 方法，根据返回值进行排序
? ? ?比较器排序：创建TreeSet 对象得时候传递Comparator 得实现类对象，重写compare方法，根据返回值进行排序。
? ? ?再使用的时候，默认使用自然排序，当自然排序不满足现在的需求时，使用比较器排序

两种方式中，关于返回值的规则：
? ? ? ? 如果返回值为负数，表示当前存入的元素是较小值，存左边
? ? ? ? 如果返回值为0 ，表示当前存入的元素跟集合中元素重复了，不存
? ? ? ? 如果返回值为正数，表示当前存入的元素是较大值，存右边

    //使用空参构造
    @Override
    public int compareTo(Student o) {
        int result = this.age - o.getAge();
        if (result == 0){
            Collator instance = Collator.getInstance(Locale.CANADA);
            return instance.compare(this.name,o.name);
        }
        return result;
    }

    //使用比造器
    TreeSet<Student> ts = new TreeSet<>(
        (o1, o2) -> {
            int result = o1.getAge() - o2.getAge();
            if (result == 0){
                Collator instance = Collator.getInstance(Locale.CANADA);
                return instance.compare(o1.getName(),o2.getName());
            }
            return result;
        }
    );

11.树的数据结构

二叉树：
? ? ? ? 每个结点由四部分组成：
? ? ? ? ? ? ? ? 父节点地址
? ? ? ? ? ? ? ? ? ? ? 值
? ? ? ??左子节点?? 右子节点
? ? ? ? ? ? ?地址? ? ? ? 地址

一些名词：
? ? ? ? ? 度：每个节点的子节点数目
? ? ? 树高： 二叉树的最大长度
? ?根节点：最顶层的节点
? ?左子树：根节点的左侧? ? ? ? ?右边同理

二叉查找树规则：
? ? ? ? 小的存左边
? ? ? ? 大的存右边
? ? ? ? 一样的不存

平衡二叉树：
? ? ? ? 二叉树左右两个子数的高度差不超过1
? ? ? ? 任意节点的左右两个子数都是一棵平衡二叉树

?完全二叉树...左旋...右旋...

public class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {}

    TreeNode(int val) { this.val = val; }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

12.红黑树

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

红黑树：
? ? ? ? 每个节点由五部分组成：
? ? ? ? ? ? ? ? 父节点地址
? ? ? ? ? ? ? ? ? ? ? 值
? ? ? ??左子节点?? 右子节点
? ? ? ? ? ? ?地址? ? ? ? 地址
? ? ? ? ? ? ? ? ? ?颜色值

红黑规则
? ? ? ? 1.每一个节点或是红色，或是黑色的。
? ? ? ? 2.根节点必须是黑色的
? ? ? ? 3.叶子节点必须是黑色的
? ? ? ? 4.不能出现两个红色结点相连的情况
? ? ? ? 5.对每一个节点，从该节点到其所有后代叶子节点的简单路径上，均包含相同数目的黑色节点

13.HashSet 集合

HashSet 结合特点? ? ? ? （底层源码就是HashMap）
? ? ? ? 底层数据结构是哈希表
? ? ? ? 不能保证存储和取出的顺序完全一致
? ? ? ? 没有带所用的方法，所以不能通过普通for循环遍历
? ? ? ? 由于是Set集合，所以元素唯一? ? ? (重写hashCode 和 equals 方法)

哈希值
? ? ? ? 是JDK 更具对象的地址或者属性值，算出来的int类型的整数

Object 类中有一个方法可以获取对象的哈希值
? ? ? ? public int hashCode（）：更具对象的地址计算出来的哈希值

对象的哈希值特点
? ? ? ? 如果没有重写的hashCode 方法，那么是根据对象的地址值计算出来的哈希值
? ? ? ? ? ? ? ? 同一个对象多次调用hashCode() 方法返回的哈希值是相同的
? ? ? ? ? ? ? ? 不同对象的哈希值是不一样的

? ? ? ? 如果重写了hashCode 方法，一般都是通过对象的属性值计算出哈希值
? ? ? ? ? ? ? ? 如果不同的对象属性值是一样的，那么计算出来的哈希值也是一样的

哈希表
? ? ? ? JDK 8之前，底层采用数组+链表实现
? ? ? ? JDK 8以后，底层进行了优化。由数组+链表+红黑树实现。（链表超过8改用红黑树）

HashSet 1.7版本原理解析
? ? ? ? 1.创建一个默认长度16，默认加载因子0.75的数组
? ? ? ? 2.根据元素的哈希值跟数组的长度计算出应存入的位置
? ? ? ? 3.判断当前位置是否为null，如果是null直接存入
? ? ? ? 4.如果应存入的位置不为null，表示由元素，则调用equals方法比较属性值
? ? ? ? 5.如果一样，则不存，如果不一样，则存入数组，老元素挂在新元素下面

HashSet 1.8版本原理解析
? ? ? ? 原理同上，当链表长度超过8时，再添加自动转成红黑树
? ? ? ? 因为当挂在下面的元素过多，不利于添加，也不利于查询，所以JDK 8以后
? ? ? ? 当链表长度超过8的时候，会自动转换为红黑树
????????

14.Map 集合

Map 集合概述： （双列集合）
? ? ? ? Interface Map<K，V>? 键值对
? ? ? ? 键不能重复，值可以重复
? ? ? ? 键值是一一对应的，每个键只能找到自己对应的值
? ? ? ? (键 + 值) 这个整体我们称之为“键值对” 或者“键值对对象” ，再Java中叫做“Entry对象”

三种遍历方式：

public class Main {
    public static void main(String[] args) {
        Map<Student, String> ms = new HashMap();
        ms.put(new Student("小鹏", 21), "中国");
        ms.put(new Student("小强", 22), "中国");
        ms.put(new Student("小鹏", 21), "中国");
        //第一种遍历
        Set<Student> keys = ms.keySet();
        for (Student k : keys) {
            String v = ms.get(k);
            System.out.println(k + "  " + v);
        }
        //第二种遍历
        Set<Map.Entry<Student, String>> entries = ms.entrySet();
        for (Map.Entry<Student, String> entry : entries) {
            Student k = entry.getKey();
            String v = entry.getValue();
            System.out.println(k + "  " + v);
        }
        //第三种遍历
        ms.forEach(
                (k, v) -> System.out.println(k + "  " + v)
        );
    }
}

15.HashMap 集合

HashMap 的特点：
? ? ? ? HashMap 是Map 里面的一个实现类
? ? ? ? 没有额外需要学习的特用方法，直接使用Map 里面的方法就可以了
? ? ? ? HashMap 跟 HashSet 一样底层是哈希表结构的

依赖HashCode 方法和equals 方法保证键的唯一

如果键要存储的是自定义对象，需要重写HashCode 和 equals 方法

16.TreeMap 集合

TreeMap 底层时红黑树结构的
????????依赖自然排序或者比较器排序，对键进行排序
????????如果键存储的是自定义对象，需要实现Comparable 接口或者在创建TreeMap 对象时给出比较器排序规则