Lodash _.uniq Deduplication Algorithm Explained

The _.uniq method in the Lodash JavaScript library creates a duplicate-free version of an array by filtering values through an internal function called baseUniq. Rather than relying on a single static algorithm, Lodash dynamically chooses between a linear search approach and a hash-set-based approach depending on the array's size and the runtime environment's capabilities. This hybrid strategy allows Lodash to balance memory allocation overhead with execution speed, achieving an optimal \(O(n)\) average time complexity for large datasets while minimizing initialization costs for small arrays.

The Core Implementation: baseUniq

When _.uniq(array) is called, it passes the input array to the internal baseUniq utility without a custom iteratee or comparator. The function processes the array sequentially, checking each item against previously encountered items before appending it to a newly allocated results array.

Optimization Strategy Based on Array Size

Lodash utilizes an internal threshold—traditionally set to 200 elements—to determine the deduplication strategy:

1. Small Arrays (Length < 200): Linear Scanning (\(O(n^2)\)) For small arrays, the performance overhead of instantiating advanced data structures outweighs the cost of sequential iteration. Lodash iterates through the input elements and performs an array scan (similar to Array.prototype.indexOf or includes) against the result array. Because the collection is small, this nested loop runs rapidly in memory without incurring garbage collection or allocation overhead from hash maps.

2. Large Arrays (Length >= 200): Hash-Set Lookup (\(O(n)\)) When the array size meets or exceeds 200 elements, nested iteration becomes inefficient. Lodash switches to a caching structure called SetCache. It converts the accumulated values into a hash-backed set, reducing duplicate lookups from \(O(n)\) to \(O(1)\). Consequently, the overall deduplication process runs in \(O(n)\) linear time.

The Role of SetCache and Native Set

In modern JavaScript environments, SetCache relies directly on the native ECMAScript 6 Set primitive. If native Set is supported and no custom comparator is used, baseUniq optimizes the process by passing the array values directly into a Set or utilizing the native structure for instant existence checks (set.has(value)).

In older legacy environments lacking native Set support, SetCache falls back to an internal hash map implementation that groups primitive values (strings, numbers, booleans) by type and keys to simulate set functionality.

Equality Semantics: SameValueZero

Lodash's deduplication algorithm does not use strict equality (===). Instead, it implements the SameValueZero comparison algorithm defined by ECMAScript specifications. This ensures distinct edge-case behaviors:

• NaN Handling: In strict equality, NaN === NaN evaluates to false. Under SameValueZero, NaN values are considered equal, meaning multiple NaN entries in an array are reduced to a single instance.
• Signed Zeros: Both +0 and -0 are evaluated as identical values.

Summary of Complexity

• Time Complexity: \(O(n)\) on average for arrays with 200 or more items via SetCache; \(O(n^2)\) worst-case for small arrays where the absolute execution time remains negligible.
• Space Complexity: \(O(n)\) auxiliary space to store the unique result array and the hash lookup set.