8.3 Set集合 8.3.1 HashSet类

• 8.3 Set集合
• 8.3.1 HashSet类
  • HashSet特点
  • 重写hashCode()方法的基本规则
  • 重写hashCode()方法的一般步骤

8.3 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会调用该对象的hashCode()方法来得到该对象的hashCode值,然后根据该hashCode值决定该对象在HashSet中的存储位置。如果有两个元素通过equals()方法比较返回true,但它们的hashCode()方法返回值不相等, HashSet将会把它们存储在不同的位置,依然可以添加成功。
也就是说, HashSet集合判断两个元素相等的标准是两个对象通过equals方法比较相等,并且两个对象的hashCode()方法返回值也相等.
下面程序分别提供了三个类A、B和C,它们分别重写了equals、 hashCode()两个方法的一个或全部,通过此程序可以让读者看到HashSet判断集合元素相同的标准。

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对象当成同一个对象。运行上面程序,看到如下运行结果:

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

从上面程序可以看出,即使两个A对象通过equals()方法比较返回true,但HashSet依然把它们当成两个对象;即使两个B对象的hashCode()返回相同值(都是1),但HashSet依然把它们当成两个对象。
这里有一个注意点:当把一个对象放入HashSet中时,如果需要重写该对象对应类的equals()方法,则也应该重写其hashCode()方法。规则是:如果两个对象通过equals方法比较返回true,这两个对象的hashCode()方法的返回值也应该相同
如果两个对象的hashCode()方法返回的hashCode值相同,但它们通过equals()方法比较返回false时将更麻烦:因为两个对象的hashCode值相同, HashSet将试图把它们保存在同一个位置,但是放在同一个位置是不行的,因为新的对象会覆盖旧的对象导致数据丢失,所以实际上会在这个位置用链式结构来保存多个对象;而HashSet访问集合元素时也是根据元素的hashCode值来快速定位的,如果HashSet中两个以上的元素具有相同的hashCode值,将会导致性能下降。

学生提问:hashCode()方法对于HashSet是不是十分重要?
答:hash算法的能快速查找被检索的对象,hash算法的价值在于速度。当需要查询集合中某个元素时,hash算法可以直接根据该元素的hashCode值计算出该元素的存储位置,从而快速定位到该元素。
为了理解这个概念,可以先看数组(数组是所有能存储一组元素里最快的数据结构)数组可以包含多个元素,每个元素都有索引,如果需要访问某个数组元素,只需提供该元素的索引,接下来即可根据索引计算该元素在内存里的存储位置。
表面上看起来, HashSet集合里的元素都没有索引,实陈上当程序向HashSet集合中添加元素时, HashSet会根据该元素的hashCode值来计算它的存储位置,这样也可快速定位到该元素。

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

为什么不直接使用数组、还需要使用HashSet呢?因为数组元素的索引是连续的,而且数组的长度是固定的,无法自由增加数组的长度。而HashSet就不一样了, HashSet采用每个元素的hashCode值来计算其存储位置,从而可以自由增加HashSet的长度,并可以根据元素的hashCode值来访问元素。因此,当从HashSet中访问元素时, HashSet先计算该元素的hashCode值(也就是调用该对象的hashCode方法的返回值),然后直接到该hashCode值对应的位置去取出该元素——这就是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值。计算方式如表8.1所示。

表8.1 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();

2.用第1步计算出来的多个hashCode值组合计算出一个hashCode值返回。例如如下代码:

return f1.hashCode()+(int)f2;

为了避免直接相加产生偶然相等(两个对象的f1、f2实例变量并不相等,但它们的hash Code的和恰好相等),可以通过为各实例变量的hashCode值各自乘以任意一个质数后再相加。例如如下代码:

return f1.hashCode() * 19 +(int) f2 *31;

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

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对象与集合中的其他对象相同。程序运行结果下所示:

[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

正如图8.4中所见到的, 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无法正确操作这些集合元素。
注意:
当向HashSet中添加可变对象时,必须十分小心。如果修改HashSet集合中的对象,有可能导致该对象与集合中的其他对象相等,从而导致HashSet无法准确访问该对象.

原文链接: 8.3 Set集合 8.3.1 HashSet类