處理 JS 數(shù)組去重幾乎是每個前端和 Node 開發(fā)都繞不開的事。平時數(shù)據(jù)量小怎么寫都不卡可一旦數(shù)據(jù)量拉到百萬級不同去重方式之間的差距會從“都能用”變成“一個幾十毫秒、一個卡死頁面”。我之前在優(yōu)化一個數(shù)據(jù)清洗腳本時就因為順手用了filter indexOf去重 100 萬行數(shù)據(jù)跑了將近十分鐘一度以為程序死循環(huán)了。后來換成 Set幾十毫秒出結(jié)果。這個反差讓我徹底明白js 去重方式不是隨手挑一個就行在百萬級數(shù)據(jù)量級下選錯方式是真的會出事。這篇內(nèi)容主要講兩件事一是各種主流 js 去重方式的底層原理和時間復雜度二是我在百萬級數(shù)據(jù)下實際跑出來的結(jié)果以及不同場景下到底該怎么選。無論你是剛接觸前端不久還是在搞埋點日志、數(shù)據(jù)清洗這份對比和踩坑記錄都值得收藏。1. 去重方式的底層差異為什么 Set 能把百萬級數(shù)據(jù)按在地上摩擦1.1 先說結(jié)論查重思路決定時間復雜度常見的去重方式有 Set、Map、filter indexOf、對象鍵值法、排序去重、雙重循環(huán)。表面上看都是“把重復元素干掉”但它們判斷重復的方式完全不同性能差距也由此而來。Set 和 Map 底層都是哈希表結(jié)構(gòu)。插入一個元素時能平均在 O(1) 時間內(nèi)完成“這個值我之前有沒有見過”的判斷。循環(huán) n 個元素總時間復雜度就是 O(n)。filter indexOf 則完全不同每次 indexOf 都要從數(shù)組頭開始掃描判斷一個元素需要遍歷一遍已有數(shù)組內(nèi)層循環(huán)套外層循環(huán)整體就是 O(n2)。百萬級數(shù)據(jù)下n 1,000,000O(n2) 意味著大約 10^12 次操作而 O(n) 只有一百萬次理論差距就是百萬倍。即便哈希表有常數(shù)開銷這個數(shù)量級差距也已經(jīng)決定勝負了。1.2 百萬級數(shù)據(jù)量到底放大了什么100 萬條數(shù)據(jù)對瀏覽器來說已經(jīng)不是小數(shù)目。一個純數(shù)字的數(shù)組按 Number 類型每個 8 字節(jié)算大約占用 8MB 左右如果存的是字符串或者對象內(nèi)存占用會成倍上漲。這個時候如果去重方法還要創(chuàng)建大量中間數(shù)組、反復深拷貝或者出現(xiàn)嵌套循環(huán)內(nèi)存和 GC 壓力會跟著爆炸不是光慢那么簡單有可能直接把標簽頁搞崩。我用一個生活化類比indexOf 去重就像是新來一個人要挨個問前面所有人“你們見過這個人嗎”每來一個都問一遍人越多詢問次數(shù)膨脹得越離譜。而 Set 是給每個值一個獨立柜子看到新名字先打開對應柜子看看有沒有人有就跳過沒有就登記。柜子查找是常數(shù)時間即便 100 萬人也只需要 100 萬次開柜子。差距就是這么來的。1.3 核心衡量指標時間復雜度、內(nèi)存、可讀性選去重方式不能只看速度還要兼顧內(nèi)存和可讀性。時間復雜度在百萬級數(shù)據(jù)下基本決定一切Set、Map 這類哈希方案統(tǒng)治級領(lǐng)先。內(nèi)存方面Set/Map 本身要有額外哈希表開銷但相比 O(n2) 方案不斷創(chuàng)建臨時數(shù)組和頻繁調(diào)用棧通常還是更劃算?？勺x性上Set 一行代碼最直觀Map 做對象數(shù)組按字段去重時邏輯也很清晰。我一般按這個順序權(quán)衡先看會不會修改原數(shù)組再看時間復雜度和內(nèi)存最后考慮代碼給別人看的時候要不要解釋半天。百萬級數(shù)據(jù)場景下時間和內(nèi)存優(yōu)先級最高代碼稍微繞一點加注釋就行但性能不行就真的不行。2. 百萬級數(shù)據(jù)實測搭一個能復現(xiàn)的基準測試2.1 測試環(huán)境與數(shù)據(jù)準備先說測試環(huán)境Node.js 18.16.0M1 MacBook Pro16G 內(nèi)存。瀏覽器端結(jié)論類似但不同 JS 引擎對 Set 的優(yōu)化有差異數(shù)字不會完全一致。想復現(xiàn)的話把代碼粘到 Node 環(huán)境直接跑就行。數(shù)據(jù)準備很關(guān)鍵。不能用固定順序的數(shù)組如果數(shù)據(jù)恰好有序排序去重會占大便宜。為了模擬真實混排數(shù)據(jù)我用隨機數(shù)生成 100 萬條數(shù)組取值范圍 0 到 499999這樣重復率不會太低也不會全部重復。生成代碼很簡單const arr Array.from({ length: 1000000 }, () Math.floor(Math.random() * 500000));這行代碼會在內(nèi)存里生成約 100 萬個隨機數(shù)。取值范圍 50 萬理論上隨機生成 100 萬個位置去重后大約 43 萬左右重復率約 57%。真實業(yè)務(wù)里的臟數(shù)據(jù)通常就是這個量級有重復但不至于全是重復。2.2 測試代碼與運行方式因為 Set 這類方案耗時可能只有幾十毫秒而 filter indexOf 直接跑 100 萬可能等到天荒地老所以我把所有方案放在同一份腳本里用 performance.now 計時多跑幾次取中位數(shù)避免單次抖動。每個方案都傳入同一個 arr但方法內(nèi)部自己拷貝需要處理的數(shù)據(jù)避免前面方法改了原數(shù)組影響后面的結(jié)果。const { performance } require(perf_hooks); function test(name, fn, data) { const start performance.now(); const result fn(data); const end performance.now(); console.log(name, (end - start).toFixed(2) ms, 去重后長度:, result.length); } // filterindexOf 在 100 萬數(shù)據(jù)下太慢單獨準備一個 5 萬子集 const smallArr arr.slice(0, 50000); test(Set去重, (data) [...new Set(data)], arr); test(Map去重, (data) [...new Map(data.map((item) [item, item])).keys()], arr); test(對象鍵值去重, (data) { const obj {}; return data.filter((item) { if (obj[item]) return false; obj[item] true; return true; }); }, arr); test(排序相鄰去重, (data) { const sorted [...data].sort((a, b) a - b); return sorted.filter((item, i) i 0 || item ! sorted[i - 1]); }, arr); test(filterindexOf, (data) data.filter((item, index) data.indexOf(item) index), smallArr);我在測試時特意把 filter indexOf 單獨放到 5 萬條數(shù)據(jù)上不直接跑 100 萬因為 100 萬條下它可能要等好幾分鐘腳本看起來就像卡死了。這也是踩坑之后學到的教訓基準測試也要先評估被測試方法能不能扛住測試規(guī)模不能拍腦袋直接全部跑 100 萬。2.3 從數(shù)據(jù)上理解為什么差了幾個數(shù)量級我這邊跑出來的結(jié)果大致如下具體數(shù)字和運行環(huán)境有關(guān)但數(shù)量級差距不會變?nèi)ブ胤绞綌?shù)據(jù)量耗時去重結(jié)果長度Set100 萬約 25~35ms約 43 萬Map100 萬約 35~45ms約 43 萬對象鍵值100 萬約 50~70ms約 43 萬排序相鄰100 萬約 120~180ms約 43 萬filterindexOf5 萬約 1500~2000ms約 4.8 萬注意表格里的 filter indexOf 只跑了 5 萬條數(shù)據(jù)。它的復雜度是 O(n2)數(shù)據(jù)量從 5 萬漲到 100 萬變成了 20 倍耗時理論上要變成 400 倍。按 1.5 秒估算到 100 萬就是 600 秒約 10 分鐘。這個數(shù)量級基本是災難不是優(yōu)化能救回來的。3. 五種主流去重方式逐個拆解與結(jié)果對比3.1 Set 去重一行代碼為什么最快Set 去重是現(xiàn)在最常用的寫法核心就是利用 Set 存唯一值的特性const unique [...new Set(arr)]; // 或者 Array.from(new Set(arr))Set 底層使用哈希表插入時計算哈希值定位到桶沖突概率小的話平均 O(1) 完成插入。整個過程只需要一次循環(huán)不需要額外的 indexOf 掃描內(nèi)存多出一份 Set 結(jié)構(gòu)的大小。字符串、數(shù)字、布爾值這些原始類型都可以直接存NaN 也能正確去重這是它相比 indexOf 方案的一個隱藏優(yōu)勢。我實際測下來100 萬數(shù)據(jù) Set 去重基本都在幾十毫秒內(nèi)代碼只有一行幾乎沒有比它更好的性價比。唯一的硬傷是對引用類型Set 比較的是引用地址而不是結(jié)構(gòu)。兩個內(nèi)容完全一樣的對象只要不是同一個引用Set 就不會去重。這個后面講對象數(shù)組去重時會單獨說。3.2 filter indexOf典型 O(n2) 反面教材代碼非常好讀const unique arr.filter((item, index) arr.indexOf(item) index);意思就是只有當某個元素在數(shù)組里第一次出現(xiàn)的位置就是當前位置時才保留它。問題在于indexOf 每次都要從數(shù)組頭部開始遍歷查找filter 本身也要整體遍歷一遍很多元素會被反復掃描。數(shù)據(jù)量小的時候沒感覺到百萬級就是災難。我這邊測 5 萬條數(shù)據(jù)已經(jīng)要 1.5 秒以上如果強行跑 100 萬10 分鐘是保守估計。這還沒算 filter 會創(chuàng)建新數(shù)組indexOf 在查找時不斷訪問原數(shù)組帶來大量內(nèi)存和 CPU 緩存開銷。真實瀏覽器環(huán)境里這段代碼會讓頁面長時間無響應體驗極差。如果業(yè)務(wù)上真的繞不開這個寫法最多也就處理幾百到幾千條數(shù)據(jù)。超過這個量級老老實實用 Set 或 Map。不要覺得 filter indexOf 簡潔就無腦用簡潔在這一場景里是陷阱。3.3 對象/Map 鍵值法和 Set 很像但陷阱不少對象鍵值法的常見寫法有兩種一種是對象當哈希表一種是 Map。先說對象const obj {}; const unique arr.filter((item) { if (obj[item]) return false; obj[item] true; return true; });這個方案看起來也是 O(n)但有幾個坑。第一對象的鍵名只能是字符串或 Symbol數(shù)字會被轉(zhuǎn)成字符串于是 1 和 1 會被當成同一個鍵。第二如果數(shù)據(jù)里有 proto、constructor 這類特殊字符串直接 obj[item] 可能造成原型鏈污染甚至誤判。第三對象普通屬性的讀寫比 Map 要慢一些。所以我用對象做百萬級測試時耗時通常是 Set 的兩倍左右。用 Map 會更穩(wěn)const map new Map(); arr.forEach((item) { if (!map.has(item)) map.set(item, true); }); const unique [...map.keys()];Map 的鍵可以是任意類型讀寫性能和 Set 接近而且不會把數(shù)字強轉(zhuǎn)字符串。如果只做去重Set 其實更合適如果后續(xù)還要保留每個鍵對應的某個值那 Map 是首選。百萬級數(shù)據(jù)下 Map 去重通常比 Set 慢 10~20ms差距不大可以接受。3.4 排序 相鄰比較時間不差但要注意副作用思路是先排序再遍歷一次只保留和上一個元素不同的值const sorted [...arr].sort((a, b) a - b); const unique sorted.filter((item, i) i 0 || item ! sorted[i - 1]);排序時間復雜度 O(n log n)比 O(n) 差一點但比 O(n2) 好很多。實測 100 萬數(shù)據(jù)大概 120~180ms某些場景下依然可用。但有兩個坑一是 sort 會改變元素順序如果你希望保留第一次出現(xiàn)的順序排序去重直接不滿足二是比較函數(shù)如果寫不好對有 NaN 的數(shù)組會得到很奇怪的結(jié)果。代碼里我用的是數(shù)字比較函數(shù)如果數(shù)組里有字符串需要換成 localeCompare 之類的比較器。還有sort 方法會修改原數(shù)組所以我先做了淺拷貝 [...arr]這也會增加一份內(nèi)存。如果原數(shù)組順序無所謂排序去重是個折中方案但能 Set 還是首選 Set因為 Set 代碼更短、更快。3.5 雙重循環(huán) / 標記法只適合小數(shù)組或特殊去重有些人不用 Set是因為業(yè)務(wù)場景要求按對象的某個字段去重或者要保持原順序。這時候可能會寫雙重循環(huán)const unique []; for (let i 0; i arr.length; i) { let isDuplicate false; for (let j 0; j unique.length; j) { if (unique[j] arr[i]) { isDuplicate true; break; } } if (!isDuplicate) unique.push(arr[i]); }這本質(zhì)上也是 O(n2)而且比 filter indexOf 還多一個數(shù)組 push百萬級數(shù)據(jù)下絕對不能碰。它唯一的優(yōu)勢是可以在比較時寫復雜邏輯比如比較對象多個字段。但更好的做法是用 Map 把查找重復的復雜度降到 O(1)循環(huán)本身保持 O(n)。對于 Canvas 里面實時處理上萬個點雙重循環(huán)勉強能用但超過 10 萬就要考慮換方案了。4. 不同業(yè)務(wù)場景下的最佳去重方案4.1 純原始值數(shù)組無腦用 Set如果數(shù)組元素是數(shù)字、字符串、布爾值這類原始值不需要額外保留每個值對應的其他信息Set 就是最優(yōu)解。代碼最簡單速度最快也不容易出錯。唯一要確認的是兼容性IE 不支持 Set但現(xiàn)在還在做 IE 適配的場景已經(jīng)不多了就算要兼容也應該用 polyfill而不是換成一個 O(n2) 的方案。我之前在優(yōu)化一個百萬級 ID 數(shù)組時試過用 reduce 手動去重代碼寫了一大段性能還是不如 Set。后面想通了簡單場景不要炫技直接const uniqueIds [...new Set(ids)];干凈、快、不容易出 bug。4.2 對象數(shù)組按字段去重用 Map 做 key 映射對象數(shù)組去重是另一個高頻場景比如日志列表按 userId 去重商品列表按 sku 去重。如果直接用 Set兩個字段相同但引用不同的對象會被當成不同元素去不掉。正確做法是用 Map把要去重的字段拼成 keyconst list [ { id: 1, name: a }, { id: 2, name: b }, { id: 1, name: c }, ]; const map new Map(); for (const item of list) { const key item.id; if (!map.has(key)) map.set(key, item); } const unique [...map.values()];如果去重字段不止一個可以把多個字段拼成一個字符串作 key但要注意分隔符的選擇。比如key ${item.type}-${item.id} 時如果 type 或 id 本身可能包含 -就會撞 key。更穩(wěn)妥的辦法是用嵌套 MapouterMap.get(type).set(id, item)或者手動構(gòu)造一個穩(wěn)定的字符串 key。JSON.stringify 一個只含目標字段的小對象也是一種辦法但要注意字段聲明順序不同會產(chǎn)生不同 key。這個坑我在實際項目中踩過兩個重復項沒被去掉統(tǒng)計數(shù)據(jù)差了一大截。4.3 超大數(shù)組內(nèi)存敏感分片處理或原地標記如果數(shù)據(jù)量不只百萬而是上千萬或者運行環(huán)境是內(nèi)存緊張的設(shè)備Set/Map 的內(nèi)存開銷也要考慮。Set 對每個元素都要維護哈希表項內(nèi)存可能比原數(shù)組大好幾倍。這時候可以分片處理比如每次處理 20 萬條去重后合并用全局 Set 存放已見值function dedupeInChunks(arr, chunkSize 200000) { const seen new Set(); const result []; for (let i 0; i arr.length; i chunkSize) { const chunk arr.slice(i, i chunkSize); for (const item of chunk) { if (!seen.has(item)) { seen.add(item); result.push(item); } } } return result; }這種寫法的時間復雜度仍是 O(n)內(nèi)存不會一次性塞入全部 Set適合數(shù)據(jù)量特別大的場景。代價是代碼變長。如果內(nèi)存非常緊張可以不 slice直接通過索引在原數(shù)組上遍歷。4.4 需要保持順序不同方案順序表現(xiàn)保留順序的需求經(jīng)常被忽略。Set、Map、filter indexOf 天然保留第一次出現(xiàn)的順序。對象鍵值法如果只用 filter 也是保留順序的但特殊鍵名有風險。排序去重會改變順序不適合需要按原順序輸出的場景。如果在去重的同時還需要把每類數(shù)據(jù)的最后一條記錄取出來Map 也可以實現(xiàn)更復雜的操作通過每次都更新 value 就行。這是 Set 做不到的需要按場景選型。4.5 性能速查表方案時間復雜度內(nèi)存占用是否保序百萬級實測參考適用場景SetO(n)中是25~35ms原始值數(shù)組首選MapO(n)中是35~45ms對象按字段去重/需要鍵值映射對象鍵值O(n)低是50~70ms簡單場景注意鍵名陷阱排序相鄰O(n log n)高排序拷貝否120~180ms不要求順序數(shù)據(jù)非海量filterindexOfO(n2)中是5萬約1.5s只適合幾百到幾千的小數(shù)組表格里的耗時是我個人環(huán)境的結(jié)果不代表所有瀏覽器但時間復雜度是確定的。你在自己機器上跑一遍就能驗證這個數(shù)量級。5. 實戰(zhàn)案例百萬級日志按用戶去重的完整方案5.1 需求描述與踩坑案例一個真實場景某天我需要處理 100 萬條登錄日志每條 log 是一個對象包含 uid、time、device 等字段。業(yè)務(wù)要求按 uid 去重并且保留每個 uid 最新的一條日志。數(shù)據(jù)量百萬級如果寫雙重循環(huán)或者 filter indexOf頁面或者 Node 腳本基本就廢了。一開始同事用 sort 按時間倒序排然后 filter 相鄰 uid 去重logs.sort((a, b) Date.parse(b.time) - Date.parse(a.time)); const result logs.filter((item, i) i 0 || item.uid ! logs[i - 1].uid);這個方案在 100 萬條數(shù)據(jù)下大約跑了 1 秒多看起來還行但它改變了原數(shù)組順序而且如果 uid 是數(shù)字和字符串混合判斷item.uid ! logs[i - 1].uid就會把123和123當成不同用戶。我們線上就因為這個踩了坑。5.2 高效實現(xiàn)與關(guān)鍵代碼最穩(wěn)的方案是直接一遍 Map邊遍歷邊比較時間保留最新記錄。時間復雜度 O(n)也不會被 uid 類型混合影響const map new Map(); for (const log of logs) { const uid String(log.uid); // 統(tǒng)一字符串 key避免 123 和 123 分離 const old map.get(uid); if (!old || Date.parse(log.time) Date.parse(old.time)) { map.set(uid, log); } } const result [...map.values()];如果不想每次比較都重新 Date.parse可以先預處理一個小結(jié)構(gòu)把日志時間轉(zhuǎn)成時間戳再進 Mapconst map new Map(); for (let i 0; i logs.length; i) { const log logs[i]; const uid String(log.uid); const timestamp Date.parse(log.time); const old map.get(uid); if (!old || timestamp old._ts) { map.set(uid, { ...log, _ts: timestamp }); } } const result [...map.values()].map(({ _ts, ...rest }) rest);第二種做法把 Date.parse 的調(diào)用次數(shù)減少到每個用戶至多兩次時間比較也變成純數(shù)字比較百萬級數(shù)據(jù)實測大約 200~300ms 出結(jié)果。相比排序去重的 1 秒多又快了不少而且完整保留了原始對象只是中間多了一個臨時字段。5.3 結(jié)果和擴展建議按這個方案跑下來100 萬條日志去重后長度大概在 30 萬左右耗時穩(wěn)定在 300ms 以內(nèi)。如果數(shù)據(jù)量繼續(xù)漲到 500 萬、1000 萬我建議直接分片每 20 萬條一批處理配合全局 Map避免單次內(nèi)存占用過高。再大一點可以把任務(wù)丟到 Web Worker 里跑瀏覽器主線程完全不卡。這個案例還說明了一個道理去重的核心不一定是“快速去掉重復項”而是“在去重的同時拿到你真正需要的那條數(shù)據(jù)”。用 Map 可以邊去重邊保留最新的、最早的、或者聚合后的值比單純 Set 更靈活。6. 避坑指南與我的實操建議6.1 你以為去重很純粹NaN、-0、引用類型這些邊角料Set 對 NaN 的處理比 indexOf 強。indexOf 內(nèi)部走的是嚴格相等NaN NaN 為 false所以用 indexOf 去重時多個 NaN 不會被去掉。Set 內(nèi)部用的是 SameValueZero 算法NaN 算同一個值能正常去重。另外-0 和 0 在 Set 里也被認為是同一個值不會產(chǎn)生兩個元素。對于引用類型Set 比較的是引用地址。如果兩個對象結(jié)構(gòu)完全一樣但屬于不同引用Set 不會去重。所以不要試圖用 Set 直接去重對象數(shù)組除非你明確知道對象都是同一個引用。還有一個容易忽略的用 JSON.stringify 配合 Set 做對象去重時如果對象里有函數(shù)、undefined、Symbol這些會被 JSON.stringify 忽略或轉(zhuǎn)成 null可能導致錯誤去重。比如兩個對象一個多了 undefined 字段序列化后居然一樣。這個坑我踩過最后改成手動拼接關(guān)鍵字段才解決。6.2 測試時最容易犯的錯編譯器優(yōu)化、隨機數(shù)干擾做性能對比時很多人直接 console.time 包一下就下結(jié)論結(jié)果被誤導。第一必須保證各方法操作的是同一份數(shù)據(jù)源或等價數(shù)據(jù)不能一個方法改了原數(shù)組后面方法跟著受影響。第二如果方法內(nèi)部創(chuàng)建了新數(shù)組測試時要把新數(shù)組消費掉否則引擎覺得結(jié)果沒被使用可能會做死代碼消除導致結(jié)果虛低。第三隨機數(shù)組每次內(nèi)容不同重復率不同會影響排序去重這類方案的耗時所以要固定數(shù)據(jù)源或多次取平均。我調(diào)試時的做法是先固定生成一份數(shù)組存在變量里每個方法傳入同一個 arr方法內(nèi)部自己拷貝需要的部分保證互不干擾。運行多次取中位數(shù)比單次結(jié)果更可信。另一個容易被忽略的是 JIT 編譯預熱。第一次調(diào)用某個函數(shù)時JS 引擎可能要優(yōu)化編譯所以測試時先跑一遍熱身再用第二遍的結(jié)果作為參考。如果只跑一遍可能會把預熱時間也算進去得到不真實的數(shù)字。6.3 我用了這么久的一點心得文章寫到這里我把個人沉淀的幾個習慣分享出來。第一在大數(shù)據(jù)量場景里不要聰明過頭先無腦用 Set 把功能跑通再用性能分析工具看瓶頸。很多同事一上來就寫個看起來很高效的排序去重結(jié)果數(shù)據(jù)不是數(shù)值類型排序還得寫復雜比較器反而比 Set 更慢。第二去重需求往往伴隨著統(tǒng)計需求比如去重后還要計算每個分類的數(shù)量、保留最近一條記錄等這時候直接用 Map 而不是 Set省得后面再造一遍輪子。第三如果數(shù)據(jù)量已經(jīng)大到 Set 也撐不住除了分片還可以考慮在數(shù)據(jù)源頭做約束比如后端 SQL 里加 DISTINCT或者日志采集時先用更節(jié)省空間的概率結(jié)構(gòu)把明顯重復的丟掉。前端 JS 能做的優(yōu)化有上限不能把壓力全扛在瀏覽器里。我用分片處理后再配合 Web Worker 把任務(wù)丟到后臺線程跑頁面完全不會卡體驗好了很多。最后分享一個小技巧當數(shù)組是百萬級且全是不重復的數(shù)字時可以把數(shù)字轉(zhuǎn)成 Uint32Array 之類的 TypedArray 來省內(nèi)存。但要注意TypedArray 在去重這件事上并不會比普通數(shù)組快很多它主要省內(nèi)存不是省時間。真正要省時間還是要回到哈希表加 O(n) 循環(huán)這條路。希望這份實測記錄能幫你少走點彎路。