Java集合（三）—— Set详解

2022-12-09 18:05:42

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的学生，姓名为：张平

码农公寓