Set<List<Integer>>内部工作原理解析：为何仅同序列表判定为重复

问题背景 #

以下是测试用的Java代码：

public static void main(String[] args) {
        Set<List<Integer>> s = new HashSet<>();
        List<Integer> l1 = new ArrayList<>(List.of(1,2,3));
        List<Integer> l2 = new ArrayList<>(List.of(1,2,3));
        List<Integer> l3 = new ArrayList<>(List.of(3,2,1));
        s.add(l1);
        if(s.contains(l2)) {
            System.out.println("l2 is already present");
        }
        if(s.contains(l3)) {
            System.out.println("l3 is present");
        } else {
            System.out.println("l3 is absent");
        }
}

程序运行输出：

l2 is already present
l3 is absent

基于Java的equals、hashCode及Object基础概念，需要解释两个核心问题：

1. Set内部如何比较整数列表判断其是否已存在？
2. 为何仅当列表元素顺序相同时才会被识别为重复？

一、Set（HashSet）判断元素存在的逻辑 #

HashSet的核心判断逻辑完全依赖元素的**hashCode()和equals()**方法，流程如下：

1. 当调用add()或contains()方法时，首先计算待判断元素的hashCode()值，以此确定它在哈希表中的对应桶位置。
2. 检查该桶的内容：
   • 如果桶为空，直接判定元素不存在；
   • 如果桶内已有元素，则逐个调用元素的equals()方法与待判断元素对比，只要有一个对比返回true，就认为元素已存在。

简单说：先靠hashCode快速定位，再用equals精准匹配。

二、顺序不同的列表不被视为重复的原因 #

这本质是ArrayList自身的equals()和hashCode()实现逻辑决定的：

1. equals()方法的规则：
   ArrayList的equals会先比较两个列表的长度，长度不同直接返回false；长度相同时，会按索引顺序逐个比较对应位置的元素，只要有一个位置的元素不相等（调用元素自身的equals），就返回false。
   所以[1,2,3]和[3,2,1]在索引0、2位置的元素完全不同，equals对比结果为false。

2. hashCode()方法的规则：
   ArrayList的hashCode计算是顺序敏感的，大致公式为：hashCode = 31 * 之前的hashCode + 当前元素的hashCode()。元素顺序改变后，最终计算出的hashCode值几乎必然不同。
   对于HashSet来说，hashCode不同意味着元素会被分配到不同的桶里，连进入equals对比的环节都没有，直接被判定为不同元素。

内容的提问来源于stack exchange，提问作者curiousengineer