JavaSE：集合①Collection体系

集合

涉及的知识点

  • Java 知识：泛型
  • 数据结构：、树、散列表
  • 设计模式：

集合：对象的容器，提供操作对象的方法

分为 Collection 和 Map 两个体系。

  • Collection：存储元素
  • Map：存储记录（K-V 键值对）

Collection 体系

image-20220302233359176

  • List：有序、有下标、元素可重复

    JDK 存储结构 线程安全
    ArrayList 1.2 数组 线程不安全
    LinkedList 1.2 双向链表
    Vector 1.0 数组 线程安全

  • Set：无序、无下标、元素不可重复

    JDK 存储结构 元素不重复 说明
    HashSet 1.2 HashMap 基于 hashCode 判断相等：先 hashCode()，再 equals()
    LinkedHashSet 1.4 链表 基于hashCode 继承 HashSet，保留元素的插入顺序
    TreeSet 1.2 红黑树 基于排列顺序 实现 SortedSet 接口，对集合元素自动排序。
    （元素对象需实现 Comparable 接口，指定排序规则）

Collection 接口

Collection 体系的父接口。

强调几个方法

  • iterator()：返回集合的迭代器，由具体实现类负责迭代器。

  • toArray()：返回包含 collection 中所有元素的数组。

  • removeAll()：删除此集合中包含在指定集合中的元素（集合相减）

  • retainAll()：仅保留此集合中包含在指定集合中的元素（集合交）

    image-20220303000559952

List 接口

特点：有序、有下标、元素可以重复。

方法：除了 Collection 父接口中的方法，还定义了一些新的方法。

说明

1、强调几个方法

增加了几个与下标有关的方法，还引入了一个列表迭代器

  • add(int, E)、remove()：指定位置插入

  • remove()：指定位置删除

  • get()、set()：指定位置读写

  • indexOf()：获取元素下标（首次出现）

  • lastIndexOf()：获取元素下标（最后一次出现）

  • listIterator()：列表迭代器，比 iterator 功能更强大

  • subList()：子集，左闭右开

    image-20220303233549955

2、注意几个问题

  • 自动装箱：集合不能存放基本类型，但是 Java 会自动装箱为对应的包装类型。

  • remove()：集合中存放的是整数时，调用此方法需要区分是 “按下标删除” 还是 “按元素删除”

    • 按下标：传参为下标；
    • 按元素：传参为对象，需要强转为 Object 或使用包装类。

  • equals()

    • remove()、indexOf()、lastIndexOf()、contains() 等，都是通过 equals() 方法来判断元素是否相同；

    • Object 类默认实现：比较引用地址（return (this == obj);）

    • 若要自定义比较规则，需要在自定义类中重写 equals() 方法。

      @Override
public boolean equals(Object obj) {
    if (obj == null) {
        return false;
    }

    if (this == obj) {
        return true;
    }

    if (obj instanceof Person) {
        Person p = (Person) obj;

        return this.name.equals(p.name) && p.age == this.age;
    }

    return false;
}

3、遍历 List

以 ArrayList 为例，演示一下遍历的几种方式。

  • for

  • 增强 for

  • 迭代器

  • list 迭代器：向后、向前

    ArrayList list = new ArrayList<>();

@Test
public void testTraverse() {
	// for
    for (int i = 0; i < list.size(); i++) {
        System.out.println(list.get(i));
    }

	// foreach
    for (Person person : list) {
        System.out.println(person);
    }

	// iterator
    Iterator iterator = list.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }

    // listIterator
    ListIterator listIterator = list.listIterator();
    // 向后
    while(listIterator.hasNext()){
        System.out.println(listIterator.next());
    }

    // 向前
    while(listIterator.hasPrevious()){
        System.out.println(listIterator.previous());
    }
}

ArrayList 源码分析（!）

部分源码分析

属性

  • elementData：存放元素的数组
  • size：实际元素个数（ArrayList 的长度）
  • DEFAULT_CAPACITY：默认初始容量，10
  • EMPTY_ELEMENTDATA：空数组
  • DEFAULTCAPACITY_EMPTY_ELEMENTDATA：默认容量的空数组

二者都是空数组实例，区别在于使用的场景不同。后者是用于在添加首个元素时，了解膨胀的大小。

源码：无参构造函数

  • 将【默认容量的空数组】赋值给 elementData

  • 说明：仅调用无参构造函数，没有添加元素时，size 和 capacity 为 0

    public ArrayList() {
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

源码：add()

// 1
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}
// 2
private void ensureCapacityInternal(int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}
// 3
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}
// 4
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    // MAX_ARRAY_SIZE = Integer.MAX_VALUE - 8
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

首次调用 add()

  1. add()：调用方法 2，传参为 1

  2. ensureCapacityInternal()

  3. if：二者相等，成立

  4. Math.max()：默认容量 == 10，minCapacity == 1，取最大值。minCapacity == 10

  5. 调用方法 3，传参为 10

  6. ensureExplicitCapacity()

    1. if：minCapacity == 10，elementData.length == 0，成立。
    2. 调用方法 4，传参为 10

  7. grow()：数组扩容

  • 第一个 if：old == 0，new == 0，成立。new == 10
  • 第二个 if：不成立
  • Arrays.copyOf()：将 elementData 赋值为一个容量为 10 的数组
    （此时 ArrayList 的数组才具有默认容量）
  1. 回到 add()：赋值并返回 true。

再次调用 add()

（数组未满的情况下）

假设集合中已有 7 个元素，size == 7

  1. add()：调用方法 2，传参为 8
  2. ensureCapacityInternal()
    1. if：二者不相等，不成立
    2. 调用方法 3，传参为 8
  3. ensureExplicitCapacity()
    1. if：minCapacity == 8，elementData.length == 10，不成立。
    2. 说明不需要扩容，直接回到 add()
  4. 回到 add()：赋值并返回 true。

数组扩容

（数组已满）

目前已有 10 个元素，size ==10

  1. add()：调用方法 2，传参为 11
  2. ensureCapacityInternal()
    1. if：二者不相等，不成立
    2. 调用方法 3，传参为 11
  3. ensureExplicitCapacity()
    1. if：minCapacity == 11，elementData.length == 10，成立。
    2. 调用方法 4，传参为 11
  4. grow()：数组扩容
    • old == 10，new == 15（old >> 1，表示右移一位，即除以 2）
    • 第一个 if：不成立
    • 第二个 if：不成立
    • Arrays.copyOf()：将 elementData 赋值为一个容量为 15 的数组
  5. 回到 add()：赋值并返回 true。

结论：数组扩容增量，每次是原来的 1.5 倍【new = old + (old >> 1)】

LinkedList 源码分析

需要了解：

Node

结点类：LinkedList 将 Node 声明为内部类。

private static class Node {
    // 数据
    E item;
    
    Node next;
    Node prev;

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

属性

  • size：实际元素个数（LinkedList 的长度）
  • first：头结点
  • last：尾结点

如何添加元素

为了方便描述

  • 当前头结点（first）、当前尾结点（last）
  • 新结点（nNode）：前驱（prev）、后继（next）

先把源码放一边，思考一下如何将元素插入双向链表？

  1. 创建 nNode：prev 为 last，next 为空

    Node nNode = new Node(last, data, null);

  2. last.next 改为 nNode：需要考虑一个问题，last == null 吗？

    • 如果 last == null，说明链表为空。添加 nNode 后作为当前链表的 first 和 last。
    • 如果 last != null，则将 last.next 改为 nNode，并且 nNode 作为当前链表的 last。
    if (last == null){
    first = nNode;
    last = nNode;
} else {
    last.next = nNode;
    last = nNode;
}

  3. 由于 if-else 有重复代码，可以抽取出来。

    // 完整的添加语句
Node nNode = new Node(last, data, null);

if (last == null){
    first = nNode;
} else {
    last.next = nNode;
}

last = nNode;

图示过程

  1. last == null（空表）

    image-20220304184517883

  2. last != null

    image-20220304184535271

源码：add()

知道如何添加元素后，再来看看源码。

可以看出几点区别

  • 将 last 赋给一个常值变量 l
  • 先将 last 指向 nNode，再判断尾指针的空值问题
  • 其它操作基本相同，对着源码理解即可
public boolean add(E e) {
    linkLast(e);
    return true;
}

void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

为什么要将 last 赋值给一个局部常量

而不是像刚才我们分析的那样，直接用 last 操作呢？

我的个人理解（从 JVM 角度）

  • last 是一个成员变量，位于堆中。
  • 将 last 保存到一个局部常量，位于常量池（相当于一个本地缓存）
  • 从常量池中读取数据，比从堆中读取数据的效率高。
  • 结论：先将 last 赋值给一个局部常量，在一定程度上能提高效率。

Vector

Vector 现已很少使用

值得一提的是，类中使用到了 Enumeration 枚举器。

在 Iterator 诞生之前，就是使用 Enumeration 遍历集合。

Iterator（JDK 1.2） 就是用来取代 Enumeration（JDK 1.0）的，具体可查看

Set 接口

特点：无序、无下标、元素不可重复。

方法：只有 Collection 父接口方法，没有定义其它方法。

  • List 接口：有下标的概念，因此定义了一系列有关下标的方法。
  • Set 接口：没有下标的概念，所有方法都是继承自 Collection 父接口。

遍历 Set

遍历 List 的方式：for、增强 for、迭代器、list 迭代器。

  • Set 无下标，无法用 for 循环。
  • list 迭代器是 List 集合独有的。

以 HashSet 为例，演示遍历的两种方式。

  • 增强 for

  • 迭代器

    HashSet set = new HashSet<>();

@Test
public void testTraverse() {
    // for
    for (Person person : set) {
        System.out.println(person);
    }

	// 迭代器
    Iterator iterator = set.iterator();
    while (iterator.hasNext()) {
        System.out.println(iterator.next());
    }
}

浅聊 HashTable

在学习 HashSet 之前，先了解一下 HashTable 的结构，有助于理解。

  • HashTable 是一种数据结构，它是数组与链表的结合。
  • 属于 Map 体系，在之后会详细讲解

从整体上看，HashTable 是一个数组，而数组中的每个元素是一张链表。

image-20220305175816976

  • 如何理解每个元素是一张链表？

    • HashTable 声明一个结点类型的数组，每个数组元素就是一个链表的头结点。
    • 通过头结点，就得到一张链表。

  • HashTable 中的结点是什么样的？

    • HashTable 属于 Map 体系，存放的是记录（键值对），记为 Entry
    • 从源码可以看出，Entry 类就是结点类（Node）。
    private static class Entry implements Map.Entry {
    final int hash;
    final K key;
    V value;
    Entry next;

	// 方法
}

  • 结论：HashTable 的存储结构，是一个 Entry 类型的数组。

    private transient Entry<?,?>[] table;

HashSet（!）

存储机制

HashSet 存储机制：通过 hashCode() 找位置，通过 equals() 判断相等

相等条件：hashCode 相等且 equals() 为 true，则相等。

以添加元素 e 为例

根据 e 的哈希值找到要存放的数组位置。

  • 对应位置上没有元素，将 e 保存到当前位置。
  • 对应位置上已有元素，遍历当前位置的链表，逐个元素判断 equals() 是否成立。
    • 如果 equals() 返回 true，说明已有相同记录，无法添加。
    • 否则，新记录插入到链表中。

Object 默认实现

public boolean equals(Object obj) {
    return (this == obj);
}

public native int hashCode();

  • equals()：比较对象引用地址，同一个对象引用才相等。

  • hashCode()：本地方法。

    • 同一个对象引用的哈希值相等。
    • 不同对象引用，即使属性完全相等，哈希值也不相等。

    关于 hashCode() 的小实验

    • 使用 new 关键字创建 10000 个属性完全相同的对象，将对象的哈希值添加到集合中。

    • 进入双重 for 循环，判断是否存在相同的哈希值，结果为 fasle

      image-20220305185712791

    • 查看 ArrayList 中有的哈希值，向集合中添加一个存在的哈希值。

    • 再次遍历，结果为 true。

      image-20220305185952732

方法重写

  • 存储机制：HashSet 先后根据 hashCode() 和 equals() 方法，来判断一个对象是否相等。
  • Object 默认实现：只有当两个对象的引用相同时，才会认为是同一个对象。

重写 hashCode() 和 equals() 方法：自己重写

  • hashCode()：哈希值，可以简单地重写为属性的哈希值求和。

    • String 的哈希值，在 String 类中已重写；
    • int 的哈希值，就是数值本身。

  • equals()：判断对象相等，可以重写为属性相同则相等。

    • 判空
    • 判断是否同一引用
    • 向下转型，判断属性是否相同
    @Override
public int hashCode() {
    return name.hashCode() + age;
}

@Override
public boolean equals(Object obj) {
    if (obj == null) { return false; }

    if (this == obj) { return true; }

    if (obj instanceof Person) {
        Person p = (Person) obj;

        return this.name.equals(p.name) && p.age == this.age;
    }

    return false;
}

使用 IDE 生成 hashCode() 和 equals()

（以 IntelliJ IDEA 为例）

image-20220306114318775 
@Override
public boolean equals(Object o) {
    if (this == o) { return true; }
    if (o == null || getClass() != o.getClass()) { return false; }
    Person person = (Person) o;
    return age == person.age && Objects.equals(name, person.name);
}

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

先看看 equals() 的区别

  • 通过 getClass() 判断是否同一个类，是则直接强转。
    （我们是判断 instanceof，向下转型）
  • 通过 Object.equals() 判断元素是否相等，避免其中某个元素为空，导致可能出现 NPE。
    （我们没有考虑到 this.name 为空的情况）

再来看看 hashCode() 的实现，点进源码

  • 方法的参数以数组形式（可变参数）存储。

  • 算法（迭代）：记哈希值为 h，数组元素为 i
    $$
    公式：h = 31 × h + i 的哈希值
    $$

    public static int hash(Object... values) {
    return Arrays.hashCode(values);
}

public static int hashCode(Object a[]) {
    if (a == null)
        return 0;

    int result = 1;

    for (Object element : a)
        result = 31 * result + (element == null ? 0 : element.hashCode());

    return result;
}

使用 31 作为乘子的原因

  1. 质数：在计算时可以尽量减少哈希冲突（根据 hashCode 计算出的位置相同）
  2. 执行效率：31 可以被 JVM 优化（25 -1）
    • 31 * i = (i<<5) - 1
    • 位运算的执行效率比除法高

TreeSet

TreeSet 存储机制：通过 compareTo() 方法，判断元素是否相等。

相等条件：compareTo() 返回 0，表示重复

定义 compareTo() 的几种方式

  • 元素对象所在的类，实现 Comparable 接口，实现 compareTo() 方法。

  • 创建 TreeSet 时，以匿名内部类形式创建 Comparator 实现类。

    // 1、元素对象所在的类
public class Student implements Comparable {
    // 属性、其它方法

    @Override
    public int compareTo(Student s) {
        // 规则：先比较姓名，再比较年龄
        int c1 = this.name.compareTo(s.getName());
        int c2 = this.score - s.getScore();

        return c1 != 0 ? c1 : c2;
    }
}
// 2.1、匿名内部类
TreeSet set = new TreeSet<>(new Comparator() {
    @Override
    public int compare(Student s1, Student s2) {
        int c1 = s1.getName().compareTo(s2.getName());
        int c2 = s1.getScore() - s2.getScore();

        return c1 != 0 ? c1 : c2;
    }
});
// 2.2、lambda表达式（对匿名内部类的简化）
TreeSet set = new TreeSet<>((s1, s2) -> {
    int c1 = s1.getName().compareTo(s2.getName());
    int c2 = s1.getScore() - s2.getScore();

    return c1 != 0 ? c1 : c2;
});
JavaSE

相关

JAVA SE基础笔记（四）-re

Java Servlet介绍 1

Java Servlet 与eclipse的搭建

VSCode点击启动调试提示"The Language Support for Java server crashed"

Java SE进阶笔记

Review: Java SE 04(异常机制和File类、IO流、多线程、网络编程、反射机制)

Review: Java SE 03(常用类、String类、可变字符串类和日期类、集合类库)

浅谈JAVA servlet

Java Servlet

Java selenium错误——org.openqa.selenium.WebDriverException: unknown error: cann

Java Servlet之 HttpServletResponse

【Java SE】IO流

标签