经验首页 前端设计 程序设计 Java相关 移动开发 数据库/运维 软件/图像 大数据/云计算 其他经验
当前位置:技术经验 » Java相关 » Java » 查看文章
小测试:HashSet可以插入重复的元素吗?
来源:cnblogs  作者:阿牛20  时间:2023/11/6 9:11:51  对本文有异议

  Set的定义是一群不重复的元素的集合容器。也就是说,只要使用Set组件,应该是要保证相同的数据只能写入一份,要么报错,要么忽略。当然一般是直接忽略。

  如题,HashSet是Set的一种实现,自然也符合其基本的定义。它的自然表现是,一直往里面插入数据,然后最后可以得到全部不重复的数据集合,即直到天然去重的效果。

 

1. 简单使用如下

  先插入几个元素,得到的结果是没有重复的结果数量。

    @Test
    public void testSetAdd() {
        Set<String> data = new HashSet<>();
        data.add("a");
        data.add("b");
        data.add("a");
        Assert.assertEquals("数量不正确", 2, data.size());
    }

  简单说下HashSet的实现原理,它是基于HashMap实现的一种set容器,直白说就是HashSet内部维护了一个HashMap的实例,插入和删除时委托给HashMap去实现,而HashMap中的Key就是HashSet中的值,HashMap的value就是一个常量Object.

    // Dummy value to associate with an Object in the backing Map
    private static final Object PRESENT = new Object();

    /**
     * Constructs a new, empty set; the backing <tt>HashMap</tt> instance has
     * default initial capacity (16) and load factor (0.75).
     */
    public HashSet() {
        map = new HashMap<>();
    }

    /**
     * Adds the specified element to this set if it is not already present.
     * More formally, adds the specified element <tt>e</tt> to this set if
     * this set contains no element <tt>e2</tt> such that
     * <tt>(e==null&nbsp;?&nbsp;e2==null&nbsp;:&nbsp;e.equals(e2))</tt>.
     * If this set already contains the element, the call leaves the set
     * unchanged and returns <tt>false</tt>.
     *
     * @param e element to be added to this set
     * @return <tt>true</tt> if this set did not already contain the specified
     * element
     */
    public boolean add(E e) {
        return map.put(e, PRESENT)==null;
    }

  还是比较清晰的。

 

2. HashSet保证元素不重复的原理

  上节讲了HashSet是基于HashMap实现的,只不过它忽略了HashMap中的value信息。那么它怎么样保证不重复呢,自然也是依赖于HashMap了,HashMap中要保证key不重复有两个点:一是hashCode()要返回相同的值;二是equals()要返回true;换句话说就是要我们绝对认为该对象就是同一个时,才会替换原来的值。即要重写 hashCode()和equals()方法。样例如下:

class TableFieldDesc {

    private String fieldName;

    private String alias;

    public TableFieldDesc(String fieldName, String alias) {
        this.fieldName = fieldName;
        this.alias = alias;
    }

    @Override
    public int hashCode() {
        return Objects.hash(fieldName, alias);
    }
    
    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TableFieldDesc that = (TableFieldDesc) o;
        return Objects.equals(fieldName, that.fieldName) &&
                Objects.equals(alias, that.alias);
    }

}

  这样一来的话, new TableFieldDesc("f_a", "a") 与 new TableFieldDesc("f_a", "a") 就可以相等了,也就是说,如果有两个这样的元素插入,只会被当作同一个来处理了,从而达到去重的效果。测试如下:

    @Test
    public void testSetAdd2() {
        Set<TableFieldDesc> data = new HashSet<>();
        data.add(new TableFieldDesc("f_a", "a"));
        data.add(new TableFieldDesc("f_a", "a"));
        Assert.assertEquals("数量不正确", 1, data.size());
    }

 

3. HashSet真能够保证不插入重复元素吗?

  如题,hashSet真的能够保证不插入重复元素吗?我们常规理解好像是的,但是实际上还是有点问题。一般地,我们要求HashMap的key是不可变的,为什么会有这种要求呢?因为简单啊。但是,实际场景需要,也允许可变,就是要做到上节说的hashCode与equals重写。看起来一切都很美好,但是真的就没问题了吗?其实是有的。如下:

    @Test
    public void testSetAdd3() {
        Set<TableFieldDesc> data = new HashSet<>();
        TableFieldDesc fa = new TableFieldDesc("f_a", "a");
        data.add(fa);
        // 将f_a 改成了f_b,即 new TableFieldDesc("f_b", "a");
        fa.setFieldName("f_b");

        TableFieldDesc fb = new TableFieldDesc("f_b", "a");
        data.add(fb);
        System.out.println("data:" + data);
        // 此处就插入了重复的元素了
        Assert.assertEquals("数量不正确", 2, data.size());
    }

  如上就是,插入了两个重复的元素了,打印信息为:

data:[TableFieldDesc{fieldName='f_b', alias='a'}, TableFieldDesc{fieldName='f_b', alias='a'}]

  完整的TableFieldDesc描述如下:

class TableFieldDesc {

    private String fieldName;

    private String alias;

    public TableFieldDesc(String fieldName, String alias) {
        this.fieldName = fieldName;
        this.alias = alias;
    }

    public void setFieldName(String fieldName) {
        this.fieldName = fieldName;
    }

    public void setAlias(String alias) {
        this.alias = alias;
    }

    @Override
    public int hashCode() {
        return Objects.hash(fieldName, alias);
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        TableFieldDesc that = (TableFieldDesc) o;
        return Objects.equals(fieldName, that.fieldName) &&
                Objects.equals(alias, that.alias);
    }

    @Override
    public String toString() {
        return "TableFieldDesc{" +
                "fieldName='" + fieldName + '\'' +
                ", alias='" + alias + '\'' +
                '}';
    }
}
View Code

  为什么会这样呢?就像测试用例中写的,先插入了一个元素,然后再改变里面的某个值,随后再插入一个改变过之后的值,就重复了。因为hashCode是在插入的时候计算的,而当后续用户改变key的数据值,导致hashCode变更,这时就存在,在对应的slot上,不存在对应元素的情况,所以下次再插入另一个相同元素时,就被认为元素不存在从而插入重复数据了。

  更严重的,当元素数据达到一定的时候,会存在扩容,会重复迁移所有元素,可能还会存在hash重新计算从而将重复的元素变为不重复的情况,就更玄乎了。(不过幸好,HashMap中的扩容不会重新计算hash,它会保留原来的hash,所以重复的元素永远会重复。)

  结语警示:如果想用Set容器去做去重的工作,需要仔细了解其实现原理,而非想当然的认为会去重。能做到不改变key值就尽量避开,甚至不暴露修改数据的方法,即做到对象不可变的效果。从而避免踩坑。

原文链接:https://www.cnblogs.com/yougewe/p/17810541.html

 友情链接:直通硅谷  点职佳