Java中HashSet存储List时是否会出现重复元素？附Python中不可hash问题

Java中HashSet存储List时是否会出现重复元素？

问题起因

今天遇到了py中的不可hash问题。对比了java中，Set嵌套List的场景，产生了如下问题：

有一个HashSet，有一个List，HashSet对这个List add两次，第一次add 时List中有3个元素，第二次add时List中有10个元素， 问：最终HashSet中有几个List元素？

答案

有两个元素，但是两个元素都是同一个List对象，也就是说原本不可能存储重复元素的Set，出现了重复元素

分析

HashSet原理

​ 大伙都知道，HashSet 本质就是 HashMap， ​ HashMap的key是不想同的，这个具体是否相同，首先根据key的 hashCode方法得到hash值， ​ 再根据某个算法计算出这个key对应的数组下标（简略一点的说法）， ​ 如果此处已经有值，判断两者hashCode是否相同，若相同则覆盖，若不相同则继续计算equals看是否相等， ​ 若equals也相等则覆盖，若不相等则存储（存链表上或红黑树上）。

重复元素出现的过程

问题关键就在于hashCode方法和equals方法的结果上。

• 第一次存储时list中元素3个，假设hashCode值为 2005，HashMap中找了下，该hashCode对应的位置无值，直接存储

• 第二次存储时，list中元素变成10个，hashCode值变为168588。此时存入HashMap，发现该hashCode对应的位置也是无值，于是又直接存储。

站在我们的视角来看，两个list分明是同一个对象，但是由于存储时的hashCode值不一致，导致了Set认为两个对象不一致。 所以Set存储List时，其实是有可能存储重复元素的。

在代码中验证

    @Test
    public void test() throws Exception {
        HashSet<List<String>> listHashSet = new HashSet<>();
        List<String> a1 = new ArrayList<>();
        a1.add("shs");
        a1.add("bb");
        a1.add("cc");

        //计算此时a1的hash值
        System.out.println(a1.hashCode());
        listHashSet.add(a1);


        //加入元素再计算a1的hash值
        a1.add("zhanfasn");
        System.out.println(a1.hashCode());
        listHashSet.add(a1);


        //取出Set中的两个List，看看他们是否相同
        List<String> a = null;
        List<String> b = null;
        for (List<String> item : listHashSet) {
            System.out.println(item);
            if (a!=null){
                b = item;
            }else {
                a = item;
            }
        }
        System.out.println(a.equals(b));

        //操作a看b是否被改变
        a.add("zhoaliu");
        System.out.println(a);
        System.out.println(b);

    }

Python中list、dict、set 不可hash

这就是为什么Python 中set 不能存储list，并且报unhashxxx 错误。

因为py中认为一个对象在整个生命周期中hash值都不能改变的对象，才是可hash的。

而dict、list、set的hash值，会随着存储元素的增减而变化，所以它的hash值在整个生命周期中是可能变化的。一旦出现变化，那么此时set嵌套list就会像java一样，存下重复元素。可能py作者考虑到这点，就直接禁止了set中存储list。

如果非要存，那就只能把list中元素取出，塞入到set中。