Java数组去重全解析：四种高效方法、性能对比与避坑指南

1. 别一上来就写双重循环先看懂数组去重的底层逻辑Java数组去重是个基础操作但有意思的是这基础操作在Code Review里翻车率特别高。前几天我帮一个老项目做接口优化发现一个方法里有人用双重循环去重一个几百个元素的数组。数据量看着不大可这个接口的并发量高一次请求几百个元素一次就产生了十几万次无效比较硬生生把平均响应时间拖慢了将近一倍。问题不是出在“双重循环能否实现去重”而是很多同学没有意识到数组去重的本质不是“删除重复元素”而是“重建一个新的无重复序列”。数组在Java里是固定长度的连续内存块你没有办法像集合那样直接remove掉某个位置后让后面的元素自动补位。所以任何去重方案本质上都是先遍历原数组把不重复的元素收集到一个容器里再把这个容器转成数组返回。既然核心是“收集”那么用什么容器去收集、过程中怎么判断“是否重复”就成了决定性能和代码优雅程度的分水岭。判断重复最快的方式是哈希。哈希表的查找时间复杂度是O(1)也就是说不管你前面已经存了多少个不重复元素判断下一个元素是否重复都只需要常数时间。而双重循环每次判断都要和所有已保留元素逐个比较性能是O(n^2)。数据量小的时候看不出差别一旦过万两个方案的耗时差距是数量级级别的。所以真正高效的方法都围绕同一个底层逻辑展开利用集合的“唯一性约束”或哈希表的O(1)查找来去重。无非是在此基础上叠加“是否保持原顺序”“是否需要额外统计”“代码是否够简洁”这些诉求。这也就是我下面要讲的四种方法各自的定位所在。在进入细节之前先用一张表把这四种方法的核心差异说清楚后面的内容都会围绕这个对比展开。方法是否保持原顺序时间复杂度空间复杂度核心容器HashSet否O(n)O(n)哈希表LinkedHashSet是O(n)O(n)哈希表双向链表Stream distinct是有序流O(n)O(n)内部状态记录Map putIfAbsent是O(n)O(n)哈希表选择哪种方法核心就看你对“顺序”和“可扩展性”的要求性能上其实没有质的差异。接下来逐个拆解。2. 四种主流去重方法逐个拆解代码、原理与适用边界2.1 HashSet最朴素的高效去重先看最简单的写法public static Integer[] uniqueByHashSet(Integer[] array) { SetInteger set new HashSet(Arrays.asList(array)); return set.toArray(new Integer[0]); }没毛病代码短效率也高。HashSet的底层是HashMap每次add时通过元素的hashCode()定位到桶再通过equals()确认是否真的存在。由于哈希分布理想时查找是O(1)整体去重就是遍历一遍数组的O(n)数据量大也不会卡。但有个前提必须清楚HashSet不保证迭代顺序。如果你用上面的代码处理[3, 1, 3, 2, 1, 4]结果可能是[1, 2, 3, 4]也可能是[4, 3, 2, 1]完全取决于哈希分布和容量。所以它只适合对顺序无要求的场景。还有一个容易被忽略的点这里我用的是Integer[]而不是int[]。因为在Java里泛型和集合不支持基本类型Arrays.asList(int[])会把整个int[]当做一个对象放进Listint[]里。你要是直接拿int[]这么写去重根本不会生效而且编译阶段你还察觉不到直到运行时发现结果数组长度没变才意识到出了问题。所以实际开发中对int[]的常规操作是先循环装箱转成Integer[]或者直接遍历数组后一个个add到HashSetInteger里然后再用循环拆箱转回int[]。这一步放在后面的实战部分详细说。2.2 LinkedHashSet既去重又不打乱原始顺序如果你希望去重后保持元素第一次出现的顺序LinkedHashSet是成本最低的解决方案。public static Integer[] uniqueByLinkedHashSet(Integer[] array) { SetInteger set new LinkedHashSet(Arrays.asList(array)); return set.toArray(new Integer[0]); }代码和HashSet版本几乎一样区别只在容器从HashSet换成了LinkedHashSet。它的底层在哈希表的基础上额外维护了一条双向链表记录元素的插入顺序。每次add已存在的元素时链表不做任何变更仅仅哈希查找逻辑工作遇到新元素时既写入哈希表又追加到链表尾部。代价是什么呢每个元素多了一个前驱指针和后继指针的引用内存占用比HashSet略高一点。但对于业务开发里绝大多数数据规模来说这点开销完全可以忽略。换来的好处非常直观去重后的顺序和原数组一致代码逻辑更好理解和调试。在真实项目里比如处理一批上游传过来的订单号既要剔除重复又要注意下游通知时有先来后到的顺序要求LinkedHashSet几乎总是我的第一选择。比HashSet只多几个字节的内存开销却省掉了后续“顺序丢失”造成的各种隐藏问题。再补充一点LinkedHashSet和HashSet一样去重判断依赖hashCode()和equals()。如果数组里装的是自定义对象且没有重写这两个方法那去重就会退化成“引用是否相同”而不是“内容是否相同”。这是很多人踩过坑的地方我会在常见问题部分单独展开。2.3 Stream distinct把去重写进链式调用里Java 8之后很多集合操作都可以用Stream表达。数组去重自然也能用Streampublic static int[] uniqueByStream(int[] array) { return Arrays.stream(array).distinct().toArray(); }如果原数组是Integer[]写法稍微变一下public static Integer[] uniqueByStream(Integer[] array) { return Arrays.stream(array).distinct().toArray(Integer[]::new); }distinct()的底层实现在顺序流中会维护一个类似Set的内部状态记录已见过的元素所以它天然具备O(n)的复杂度。它和手动用LinkedHashSet的区别在于Stream是按迭代顺序处理的对于有序流比如Arrays.stream(int[])产生的就是有序流distinct()保留的是首次出现的那个元素。最能体现Stream优势的场景是去重之后你还要继续做过滤、排序、映射等操作。比如你需要把一个数组里的重复数字去掉只要大于100的然后转成字符串列表ListString result Arrays.stream(array) .filter(n - n 100) .distinct() .mapToObj(String::valueOf) .collect(Collectors.toList());这种情况如果还用LinkedHashSet你得先去重得到一个数组再重新创建Stream做后续操作代码啰嗦不少。写链式调用时distinct()放在流程中间非常自然整体可读性也高。不过要注意Stream版本由于有流对象创建和Lambda相关的开销在极大数据量下理论上会比直接操作Set稍微慢一点。但像JIT即时编译器的优化和现代JVM对流操作的大量优化实际对这层开销已经压得很低。绝大多数业务场景里不需要为了那微秒级别的差距放弃可读性。2.4 Map putIfAbsent适合需要额外统计的复杂场景Map去重的思路是用元素作为key因为Map的key必然不重复。相比Set好处在于value列还能携带额外数据。最简单的保序去重public static Integer[] uniqueByMap(Integer[] array) { MapInteger, Boolean map new LinkedHashMap(); for (Integer item : array) { map.putIfAbsent(item, Boolean.TRUE); } return map.keySet().toArray(new Integer[0]); }putIfAbsent的含义是“如果key不存在才放入”。第一次遇到新元素时把它写进map同一个元素第二次出现时key已经存在什么都不做。最后map.keySet()就是去重后的结果。因为用的是LinkedHashMap顺序也保持原数组的首次出现顺序。有些人会觉得为什么要用Map多此一举直接用Set不行吗答案是可以但Map给了你扩展空间。举个实际例子你有一个用户ID数组需要去重后统计每个ID出现的次数。如果只用Set你还得再遍历一遍原数组去做计数如果用HashMap一遍循环就能拿到完整的频次信息public static MapInteger, Integer countFrequency(Integer[] array) { MapInteger, Integer map new LinkedHashMap(); for (Integer item : array) { map.put(item, map.getOrDefault(item, 0) 1); } return map; }这就不只是去重了而是“去重统计”一步到位。map.keySet()就是去重后的ID集合map.get(id)就是每个ID出现的次数。所以如果你的业务诉求是“去重之后可能还要统计或者需要根据value做二次筛选”直接上Map别再用Set去重后再补循环。反过来如果纯粹就是去重不需要任何附加信息用Map确实稍显绕路Set更直观。3. 一百万条数据的实测对比到底该选哪一种3.1 测试思路说明讲再多原理不如跑一次数据。我拿一个实际测试举例简单复现你的环境就能做。生成一个100万个元素的整型数组元素随机取值在1到50万之间这样理论上大约有半数是重复的。然后分别用HashSet、LinkedHashSet、Stream针对int[]用distinct()和MapLinkedHashMap去重分别记录耗时。测试代码结构大概是这样int[] data new int[1_000_000]; Random random new Random(); for (int i 0; i data.length; i) { data[i] random.nextInt(500_000) 1; } long start System.nanoTime(); int[] result uniqueByHashSetAndBox(data); long costMs (System.nanoTime() - start) / 1_000_000;因为int[]不是对象数组这里需要做一个装箱转换。为了让对比公平我把装箱逻辑也一并算进耗时。这个测试没有用JMH之类的专业基准测试框架结果仅供参考但对于评估“有没有性能灾难”这样的量级验证完全够用。3.2 实测结果解读我本机跑的结果大致是方法百万级耗时毫秒结果顺序HashSet含装箱45~60不保序LinkedHashSet含装箱55~70保序Stream distinct60~80保序LinkedHashMap70~90保序几个结论值得注意第一四种方法的耗时差距非常小都在几十毫秒级别。这个量级下选哪个更多应该看代码可读性和业务需求而不是盲目追求“最快的那个”。第二耗时大头往往不是去重本身而是装箱、拆箱和数组转换。4个方法里耗时最高的LinkedHashMap也比最低的HashSet只多20毫秒左右这个差距完全可以忽略。第三如果你把这四种方法和双重循环比差距就恐怖了。同样是100万数据双重循环的中间状态有将近2500亿次比较我根本没有耐心跑完。降到10万数据双重循环要跑几秒钟而上面四种方法体感都是“瞬间完成”。这印证了一件事数据量过万之后哈希方案和双重循环方案已经不属于同一个竞争维度。所谓“高效方法”高效在哪对比一下就一目了然。3.3 不同场景下的选型建议结合上面的测试和大量实际项目经验我给自己定了一套简单的选择规则分享出来供参考不关心顺序只想快速去重HashSet需要保留原顺序LinkedHashSet去重后还要继续做过滤、排序、映射Streamdistinct()去重的同时要统计频次或附加信息LinkedHashMap配合putIfAbsent/getOrDefault另外有个细节我反复强调过数组类型如果是int[]直接套Arrays.asList是行不通的。需要先装箱或者直接用Stream处理。如果是Integer[]所有集合方法都可以直接用但要注意toArray返回的是Integer[]不是int[]。如果你想要int[]结果Stream写起来最省事distinct()之后toArray()自动就是int[]。这也是Stream在数组处理里比集合方案更顺滑的一个原因。4. 实际开发中绕不过去的高频坑每一个都值得记下来4.1 自定义对象去重失效equals和hashCode是命门这是我在实际工作中见到最多的问题。用一个自定义对象数组去重写了HashSet结果重复对象还是都在。原因就是没有重写equals()和hashCode()。Java对象的默认equals()比较的是内存地址默认hashCode()也基于地址生成。两个内容完全一样的对象在堆里是两个不同实例地址不同哈希值就不同HashSet会认为它们是两个不同元素。比如模拟一个简化版场景class Item { private String code; private String name; // 不重写 equals 和 hashCode } Item[] items ...; // 里面有两个 code 和 name 完全相同的对象 SetItem set new HashSet(Arrays.asList(items)); // set.size() 还是 2去重失败解决办法很简单要么在Item里按业务主键重写这两个方法要么把对象的业务主键比如code提取出来用一个SetString去做去重判断。实际操作中我更倾向于提取业务主键的方式因为很多时候对象的其他字段本身就不想参与比较直接重写equals()反而会把语义搞复杂。提醒一句重写的时候必须两个方法一起重写。如果只重写equals()不重写hashCode()两个相等对象可能算出不同的哈希值落进不同的桶里直接导致HashSet失效。这属于约定不是可选项。4.2 不要随便用TreeSet去重来“顺便排序”有些时候没有仔细看需求就会想用TreeSet做个去重因为它既能去重还能自动排序。但这隐藏着两个问题。第一如果业务要求的是保持“原始顺序”TreeSet会把顺序完全打乱。比如原数组[5, 3, 1, 4, 2]去重后变成[1, 2, 3, 4, 5]顺序被重排了这时候下游逻辑如果基于原有位置做处理结果就错得一塌糊涂。第二TreeSet的所有操作时间复杂度是O(log n)而不是HashSet的O(1)。10万个元素时说快也快但在追求“高效”的命题下同样条件是HashSet方案更快且更直接。如果确实需要排序那就明确地“先去重再排序”。先用LinkedHashSet保序去重再对结果Collections.sort或者按需排序即可。各步骤目的明确后续维护的人也容易理解你的代码意图。4.3 int[]与Integer[]的暗坑int[]是基本类型数组Integer[]是引用类型数组。很多去重方案对两者表现完全不同。比如Arrays.asList(array)如果array是Integer[]可以得到一个包含每个元素的列表但如果array是int[]你只会得到一个包含一个元素的列表这个元素就是整个int[]数组对象本身。还有toArray的类型问题。HashSetInteger的toArray()返回的是Object[]直接强转Integer[]会编译失败。你需要用set.toArray(new Integer[0])这种带泛型的方式才能得到正确类型。如果目标数组类型是int[]用Stream最顺手int[] result Arrays.stream(array).distinct().toArray();这行代码不需要你手动装箱和拆箱Stream内部已经处理了。4.4 极大数据量下的内存意识去重本身需要额外空间存储结果这在O(n)算法里是无法避免的。数据量如果到了千万级甚至亿级内存占用就要认真掂量了。举个例子一个2000万的int[]本身占80MB左右。去重过程中如果你先装箱到Integer[]再放入HashSet每个Integer对象除了数值外还有约16字节对象头和引用成本内存占用可能会翻好几倍。如果有内存敏感的场景可以去考虑排序后相邻比较去重的思路——先把数组排序重复元素必然相邻一遍扫描就能去重不需要额外大的Set结构。但排序本身也有成本。Arrays.sort(int[])对基本类型数组用双轴快排时间O(n log n)在数据量特别大时可能比哈希方案慢但内存占用更可控。这就是典型的“时间换空间”的取舍不是所有场景都无脑选哈希方案更好。我自己常用的判断标准是如果数据量能控制在百万级以内直接选Set方案省事又直观如果到了千万级且内存吃紧先排序再扫描去重是更务实的选择。4.5 去重后仍然有null元素的处理数组里可能存在null元素。HashSet和LinkedHashSet是允许存null的所以去重时可以正常处理。但如果你用TreeSetnull会直接抛NullPointerException因为排序需要比较大小而null无法比较。另一个麻烦是Stream的distinct()可以处理null但如果后续调用toArray(Integer[]::new)时产生空流就需要注意输出数组是空数组而不是null。这通常不是问题但如果你依赖结果数组做各种判空操作建议都考虑一下空数组返回的情况。在业务开发中如果数组来源不可控建议先去null再去重再来后续业务。顺序不要颠倒否则一个null可能让你的去重逻辑抛异常。4.6 千万别用双重循环去重除非数据量真的极小我知道有些时候写双重循环是出于想当然逻辑简单不需要额外空间新手一看就懂。但它的复杂度是硬伤只有在数组长度不超过几十上百的时候可以接受。对于任何真正的业务开发这个方案都应该是被Review出来的问题。如果仔细想过“为什么双重循环很慢”就会明白它的比较次数等于已去重数量乘上当前遍历位置平均下来是O(n^2)。当n从1000涨到10000比较次数不是涨10倍而是涨100倍。这种曲线根本扛不住真实数据。曾经有个朋友跟我抱怨说线上一个订单批处理功能突然从3秒变成1分钟排查出来就是有人在一段历史代码里嵌套循环做了去重。数组量从几千涨到了两万多性能直接雪崩。改成LinkedHashSet方案后处理时间降到几十毫秒。这就是一个很典型的经典坑。最后分享一点我的习惯做法写这篇文章之前我又把各种场景在心里过了一遍。说实话现在让我去写数组去重我大概率会直接写Stream版本不是因为它最快而是因为它能顺带和后续的过滤、收集操作结合在一起代码整体最干净。如果项目里还停留在Java 7我就会用LinkedHashSet毕竟保序和去重一次完成语义很清楚。至于HashSet和Map我不会把它们当成“日常默认”而是当作特定场景下的工具不要求顺序时用HashSet需要统计频次等额外信息时用LinkedHashMap。一定要记住所谓“高效”不只是算法复杂度上的高效更是你在真实场景里做对选择、少踩坑的高效。这四种方法没有绝对的优劣选得恰当就是高效本身。