Java中的HashSet如何实现判重

迈不过友情╰ 2023-10-05 13:11 1阅读 0赞

要理解HashSet如何判重，首先要知道HashSet的数据结构。HashSet其实是用Hash Map实现的，内部维护了一个Hash Map来存放数值。HashSet的元素放在了key中，value则是生成了一个空对象作为占位。由于HashMap的key是可以接收null值的，所以自然而然，HashSet也是可以接收null值的。

// HashSet内部维护了一个
       private transient HashMap<E,Object> map;
    
        // map中存储的虚拟值
        private static final Object PRESENT = new Object();
    
        /**
         * 创建一个新Set，其实是创建一个容量为16，负载因子为0.75的map
         */
        public HashSet() {
        
            map = new HashMap<>();
        }
        /**
        * 构造一个制定大小和负载因子的HashSet
        */
        public HashSet(int initialCapacity, float loadFactor) {
        
            map = new HashMap<>(initialCapacity, loadFactor);
        }
        
        /**
        * 创建迭代器方法
        * 其实就是创建map中keyset的迭代器
        */
        public Iterator<E> iterator() {
        
            return map.keySet().iterator();
        }

再来看hashset的一些常用操作  
基本上都是通过map来实现的。

/**
         * 查询Set中元素个数，其实就是返回map元素个数
         */
        public int size() {
        
            return map.size();
        }
    
        /**
         * 判断是否为空
         */
        public boolean isEmpty() {
        
            return map.isEmpty();
        }
    
        /**
         * 是否包含某个对象
         */
        public boolean contains(Object o) {
        
            return map.containsKey(o);
        }
    
        /**
         * 添加对象
         * 其实就是新增一个map元素，key为传进来的对象，value为虚拟值
         */
        public boolean add(E e) {
        
            return map.put(e, PRESENT)==null;
        }
    
        /**
         * 移除对象
         */
        public boolean remove(Object o) {
        
            return map.remove(o)==PRESENT;
        }
    
        /**
         * 清空set元素
         */
        public void clear() {
        
            map.clear();
        }

通过以上代码可以发现，其实操作的就是一个map。

Set集合有个很重要的特性就是不会存入重复元素，这个也很好理解，因为map中不能存放两个一样key值的元素。那怎么保证，或者说怎么判断元素是否重复呢？这就要涉及到hashmap的插入机制了。

#### HashMap如何插入元素 ####

hashmap在插入元素的时候，会先去计算key值的hashCode，然后通过HashCode&(n-1)（n为hashMap中table长度）来计算元素在table中的位置，如果table中的相应位置没有元素，则放入该位置，如果有元素，则要比较元素的key值是否和当前key值相同（equals方法）。如果相同，则覆盖。对于这块不理解的同学，可以去找找HashMap的响应文章来看看。

通过上面描述我们可以知道，hashMap判断元素是否覆盖，用到了hashCode和equals方法，于是，我们就能理解，为什么hashSet在重新定义判重逻辑的时候，需要重写HashCode和equals两个方法，重写其中任意一个，都不会起作用。

下面通过一个实例来说明。  
我们新建一个实例类，person，包含姓名和年龄两个字段。并用HashSet来存储。并且，定义只要名字相同，就认为两个元素是相同的，不管他们的年龄是否相同。以此，我们也可以验证一个问题，当HashSet中插入相同元素的时候，是覆盖，还是丢弃。（其实，只要知道HashSet内部是一个HashMap，我们也可以推断，是覆盖。然而是覆盖value值，所以key值不会变。但是不能单纯的理解为丢弃）

person类。

static class person{
        
        String name;
        int age;
    
        // 构造方法
        person(String name, int age){
        
            this.name = name;
            this.age = age;
        }
    
        @Override
        public int hashCode() {
        //重写hashCode()方法
            // 因为如果名字相同，就认为是相同元素
            // 所以这里只需要重写成，返回姓名字段hashCode即可
            // 如果是判断名字和年龄都相同的情况下，
            // 则需要对两个字段都求hash值，并返回
            return (name == null) ? 0 : name.hashCode();
        }
        @Override
        public boolean equals(Object obj) {
        
        	//重写 equals()方法
            if (obj == null)
                return false;
            if (this == obj)
                return true;
            if (getClass() != obj.getClass())
                return false;
            person other = (person) obj;
            // 只要name相同，就认为是同一个元素
            if (name == null) {
        
                if (other.name != null)
                    return false;
            }
            return name.equals(other.name);
        }
    
        // 重写toString方法
        public String toString(){
        
            return "hashCode:"+hashCode()+",name:" + this.name + ",age:" + this.age;
        }
    }

下面写一个方法来调用

public class HashSetTest {
        
    
        public static void main(String[] args) throws Exception{
        
    
            Set<person> hashset = new HashSet<>();
    
            // 加入null值，验证是否可以加入null值
            hashset.add(null);
            // 新建三个对象
            person p1 = new person("bob",21);
            person p2 = new person("bob",21);
            person p3 = new person("bob",22);
            person p4 = new person("jane",21);
            // 加入对象p1
            hashset.add(p1);
            // 再次对象p1，这个时候其实是同一个对象，
            // 就算不重写hashCode和equals方法，
            // 也可以判断为同一个严肃，不会添加多个
            hashset.add(p1);
            // 再次加入p2，这个时候其实是一个新的对象，虽然属性值相同
            // 所以在不重写HashCode和equals方法的时候，
            // 是会在Set中新增一个元素的
            hashset.add(p2);
            // 加入p3，姓名相同，年龄不同
            // 运行结果会发现，这个元素也没有加入
            // 并不是这个元素被抛弃了，而是hashMap在处理相同key值的时候
            // 将value值覆盖，而不覆盖key值，所以key中还是原来那个key，
            // 不会编程新的key
            hashset.add(p3);
            // 加入p4，姓名和年龄都不相同
            // 毋庸置疑，会新增元素
            hashset.add(p4);
            // 打印HashSet中的元素，查看结果
            hashset.forEach(System.out::println);
    
        }
    }

先看不重写hashCode和equals方法的运行结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center]  
可以看到，Bob插入了三次。

下面看重写了hashCode和equals方法后的运行结果  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 1]  
过滤掉了Bod的重复元素。

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center]: https://img-blog.csdnimg.cn/20201105225053222.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0,size_16,color_FFFFFF,t_70#pic_center
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0_size_16_color_FFFFFF_t_70_pic_center 1]: https://img-blog.csdnimg.cn/20201105225338134.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQyMzg5NzY0,size_16,color_FFFFFF,t_70#pic_center