如果给你10亿条id数据让你去重，你会怎么做？

如果给你10亿条id数据让你去重你会怎么做最近在刷一些其他题库的题发现遇到一些类似的问题甚至是相同的题还是会卡住我觉得我需要转变一下思路总结一下一类题的算法而不是每天写一道题的解题思路不然的话之前解题时卡在哪里后面遇到还是会卡在哪里。题目分析说到数组去重大家第一时间想到的就是Set 去重或者利用 Map 或 对象属性 key 的唯一性去重但是这道题10亿条数据如果存储为 Set 或者 Map 直接会内存溢出一些常规的遍历去重都会失效面对这样的大量数据去重如果数组本身是有序的我们可以用快慢指针去重如果是乱序的那我们需要用到位图法 (Bitmap)和布隆过滤器 (Bloom Filter)。ok接下来我们就来讲讲数组的去重吧。数组去重我们先来列举一下数组去重的通用方法Set 去重filter 去重利用 Map 或 对象属性 key 的唯一性去重快慢指针去重计数法/桶映射位图法 (Bitmap)布隆过滤器 (Bloom Filter)Set 去重原理这个应该目前最常用、最简洁的去重方法Set 是一种不允许重复值的数据结构。我们可以直接将原数组作为构造器的参数传递给 Set 再将 Set 转回成数组就能完成去重时间复杂度O(n)空间复杂度O(n)functionremoveDuplicates(arr){return[...newSet(arr)];}filter 去重原理利用indexOf总是返回元素第一次出现索引的特性。时间复杂度O(n2)空间复杂度O(1)functionremoveDuplicates(arr){returnarr.filter((item,index)arr.indexOf(item)index);}利用 Map 或 对象属性 key 的唯一性去重原理利用 Map 或 对象属性 key 的唯一性遍历数组将数组元素作为 key 添加到 Map 或者 对象中遇到重复 key 值可以不操作也可以做计数操作。这种方法其实跟 Set 去重原理相似但是直接传递数组给 Set 它内部一次性迭代整个可迭代对象引擎可以做优化这样性能更高但是自己遍历的话可以在循环中自己添加一些其他的逻辑这样更灵活。functionremoveDuplicates(arr){constmapnewMap();arr.forEach(item{if(!map.has(item)){map.set(item,1);}else{map.set(item,map.get(item)1);// 如果需要统计重复次数可以在这里更新计数}});returnArray.from(map.keys());}排序去重 快慢指针去重原理先对数组进行排序如快排或归并排序然后通过快慢指针Double Pointers遍历。如果arr[i] ! arr[i-1]则它是唯一的。如果不想开辟额外的空间或者数组本身是有序的就可以采用这种方法所以如果这10亿的数据本身是有序的那这种方法就是最优解。如果是乱序的数组我们需要加上排序本身的时间复杂但是如果你一些情况下它依旧是最稳妥的方法。时间复杂度O (n log n)空间复杂度O (1)原地修改functionremoveDuplicates(arr){if(arr.length0)return[];arr.sort();// 先排序for(leti1;iarr.length;i){if(arr[i]arr[i-1]){arr.splice(i,1);i--;// 删除后需要调整索引}}}计数法/桶映射原理创建一个长度覆盖数据范围的数组桶值出现时在对应下标处计数。这种方法适用于整数类型的数组因为数组的下标必须要是 0的整数面对其他类型的数组我们也可以使用统一的方法映射成数字但是如果数值范围过大就不适用了。时间复杂度O(n k) k 是数据的取值范围 空间复杂度O (n)// 假设元素范围 1 - 10000functionremoveDuplicates(arr){constcountnewArray(10001).fill(false);// 创建一个布尔数组来记录出现过的元素constresult[];for(leti0;iarr.length;i){if(arr[i]1arr[i]10000){// 确保元素在范围内count[arr[i]]true;// 标记出现过的元素}}for(leti1;i10000;i){if(count[i]){result.push(i);}}returnresult;}位图法 (Bitmap)这其实是针对计数法空间上的优化我们既然能够将其他类型的元素映射成数字那么我们也可以将数字映射成更小的值。原理使用每一“位”Bit来表示一个数字是否存在。时间复杂度O(n)空间复杂度O(k / 8) k 是数据的取值范围如果 10 亿数据是连续或范围可控的正整数例如用户 ID、手机号位图是唯一能实现 “既精确又省空间” 的方法。JavaScript 原生是没有位图数据结构的我们需要自己写一个classBitmap{constructor(size){this.sizesize;this.bitmapnewUint8Array(Math.ceil(size/8));// 使用 Uint8Array 来存储位图}setBit(index){constbyteIndexMath.floor(index/8);constbitIndexindex%8;this.bitmap[byteIndex]|(1bitIndex);// 设置对应位}getBit(index){constbyteIndexMath.floor(index/8);constbitIndexindex%8;return(this.bitmap[byteIndex](1bitIndex))!0;// 检查对应位是否被设置}}functionremoveDuplicates(arr){constbitmapnewBitmap(10000);constresult[];for(leti0;iarr.length;i){if(arr[i]1arr[i]10000){// 确保元素在范围内if(!bitmap.getBit(arr[i])){// 如果位图中没有设置该元素bitmap.setBit(arr[i]);// 设置该元素的位result.push(arr[i]);// 将该元素添加到结果数组中}}}returnresult;}布隆过滤器 (Bloom Filter)原理将元素通过多个哈希函数映射到位图的多个位置。如果所有位置都为1说明该元素“可能”已存在。时间复杂度O(n)空间复杂度O(m) m 比特数组的长度如果要追求极致速度且不在乎一点误差就可以选用这种方法。classBloomFilter{constructor(size1024,hashCount3){this.sizesize;// 位数组的大小bitthis.hashCounthashCount;// 哈希函数的数量// 使用 Uint8Array每个元素占 8 位所以长度除以 8this.bitArraynewUint8Array(Math.ceil(size/8));}// 添加元素add(item){consthashesthis._getHashes(item);hashes.forEach(hash{constbitPoshash%this.size;constarrayIdxMath.floor(bitPos/8);constbitIdxbitPos%8;// 将对应位置为 1this.bitArray[arrayIdx]|(1bitIdx);});}// 查询元素是否存在has(item){consthashesthis._getHashes(item);returnhashes.every(hash{constbitPoshash%this.size;constarrayIdxMath.floor(bitPos/8);constbitIdxbitPos%8;// 检查对应位是否为 1return(this.bitArray[arrayIdx](1bitIdx))!0;});}// 简单的哈希生成逻辑实际生产建议用 MurmurHash 等_getHashes(item){consthashes[];conststrString(item);for(leti0;ithis.hashCount;i){// 模拟不同的哈希函数通过给字符串加盐并进行简单的位运算lethash0;constsaltedStrstri;for(letj0;jsaltedStr.length;j){hash(hash5)-hashsaltedStr.charCodeAt(j);hash|0;// 强制转为 32 位整数}hashes.push(Math.abs(hash));}returnhashes;}}functionremoveDuplicates(arr){constbloomFilternewBloomFilter(1024,3);// 创建一个布隆过滤器constresult[];for(leti0;iarr.length;i){if(!bloomFilter.has(arr[i])){// 如果布隆过滤器中没有该元素bloomFilter.add(arr[i]);// 将该元素添加到布隆过滤器中result.push(arr[i]);// 将该元素添加到结果数组中}}returnresult;}这个方法空间性能平衡极佳但是会有极低概率的误判可能会把一个没见过的元素误判为见过详细原理:布隆过滤器结构一个 bit 数组 k 个哈希函数插入元素 x对 x 做 k 次哈希得到 k 个位置把这 k 个 bit 都置为 1查询元素 y同样算 k 个哈希位置如果所有位置都是 1→ 判定 y 存在只要有一个是 0 → 判定 y 不存在误判场景:元素y 实际不存在但之前插入的其他元素刚好把 y 对应的 k 个 bit 位全都覆盖成 1 了布隆过滤器只能看到 bit 是 1不知道是谁置的于是误判 y 存在布隆过滤器的性能取决于哈希函数的质量和数量哈希函数数量太少误报率高冲突多哈希函数数量太多位数组迅速填满性能下降。所以选择size和hashCount就很重要了需要根据预期的数据量 ( n )和可接受的误报率( p )来计算注意的 JS 是单线程的计算大量哈希值会阻塞事件循环。在大规模场景下通常将此逻辑放在Worker中。哈希分片最后提一嘴哈希分片哈希分片Hash Sharding并不属于一种独立的 “去重算法” 而是一种处理大规模数据的“分治策略”Divide and Conquer。如果把普通的去重比作 “在碗里挑出重复的豆子” 哈希分片就是“因为豆子太多一碗装不下所以先把豆子分装到不同的碗里并保证相同的豆子一定在同一个碗里”。如果内存不够用就可以将数据进行分片再在各个片段中执行去重操作就 ok 了。