JavaScript数据结构与算法深度解析

一、内置数据结构：Map/Set与弱引用版本

1. Map与Set基础

Map 是键值对集合，与普通Object的主要区别：

• 键可以是任意类型（Object只能用字符串/Symbol）
• 保持插入顺序
• 提供更直观的API（size、forEach等）

const map = new Map();
map.set('name', 'John');  // 字符串键
map.set(1, 'Number One'); // 数字键
map.set({}, 'Object');    // 对象键

console.log(map.get(1)); // "Number One"
console.log(map.size);    // 3

Set 是唯一值的集合：

const set = new Set([1, 2, 3, 3, 4]);
console.log(set.size); // 4 (自动去重)
set.add(5).delete(1);  // 链式调用

2. WeakMap与WeakSet特性

弱引用集合的特点：

• 只接受对象作为键（WeakMap）或值（WeakSet）
• 不阻止垃圾回收
• 不可迭代、无size属性

let obj = {};
const weakMap = new WeakMap();
weakMap.set(obj, 'private data');

obj = null; // 下次GC时会自动清除weakMap中的条目

使用场景对比：

二、类型化数组与二进制处理

1. ArrayBuffer与视图

核心概念：

• ArrayBuffer：原始二进制数据缓冲区
• TypedArray：特定类型的视图（如Int32Array）
• DataView：灵活的类型无关视图

// 创建4字节缓冲区
const buffer = new ArrayBuffer(4); 

// 32位有符号整数视图
const int32View = new Int32Array(buffer);
int32View[0] = 42;

// 8位无符号视图（共享同一buffer）
const uint8View = new Uint8Array(buffer);
console.log(uint8View[0]); // 42 (低位字节)

2. 实际应用示例

图像数据处理：

function processImage(buffer) {
    const header = new DataView(buffer, 0, 8);
    const width = header.getUint32(0);
    const height = header.getUint32(4);
    
    const pixels = new Uint8ClampedArray(buffer, 8);
    // 像素处理...
}

性能对比：

// 普通数组
const arr = new Array(1000000).fill(0);
console.time('normal');
arr.map(x => x * 2);
console.timeEnd('normal'); // ~120ms

// 类型化数组
const typedArr = new Float64Array(1000000);
console.time('typed');
for(let i=0; i<typedArr.length; i++) {
    typedArr[i] *= 2;
}
console.timeEnd('typed'); // ~5ms

三、经典算法实现

1. 排序算法

快速排序（分治策略）：

function quickSort(arr) {
    if (arr.length <= 1) return arr;
    
    const pivot = arr[Math.floor(arr.length/2)];
    const left = [], right = [];
    
    for(let i=0; i<arr.length; i++) {
        if(i === Math.floor(arr.length/2)) continue;
        arr[i] < pivot ? left.push(arr[i]) : right.push(arr[i]);
    }
    
    return [...quickSort(left), pivot, ...quickSort(right)];
}

性能比较：

2. 搜索算法

二分查找（要求已排序）：

function binarySearch(arr, target) {
    let left = 0, right = arr.length - 1;
    
    while(left <= right) {
        const mid = Math.floor((left + right)/2);
        if(arr[mid] === target) return mid;
        arr[mid] < target ? left = mid + 1 : right = mid - 1;
    }
    
    return -1;
}

DFS与BFS实现：

// 图的深度优先搜索
function dfs(graph, start, visited = new Set()) {
    visited.add(start);
    for(const neighbor of graph[start]) {
        if(!visited.has(neighbor)) {
            dfs(graph, neighbor, visited);
        }
    }
    return visited;
}

// 广度优先搜索（使用队列）
function bfs(graph, start) {
    const queue = [start], visited = new Set([start]);
    
    while(queue.length) {
        const node = queue.shift();
        for(const neighbor of graph[node]) {
            if(!visited.has(neighbor)) {
                visited.add(neighbor);
                queue.push(neighbor);
            }
        }
    }
    return visited;
}

四、性能优化实践建议

1. 数据结构选择：

   • 频繁键值操作 → 使用Map替代Object
   • 大数据处理 → 优先考虑TypedArray
   • 临时对象关联 → WeakMap避免内存泄漏

2. 算法优化技巧：

   // 缓存计算结果（Memoization）
   function fibonacci(n, memo = {}) {
       if(n in memo) return memo[n];
       if(n <= 2) return 1;
       memo[n] = fibonacci(n-1, memo) + fibonacci(n-2, memo);
       return memo[n];
   }

3. 现代API结合：

   // 使用Map实现LRU缓存
   class LRUCache {
       constructor(capacity) {
           this.capacity = capacity;
           this.cache = new Map();
       }
       
       get(key) {
           if(!this.cache.has(key)) return -1;
           const value = this.cache.get(key);
           this.cache.delete(key);
           this.cache.set(key, value);
           return value;
       }
   }

五、前沿趋势

1. WebAssembly交互：

   // 加载WASM模块
   WebAssembly.instantiateStreaming(fetch('module.wasm'))
       .then(obj => {
           const result = obj.instance.exports.compute(10);
           console.log(result);
       });

2. 算法新特性：

   // 使用Temporal API处理时间计算
   const start = Temporal.Now.instant();
   // 执行算法...
   const end = Temporal.Now.instant();
   console.log(`耗时: ${end.since(start).milliseconds}ms`);

掌握这些数据结构与算法，将显著提升JavaScript应用的性能和可维护性。建议结合实际场景进行针对性练习，如图处理、状态管理等高级应用场景。