写在前面：

视频是什么东西，有看文档精彩吗？

视频是什么东西，有看文档速度快吗？

视频是什么东西，有看文档效率高吗？

1. 介绍

诸小亮：下面我们介绍——Set 接口

张小飞：Set 也是 Collection 接口下最常用的子接口之一吗？

诸小亮：是的，它有以下特点：

• 存储的元素是无序的（存储的顺序和取出的顺序不一致）

• 第一个存放‘a’，使用迭代器取时，第一个取出的不一定是 ‘a’

• 不能通过下标获取元素，只能使用迭代器或者增强 for 循环
• 不允许存储重复元素（自动去重）

张小飞：这，完全跟 List 不同

诸小亮：不错，它们是两种容器，Set 按照数据结构（存储数据的方式）划分，常用子类有2个：

• HashSet：底层是哈希表，专业名词：散列表
• TreeSet：底层是二叉树结构

2. HashSet

诸小亮：我们先学习——HashSet

2.1. 无序且自动去重

张小飞：您刚才说 Set 无序而且会自动去除重复元素，能不能演示一下？

诸小亮：当然可以了，看下面代码

public static void main(String[] args) throws Exception {
    Set set = new HashSet();
    set.add("c");
    set.add("a");
    set.add("b");
    set.add("a");
    System.out.println(set);
}

结果：

张小飞：原来如此，确实会自动去除重复

诸小亮：另外， 使用迭代器获取元素时

结果：

诸小亮：我们第一个添加的是 ‘c‘，但是使用迭代器第一个取出来的是 ‘a’

张小飞：嗯嗯，明白了，Set 可以使用增强 for 循环吗？

诸小亮：把那个 ‘吗’字去掉，当然可以用了，比如：

2.2. 哈希表

2.2.1. 介绍

张小飞：为什么 Set 是无序的，而且可以自动去重呢？

诸小亮：因为它的底层数据结构是哈希表

• 哈希表：又叫散列表，其实本质：可变数组+链表，不过使用数组方式有些特殊

张小飞：哦？我倒要瞧瞧是怎么特殊了

诸小亮：使用哈希表存储数据的过程是这样的

• 先根据哈希算法对 数据 计算出一个hash值，也叫：hashcode

• Object 类中就有 hashCode 方法

• 然后，使用 hashcode % 数组长度得到一个index，元素就存到对应的 index 位置

如下图，想把 abc 这个字符串存到哈希表中，其过程：

• 先计算 abc 的 hashcode

• String类中复写了Object的 hashCode 方法，专门计算字符串的 hash 值，之后Set底层还会对hash值进一步加工，此处不详细解释

• 然后计算index，假如 index = 3，那么 abc 就会放到对应位置：

张小飞：原来如此，不过，存一个数据而已为什么要搞的这么复杂呢？

诸小亮：真相只有一个——提高查询速度

张小飞：？？？很快嘛？

诸小亮：比 List 快，比如：判断集合中是否包含abc，用 List 你怎么做？

张小飞：这简单，搞个 for 循环然后调用 contains 方法就行了

诸小亮：如果使用 Set 直接计算 hashcode 就行了，比 一个个调用 contains 方法快多了

张小飞：明白了，计算出 hashcode，在计算 index，就能判断出对应的位置有没有元素了

诸小亮：正是这个道理

2.2.2. 哈希冲突

张小飞：那如果两个不一样的数据，计算出的 hashcode 相同呢？

诸小亮：这中情况称为——哈希冲突

• 哈希冲突：两个元素本身不同，但是通过哈希算法计算的两个 hashcode 相同

张小飞：这种情况应该怎么办呢？

诸小亮：这时，会以链表方式继续存储数据，比如：

• 假设 abc 和 cba 两个字符串的hashcode一样，会调用元素的 equals 方法，判断它们的内容是否一样，如果不一样以链表方式继续存储，如下图

这时，abc 就是链表的头节点

张小飞：明白了，相当于数组中的每个元素都是一个链表

诸小亮：完全正确，来，我们总结一下哈希表存储元素的过程：

• 先调用目标元素的 hashCode 方法，最终拿到 index，判断否已经存在

• 不存在：存储
• 存在，再调用equals方法，判断跟已有元素是否相同

• 相同：不存储
• 不相同：添加到列表的尾节点

2.2.3. 优劣和扩容

张小飞：我想，哈希表也是有一些缺点的吧

诸小亮：是的，它的优缺点如下：

• 优点：查询效率高
• 缺点：数组的某些位置可能不会存储数据，造成内存浪费

张小飞：不是数组中每个位置都有一个链表吗？

诸小亮：因为计算下标时，并不能保证数组中的每个位置都有一个链表，所以。。。。。

张小飞：既然这样，它什么时候扩容呢？

诸小亮：默认情况下，当存储的元素数量达到总容量的 75% 时，数组会自动扩容为原来的 2 倍

• 数组初始化长度是16，16 * 0.75 =12，当存储第13个元素时候，数组自动扩容为 32 长度

张小飞：明白了

2.3. 存储自定义对象

张小飞：Set 也可以存储自定义对象吧

诸小亮：当然可以啊

张小飞：那会自动去重吗？

诸小亮：必须的，你到底想说什么？

张小飞：那，为什么我下面的代码没有自动去重呢？

public static void main(String[] args) throws Exception {
    //存储Hero对象，如果name一样，视为同一人
    Set set = new HashSet();
    set.add(new Hero("妲己"));
    set.add(new Hero("西施"));
    set.add(new Hero("嫦娥"));
    set.add(new Hero("妲己"));
    System.out.println(set);
}

结果：

诸小亮：原来你说的是这个问题啊，我问你，HashSet 存储数据的第一步是什么？

张小飞：计算目标元素的 HashCode 最终获取一个 index

诸小亮：你没有在 Hero 类中重写 hashCode 方法吧

张小飞：额。。。。，没有

诸小亮：这就是了，默认调用的是 Object 中的 hashCode 方法，从而导致 hashcode 不同

张小飞：那应该怎么办呢？

诸小亮：在 Hero 中复写 hashCode 方法，比如：

@Override
public int hashCode() {
    return name.hashCode();//name的hashcode就是整个对象的hashcode
}

再次运行，结果：

张小飞：明白了

2.4. LinkedHashSet(了解)

诸小亮：HashSet 还有一个子类——LinkedHashSet，底层是：哈希表 + 双向链表

• 其他说法：数组 + 双重链表

张小飞：什么是双重链表？

诸小亮：看下图

诸小亮：哈希表 = 数组 + 链表，LinkedHashSet中又融入了 双向链表，所以叫：双重链表

张小飞：原来如此，不过为什么这么做呢？

诸小亮：这样可以保证数据是有序的，比如使用 HashSet 时：

结果，嫦娥在西施前面：

诸小亮：如果使用LinkedHashSet

结果：

张小飞：为什么它能保证元素插入时的顺序呢？

诸小亮：主要是因为双向链表的存在

• 双向链表中的每个节点都有 before 和 after 属性
• 在添加数据时，先求 hash 值，再计算 index，然后把数据放到双向链表中
• 遍历时，先拿到头结点，然后就可以有序的拿到所有元素

张小飞：原来如此，明白了