Set接口及其实现类

胡泽宇 2020年02月11日 48次浏览

Set 接口

基本等同于Collection,增加了2个要求:
    1. 元素不允许重复。
    2. 元素是无序的。
Set的实现类
HashSet(最常用)TreeSet

HashSet

特征:

  1. 元素不允许重复
  2. 元素是无序的
  3. 快速的存/取数据。

HashSet最大的特征就是:
Set最常用的实现类,就是HashSet

HashSet如何判断两个元素相等:

  1. 要求两个对象对象通过equals比较相等。
  2. 要求两个对象的hashCode()返回值相等。

HashCode方法是干什么的?

给HashSet、HashMap等需要Hash算法的程序调用的,作为该对象的标识。
怎么重写hashCode方法

  1. 所有参与equal比较的field,都要参与hashCode的计算
  2. 计算出每个Field的hashCode值,然后将他们累加起来即可(累加之前要乘以31)

目的是为了让equal方法与hashCode方法是一致的。
Java系统提供的类,只要重写了equals方法,一般都同时重写了hashCode方法。 因此,这些类只要通过equals方法比较返回true,那么他们hashCode值也相等
实例:

  • 首先,自定义了一个Student类重写了equals方法和hashCode方法,使得它们只要equals相等,hashCode也相等:
    9
  • 创建一个HashSet对象来放入Student对象测试:
    10
  • 输出结果:
    11

测试: 是不是调用了hashCode?
12
测试结果:
13

HashSet为何那么快?

HashSet是基于 Hash表(本质就是数组)实现的。

数组,在所有数据结构中是存、取是最快的。
数组变量: 保存了数组对象的首地址(一个数组的地址是连续的) 
第i个元素地址 = 首地址 + i(从0开始) * 元素的大小。
当程序需要取第i个元素时,直接根据计算出来的地址去取值。
i为何从0开始: 因为如果从1开始,在去i个元素地址公式里i就要减1了
在计算机中,减法耗时比加法长得多,要补码之类的。
因此,最求速度,规定索引都从0开始。
HashSet存元素的步骤:
  1. HashSet会先调用元素的hashCode()方法,该方法返回一个int值。
  2. HashSet会根据元素的hashCode值计算该元素应该保存在hashSet底层的哪个位置。
  3. HashSet会到底层数组该位置去检查,这个位置是否有元素
    1. 如果该位置没有元素,直接把心元素保存到数组的该位置。
    2. 如果该元素有元素,此处就会形成链。
HashSet取元素的步骤
  1. HashSet会先调用元素的hashCode()方法,该方法返回一个int值。
  2. HashSet会根据元素的hashCode值计算该元素应该保存在hashSet底层的哪个位置。
  3. HashSet会到底层数组该位置去检查,这个位置是否为要找的元素
    1. 如果该位置确实保存着要找的元素,直接取出该元素即可。
    2. 如果该位置的元素不是要找的元素,此时就需要顺着这个链逐个去找。

链的意思 : 假如有一个位置已经有值了,把新加入的值再填进去,把原来的值和它之间创建一个链接


从上面看,指定位置有元素就形成链,链越长,查找的性能就越差。
HashSet底层数组越大,形成链条概率越小。

HashSet其中一个构造器
    HashSet(int initialCapacity,float loadFactor)
    有两个性能选项:
    inintialCapacity: 初始大小:创建HashSet时底层数组的长度。默认是16
    (一定是2^n)
    loadFactor:负载因子。默认值是0.75(当 元素个数 / 数组长度 >= 负载因子时,
    HashSet会将数组长度扩大一倍)

假如设置负载因子为 0.1 就是每用到1/10 就扩大一倍
假如设置负载因子为 0.25 就是没用到1/4就扩大一倍
假如设置负载因子为 0.5 就是每用到一半就扩大一倍
默认负载因子为 0.75 就是用到3/4时,底层数组就会扩大一倍

负载因子越大,数组利用率越高(越省内存的利用率),形成链条的概率就越大。
负载因子越小,数组利用率越低(越耗内存的利用率),形成链条的概率就越小。
通常负载因子设置小一点,牺牲内存来提升性能。

LinkedHashSet

LinkedHashSet是HashSet的子类,因此与HashSet功能完全相同。
LinkedHashSet会维护链(额外开销,与HashSet相比略慢),用于记住元素的添加顺序。
LinkedHashSet是有序的。

与HashSet相比
  1. 速度略慢
  2. 记得住添加顺序

TreeSet

TreeSet是基于'红黑树'实现的。 '红黑树'是半平衡的排序二叉树

特征:

  1. 元素不允许重复
  2. 比HashSet要慢。
  3. TreeSet实现了SortedSet,因此TreeSet会对元素按从小到大排列。

TreeSet怎么比较元素的大小?

  • 自然排序:元素本身就可以比较大小。因为元素的类型实现了一个Comparable接口、并实现了该接口中的compareTo方法。
  • 定制排序:不要求元素本身可比较大小。
    但此时要求创建TreeSet时传入Comparator对象,该对象负责比较元素的大小。

TreeSet要求集合元素只能是同一个类型,比如屎能和猫比较吗🤗


  • 自然排序:元素本身就可以比较大小。因为元素的类型实现了一个Comparable接口、并实现了该接口中的compareTo方法。
    • 实例:
      • 自定义方法没有实现Comparable接口来使用TreeSet添加对象
        14
      • 给自定义的Cow类实现了Comparable接口,并实现了compareTo方法:
        15
  • 定制排序:不要求元素本身可比较大小。
    但此时要求创建TreeSet时传入Comparator对象,该对象负责比较元素的大小。
    • 在API中找到一个TreeSet的构造器:
      16
    • 发现Comparator是一个函数式接口:
      17
      里面有一个抽象方法要实现
      18
    • 创建TreeSet时构造器里传入Comparator就可以了:
      19
      是不是很简单。

TreeSet怎么判断两个元素相等?

只要两个元素通过compareTo(自然排序 实现Comparable)
或compare(定制排序 实现函数式接口 Comparator)
比较返回0 , TreeSet就认为它们是相等的。

举个栗子:
20

原因很简单: 上面说了 只要compareTo里面返回0 就判断两个对象是相等的

public int compareTo(Cow cow) {
        return this.weight > cow.weight ? 1 : (this.weight < cow.weight)? -1 : 0;
    }
这个方法只是判断了weight,所以尽管名字不同
weight相等返回值还是0,程序就认为是同一个对象
所以,胡泽宇就失踪了。

21