8.3 Set集合 8.3.1 HashSet类

发表于 更新于 分类于 ， ， Waline： 本文字数： 6.1k 阅读时长 ≈ 6 分钟

8.3 Set集合

Set集合无序

前面已经介绍过Set集合,它类似于一个罐子,程序可以依次把多个对象”丢进”Set集合,而Set集合通常不能记住元素的添加顺序。

Set集合不可重复

Set集合与Collection基本相同,没有提供任何额外的方法。实际上Set就是Collection,只是行为略有不同(Set不允许包含重复元素)。

Set集合不允许包含相同的元素,如果试图把两个相同的元素加入同一个Set集合中,则添加操作失败,add()方法返回false,并且新元素不会覆盖旧元素。

上面介绍的是Set集合的通用知识,因此完全适合后面介绍的HashSet、 TreeSet和EnumSet三个实现类,只是三个实现类还各有特色。

8.3.1 HashSet类

HashSet是Set接口的典型实现,大多数时候使用Set集合时就是使用这个实现类。 HashSet按Hash算法来存储集合中的元素,具有很好的存取和査找性能。

HashSet特点

HashSet具有以下特点。

  • 不能保证元素的排列顺序,顺序可能与添加顺序不同,顺序也有可能发生变化。
  • HashSet不是同步的,如果多个线程同时访问一个HashSet,假设有两个或者两个以上线程同时修改了HashSet集合时,则必须通过代码来保证其同步。
  • 集合元素值可以是null

HashSet判断两个元素相等的标准

当向HashSet集合中存入一个元素时, HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值,然后根据该hashCode值决定该对象在HashSet中的存储位置。

如果有两个元素通过equals()方法比较返回true,但它们的hashCode()方法返回值不相等, HashSet将会把它们存储在不同的位置,依然可以添加成功。

也就是说, HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等,并且两个对象的hashCode()方法返回值也相等。

程序 HashSet判断元素相同的标准

下面程序分别提供了三个类A、B和C,它们分别重写了equals、 hashCode()两个方法的一个或全部,通过此程序可以让读者看到HashSet判断集合元素相同的标准。

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
import java.util.*;

// 类A的equals方法总是返回true，但没有重写其hashCode()方法
class A
{
    public boolean equals(Object obj)
    {
        return true;
    }
}
// 类B的hashCode()方法总是返回1，但没有重写其equals()方法
class B
{
    public int hashCode()
    {
        return 1;
    }
}
// 类C的hashCode()方法总是返回2，且重写其equals()方法总是返回true
class C
{
    public int hashCode()
    {
        return 2;
    }
    public boolean equals(Object obj)
    {
        return true;
    }
}
public class HashSetTest
{
    public static void main(String[] args)
    {
        HashSet books = new HashSet();
        // 分别向books集合中添加两个A对象，两个B对象，两个C对象
        books.add(new A());
        books.add(new A());
        books.add(new B());
        books.add(new B());
        books.add(new C());
        books.add(new C());
        System.out.println(books);
    }
}

上面程序中向books集合中分别添加了两个A对象、两个B对象和两个C对象,其中C类重写了equals方法总是返回true, hashCode()方法总是返回2,这将导致HashSet把两个C对象当成同一个对象。运行上面程序,看到如下运行结果:

1
[A@7852e922, B@1, B@1, C@2, A@4e25154f]

从上面程序可以看出:

  • 即使两个A对象通过equals()方法比较返回true,但HashSet依然把它们当成两个对象;
  • 即使两个B对象的hashCode()返回相同值(都是1),但HashSet依然把它们当成两个对象。

HashSet中的元素要求 equals方法和hashCode方法返回值相同

这里有一个注意点:当把一个对象放入HashSet中时,如果需要重写该对象对应类的equals()方法,则也应该重写其hashCode()方法。
规则是:如果两个对象通过equals方法比较返回true,这两个对象的hashCode()方法的返回值也应该相同

hashCode返回值相同 equals返回值不同时会怎样

如果两个对象的hashCode()方法返回的hashCode值相同,但它们通过equals()方法比较返回false时将更麻烦:因为两个对象的hashCode值相同, HashSet将试图把它们保存在同一个位置,但是放在同一个位置是不行的,因为新的对象会覆盖旧的对象导致数据丢失,所以实际上会在这个位置用链式结构来保存多个对象;

而HashSet访问集合元素时也是根据元素的hashCode值来快速定位的,如果HashSet中两个以上的元素具有相同的hashCode值,这需要链表上继续查找,这将会导致性能下降。

hashCode()方法对于HashSet是不是十分重要

hash算法可以快速查找被检索的对象,hash算法的价值在于速度。当需要查询集合中某个元素时,hash算法可以直接根据该元素的hashCode值计算出该元素的存储位置,从而快速定位到该元素。

通过索引可以计算数组元素在内存中的位置

为了理解这个概念,可以先看数组(数组是所有能存储一组元素里最快的数据结构)数组可以包含多个元素,每个元素都有索引,如果需要访问某个数组元素,只需提供该元素的索引,接下来即可根据索引计算该元素在内存里的存储位置。

通过hashCode也可以计算元素的存储位置

表面上看起来, HashSet集合里的元素都没有索引,实际上,当程序向HashSet集合中添加元素时, HashSet会根据该元素的hashCode值来计算它的存储位置,这样也可快速定位到该元素。

为什么不直接使用数组、还需要使用HashSet呢?

为什么不直接使用数组、还需要使用HashSet呢?因为数组元素的索引是连续的,而且数组的长度是固定的,无法自由增加数组的长度。

而HashSet就不一样了, HashSet采用每个元素的hashCode值来计算其存储位置,从而可以自由增加HashSet的长度,并可以根据元素的hashCode值来访问元素。

因此,当从HashSet中访问元素时, HashSet先调用该对象的hashCode方法来计算该元素的hashCode值,然后直接到该hashCode值对应的内存地址去取出该元素,这就是HashSet速度很快的原因。

HashSet的桶

HashSet中每个能存储元素的”槽位”(slot)通常称为”桶”(bucket),如果有多个元素的hashCode值相同,但它们通过equals方法比较返回false,就需要在一个”桶”里放多个元素,这样会导致性能下降。

重写hashCode()方法的基本规则

前面介绍了hashCode()方法对于HashSet的重要性(实际上,对象的hashCode值对于后面的HashMap同样重要),下面给出重写hashCode()方法的基本规则。

  1. 在程序运行过程中,同一个对象多次调用hashCode()方法应该返回相同的值。
  2. 当两个对象通过equals()方法比较返回true时,这两个对象的hashCode()方法应返回相等的值。
  3. 对象中用作equals方法比较标准的实例变量,都应该用于计算hashCode值。

重写hashCode()方法的一般步骤

下面给出重写hashCode()方法的一般步骤。

  1. 把对象内每个参与equals方法比较标准的实例变量都计算出一个int类型的hashCode值。计算方式如下表所示:
实例变量类型 计算方式
boolean变量f hashCode=(f?0:1)
整数类型(byte,short,char,int)变量f hashCode=(int) f;
long类型变量f hashCode=(int)(f^(f>>>32));
float类型变量f hashCode=Float.frontToIntBits(f);
double类型变量f long l=Double.doubleToLongBits(f); hashCode=(int)(l^(l>>>32));
引用类型变量f hashCode=f.hashCode();
  1. 用第1步计算出来的多个hashCode值组合计算出一个hashCode值返回。例如如下代码:
    1
    return f1.hashCode()+(int)f2;
    为了避免直接相加产生偶然相等(两个对象的f1、f2实例变量并不相等,但它们的hash Code的和恰好相等),可以通过为各实例变量的hashCode值各自乘以任意一个质数后再相加。例如如下代码:
    1
    return f1.hashCode() * 19 +(int) f2 *31;

HashSet中添加可变对象出现的问题

如果向HashSet中添加一个可变对象后,后面程序修改了该可变对象的实例变量,则可能导致它与集合中的其他元素相同(即两个对象通过equals方法比较返回true,两个对象的hashCode值也相等),这就有可能导致HashSet中包含两个相同的对象。

下面程序演示了这种情况。

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
import java.util.*;

class R
{
    int count;
    public R(int count)
    {
        this.count = count;
    }
    public String toString()
    {
        return "R[count:" + count + "]";
    }
    public boolean equals(Object obj)
    {
        if(this == obj)
            return true;
        if (obj != null && obj.getClass() == R.class)
        {
            R r = (R)obj;
            return this.count == r.count;
        }
        return false;
    }
    public int hashCode()
    {
        return this.count;
    }
}
public class HashSetTest2
{
    public static void main(String[] args)
    {
        HashSet hs = new HashSet();
        hs.add(new R(5));
        hs.add(new R(-3));
        hs.add(new R(9));
        hs.add(new R(-2));
        // 打印HashSet集合，集合元素没有重复
        System.out.println(hs);
        // 取出第一个元素
        Iterator it = hs.iterator();
        R first = (R)it.next();
        // 为第一个元素的count实例变量赋值
        first.count = -3;     // ①
        // 再次输出HashSet集合，集合元素有重复元素
        System.out.println(hs);
        // 删除count为-3的R对象
        hs.remove(new R(-3));    // ②
        // 可以看到被删除了一个R元素
        System.out.println(hs);
        System.out.println("hs是否包含count为-3的R对象？"
            + hs.contains(new R(-3))); // 输出false
        System.out.println("hs是否包含count为-2的R对象？"
            + hs.contains(new R(-2))); // 输出false
    }
}

上面程序中提供了R类,R类重写了equals(Object object)方法和hashCode()方法,这两个方法都是根据R对象的count实例变量来判断的。

上面程序的①号代码处改变了Set集合中第一个R对象的count实例变量的值,这将导致该R对象与集合中的其他对象相同。

程序运行结果如下所示:

1
2
3
4
5
[R[count:-2], R[count:-3], R[count:5], R[count:9]]
[R[count:-3], R[count:-3], R[count:5], R[count:9]]
[R[count:-3], R[count:5], R[count:9]]
hs是否包含count为-3的R对象？false
hs是否包含count为-2的R对象？false

正如上面运行结果中所见到的,HashSet集合中的第1个元素和第2个元素完全相同,这表明两个元素已经重复。

此时HashSet会比较混乱:当试图删除count为-3的R对象时, HashSet会计算出该对象的hashCode值,从而找出该对象在集合中的保存位置,然后把此处的对象与count为-3的R对象通过equals方法进行比较,如果相等则删除该对象。

HashSet只有第2个元素才满足该条件(第1个元素实际上保存在count为-2的R对象对应的位置),所以第2个元素被删除。

至于第一个count为-3的R对象,它保存在count为-2的R对象对应的位置,但使用equals方法拿它和count为-2的R对象比较时又返回false
这将导致HashSet不可能准确访问该元素。

元素放到HashSet后,不要修改参与计算hashCode和equals的实例变量的值

由此可见,当程序把可变对象添加到HashSet中之后,尽量不要去修改该集合元素中参与计算hashCode()、 equals()的实例变量,否则将会导致HashSet无法正确操作这些集合元素。

注意:
当向HashSet中添加可变对象时,必须十分小心。如果修改HashSet集合中的对象,有可能导致该对象与集合中的其他对象相等,从而导致HashSet无法准确访问该对象。