HashSet如何保证元素唯一性？

布满荆棘的人生 2022-07-12 13:17 217阅读 0赞

Collection中的Set分为HashSet和TreeSet  
Set中的元素是无序的，即存入和取出的顺序**不一定一致**，**元素不可以重复**。HashSet的底层数据结构是哈希表，元素存入的顺序是按照哈希值来排序的。  
那么HashSet是如何保证元素唯一性的呢？

首先我们先直观地看看哈希值的样子

class Demo{
    }
    
    public class HashSetTest {
    
        public static void main(String[] args) {
            Demo d1=new Demo();
            Demo d2=new Demo();
            sop(d1);
            sop(d2);
        }
        public static void sop(Object obj){
       //定义此sop方法用来快捷输出，在输出较多的情况下尤为快捷。
            System.out.println(obj);
        }
    }

![这里写图片描述][SouthEast]

HashCode就长这个样子

**这些HashCode是如何产生的呢？**  
HashSet有一个方法叫做 int hashCode()，会在默认情况下产生无序的16进制hashcode值。  
为了让其得到体现，我们可以直接将其重写：  
在Demo类中重写hashCode()方法

class Demo{
         public int hashCode()
         {
             return 60;
         }
    }
    
    public class HashSetTest {
    
        public static void main(String[] args) {
            Demo d1=new Demo();
            Demo d2=new Demo();
            sop(d1);
            sop(d2);
        }
        public static void sop(Object obj){
            System.out.println(obj);
        }
    }

重写的效果就是，不管什么情况下，hashCode()方法都只返回一个hashCode值，60（16进制下为3c），所以其结果如下:

![这里写图片描述][SouthEast 1]

那么问题来了，由于HashSet是根据哈希值来排序的，那么如果有相同的哈希值的时候会发生什么情况？

再次举个例子，我们使用一个比较健全的自定义类，Person，此类有两个元素，String name和 int age，还有getName(),getAge()两个基础方法，再加上复写的hashCode()方法。定义HashSet对象hs。

class Person
    {
        private String name;
        private int age;
        Person(String name,int age)
        {
            this.name=name;
            this.age=age;
        }
    
        public String getName()
        {
            return name;
        }
        public int getAge()
        {
            return age;
        }
        public int hashCode()
        {
            System.out.println(this.name+"......hashCode");
            return 60;
        }
    }
    
    public class HashSetDemo {
    
        public static void sop(Object obj)
        {
            System.out.println(obj);
        }
        public static void main(String[] args) {
            HashSet hs=new HashSet<>();
    
            hs.add(new Person("a1",11));
            hs.add(new Person("a2",12));
            hs.add(new Person("a2",12));
            hs.add(new Person("a3",13));
    
            Iterator it=hs.iterator();
            while(it.hasNext()){
                Person p=(Person)it.next();
                sop(p.getName()+"::"+p.getAge());
            }
        }
    
    }
    /*思路： * 1，对人描述，将数据封装进人对象 * 2，定义容器，将人存入 * 3，取出 */

![这里写图片描述][SouthEast 2]

运行结果前四句表示每一步都调用了复写完的hashCode()方法计算哈希值，后四句表示将a1,a2,a3都写入和新容器，且a2写了两次。

这个情况就是所有的a对象（转型到了hashSet），他们的hashcode都是一样的，依旧无法避免他们写入，没有保证元素的唯一性。

**因为HashSet()保证元素唯一性是通过元素的两个方法，hashCode()和equals()来完成的。**  
**如果元素的HashCode值相同，才会判断equals是否为true。**  
**如果元素的HashCode值不同，不会调用equals。**

由于原始equals方法只适用于String的判断，不能识别name和age的组合，所以会出现重复的元素写入。

让我们重写一个适用于Person的equals方法

public boolean equals(Object obj)
        {
    
            if(!(obj instanceof Person))
                return false;
            Person p=(Person)obj;
            System.out.println(this.name+"...."+p.name);
            return this.name.equals(p.name) && this.age == p.age;
        }

此方法实现了保证name和age都相同时视为重复元素。在hashCode()方法运行时会自动调用equals方法  
![这里写图片描述][SouthEast 3]  
第一句：计算a1哈希值，存入  
第二句：计算a2哈希值，发现和a1一样为3c  
第三句：a2和a1进行equals比较，不一样，存入  
第四句：第二个a2来了，计算哈希值也是3c  
第五句：第二个a2和第一个a2equals比较，一样，不存入  
第六句：a3计算哈希值，为3c  
七八句为a3和与其哈希值相同的a1，a2比较equals。  
九，十，十一就是存入的结果，没有重复。  
其实这是一种比较尴尬的状态，因为所有的元素哈希值都是一样的，这就意味着第2个元素要和第一个比较，第3个要和1，2比较，第4个要和1，2，3比较，第5个要和1，2，3，4比较，效率较低

所以做个优化，将hashCode()方法的return 60；换成return name.hashCode()+age\*37;（37为随意取值）

完整代码

import java.util.*;
    
    class Person
    {
        private String name;
        private int age;
        Person(String name,int age)
        {
            this.name=name;
            this.age=age;
        }
        public int hashCode()
        {
            System.out.println(this.name+"......hashCode");
            return name.hashCode()+age*37;
        }
    
        public boolean equals(Object obj)
        {
    
            if(!(obj instanceof Person))
                return false;
            Person p=(Person)obj;
            System.out.println(this.name+"....equals...."+p.name);
            return this.name.equals(p.name) && this.age == p.age;
        }
        public String getName()
        {
            return name;
        }
        public int getAge()
        {
            return age;
        }
    }
    
    public class HashSetDemo {
    
        public static void sop(Object obj)
        {
            System.out.println(obj);
        }
        public static void main(String[] args) {
            HashSet hs=new HashSet<>();
    
            hs.add(new Person("a1",11));
            hs.add(new Person("a2",12));
            hs.add(new Person("a2",12));
            hs.add(new Person("a3",13));
    
            Iterator it=hs.iterator();
            while(it.hasNext()){
                Person p=(Person)it.next();
                sop(p.getName()+"::"+p.getAge());
            }
        }
    
    }

运行结果：  
![这里写图片描述][SouthEast 4]

避免了重复比较。

总结：

Set:元素无序（存入和取出的顺序不一定一致），元素不可以重复。

*  HashSet：底层数据结构是哈希表。
 *  HashSet如何保证 元素唯一性的呢？  
    是通过元素的两个方法，hashCode和equals来完成的。  
    如果元素的HashCode值相同，才会判断equals是否为true。  
    如果元素的HashCode值不同，不会调用equals。

注意，对于判断元素是否存在，以及删除等操作，依赖的方法是元素的HashCode和equals方法  
先判断hashcode是否相同，如果相同再判断equals

！！（ArrayList判断和删除元素只依赖equals）

[SouthEast]: /images/20220710/3625eb39579948298e88b432f9ed4796.png
[SouthEast 1]: /images/20220710/1c1481391b3046b0aee6d2f5d066942d.png
[SouthEast 2]: /images/20220710/2397fea52a5042b28d7b881d26410843.png
[SouthEast 3]: /images/20220710/66517be5f2494968a38b675444606b7b.png
[SouthEast 4]: /images/20220710/225e762a16874cfe818691ec79211989.png

发表评论取消回复

表情：

评论列表（有 0 条评论，217人围观）

还没有评论，来说两句吧...

相关阅读

相关【HashSet如何保证元素不重复】

HashSet使用了哈希表（Hash Table）数据结构，它是一种以键-值（Key-Value）存储数据的结构，可以快速的插入或查找元素。在HashSet中，元素被添加进来时

浅浅的花香味﹌/ 2024年03月26日 16:58/ 0 赞/ 46 阅读

相关 HashSet如何判定两个元素相同

在介绍java的集合时，我们提到，set是一个“罐子”。我们可以向其中放入各式各样的元素，这些元素没有顺序，但不能相同。其中，HashSet是最常用的一个实现类。

桃扇骨/ 2022年08月20日 07:29/ 0 赞/ 197 阅读

相关元素唯一性问题（C实现）

include <stdio.h> define true 1 define false 0 int UniqueElements(i

末蓝、/ 2022年08月10日 00:56/ 0 赞/ 82 阅读

相关 HashSet如何保证元素唯一性？

Collection中的Set分为HashSet和TreeSet Set中的元素是无序的，即存入和取出的顺序不一定一致，元素不可以重复。HashSet的底层数据结构是哈希表

布满荆棘的人生/ 2022年07月12日 13:17/ 0 赞/ 218 阅读

相关 set,hashset及HashSet存储自定义对象保证元素唯一性的解析，还有eclipse批量替换查询

接口 Set<E> 类型参数： E - 此 set 所维护元素的类型所有超级接口： Collection<E>, It

分手后的思念是犯贱/ 2022年06月16日 08:26/ 0 赞/ 145 阅读

相关查找集合相同字段保证唯一性

List<Product> list = productServices.getProductNameList(product);

叁歲伎倆/ 2022年06月14日 05:43/ 0 赞/ 177 阅读

相关 Java_基础—HashSet存储自定义对象保证元素唯一性

创建一个Person类，属性为name, age Alt + Shift +S → C 空参构造 Alt + Shift +S → O 有参构造 Alt + Shif

太过爱你忘了你带给我的痛/ 2022年06月12日 04:12/ 0 赞/ 168 阅读

相关 HashSet如何保证元素唯一

hashset基于hashmap去实现，但是hashset如何保证集合内元素是唯一的呢，以下文章接下来去记录一下这个过程。 1.HashSet原理我们使用Set集合都

本是古典何须时尚/ 2022年04月23日 15:54/ 0 赞/ 235 阅读

相关保证Spring事务内连接的唯一性

> 保证Spring事务内连接的唯一性有时在Spring下需要配置多个数据源，通过DataSource来得到操作数据库的管道Connection，多线程下保证一个线

ゞ浴缸里的玫瑰/ 2022年04月23日 11:52/ 0 赞/ 172 阅读

相关 HashSet存储自定义对象保证元素唯一性图解原理及代码优化

HashSet存储自定义对象保证元素唯一性图解原理及代码优化 1.原理： \ 1.HashSet原理 \ 我们使用Set集合都是需要去掉重复元素的, 如果在

快来打我*/ 2022年04月23日 05:48/ 0 赞/ 207 阅读