HashSet去重原理及Set无序性

HashSet的主要特征

　　1.实现了Collection接口的子类：Set接口。

　　2.HashSet的储存是无序的，即遍历的顺序和我们添加的顺序无关。

　　3.HashSet底层的数据结构是哈希表。根据哈希表得出的哈希值代表该对象的储存位置

　　4.HashSet不能添加重复的元素，底层是基于HashMap实现的

HashSet如何去重？

　　Set调用 add 方法时，调用了添加对象的 hashCode方法和 equals 方法：如果Set集合中没有与该元素 hashCode 值相同的元素，则说明该元素是新元素，可以添加到 Set 集合中；如果两个元素的 hashCode 值相同，再使用 equals 方法比较，如果返回值为 true，就说明两个元素相同，新元素不会被添加到 Set 集合中；如果 hashCode 值相同，但是 equals 方法比较后，返回值为 false ，就说明两个元素不相同，新元素会被添加到 Set 集合中。

　　一般来说，一个类必要时会同时重写hashCode()和equals()两个方法（如果没有重写，那么就默认调用Object中的hashCode()和equals()）。这也是HashSet去重机制的关键。

去重代码示例

public class User {
	private String name;
	private String sex;
	private int age;
	
	public User(String name,String sex,int age) {
		this.name=name;
		this.sex=sex;
		this.age=age;
	}
	
	public String getName() {
		return name;
	}
	public void setName(String name) {
		this.name = name;
	}
	public String getSex() {
		return sex;
	}
	public void setSex(String sex) {
		this.sex = sex;
	}
	public int getAge() {
		return age;
	}
	public void setAge(int age) {
		this.age = age;
	}
	
	//重写toString
	public String toString() {
		return name+"--"+sex+"--"+"--"+age;
	}
}

当没有重写hashCode()和equals()时

public class test {
　　public static void main(String[] args) {

	User user1 = new User("张三","男",20);
	User user2 = new User("张三","男",20);
	Set<User> users = new HashSet<User>();
	users.add(user1);
	users.add(user2);
		
	//遍历
	Iterator<User> iterator = users.iterator();
	while(iterator.hasNext()) {
		System.out.println(iterator.next());
	}
　　}
}

运行结果：

张三--男----20
张三--男----20

从运行结果可以看到user1和uer2都被添加进HashSet集合中。因为我这里没有重写hashCode()和equals()，所以这里默认使用了Object类中的hashCode()，通过Object中hashCode()得出的user1和user2的哈希值是不同的，因为他们的存放地址是不一样。即直接判定这两个对象是不同的，可以同时放入HashSet集合。

如果两个对象即使存储位置不同，只要属性完全相同就不能存放进HashSet。这时需要重写hashCode()和equals()方法。

在User类中添加重写的hashCode()和equals()方法。

　　　　　public int hashCode() {	
		int result = 17;
		result = result*31 + this.name.hashCode();
		result = result*31 + this.sex.hashCode();
		result = result*31 + this.age;
		return result;	
	}
	// 重写equals
	public boolean equals(Object obj) {
	     if(this == obj){
               return true;//地址相等
             }
             if(obj == null){
               return false;//非空性：对于任意非空引用x，x.equals(null)应该返回false。
             }
             if(obj instanceof User) {
        	  User user  = (User)obj;
　　　　　　　 if(this.name.equals(user.name)&&this.sex.equals(user.sex)&&this.age==user.age) {
        		return true;
        	   }
             }
		return false;
	  }

运行结果：

张三--男----20

可以发现，这个时候只能加入一个user，并且是user1。（因为user1先执行add操作）通过重写了hashCode()和equals()方法，我们修改了判定规则，我们通过属性的hash值返回hashCode的结果，并且在重写后的equals()方法通过比较属性来判断是否是同一个对象。

Set无序性探索

　我们经常听说List是有序且可重复的，Set是无序且不重复的。这是一个误区，这里所说的顺序有两个概念，一是按照添加的顺序排列，二是按照自然顺序a-z排列。Set并不是无序的,传统所说的Set无序指的是HashSet，它不能保证元素的添加顺序，更不能保证自然顺序，而Set的其他实现类是可以实现这两种顺序的。

1，LinkedHashset : 保证元素添加的自然顺序

2，TreeSet : 保证元素的自然顺序

通过下面一段代码来理解上述问题：

import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.Set;
import java.util.TreeSet;
 
public class set {
    public static void main(String[] args) {
        // Tree保证元素按照自然顺序a-z排列
        Set set=new TreeSet<String>();
        set.add("aa");
        set.add("b2");
        set.add("cc3");
        set.add("d4");
        set.add("a");
        System.out.println("TreeSet---"+set);
 
        // HashSet无序
        Set hashSet=new HashSet();
        hashSet.add("aa");
        hashSet.add("b2");
        hashSet.add("cc3");
        hashSet.add("d4");
        hashSet.add("a");
        System.out.println("HashSet---"+hashSet);
 
        //LinkedHashSet会保证元素的添加顺序
        Set<String> linkedHashSet = new LinkedHashSet<>();
        linkedHashSet.add("a");
        linkedHashSet.add("c");
        linkedHashSet.add("b");
        linkedHashSet.add("e");
        linkedHashSet.add("d");
        //linkedHashSet.forEach(e-> System.out.print(e+" "));
        System.out.println("LinkedHashSet---"+linkedHashSet);
    }
 
}　

输出结果：

TreeSet---[a, aa, b2, cc3, d4]          TreeSet元素按自然顺序排序
HashSet---[aa, b2, d4, a, cc3]         HashSet元素乱序
LinkedHashSet---[a, c, b, e, d]        LinkedHashSet保证元素添加顺序