Java集合(三)—— Set详解

Set接口

一、HashSet

public class HashSet<E>extends AbstractSet<E>implements Set<E>, Cloneable, Serializable

HashSet继承自Set接口,无序、不可重复的,线程不安全,存取速度快。
当向HashSet集合中存入一个元素时,HashSet会调用该对象的hashCode()方法来得到该对象的hashCode值,然后根据hashCode值决定该对象在HashSet中的存储位置。
如果两个元素的equals()方法返回true,但它们的hashCode()返回值不相等,hashSet将会把它们存储在不同的位置,但依然可以添加成功,

1、实现原理

HashSet 是基于 HashMap 实现的,HashSet的值存放于 HashMap的key上,HashMap的value统一为present,因此 HashSet 的实现比较简单,相关 HashSet 的操作,基本上都是直接调用底层HashMap 的相关方法来完成,HashSet 不允许重复的值。

2、扩容机制

HashMap 默认初始容量为16(为何是16?),加载因子为 0.75(即当 元素个数 超过 容量长度的0.75倍时,进行扩容)。
扩容增量是原容量的 1 倍,扩展后的新容量为原容量的2倍。

如:HashSet的容量为16,一次扩容后是容量为32

3、HashSet添加元素

3.1、什么是hashCode

hashCode就是对象的散列码,是根据对象的某些信息推导出的一个整数值,默认情况下表示是对象的存储地址。通过散列码,可以提高检索的效率,主要用于在散列存储结构中快速确定对象的存储地址,如Hashtable、hashMap中。

hashCode详细可以看另一篇博客hashCode 以及 hashCode()与equals()的联系

3.2、HashSet如何检查重复?HashSet是如何保证数据不可重复的?

向HashSet 中add ()元素时,判断元素是否存在的依据,不仅要比较hash值,同时还要结合equles 方法比较。
HashSet 中的add ()方法会使用HashMap 的put()方法。
HashMap 的 key 是唯一的,由源码可以看出 HashSet 添加进去的值就是作为HashMap 的key,并且在HashMap中如果K/V相同时,会用新的V覆盖掉旧的V,然后返回旧的V。所以不会重复(HashMap 比较key是否相等是先比较hashcode 再比较equals )。

是HashSet 部分源码:

private static final Object PRESENT = new Object();
private transient HashMap<E,Object> map;
public HashSet() {
map = new HashMap<>();
}
public boolean add(E e) {
// 调用HashMap的put方法,PRESENT是一个至始至终都相同的虚值
return map.put(e, PRESENT)==null;
}

hashCode()与equals()的相关规定:

1.如果两个对象相等,则hashcode一定也是相同的
hashCode是jdk根据对象的地址或者字符串或者数字算出来的int类型的数值
2. 两个对象相等,对两个equals方法返回true
3. 两个对象有相同的hashcode值,它们也不一定是相等的
4. 综上,equals方法被覆盖过,则hashCode方法也必须被覆盖
5. hashCode()的默认行为是对堆上的对象产生独特值。如果没有重写hashCode(),则该class的两个
对象无论如何都不会相等(即使这两个对象指向相同的数据)。

3.3、HashSet与HashMap的区别

HashMap HashSet
实现了Map接口 实现Set接口
存储键值对 仅存储对象
调用put() 向map中添加元素 调用add()方法向Set中添加元素
HashMap使用键(Key)计算Hashcode HashSet使用成员对象来计算hashcode值,对于两个对象来说hashcode可能相同,所以equals()方法用来判断对象的相等性,如果两个对象不同的话,那么返回false
HashMap相对于HashSet较快,因为它是使用唯一的键获取对象 HashSet较HashMap来说比较慢

二、TreeSet

public class TreeSet<E>extends AbstractSet<E>implements NavigableSet<E>, Cloneable, Serializable

TreeSet继承自Set接口,有序、不可重复的,线程不安全。
TreeSet中的元素默认按照自然升序排列。
TreeSet底层是TreeMap实现的,添加的数据存入了map的 key 的位置,而value则固定是PRESENT

1、自定义排序

如果程序员想定义自己的排序方式,方法也很简单,就是让加入 TreeSet 集合中的对象所属的类实现 Comparable 接口,通过实现 compareTo(Object o)方法,达到排序的目的。
假设有这样的需求,学生对象有两个属性,分别是学号和姓名。希望将这些学生对象加入TreeSet 集合后,按照学号大小从小到大进行排序,学号相同的再按照姓名自然排序。来看学生类的代码(实现 Comparable 接口):

class Student implements Comparable {
	int stuNum =-1; //学生学号
	String stuName =""; //学生姓名
	Student(String name, int num){
		this.stuNum = num;
		this.stuName = name;
	}
	//返回该对象的字符串表示,利于输出
	public String toString() {
		return "学号为:"+ stuNum +"的学生,姓名为:"+ stuName;
	}
	//实现 Comparable 的 compareTo 方法
	public int compareTo(Object o){
		Student input =(Student) o;
		//此学生对象的学号和指定学生对象的学号比较
		//此学生对象学号若大则 res 为 1,若小则 res 为-1,相同的话 res =0
		int res = stuNum > input.stuNum?1:(stuNum == input.stuNum?0:-1);
		//若学号相同,则按照 String 类自然排序比较学生姓名
		if(res == O){
			res = stuName.compareTo(input.stuName);
		}
		return res;
	}
}

其中,int compareTo(Object o)方法是用此对象和指定对象进行比较的,如果该对象小于、等于或大于指定对象,则分别返回负整数、零或正整数。编写测试程序,具体代码如下。

public class TestTreeSet2{
	public static void main(String[] args){
	//用有序的 TreeSet 存储学生对象
	Set stuTS = new TreeSetO;
	stuTS.add(new Student("王云",1));
	stuTS,add(new Student("南天华",3));
	stuTS,add(new Student("刘静涛",2));
	stuTS,add(new Student("张平",3));
	//使用迭代器循环输出
	Iterator it=stuTS.iterator();
	while(it.hasNext()){
		System.out.println(it.next());
	}
结果输出

学号为:1的学生,姓名为:王云
学号为:2的学生,姓名为:刘静涛
学号为:3的学生,姓名为:南天华
学号为:3的学生,姓名为:张平
上一篇:【Java】对两个Set取交集,差集,并集


下一篇:HashSet底层实现