集合------Set集合（HashSet/LinkedHashSet）

目录

• Set接口
• HashSet集合
• • 简述(要点)：
  • HashSet集合存储数据的结构---哈希表
  • HashSet集合存储数据的方式--处理流程
• LinkedHashSet
• • 简述

Set接口

简述(要点)：

• java.util.Set

  接口和

  java.util.List

  接口一样，同样继承自

  Collection

  接口，
• 它与

  Collection

  接口中的方法基本一致，并没有对

  Collection

  接口进行功能上的扩充，
• 与

  List

  接口不同的是，

  Set

  接口中元素无序，并且都会以某种规则保证存入的元素不出现重复。

Set集合取出元素的方式可以采用：迭代器、增强for。

Set

集合有多个子类，主要介绍其中的

java.util.HashSet

、

java.util.LinkedHashSet

HashSet集合

简述(要点)：

• java.util.HashSet

  是

  Set

  接口的一个实现类
• 它所存储的元素是不可重复的，并且元素都是无序的(即存取顺序不一致)。

• java.util.HashSet

  底层的实现其实是一个

  java.util.HashMap

• HashSet

  是根据对象的哈希值来确定元素在集合中的存储位置，因此具有良好的存取和查找性能。
• 保证元素唯一性的方式依赖于：

  hashCode

  与

  equals

  方法。

HashSet集合存储数据的结构—哈希表

什么是哈希表？

• 在JDK1.8之前，哈希表底层采用数组+链表实现，即使用链表处理冲突，同一hash值的链表都存储在一个链表里。但是当位于一个桶中的元素较多，即hash值相等的元素较多时，通过key值依次查找的效率较低。
• 而在JDK1.8中，哈希表存储采用数组+链表+红黑树实现，当链表长度超过阈值（8）时，将链表转换为红黑树，这样大大减少了查找时间。

简单的来说，哈希表是由数组+链表+红黑树（JDK1.8增加了红黑树部分）实现的。

原理图1：

原理图2：

HashSet集合存储数据的方式–处理流程

（即HashMap底层）

LinkedHashSet

简述

• HashSet下面有一个子类

  java.util.LinkedHashSet

• 它是链表和哈希表组合的一个数据存储结构。
• 元素的存取是有序的