Node.js中Set的查找是否不具备O(1)时间复杂度？

I wrote test code to verify the lookup speed of Set in Node.js (v8.4). The code is as follows:

const size = 5000000; 
const lookups = 1000000; 
const set = new Set(); 
for (let i = 0; i < size; i++) { set.add(i); } 
const samples = []; 
for (let i = 0; i < lookups; i++) { samples.push(Math.floor(Math.random() * size)); } 
const start = Date.now(); 
for (const key of samples) { set.has(key); } 
console.log(`size: ${size}, time: ${Date.now() - start}`);

When I ran it with size set to 5000, 50000, 500000, 5000000 respectively, the results showed that Set lookup doesn't seem to be O(1). I'm writing to ask why.

Great question—this is a classic case where real-world benchmark results don't match theoretical time complexity, and it all comes down to how V8 implements sets plus hardware limitations. Let's break down the key reasons:

1. V8's Dual Storage Strategy for Sets (v8.4 Era) #

Back in Node.js v8.4 (which uses V8 engine version 6.0), Set didn't use a hash table for all sizes. V8 used a two-stage approach to balance memory efficiency and speed:

• Small sets (under ~1000 elements): Elements were stored in a sorted FixedArray, and has() relied on linear search. This gives O(n) time for smaller sizes, which explains why your 5k and 50k runs might have scaled more than you expected.
• Large sets: Once the set grows beyond that threshold, V8 switches to a hash table, which provides average-case O(1) lookups. But even here, real-world factors can obscure this theoretical performance.

2. CPU Cache Misses Dominate Large-Size Performance #

The biggest culprit for your 500k/5M size results is CPU cache locality:

• Small sets fit entirely in the CPU's fast L1/L2 cache. Every has() call pulls data from cache, which is extremely fast (nanosecond-scale).
• When the set hits 500k+ elements, the hash table becomes too large to fit in cache. Each lookup now has to fetch data from main memory, which is 100–1000x slower. Your random sampling makes this even worse—random keys spread access across the entire hash table, leading to frequent cache misses. This creates the illusion of O(n) scaling, but it's a hardware limitation, not a flaw in the hash table algorithm.

3. JIT Optimization and Minimal Overhead #

While V8's JIT compiler will optimize your loop over time, there's still minimal per-call overhead for has(). For small sets, this overhead is negligible compared to cache hits. For large sets, the cache miss penalty swamps everything else, making total time grow with set size even though each lookup is still O(1) in terms of algorithmic steps.

How to Verify These Claims #

• Test the threshold: Run your benchmark with sizes just below and above ~1000 elements. You should see a sharp drop in per-lookup time once the set switches to a hash table.
• Try sequential lookups: Replace your random samples with sequential keys (e.g., samples.push(i % size)). You'll notice faster times because sequential access leverages cache prefetching, reducing misses.

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