Java_集合框架(一)

Java
5.4k 词

概述

  1. 集合：集合是一种容器，用来装数据的，类似于数组，但集合的大小可变，开发中也非常常用。为了满足不同的业务场景需求，Java还提供了很多不同特点的集合给我们选择。

  2. 集合体系结构：

    • 单列集合：每个元素（数据）只包含一个值

      Collection，List，ArrayList，LinkedList，Set，HashSet，LinkedHashSet，TreeSet

    • 双列集合：每个元素包括两个值（键值对）

      Map，HashMap，TreeMap，LinedHashMap。

  3. Collection集合体系：

    1
    2
    3
    4
    5
    6
    7
    8
    graph TB;
        Collection-->List
        Collection-->Set
        List-->ArrayList
        List-->LinkedList
    	Set-->HashSet
    	HashSet-->LinkedHashSet
    	Set-->TreeSet

  4. Collection集合特点：

    • List系列集合：添加的元素是有序的、可重复、有索引
      • ArrayList、LinkedList：有序、可重复、有索引
    • Set系列集合：添加的元素是无序的，不重复、无索引
      • HashSet：无序、不重复、无索引
      • LinkedHashSet：有序、不重复、无索引
      • TreeSet：按照大小默认升序排序、不重复、无索引

Collection

Collection的常用方法

  1. 为什么要先学Collection的常用方法？

    • Collection是单列结合是祖宗，它规定的方法（功能）是全部单列集合都会继承的。

  2. Collection的常见方法：

    方法名 说明
    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的遍历方式

迭代器

  1. 迭代器概述

    • 迭代器是用来遍历集合的专用方式（数组没有迭代器），在Java中迭代器的代表是Iterator。

  2. Collection集合获取迭代器的方法：

    方法名称 说明
    Iterator<E> iterator() 返回集合中的迭代器对象，该迭代器对象默认指向当前集合的第一个元素

  3. Iterator迭代器中的常用方法：

    方法名称 说明
    boolean hasNext 询问当前位置是否有元素存在，存在返回true，不存在返回false
    E next() 获取当前位置的元素，并同时将迭代器对象指向下一个元素处

增强for循环

  1. 增强for循环的格式：

    1
    2
    3
    4
    5
    6
    7
    8
    9
    for(元素的数据类型 变量名: 数组或者集合){
        
    }

    // 示例
    Collection<String> c = new ArrayList<>();
    for (String s :c){
         System.out.println(s);
    }

  2. 增强for可以用来遍历集合或者数组

  3. 增强for遍历集合，本质就是迭代器遍历集合的简化写法

Lambda表达式

  1. Lambda表达式遍历集合

    • 得益于JDK 8开始的新技术，提供了一种更简单、更直接的方式来遍历集合

  2. 需要使用Collection的如下方法来完成

    方法名称 说明
    default void forEach(Consumer<? super T> action) 结合lambda遍历集合

List集合

特点、特有方法

  1. List系列集合特点：有序，可重复，有索引

    • ArrayList：有序，可重复，有索引
    • LinkedList：有序，可重复，有索引
    • ArrayList和LinkedList底层采用的数据结构不同，应用场景不同

  2. List集合的特有方法

    • List集合因为支持索引，所以多了很多与索引相关的方法，当然，Collection的功能List也都继承了
    方法名称 说明
    void add(int index, E element) 在此集合中的指定位置插入指定元素
    E remove(int index) 删除指定索引处的元素，返回被删除的元素
    E set(int index, E element) 修改指定索引处的元素，返回被修改的元素
    E get(int index) 返回指定索引处的元素

遍历方式

  1. for循环（因为List集合有索引）
  2. 迭代器
  3. 增强for循环
  4. Lambda表达式

ArrayList

  1. ArrayList基于数组实现的，数组的特点：查询快、增删慢
    • 查询快：查询数据通过地址值和索引定位，查询任意数据耗时相同
    • 删除效率低：可能需要把后面很多的数据进行前移
    • 添加效率极低：可能需要把后面很多的数据后移，再添加元素；或者也可能需要进行数组的扩容
  2. ArrayList实现：
    • 利用无参构造器创建的集合，会在底层创建一个默认长度为0的数组
    • 添加第一个元素时，底层会创建一个新的长度为10的数组
    • 存满时，会扩容1.5倍
    • 如果一次添加多个元素，1.5倍还放不下，则新创建数组的长度以实际为准
  3. ArrayList集合适合的应用场景
    • ArrayList适合：根据索引查询数据，比如根据随机索引取数组（高效）或者数据量不是很大时
    • ArrayList不适合：数据量大的同时，又要频繁的进行增删操作

LinkedList

  1. 链表：链表中的节点是独立的对象，在内存中是不连续的，每个节点包含数据值和下一个节点的地址

    特点：

    • 查询慢：无论查询哪个数据都要从头开始找
    • 增删相对快

  2. LinkedList底层原理

    • 基于双链表实现（每个节点包含数据、前一个结点地址和后一个结点地址）
    • 特点：查询慢，增删相对较快，但对首尾元素进行增删改查的速度是极快的

  3. LinkedList新增了很多首尾操作的特有方法

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

  4. LinkedList的应用场景：

    • 设计队列（先进先出，后进后出）

      数据进入队列的过程称为：入队

      数据离开队列的过程称为：出队

    • 设计栈（后进先出，先进后出）

      数据进入栈模型的过程称为：压/进站（push）

      数据离开栈模型的过程称为：弹/出栈（pop）

Set集合

Set系列集合特点

  1. Set系集合特点：无序：添加数据的顺序和获取出的数据顺序不一致；不重复；无索引；
  2. HashSet：无序、不重复、无索引。
  3. LinkedHashSet：有序、不重复、无索引。
  4. TreeSet：排序、不重复、无索引。
  5. 注意：Set要用到的常用方法，基本上就是Collection提供的！！！自己几乎没有额外新增的一些常用方法！

HashSet

  1. HashSet集合的底层原理：哈希表
  2. HashSet集合去重复的机制
    • HashSet集合默认不能对内容一样的两个不同对象去重复
    • 如何让HashSet集合实现对内容一样的两个不同对象进行去重：重写hashCode()和equals()方法

LinkedHashSet

  1. LinkedHashSet集合底层原理：
    • 哈希表（数组、链表、红黑树）
    • 但是，LinkedHashSet的每个元素都额外的多了一个双链表的机制记录它前后元素的位置

TreeSet

  1. TreeSet底层基于红黑树实现

  2. 排序规则：

    • 对于数值类型：Integer，Double，默认按照数值大小的本身进行升序排序
    • 对于字符串类型：默认按照首字母的编号升序排序
    • 对于自定义类型的对象，TreeSet默认是无法直接排序的

  3. 自定义排序规则

    • 方法一：让该对象的类实现comparable(比较规则)接口，然后重写compareTo方法，自己制定比较规则

    • 方法二：通过调用TreeSet集合有参数构造器，可以设置Comparator（比较器对象，用于指定比较规则）

      1
      public TreeSet(Comparator<? super E> comparator)

    • 注意：如果类本身有实现Comparable接口，TreeSet集合同时也自带比较器，默认使用集合自带的比较器排序。

Collection集合总结

使用场景

  1. 如果希望记住元素的添加顺序，需要存储重复的元素，又要频繁的根据索引查询数据？
    • 用ArrayList集合（有序、可重复、有索引)，底层基于数组的。(常用)
  2. 如果希望记住元素的添加顺序，且增删首尾数据的情况较多?
    • 用LinkedList集合（有序、可重复、有索引)，底层基于双链表实现的。
  3. 如果不在意元素顺序，也没有重复元素需要存储，只希望增删改查都快?
    • 用HashSet集合（无序，不重复，无索引)，底层基于哈希表实现的。(常用)
  4. 如果希望记住元素的添加顺序，也没有重复元素需要存储，且希望增删改查都快?
    • 用LinkedHashSet集合（有序，不重复，无索引)，底层基于哈希表和双链表。
  5. 如果要对元素进行排序，也没有重复元素需要存储?且希望增删改查都快?
    • 用TreeSet集合，基于红黑树实现。

集合的并发修改异常问题

  1. 集合的并发修改异常
    • 使用迭代器遍历集合时，又同时在删除集合中的数据，程序就会出现并发修改异常的错误。
    • 由于增强for循环遍历集合就是迭代器遍历集合的简化写法，因此，使用增强for循环遍历集合，又在同时删除集合中的数据时，程序也会出现并发修改异常的错误
  2. 怎么保证遍历集合同时删除数据时不出bug
    • 使用迭代器遍历集合，但用迭代器自己的删除方法删除数据即可。
    • 如果能用for循环遍历时:可以倒着遍历并删除;或者从前往后遍历，但删除元素后做i--操作。

Collection的其他相关知识

前置知识：可变参数

  1. 可变参数：就是一种特殊形参，定义在方法、构造器的形参列表里，格式是：数据类型...参数名称;
  2. 可变参数的特点和好处
    • 特点：可以不传数据给它;可以传一个或者同时传多个数据给它;也可以传一个数组给它。
    • 好处：常常用来灵活的接收数据。
  3. 注意实现：
    • 可变参数在方法内部就是一个数组。
    • 一个形参列表中可变参数只能有一个。
    • 可变参数必须放在形参列表的最后面。

Collections

  1. Collections：是一个用来操作集合的工具类

  2. 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<?> list) 对List集合中的元素进行升序排序
    public static <T> void sort(List<?> list, Comparator<? super T> c) 对List集合中的元素，按照比较器对象指定的规则进行排序

拓展：

哈希表

  1. 哈希值

    • 就是一个int类型的数值，Java中每一个对象都有一个哈希值。

    • Java中的所有对象，都可以调用Object类提供的hashCode方法，返回该对象自己的哈希值。

      1
      public int hashCode()：返回对象的哈希码值。

  2. 对象哈希值的特点

    • 同一个对象多次调用hashCode()方法返回的哈希值是相同的。
    • 不同对象，他们的哈希值一般不相同，但也有可能会相同（哈希碰撞）。

  3. 哈希表

    • 哈希表是一种增删改查数据性能都较好的结构

    • JDK8之前，哈希表 = 数组 + 链表

      1. 创建一个默认长度16的数组，默认加载因子为0.75，数组名table

      2. 使用元素的哈希值对数组的长度求余计算出应存入的位置

      3. 判断当前位置是否为null，如果是null直接存入

      4. 如果不为null，表示有元素，则调用equals方法比较，相等，则不存；不相等，则存入数组

        • JDK8之前，新元素存入数组，占老元素位置，老元素挂下面

        • JDK8之后，新元素直接挂在老元素下面

    • JDK8之后，哈希表 = 数组 + 链表 + 红黑树

      1. 当链表长度超过超过8，且数组长度>=64时，自动将链表转换成红黑树

  4. 如果数组快占满了，会出现什么问题？该怎么解决

    • 链表过长，导致查询性能降低
    • 扩容：当数组存放数据的长度达到数组长度与默认加载因子的乘积时，便会执行扩容操作

树

  1. 二叉树：
    • 二叉树中，任意结点的度 <= 2
    • 度：每个节点的子节点数量
    • 树高：树的总层数
    • 根节点：最高层的节点
    • 左子节点
    • 右子节点
    • 左子树
    • 右子树
  2. 二叉查找树（二叉排序树）
    • 规则：小的存左边，大的存右边，一样的不存
    • 缺陷：当数据已经是排序好的，导致查询的性能与单链表一样，查询速度变慢
  3. 平衡二叉树：
    • 在满足查找二叉树的大小规则下，让树尽可能矮小，以此提高查数据的性能
  4. 红黑树
    • 红黑树就是平衡二叉树
    • 红黑树是一种增删改查数据性能都相对较好的结构