集合框架（三）

Set集合

特点

Set系列集合特点：

? ? ? ? 无序：添加数据的顺序和获取出的数据顺序不一致；无重复；无索引；

• HashSet：无序、不重复、无索引
• LinkedHashSet：有序、不重复、无索引
• TreeSet：排序、不重复、无索引

注意：

? ? ? ? Set要用到的常用方法，基本就是Collection提供的！

? ? ? ? 自己几乎没有额外新增一些常用功能！

HashSet集合的底层原理

注意：再正式了解HashSet集合的底层原理前，我们需要先搞清楚一个前置知识：哈希值！

哈希值

• 就是一个int类型的数值，Java中每个对象都有一个哈希值。
• Java中的所有对象，都可以调用Object类提供的hashCode方法，返回该对象自己的哈希值。

对象哈希值的特点?

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

底层原理

• 基于哈希表实现的。
• 哈希表说一致增删改查数据，性能都较好的数据结构。

哈希表

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

• JDK8之前，哈希表 = 数组+链表
• JDK8开始，哈希表 = 数组+链表+红黑树

JDK8之前HashSet集合的底层原理，基于哈希表：数组+链表

1. 创建一个默认长度16的数组，默认加载因子为0.75，数组名table
2. 使用元素的哈希值对数组的长度求余计算出因存入的位置
3. 判断当前位置是否为null，如果是null直接存入
4. 如果不为null，表示有元素，则用equals方法比较。相等，则不存；不相等，则存入数组

• JDK8之前，新元素存入数组，占老元素位置，老元素挂下面
• JDK8开始之后，新元素直接挂再老元素下面

JDK8开始HashSet集合的底层原理，基于哈希表：数组+链表+红黑树

JDK8开始，当链表长度超过8，且数组菜单>=64时，自动将链表转成红黑树

小结：JDK8开始后，哈希表中引用了红黑树之后，进一步提高了操作数据的性能。?

了解一些数据结构（树）

• 红黑树，就是可以自平衡的二叉树
• 红黑树是一种增删改查数据性能相对都较好的结构

深入理解HashSet集合去重复机制

? ? ? ? HashSet集合默认不能对内容一样的两个不同对象去重复

比如内容一样的两个学生对象存入到HashSet集合中去，HashSet集合是不能去重复的

如何让HashSet集合能够实现对内容一样的两个不同对象去重复？

????????结论：如果希望Set集合认为2个内容一样的对象是重复的，必须重新对象的hashCode（）和equals（）方法

LinkefHashSet集合的底层原理

• 依然是基于哈希表（数组、链表、红黑树）实现的。
• 但是，它的每个元素都额外的多了一个双链表的机制记录它前后元素的位置。

TreeSet集合

• 特点：不重复、无索引、可排序（默认升序排序，按照元素的大小，由小到大排序）
• 底层是基于红黑树实现的排序。

?注意：

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

自定义排序规则

• TreeSet集合存储自定义类型的对象时，必须指定排序规则，支持如下两种方法来指定比较规则。

方式一

• 让自定义的类（如学生类）实现Comparable接口，重新里面的compareTo方法来指定比较规则。

方式二

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

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

Collection集合的总结

1、如果希望记住元素的添加顺序，需要存储重复的元素，又要频繁的根据索引查询数据？

• 用ArrayList集合（有序、可重复、有索引），底层基于数值的（常用）

2、如果希望记住元素的添加顺序，且增删首尾数据的情况较多？

• 用LinkedList集合（有序、可重复、有索引），底层基于双链表实现的

3、如果不在意元素顺序，也没有重复元素需要存储，只希望增删改查都快？

• 用HashSet集合（无序、不重复、无索引），底层基于哈希表实现的（常用）

4、如果希望记住元素的添加顺序，也没有重复元素需要存储，其希望增删改查都快？

• 用LinkedSet集合（有序、不重复、无索引），底层基于哈希表实现和双链表

5、如果要对元素进行排序，也没有重复元素需要存储？且希望增删改查都快？

• 用TreeSet集合，基于红黑树实现

注意事项：集合的并发修改异常问题

集合的并发修改异常

• 使用迭代器遍历集合时，又同时再删除集合中的数据，查询就会出现并发修改异常的错误
• 由于增强for循环遍历集合就是迭代器遍历集合的简化写法，因此，使用for循环遍历集合，又在同时删除集合中的数据时，程序也会出现并发修改异常的错误

怎么保证遍历集合同时删除数据时不出bug？

• 使用迭代器遍历集合，但用迭代器自己的删除方法删除数据即可
• 如果能用for循环遍历时：可以倒着遍历并删除；或者从前往后遍历，但删除元素后做 i-- 操作

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;

public class Test {
    public static void main(String[] args) {
        // 需求：删除集合中带“李”字的名字
        List<String> list = new ArrayList<>();
        list.add("王麻子");
        list.add("小李子");
        list.add("李爱花");
        list.add("张全蛋");
        list.add("李晓");
        System.out.println(list);

//        for (int i = 0; i < list.size() ; i++) {
//            String name = list.get(i);
//            if (name.contains("李")){
//                list.remove(name);
//                i--;
//            }
//        }

        Iterator<String> it = list.iterator();
        while (it.hasNext()){
            String name = it.next();
            if (name.contains("李")){
                //list.remove(name);  并发修改异常的错误
                it.remove();
            }
        }
        System.out.println(list);
    }
}

?