本文已收录《Java常见面试题》系列，Git开源地址：https://gitee.com/mydb/interviewHashSet实现了Set接口，支持哈希表（实际上是HashMap）。HashSet不保证集合的迭代顺序，但允许插入空值。也就是说，HashSet不能保证元素的插入顺序和迭代顺序一样。HashSet具有去重特性，这意味着它可以自动过滤掉集合中的重复元素，确保HashSet中存储的元素是唯一的。一、HashSet的基本用法HashSet的基本操作方法有：add（添加）、remove（删除）、contains（判断一个元素是否存在）和size（集合个数）。如果散列函数是分散桶中元素的正确位置，则这些方法的性能是恒定的操作时间。HashSet的基本用法如下：//创建HashSet集合HashSetstrSet=newHashSet<>();//添加数据到HashSetstrSet.add("Java");strSet.add("MySQL");strSet.add("Redis");//循环打印HashSet中的所有元素strSet.forEach(s->System.out.println(s));2、HashSet无序HashSet不能保证插入元素的顺序和循环输出元素的顺序必须一致，也就是说HashSet其实是一个无序的集合。具体代码示例如下：HashSetmapSet=newHashSet<>();mapSet.add("深圳");mapSet.add("北京");mapSet.add("西安");//循环打印HashSet中的所有元素mapSet.forEach(m->System.out.println(m));上述程序的执行结果如下：从上面的代码和执行结果可以看出，HashSet的插入顺序是：深圳->北京->西安，而循环打印的顺序是：Xi'an->深圳->北京，所以HashSet是无序的，不能保证插入和迭代的顺序一致。PS：如果要保证插入顺序和迭代顺序一致，可以使用LinkedHashSet代替HashSet。3、HashSet的错误用法有人说HashSet只能保证基本数据类型不重复，不能保证自定义对象不重复？是对的吗？我们用下面的例子来说明这个问题。3.1HashSet和基本数据类型使用HashSet存储基本数据类型，实现代码如下：HashSetlongSet=newHashSet<>();longSet.add(666l);longSet.add(777l);longSet.add(999l);longSet.add(666l);//循环打印HashSet中的所有元素longSet.forEach(l->System.out.println(l));上面程序的执行结果如下：从上面的结果我们可以看出，使用HashSet可以保证底层数据类型不重复。3.2HashSet和自定义对象类型接下来，将自定义对象存储在HashSet中，实现代码如下：personSet.add(newPerson("曹操","123"));personSet.add(newPerson("孙权","123"));personSet.add(newPerson("曹操","123"));//循环并打印HashSet中的所有元素personSet.forEach(p->System.out.println(p));}}@Getter@Setter@ToStringclassPerson{私有字符串名称；私有字符串密码；publicPerson(Stringname,Stringpassword){this.name=name;this.password=密码；}}上面程序的执行结果如下：从上面的结果可以看出自定义对象类型还没有去重，也就是说HashSet不能实现自定义对象类型的去重？事实上，它不是。HashSet的去重功能依赖于元素的hashCode和equals方法。如果这两个方法返回true，那么它们就是同一个对象，否则就是不同的对象。之前的Long类型元素之所以能够实现去重，正是因为在Long类型中重写了hashCode和equals方法。具体实现源码如下：@OverridepublicinthashCode(){returnLong.hashCode(value);}publicbooleanequals(Objectobj){if(objinstanceofLong){returnvalue==((Long)obj).longValue();}returnfalse;}//省略其他源码...更多关于hashCode和equals的内容见：https://mp.weixin.qq.com/s/40zaEJEkQYM3Awk2EwIrWA然后，如果你想让HashSet支持自定义对象去重，只需要重写自定义对象中的hashCode和equals方法即可，具体实现代码如下：@Setter@Getter@ToStringclassPerson{privateStringname;私有字符串密码；publicPerson(Stringname,Stringpassword){this.name=name;this.password=密码；}@Overridepublicbooleanequals(Objecto){if(this==o)returntrue;//引用相等返回true//如果等于null，或者对象类型不同，返回falseif(o==null||getClass()!=o.getClass())returnfalse;//强制自定义Person类型Personperson=(Person)o;//如果名称和密码都相等，则返回truereturnObjects.equals(name,persion.name)&&Objects.equals(password,persion.password);}@OverridepublicinthashCode(){//比较name和password是否相等returnObjects.hash(name,password);}}重新运行上面的代码，执行结果如下图所示：从上面的结果可以看出前面的重复项“曹操”已经去重了4.HashSet如何保证元素是没有重复？我们只要了解了向HashSet中添加元素的过程，就可以知道为什么HashSet可以保证元素不重复了？向HashSet中添加元素的执行过程是：向HashSet中添加一个对象时，HashSet会先计算该对象的hashcode值，以确定添加该对象的位置，并与其他添加对象的hashcode值进行比较.如果没有匹配的hashcode，HashSet会认为该对象没有重复出现，并将该对象插入到相应的位置。但是如果找到一个hashcode值相同的对象，就会调用该对象的equals()方法来检查对象是否真的相同。如果相同，HashSet将不允许重复的对象加入到HashSet中，从而保证不重复。为了更清楚的理解HashSet的加法过程，我们可以尝试阅读HashSet的具体实现源码。HashSet添加方法的实现源码如下（以下源码基于JDK8）：//当hashmap中的put()返回null时，表示操作成功publicbooleanadd(Ee){returnmap.put(e,PRESENT)==null;}从上面的源码可以看出，HashSet中的add方法实际上调用了HashMap中的put，那么我们继续看HashMap中的put方法实现：//returnvalue：如果插入位置没有元素则返回null，否则返回前一个元素publicVput(Kkey,Vvalue){returnputVal(hash(key),key,value,false,true);}从上面的源码可以看出，HashMap中的put()方法调用了putVal()方法。putVal()的源码如下：finalVputVal(inthash,Kkey,Vvalue,booleanonlyIfAbsent,booleanevict){Node[]tab;节点p;诠释n,我;//如果哈希表为空，则调用resize()创建哈希表，并使用变量n记录哈希表的长度if((tab=table)==null||(n=tab.length)==0)n=(tab=resize()).length;/***如果指定的参数hash在表中没有对应的bucket，即没有碰撞*Hashfunction,(n-1)&hash计算key将被放置的slot*(n-1)&hash本质上是hash%n位运算速度更快*/if((p=tab[i=(n-1)&放大器;hash])==null)//只需将键值对插入地图tab[i]=newNode(hash,key,value,null);else{//元素已经存在于桶中Nodee;Kk;//比较桶中第一个元素（数组中的节点）的hash值是否相等，key是否相等if(p.hash==hash&&((k=p.key)==key||(key!=null&&key.equals(k))))//把第一个元素赋值给e，用e记录e=p;//当前桶中没有这个键值对，且桶是红黑树结构，按照红黑树结构插入elseif(pinstanceofTreeNode)e=((TreeNode)p).putTreeVal(this,tab,hash,key,value);//当前桶中没有这个键值对，桶是一个链表结构。按照链表结构插入到末尾else{for(intbinCount=0;;++binCount){//遍历到链表末尾if((e=p.next)==null){p.next=newNode(哈希，键，值，空);//检查链表的长度是否达到阈值，使得槽的节点组织形式可以转化为红黑树if(binCount>=TREEIFY_THRESHOLD-1)//-1表示第一个treeifyBin(tab,hash);休息;}//当链表节点的与put操作相同时//不重复操作跳出循环if(e.hash==hash&&((k=e.key)==key||(key!=null&&key.equals(k))))中断；p=e;}}//找到或创建一个key和hashCode等于插入元素的键值对，执行put操作if(e!=null){//key的已有映射//记录e的值VoldValue=e.值；/***onlyIfAbsent为false或者旧值为null时，允许替换旧值*否则不需要替换*/if(!onlyIfAbsent||oldValue==null)e.value=value;//访问后回调afterNodeAccess(e);//返回旧值return旧值；}}//更新结构化修改信息++modCount;//当键值对数量超过阈值时，重新哈希if(++size>threshold)resize();//回调afterNodeInsertion(evict);返回空值；}从上面的源码可以看出，当一个key-value对放入HashMap时，首先根据key的hashCode()返回值来确定Entry的存储位置。如果有两个哈希值相同的键，会判断两个元素键的equals()是否相同，如果相同则返回true，说明是重复的键值对，则HashSet中add()方法的返回值为false，说明HashSet添加元素失败。因此，如果在HashSet中加入已有的元素，新加入的集合元素不会覆盖已有的元素，从而保证元素不重复。如果不是重复元素，put方法最终会返回null，传给HashSet的add方法添加成功。综上所述，HashSet底层是通过HashMap实现的，可以实现重复元素的去重功能。如果存储自定义对象，则必须覆盖hashCode和equals方法。HashSet通过使用HashMap的put方法来保证元素不重复。存储前根据hashCode和equals判断key是否已经存在。如果存在，则不会重复插入，从而保证元素不重复。毫无意外，毫无理由，毫无愤怒地突然靠近。博主：80后程序员。爱好：阅读、写作和慢跑。公众号：Java面试真题解析
