0830（042天 集合框架06 总结二）

0830（042天 集合框架06 总结二）

每日一狗（田园犬西瓜瓜）

[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-YeX5VQ4w-1661864293677)(assets/43.png)]

集合框架06 还剩亿点

1. Set

元素无序，不重复

1.1 元素比较

1. 首先调用hashCode方法
2. 当hashCode值相等时调用equals来判定两个对象是否相等

equals返回true，hashCode必须相等，但是hashCode相等时equals不一定相等

在equalse方法中，不同类型的对象没有判定的必要

1.2 实现类

Set—>hashSet—> linkedHashSet

SortedSet —> TreeSet

HashSet

元素存放在HashMap的key位置，而HashMap是键值对的，键是唯一的。

三个特点

• 无序：
• 非重复 [equals和hashcode会保证元素无重复]
• 线程非安全的

HashSet的equals和hashCode

HashSet需要同时通过equals和HashCode来判断两个元素是否相等，具体规则是，如果两个元素通过equals为true，并且两个元素的hashCode相等，则这两个元素相等（即重复）。

所以如果要重写保存在HashSet中的对象的equals方法，也要重写hashCode方法，重写前后hashCode返回的结果相等（即保证保存在同一个位置）。所有参与计算 hashCode() 返回值的关键属性，都应该用于作为 equals() 比较的标准。
结论：要求当两个同类型对象equals为true时，必须

hashCode值一致。事实上equals方法和hashCode方法没有任何必然联系，所以说前面的规则是个潜规则

LinkedHashSet

在HashSet的基础之上还用一个链表来维护元素的插入顺序，插入的时候即要计算hashCode又要维护链表，而遍历的时候只需要按链表来访问元素

存储使用LinkedHashMap（双向链表）

因为底层采用链表和哈希表的算法。链表保证元素的添加顺序，哈希表保证元素的唯一性

TreeSet

底层是用TreeMap实现的，本质上是一个红黑树原理。

正因为它是排序了的，所以相对HashSet来说，TreeSet提供了一些额外的按排序位置访问元素的方法，例如first(), last(), lower(), higher(), subSet(), headSet(), tailSet()

**TreeSet的排序分两种类型 **

• 自然排序：存储对象实现Comparable接口
• 定制排序：在创建TreeSet对象时传入一个 Comparator

比较

1.5 Set的典型应用

List的去重

List<Integer> list = new ArrayList<>();
Random r = new Random();
for (int i = 0; i < 20; i++) {
    list.add(r.nextInt(10));
}
System.out.println(list);
Set<Integer> set = new LinkedHashSet<>(list);
System.out.println(set);
1
2
3
4
5
6
7
8

如果是公司考试就直接声明啥就new啥，除非考点是面向对象（多态的判定有时间代价）

3.3 做：创建了几个对象

com.yan1.TestString.java

创建了几个对象？

String s1 = "666"; // 1
String s2 = new String("666"); // 2
String s3 = "66"+"6"; // 1 // 常量的拼接中的优化机制

// 坑来啦
String s4 = "66";
String s5 = S4 + "6"; //2 这个有一个是变量，new StringBuilder().append(s4).append("6").toString()
s4 == s5; // false

// 天坑
String s6 = "666" + new String("666"); // 4
1
2
3
4
5
6
7
8
9
10
11

2. 补充

2.1 hash碰撞

解决办法：

线性探测法（空间固定）

相同时将其塞到紧邻的下一个空地址

链地址法

把这个相同的对象链接到这个元素的下边（）

2.2 一些工具类

Arrays

提供一系列静态方法实现对各种数组的搜索、排序等操作，

sort：排序

binarySearch：折半查找

fill：填充数据

copyOf：拷贝数组

hashCode：获取一个数组的hash值

toString：友好展示容器数据

Objects

问：浅谈一下Objects

Objects类是Final的，即不可以被其他类继承，并且它里面的方法都是static的

equals方法的功能是判断两个对象 是否是同一个对象， 或者两个对象是否相等。重点是处理了比较对象为null；

deepEquals就比较严格一点，首先它比较两个对象是否是同一个对象；如果不是，再判断它们是否是矩阵，对于矩阵的每个元素，它们是否是同一个对象；最后调用对象的equals方法

**hashCode（Object）**是计算单个对象的hashCode，这里处理了null，hashCode(Object…)是计算矩阵的hashCode

toString方法是一个加强版的toString，多了一个null处理

Collections

• 容器排序
• 搜索（子集）
• 索引Collections.binarySearch(list, 7);
• 线程安全等

List<Integer> list = Collections.synchronizedList(new ArrayList<>());

Collections.synchronizedXXX(List<T> list);
// 返回的对象中的大部分方法都有synchronized的同步代码块组成
1
2
3
4

问：Arrays.asList(null);返回的ArrayList为啥不能添加元素

他返回的是一个局部内部类的对象。 Arrays.ArrayList

用于存储数据的数组是final的。长度不可变

// 
private static class ArrayList<E> 
    extends AbstractList<E>
    implements RandomAccess,
	java.io.Serializable
{
private final E[] a; // 长度不可变
} 

1
2
3
4
5
6
7
8
9

问：Collection和Collections的区别

• Collection是java.util下的接口，它是各种集合的父接口，继承于它的接口主要有Set和List

• Collections是个java.util下的类，是针对集合的帮助类，提供一系列静态方法实现对各种集合的搜索、排序、线程安全化等操作

3. 数据结构（队列Queue、栈Stack）

3.1 Queue：FIFO

队列即：先进的先出

根据实现方式不同分为顺序队列和链式队列。

• enqueue(String item);// 入队操作
• dequeue();// 出队操作

public interface Queue<E> extends Collection<E> {
    boolean add(E e); // 向队列中添加数据，阈值为64
    boolean offer(E e); 
    E remove(); // 删除队列头部的数据
    E poll();//
    E element();//获取队列中的数据
    E peek();//


}
1
2
3
4
5
6
7
8
9
10

循环队列：基于数组的队列实现中，当tail=items.length时需要搬移大量的数据，就会导致入队操作的性能降低，可以使用循环队列解决。典型算法：约瑟夫环

3.2 Queue实现类

PriorityQueue优先队列

封装了堆

其通过堆实现，具体说是通过完全二叉树completebinarytree，实现的小顶堆（任意一个非叶子节点的权值，都不大于其左右子节点的权值），也就意味着可以通过数组来作为PriorityQueue的底层实现。

优先队列保证每一次取出的元素都是队列中权值最小的。

优先级队列的元素根据自然排序或者在构造函数时期提供Comparator来排序，具体根据构造器判断。PriorityQueue不允许null元素

• 线程不安全
• 不允许存储null
• 元素之间存在某种顺序（优先级）

阻塞队列 BlockingQueue接口

阻塞队列就是在队列的基础上添加了阻塞特性。在队列为空时，从队头获取数据会被阻塞，直到队列中有数据才返回；在队列已满时，插入数据的操作会被阻塞，直到队列中空闲位置后才插入数据，然后返回。

基于阻塞队列的生产者-消费者模式可以有效地协调生产和消费的速度。

与前边的队列相比，有两个阻塞【put(e)，take()】和超时退出的方法【offer(e, tiime, unit)，poll(tiime, unit)】

java针对阻塞队列提供了7种常见的实现，分别是

• ArrayBlockingQueue由数组结构组成的有界阻塞队列
• LinkedBlockingQueue由链表结构组成的有界阻塞队列，默认长度为Integer.MAX_VALUE，如果指定长度则有上限
• PriorityBlockingQueue支持优先级排序的无界阻塞队列
• DelayQueue使用优先级队列实现的无界阻塞队列
• SynchronousQueue不存储元素的阻塞队列,只起到一个同步器的作用
• LinkedTransferQueue由链表结构组成的无界阻塞队列
• LinkedBlockingDeque由链表结构组成的双向阻塞队列

3.3 栈Stack：FILO

对栈的基本操作只有push进栈和pop出栈两种，栈的实现可以有数组实现的顺序栈和链表结构的链式栈

java提供的具体实现类Stack

public class Stack extends Vector

• E push(E item) 将数据存储到数组中，如果集合已经满了，则添加新数据时增容
• E pop() 弹出栈顶数据
• E peek() 查看栈顶数据，并不会执行弹出操作
• search(Object o) 查找o对象的下标值

3.4 自定义栈

1、先定义接口（一定要写足注释）

public interface Stack<T> {
    //栈是否为空  记得在方法上添加注释
    boolean isEmpty();
    // data元素入栈
    void push(T data);
    //返回栈顶元素,未出栈
    T peek();
    //出栈,返回栈顶元素,同时从栈中移除该元素
    T pop();
}
1
2
3
4
5
6
7
8
9
10

2、在定义实现类，抽象类中可以顶一个size()的方法

public class SeqStack<T> implements Stack<T> {
    // 栈顶指针,-1代表空栈
    private int top = -1;
    // 容量大小默认为10
    private static final int capacity = 10;
    // 存放元素的数组
    private T[] array;
    //当前栈中存储的元素个数
    private int size;

    public SeqStack() {
        this(capacity);
    }

    @SuppressWarnings("unchecked")
    public SeqStack(int capacity) {
        array = (T[]) new Object[capacity];
    }

    public int size() {
        return size;
    }

    public boolean isEmpty() {
        return this.top == -1;
    }

    // 添加元素,从栈顶(数组尾部)插入
    public void push(T data) {
        // 判断容量是否充足
        if (array.length == size)
            ensureCapacity(size  2 + 1);// 扩容
        // 从栈顶添加元素
        array[++top] = data;
        size++;
    }

    private void ensureCapacity(int capacity) {
        // 如果需要拓展的容量比现在数组的容量还小,则无需扩容
        if (capacity < size)
            return;
        T[] old = array;
        array = (T[]) new Object[capacity];
        System.arraycopy(old, 0, array, 0, size);
    }

    // 获取栈顶元素的值,不删除
    public T peek() {
        if (isEmpty())
            throw new EmptyStackException();
        return array[top];
    }

    // 从栈顶(顺序表尾部)删除
    public T pop() {
        if (isEmpty())
            throw new EmptyStackException();
        size--;
        return array[top--];
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61

3.5 补充：堆

小顶堆：上边的最小

大顶堆：上边的最大

3.4 待总结

栈编码

双向队列

优先队列

---

扩展小芝士

• getClass()!=obj.getClass()类在程序运行过程中只会加载一次
• s子辈的类基本上都是工具类
• 线程安全：可见性，串行，原子性，