跳到主要内容

哈希和散列表✅

哈希表是计算机科学中最重要的数据结构之一，本章涵盖LRU缓存、Map实现对比、一致性哈希和洗牌算法等核心主题。

LRU缓存机制如何实现？​

// 设计并实现LRU(最近最少使用)缓存数据结构
// 支持get(key)和put(key, value)操作
// 当缓存容量达到上限时，删除最久未使用的数据
class LRUCache {
  constructor(capacity) {
    // 请实现LRU缓存
  }
  
  get(key) {
    // 获取键对应的值，如果存在则返回值并标记为最近使用
  }
  
  put(key, value) {
    // 插入或更新键值对，如果超出容量则删除最久未使用的数据
  }
}
答案

LRU核心概念​

LRU（Least Recently Used）缓存是一种缓存淘汰策略，当缓存空间不足时，优先删除最久未使用的数据。LRU缓存需要支持O(1)时间复杂度的插入、删除和查找操作。

LRU实现策略​

双向链表 + 哈希表方案：

  • 哈希表: 提供O(1)的快速查找
  • 双向链表: 维护访问顺序，支持O(1)的插入和删除
  • 头部节点: 存储最近使用的数据
  • 尾部节点: 存储最久未使用的数据

操作流程：

  1. GET操作: 查找哈希表，如果存在则将节点移到头部
  2. PUT操作: 插入新节点到头部，如果超出容量则删除尾部节点
  3. 访问更新: 每次访问都将对应节点移到链表头部

时间复杂度: O(1) - 插入、删除、查找 空间复杂度: O(capacity) - 存储capacity个键值对

LRU示例实现​

/**
 * LRU缓存实现
 * 使用双向链表 + 哈希表
 */
class LRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
    // 创建头尾虚拟节点
    this.head = { key: -1, value: -1, prev: null, next: null };
    this.tail = { key: -1, value: -1, prev: null, next: null };
    this.head.next = this.tail;
    this.tail.prev = this.head;
  }

  /**
   * 获取值
   * @param {number} key
   * @returns {number}
   */
  get(key) {
    if (this.cache.has(key)) {
      const node = this.cache.get(key);
      // 移动到头部（最近使用）
      this.moveToHead(node);
      return node.value;
    }
    return -1;
  }

  /**
   * 设置键值对
   * @param {number} key
   * @param {number} value
   */
  put(key, value) {
    if (this.cache.has(key)) {
      // 更新已存在的节点
      const node = this.cache.get(key);
      node.value = value;
      this.moveToHead(node);
    } else {
      // 创建新节点
      const newNode = { key, value, prev: null, next: null };
      
      if (this.cache.size >= this.capacity) {
        // 删除尾部节点（最久未使用）
        const tail = this.removeTail();
        this.cache.delete(tail.key);
      }
      
      this.cache.set(key, newNode);
      this.addToHead(newNode);
    }
  }

  /**
   * 将节点添加到头部
   */
  addToHead(node) {
    node.prev = this.head;
    node.next = this.head.next;
    this.head.next.prev = node;
    this.head.next = node;
  }

  /**
   * 移除节点
   */
  removeNode(node) {
    node.prev.next = node.next;
    node.next.prev = node.prev;
  }

  /**
   * 将节点移动到头部
   */
  moveToHead(node) {
    this.removeNode(node);
    this.addToHead(node);
  }

  /**
   * 移除尾部节点
   */
  removeTail() {
    const lastNode = this.tail.prev;
    this.removeNode(lastNode);
    return lastNode;
  }

  /**
   * 获取当前缓存状态（用于调试）
   */
  getState() {
    const result = [];
    let current = this.head.next;
    while (current !== this.tail) {
      result.push({ key: current.key, value: current.value });
      current = current.next;
    }
    return result;
  }
}

/**
 * 简化版LRU缓存（使用Map的插入顺序特性）
 */
class SimpleLRUCache {
  constructor(capacity) {
    this.capacity = capacity;
    this.cache = new Map();
  }

  get(key) {
    if (this.cache.has(key)) {
      const value = this.cache.get(key);
      // 重新插入以更新顺序
      this.cache.delete(key);
      this.cache.set(key, value);
      return value;
    }
    return -1;
  }

  put(key, value) {
    if (this.cache.has(key)) {
      this.cache.delete(key);
    } else if (this.cache.size >= this.capacity) {
      // 删除最早插入的项（Map迭代器的第一个）
      const firstKey = this.cache.keys().next().value;
      this.cache.delete(firstKey);
    }
    this.cache.set(key, value);
  }

  getState() {
    return Array.from(this.cache.entries()).map(([key, value]) => ({ key, value }));
  }
}

module.exports = { LRUCache, SimpleLRUCache };

Open browser consoleTests

LRU优化方案​

  • 使用Map简化实现: 利用JavaScript Map的插入顺序特性
  • 内存优化: 避免创建虚拟头尾节点，直接管理边界
  • 线程安全: 在多线程环境中添加锁机制
  • 持久化: 支持将缓存数据持久化到磁盘

LRU应用场景​

  • 操作系统: 页面置换算法
  • 数据库: 缓冲池管理
  • Web缓存: 浏览器缓存策略
  • 分布式系统: Redis等缓存中间件
  • 移动应用: 图片缓存、数据缓存

LRU面试官视角​

该题考察候选人对数据结构的综合应用能力：

  • 要点清单: 理解LRU策略原理；能设计双向链表+哈希表方案；掌握O(1)时间复杂度实现；正确处理边界情况

  • 加分项: 了解其他缓存策略(LFU、FIFO)；能优化内存使用；有实际项目应用经验；了解并发安全

  • 常见失误: 时间复杂度不是O(1)；链表操作出错；边界条件处理错误；不理解缓存淘汰策略

LRU延伸阅读​

TreeMap和HashMap的区别是什么？​

答案

Map核心概念​

HashMap和TreeMap是两种不同的Map实现，它们在底层数据结构、性能特征和功能特性上有显著差异。HashMap基于哈希表实现，TreeMap基于红黑树（或其他平衡二叉搜索树）实现。

Map详细对比​

特性HashMapTreeMap
底层结构哈希表 + 链表/红黑树红黑树（平衡BST）
时间复杂度O(1)平均，O(n)最坏O(log n)稳定
空间复杂度O(n)O(n) + 指针开销
有序性无序（插入顺序）有序（键的自然顺序）
null键值允许null键和值不允许null键

Map功能差异​

HashMap优势：

  • 平均O(1)的插入、删除、查找性能
  • 内存使用效率高
  • 支持null键值
  • 适合高频访问场景

TreeMap优势：

  • 自动维护键的有序性
  • 支持范围查询（firstKey、lastKey、subMap）
  • 性能稳定，无最坏情况退化
  • 支持自定义比较器

Map示例实现​

/**
 * HashMap vs TreeMap 对比演示
 */

/**
 * 简单的TreeMap实现（基于红黑树的简化版本）
 */
class TreeMapNode {
  constructor(key, value) {
    this.key = key;
    this.value = value;
    this.left = null;
    this.right = null;
  }
}

class SimpleTreeMap {
  constructor(compareFn = (a, b) => a < b ? -1 : a > b ? 1 : 0) {
    this.root = null;
    this.size = 0;
    this.compare = compareFn;
  }

  put(key, value) {
    if (this.root === null) {
      this.root = new TreeMapNode(key, value);
      this.size++;
      return;
    }

    this._insert(this.root, key, value);
  }

  _insert(node, key, value) {
    const cmp = this.compare(key, node.key);
    
    if (cmp === 0) {
      // 更新现有节点
      node.value = value;
      return;
    }
    
    if (cmp < 0) {
      if (node.left === null) {
        node.left = new TreeMapNode(key, value);
        this.size++;
      } else {
        this._insert(node.left, key, value);
      }
    } else {
      if (node.right === null) {
        node.right = new TreeMapNode(key, value);
        this.size++;
      } else {
        this._insert(node.right, key, value);
      }
    }
  }

  get(key) {
    return this._search(this.root, key);
  }

  _search(node, key) {
    if (node === null) return undefined;
    
    const cmp = this.compare(key, node.key);
    if (cmp === 0) return node.value;
    if (cmp < 0) return this._search(node.left, key);
    return this._search(node.right, key);
  }

  has(key) {
    return this.get(key) !== undefined;
  }

  // 中序遍历获取有序的键值对
  entries() {
    const result = [];
    this._inorderTraversal(this.root, result);
    return result;
  }

  _inorderTraversal(node, result) {
    if (node !== null) {
      this._inorderTraversal(node.left, result);
      result.push([node.key, node.value]);
      this._inorderTraversal(node.right, result);
    }
  }

  keys() {
    return this.entries().map(([key]) => key);
  }

  values() {
    return this.entries().map(([, value]) => value);
  }

  // 获取第一个（最小）键
  firstKey() {
    if (this.root === null) return undefined;
    let current = this.root;
    while (current.left !== null) {
      current = current.left;
    }
    return current.key;
  }

  // 获取最后一个（最大）键
  lastKey() {
    if (this.root === null) return undefined;
    let current = this.root;
    while (current.right !== null) {
      current = current.right;
    }
    return current.key;
  }
}

/**
 * 性能测试函数
 */
function performanceTest() {
  const testSize = 10000;
  const randomKeys = Array.from({ length: testSize }, () => 
    Math.floor(Math.random() * testSize * 2)
  );

  console.log(`=== 性能测试 (${testSize} 个操作) ===`);

  // HashMap (Map) 性能测试
  console.time('HashMap 插入');
  const hashMap = new Map();
  for (const key of randomKeys) {
    hashMap.set(key, `value_${key}`);
  }
  console.timeEnd('HashMap 插入');

  console.time('HashMap 查找');
  for (const key of randomKeys) {
    hashMap.get(key);
  }
  console.timeEnd('HashMap 查找');

  // TreeMap 性能测试
  console.time('TreeMap 插入');
  const treeMap = new SimpleTreeMap();
  for (const key of randomKeys) {
    treeMap.put(key, `value_${key}`);
  }
  console.timeEnd('TreeMap 插入');

  console.time('TreeMap 查找');
  for (const key of randomKeys) {
    treeMap.get(key);
  }
  console.timeEnd('TreeMap 查找');

  console.log(`HashMap 大小: ${hashMap.size}`);
  console.log(`TreeMap 大小: ${treeMap.size}`);
}

/**
 * 功能特性对比
 */
function featureComparison() {
  console.log('=== 功能特性对比 ===');

  const hashMap = new Map();
  const treeMap = new SimpleTreeMap();

  // 插入无序数据
  const data = [
    [30, 'thirty'],
    [10, 'ten'],
    [50, 'fifty'],
    [20, 'twenty'],
    [40, 'forty']
  ];

  console.log('\n--- 插入数据 ---');
  console.log('插入顺序:', data.map(([k, v]) => k));

  data.forEach(([key, value]) => {
    hashMap.set(key, value);
    treeMap.put(key, value);
  });

  console.log('\n--- 遍历结果 ---');
  console.log('HashMap 遍历（插入顺序）:', Array.from(hashMap.keys()));
  console.log('TreeMap 遍历（排序顺序）:', treeMap.keys());

  console.log('\n--- 范围查询 ---');
  console.log('TreeMap 最小键:', treeMap.firstKey());
  console.log('TreeMap 最大键:', treeMap.lastKey());
  console.log('HashMap 无法直接获取最小/最大键');

  console.log('\n--- 有序遍历 ---');
  console.log('TreeMap 有序键值对:', treeMap.entries());
  
  const sortedHashMap = Array.from(hashMap.entries()).sort(([a], [b]) => a - b);
  console.log('HashMap 需要手动排序:', sortedHashMap);
}

/**
 * 空间复杂度对比
 */
function spaceComplexityDemo() {
  console.log('\n=== 空间复杂度演示 ===');

  const size = 1000;
  
  // HashMap
  const hashMap = new Map();
  for (let i = 0; i < size; i++) {
    hashMap.set(i, `value_${i}`);
  }

  // TreeMap  
  const treeMap = new SimpleTreeMap();
  for (let i = 0; i < size; i++) {
    treeMap.put(i, `value_${i}`);
  }

  console.log(`HashMap: 每个条目只存储键值对`);
  console.log(`TreeMap: 每个条目额外存储左右子节点指针`);
  console.log(`TreeMap 的空间开销相对更大`);
}

module.exports = {
  SimpleTreeMap,
  TreeMapNode,
  performanceTest,
  featureComparison,
  spaceComplexityDemo
};

Open browser consoleTests

Map选择指南​

使用HashMap场景：

  • 不需要维护键的顺序
  • 追求最高的访问性能
  • 内存使用敏感的场景
  • 缓存、计数等应用

使用TreeMap场景：

  • 需要有序遍历
  • 需要范围查询功能
  • 要求稳定的性能表现
  • 实现排序相关功能

Map面试官视角​

该题考察候选人对数据结构的深入理解：

  • 要点清单: 理解两种数据结构原理；掌握时间空间复杂度差异；知道适用场景；能分析性能特点

  • 加分项: 了解哈希冲突解决方案；理解红黑树平衡机制；有性能优化经验；知道JDK实现细节

  • 常见失误: 混淆时间复杂度；不理解有序性差异；忽视内存开销；缺乏实际应用经验

Map延伸阅读​

一致性哈希如何实现？​

答案

一致性哈希核心概念​

一致性哈希是一种分布式哈希方案，解决了传统哈希在节点数量变化时需要重新映射大量数据的问题。通过构建哈希环和引入虚拟节点，实现了良好的负载均衡和最小化数据迁移。

一致性哈希算法原理​

哈希环构建：

  1. 将哈希值空间构建为一个环形结构（0 ~ 2³²-1）
  2. 将服务器节点映射到环上的特定位置
  3. 数据通过哈希函数映射到环上，顺时针找到第一个节点

虚拟节点机制：

  • 每个物理节点创建多个虚拟节点
  • 虚拟节点均匀分布在环上
  • 解决节点分布不均导致的负载不均衡问题

一致性哈希核心优势​

  • 最小化数据迁移: 节点变化时只影响相邻区间的数据
  • 负载均衡: 通过虚拟节点实现数据均匀分布
  • 容错性: 单个节点故障影响范围有限
  • 扩展性: 支持动态添加和删除节点

一致性哈希示例实现​

/**
 * 一致性哈希实现
 * 解决分布式缓存的扩展性问题
 */

/**
 * 简单哈希函数（用于演示，实际应用中应使用更好的哈希算法如MD5、SHA1）
 */
function simpleHash(str) {
  let hash = 0;
  for (let i = 0; i < str.length; i++) {
    const char = str.charCodeAt(i);
    hash = ((hash << 5) - hash) + char;
    hash = hash & hash; // 转换为32位整数
  }
  return Math.abs(hash);
}

/**
 * 一致性哈希环
 */
class ConsistentHash {
  constructor(nodes = [], virtualNodes = 150) {
    this.virtualNodes = virtualNodes; // 每个物理节点的虚拟节点数
    this.ring = new Map(); // 哈希环，key: hash值, value: 节点名
    this.sortedHashes = []; // 排序的哈希值数组
    
    // 添加初始节点
    nodes.forEach(node => this.addNode(node));
  }

  /**
   * 添加节点
   */
  addNode(node) {
    for (let i = 0; i < this.virtualNodes; i++) {
      const virtualNodeName = `${node}:${i}`;
      const hash = simpleHash(virtualNodeName);
      this.ring.set(hash, node);
    }
    this._updateSortedHashes();
    console.log(`添加节点: ${node}，虚拟节点数: ${this.virtualNodes}`);
  }

  /**
   * 移除节点
   */
  removeNode(node) {
    for (let i = 0; i < this.virtualNodes; i++) {
      const virtualNodeName = `${node}:${i}`;
      const hash = simpleHash(virtualNodeName);
      this.ring.delete(hash);
    }
    this._updateSortedHashes();
    console.log(`移除节点: ${node}`);
  }

  /**
   * 获取数据应该存储在哪个节点
   */
  getNode(key) {
    if (this.ring.size === 0) {
      return null;
    }

    const hash = simpleHash(key);
    
    // 找到第一个大于等于该哈希值的节点
    let nodeIndex = this._findNodeIndex(hash);
    
    // 如果没找到，说明应该放在第一个节点（环形结构）
    if (nodeIndex === -1) {
      nodeIndex = 0;
    }

    const nodeHash = this.sortedHashes[nodeIndex];
    return this.ring.get(nodeHash);
  }

  /**
   * 更新排序的哈希值数组
   */
  _updateSortedHashes() {
    this.sortedHashes = Array.from(this.ring.keys()).sort((a, b) => a - b);
  }

  /**
   * 二分查找第一个大于等于目标值的位置
   */
  _findNodeIndex(targetHash) {
    let left = 0;
    let right = this.sortedHashes.length - 1;
    let result = -1;

    while (left <= right) {
      const mid = Math.floor((left + right) / 2);
      if (this.sortedHashes[mid] >= targetHash) {
        result = mid;
        right = mid - 1;
      } else {
        left = mid + 1;
      }
    }

    return result;
  }

  /**
   * 获取数据分布统计
   */
  getDistribution(keys) {
    const distribution = {};
    
    keys.forEach(key => {
      const node = this.getNode(key);
      if (node) {
        distribution[node] = (distribution[node] || 0) + 1;
      }
    });

    return distribution;
  }

  /**
   * 获取环的状态信息
   */
  getRingInfo() {
    return {
      totalVirtualNodes: this.ring.size,
      physicalNodes: [...new Set(this.ring.values())],
      virtualNodesPerPhysical: this.virtualNodes
    };
  }

  /**
   * 模拟节点故障后的数据迁移
   */
  simulateFailure(failedNode, keys) {
    console.log(`\n=== 模拟节点 ${failedNode} 故障 ===`);
    
    // 故障前的分布
    const beforeDistribution = this.getDistribution(keys);
    console.log('故障前分布:', beforeDistribution);

    // 找出故障节点上的数据
    const affectedKeys = keys.filter(key => this.getNode(key) === failedNode);
    console.log(`故障节点上的数据数量: ${affectedKeys.length}`);

    // 移除故障节点
    this.removeNode(failedNode);

    // 故障后的分布
    const afterDistribution = this.getDistribution(keys);
    console.log('故障后分布:', afterDistribution);

    // 分析数据迁移
    const migrationInfo = this._analyzeMigration(affectedKeys);
    console.log('数据迁移情况:', migrationInfo);

    return {
      affectedKeys: affectedKeys.length,
      beforeDistribution,
      afterDistribution,
      migrationInfo
    };
  }

  /**
   * 分析数据迁移情况
   */
  _analyzeMigration(affectedKeys) {
    const migration = {};
    
    affectedKeys.forEach(key => {
      const newNode = this.getNode(key);
      if (newNode) {
        migration[newNode] = (migration[newNode] || 0) + 1;
      }
    });

    return migration;
  }
}

/**
 * 传统哈希方法对比（取模哈希）
 */
class SimpleModHash {
  constructor(nodeCount) {
    this.nodeCount = nodeCount;
    this.nodes = Array.from({ length: nodeCount }, (_, i) => `node-${i}`);
  }

  getNode(key) {
    const hash = simpleHash(key);
    const index = hash % this.nodeCount;
    return this.nodes[index];
  }

  removeNode() {
    this.nodeCount--;
    this.nodes.pop();
  }

  addNode(node) {
    this.nodeCount++;
    this.nodes.push(node);
  }

  getDistribution(keys) {
    const distribution = {};
    
    keys.forEach(key => {
      const node = this.getNode(key);
      distribution[node] = (distribution[node] || 0) + 1;
    });

    return distribution;
  }
}

module.exports = {
  ConsistentHash,
  SimpleModHash,
  simpleHash
};

Open browser consoleTests

一致性哈希应用场景​

  • 分布式缓存: Redis Cluster、Memcached集群
  • 负载均衡: 一致性哈希负载均衡算法
  • 分布式存储: 分布式文件系统的数据分片
  • CDN: 内容分发网络的节点选择
  • 微服务: 服务实例的路由分配

一致性哈希参数调优​

虚拟节点数量：

  • 过少：负载不均衡
  • 过多：内存开销增加，查找变慢
  • 建议：150-200个虚拟节点per物理节点

哈希函数选择：

  • MD5：分布均匀，计算开销适中
  • SHA-1：安全性更高，开销较大
  • MurmurHash：性能优秀，分布良好

一致性哈希面试官视角​

该题考察候选人对分布式系统的理解：

  • 要点清单: 理解一致性哈希原理；掌握虚拟节点机制；能分析数据迁移量；了解负载均衡效果

  • 加分项: 有分布式系统开发经验；了解实际应用场景；能优化算法参数；知道其他分片策略

  • 常见失误: 不理解环形结构；虚拟节点概念模糊；数据迁移分析错误；忽视负载均衡问题

一致性哈希延伸阅读​

洗牌算法如何实现？​

答案

洗牌算法核心概念​

洗牌算法用于将数组元素随机重排，确保每种排列出现的概率相等。正确的洗牌算法需要保证真正的均匀分布，常用的Fisher-Yates算法是标准解决方案。

洗牌算法对比​

算法时间复杂度空间复杂度均匀性推荐度
Fisher-YatesO(n)O(1)✅ 真正均匀⭐⭐⭐⭐⭐
Sort + RandomO(n log n)O(n)❌ 分布有偏⭐
Inside-OutO(n)O(n)✅ 真正均匀⭐⭐⭐⭐

洗牌算法实现原理​

Fisher-Yates算法（现代版）：

  1. 从数组末尾开始向前遍历
  2. 对于位置i，随机选择[0, i]范围内的一个位置j
  3. 交换位置i和位置j的元素
  4. 继续处理位置i-1，直到处理完所有位置

关键点：

  • 每个位置的随机范围逐渐缩小
  • 确保每个元素在每个位置出现的概率都是1/n
  • 原地操作，空间复杂度O(1)

洗牌算法示例实现​

/**
 * 洗牌算法实现
 */

/**
 * Fisher-Yates 洗牌算法（现代版本）
 * 时间复杂度: O(n)
 * 空间复杂度: O(1)
 * 真正的均匀随机分布
 */
function fisherYatesShuffle(array) {
  // 不修改原数组
  const shuffled = [...array];
  
  // 从后往前遍历
  for (let i = shuffled.length - 1; i > 0; i--) {
    // 随机选择一个位置 [0, i]
    const randomIndex = Math.floor(Math.random() * (i + 1));
    
    // 交换当前位置和随机位置的元素
    [shuffled[i], shuffled[randomIndex]] = [shuffled[randomIndex], shuffled[i]];
  }
  
  return shuffled;
}

/**
 * 错误的 sort + Math.random 方法
 * 问题：不是真正的均匀分布
 * 仅供对比演示，不推荐使用
 */
function badSortShuffle(array) {
  return [...array].sort(() => Math.random() - 0.5);
}

/**
 * Knuth-Durstenfeld 洗牌算法（Fisher-Yates的改进版）
 * 原地洗牌，修改原数组
 */
function knuthShuffle(array) {
  for (let i = array.length - 1; i > 0; i--) {
    const j = Math.floor(Math.random() * (i + 1));
    [array[i], array[j]] = [array[j], array[i]];
  }
  return array;
}

/**
 * Inside-Out 洗牌算法
 * 适合流式数据，可以边读取边洗牌
 */
function insideOutShuffle(array) {
  const result = new Array(array.length);
  
  for (let i = 0; i < array.length; i++) {
    const j = Math.floor(Math.random() * (i + 1));
    if (j !== i) {
      result[i] = result[j];
    }
    result[j] = array[i];
  }
  
  return result;
}

/**
 * 蓄水池抽样算法
 * 从未知大小的数据流中随机采样k个元素
 */
function reservoirSampling(stream, k) {
  const reservoir = [];
  
  for (let i = 0; i < stream.length; i++) {
    if (i < k) {
      // 前k个元素直接加入蓄水池
      reservoir[i] = stream[i];
    } else {
      // 以 k/(i+1) 的概率替换蓄水池中的元素
      const randomIndex = Math.floor(Math.random() * (i + 1));
      if (randomIndex < k) {
        reservoir[randomIndex] = stream[i];
      }
    }
  }
  
  return reservoir;
}

/**
 * 测试洗牌算法的均匀性
 * 通过统计每个元素在各个位置出现的频次来验证
 */
function testShuffleUniformity(shuffleFunc, testArray, iterations = 10000) {
  const positions = {};
  const arrayLength = testArray.length;
  
  // 初始化统计
  for (let i = 0; i < arrayLength; i++) {
    positions[i] = {};
    for (let j = 0; j < arrayLength; j++) {
      positions[i][testArray[j]] = 0;
    }
  }
  
  // 进行多次洗牌测试
  for (let iter = 0; iter < iterations; iter++) {
    const shuffled = shuffleFunc([...testArray]);
    for (let pos = 0; pos < arrayLength; pos++) {
      positions[pos][shuffled[pos]]++;
    }
  }
  
  // 计算每个位置的分布情况
  const results = {};
  for (let pos = 0; pos < arrayLength; pos++) {
    results[`position_${pos}`] = {};
    for (const element of testArray) {
      const frequency = positions[pos][element];
      const percentage = (frequency / iterations * 100).toFixed(1);
      results[`position_${pos}`][element] = `${frequency} (${percentage}%)`;
    }
  }
  
  return results;
}

/**
 * 性能测试
 */
function performanceTest(size = 10000, iterations = 1000) {
  const testArray = Array.from({ length: size }, (_, i) => i);
  
  console.log(`性能测试 - 数组大小: ${size}, 迭代次数: ${iterations}`);
  
  // Fisher-Yates
  console.time('Fisher-Yates');
  for (let i = 0; i < iterations; i++) {
    fisherYatesShuffle(testArray);
  }
  console.timeEnd('Fisher-Yates');
  
  // Sort + Random (错误方法)
  console.time('Sort + Random');
  for (let i = 0; i < iterations; i++) {
    badSortShuffle(testArray);
  }
  console.timeEnd('Sort + Random');
  
  // Inside-Out
  console.time('Inside-Out');
  for (let i = 0; i < iterations; i++) {
    insideOutShuffle(testArray);
  }
  console.timeEnd('Inside-Out');
}

/**
 * 洗牌质量分析
 * 使用卡方检验评估随机性
 */
function analyzeShuffleQuality(shuffleFunc, testArray, iterations = 1000) {
  const positionCounts = new Array(testArray.length).fill(0).map(() => 
    new Array(testArray.length).fill(0)
  );
  
  for (let iter = 0; iter < iterations; iter++) {
    const shuffled = shuffleFunc([...testArray]);
    for (let pos = 0; pos < shuffled.length; pos++) {
      const elementIndex = testArray.indexOf(shuffled[pos]);
      positionCounts[pos][elementIndex]++;
    }
  }
  
  // 计算期望频次
  const expectedFreq = iterations / testArray.length;
  
  // 计算卡方统计量
  let chiSquare = 0;
  for (let pos = 0; pos < testArray.length; pos++) {
    for (let elem = 0; elem < testArray.length; elem++) {
      const observed = positionCounts[pos][elem];
      const expected = expectedFreq;
      chiSquare += Math.pow(observed - expected, 2) / expected;
    }
  }
  
  return {
    chiSquare: chiSquare.toFixed(2),
    degreesOfFreedom: (testArray.length - 1) * (testArray.length - 1),
    positionCounts
  };
}

/**
 * 加权洗牌算法
 * 根据权重进行洗牌，权重高的元素更容易排在前面
 */
function weightedShuffle(items, weights) {
  if (items.length !== weights.length) {
    throw new Error('Items and weights arrays must have the same length');
  }
  
  // 创建带权重的数组
  const weightedItems = items.map((item, index) => ({
    item,
    weight: weights[index],
    random: Math.random()
  }));
  
  // 按照 random^(1/weight) 排序
  weightedItems.sort((a, b) => 
    Math.pow(b.random, 1 / b.weight) - Math.pow(a.random, 1 / a.weight)
  );
  
  return weightedItems.map(({ item }) => item);
}

module.exports = {
  fisherYatesShuffle,
  badSortShuffle,
  knuthShuffle,
  insideOutShuffle,
  reservoirSampling,
  testShuffleUniformity,
  performanceTest,
  analyzeShuffleQuality,
  weightedShuffle
};

Open browser consoleTests

洗牌算法扩展​

蓄水池抽样：

  • 从未知大小的数据流中随机选择k个元素
  • 保证每个元素被选中的概率相等
  • 内存使用固定，适合大数据场景

加权洗牌：

  • 根据权重进行洗牌，权重高的元素更容易排在前面
  • 使用随机数的幂次方法实现
  • 适用于推荐系统、广告投放等场景

洗牌算法常见错误​

错误的sort + Math.random方法：

// 错误示例 - 分布不均匀
array.sort(() => Math.random() - 0.5);

问题分析：

  • sort算法的比较次数不固定
  • Math.random() - 0.5不能保证均匀分布
  • 某些排列出现概率更高

洗牌算法面试官视角​

该题考察候选人对随机算法的理解：

  • 要点清单: 理解Fisher-Yates算法原理；知道常见错误方法的问题；能分析时间空间复杂度；了解均匀性概念
  • 加分项: 了解统计学验证方法；掌握蓄水池抽样；有随机算法应用经验；能实现加权洗牌
  • 常见失误: 使用sort+random错误方法；不理解均匀分布要求；随机范围选择错误；忽视边界条件

洗牌算法延伸阅读​

HashMap的并发问题有哪些？​

答案

HashMap并发核心概念​

HashMap在多线程环境下是不安全的，并发访问可能导致数据丢失、死循环、数据覆盖等严重问题。了解这些问题和解决方案对于开发高并发应用至关重要。

HashMap并发问题分析​

1. 死循环问题（JDK 1.7）​

  • 触发条件: 并发扩容时多个线程同时操作
  • 根本原因: 链表指针在扩容过程中形成环形结构
  • 后果: CPU使用率飙升，程序假死
  • JDK 1.8解决: 改用尾插法，避免了死循环

2. 数据丢失问题​

  • 场景: 多线程同时put操作
  • 原因: 非原子操作被中断，导致部分更新丢失
  • 表现: 数据不一致，size计数错误

3. 数据覆盖问题​

  • 场景: 并发put相同key
  • 原因: 缺乏同步机制，后写入覆盖先写入
  • 表现: 最终结果不可预期

HashMap解决方案对比​

解决方案性能线程安全推荐度说明
ConcurrentHashMap⭐⭐⭐⭐⭐✅⭐⭐⭐⭐⭐分段锁，高并发优化
Collections.synchronizedMap⭐⭐✅⭐⭐⭐全局锁，性能一般
Hashtable⭐✅⭐已过时，不推荐
自定义锁⭐⭐⭐✅⭐⭐⭐⭐灵活但复杂

HashMap ConcurrentHashMap优化​

JDK 1.7分段锁设计:

  • 将数据分为16个段(Segment)
  • 每个段独立加锁
  • 提高并发度，减少锁竞争

JDK 1.8优化改进:

  • 取消分段锁，使用CAS + synchronized
  • 锁粒度更细，锁住链表头节点
  • 红黑树优化，处理hash冲突

HashMap最佳实践​

选择指南:

  1. 高并发场景: 使用ConcurrentHashMap
  2. 低并发场景: 考虑Collections.synchronizedMap
  3. 单线程场景: 继续使用HashMap
  4. 读多写少: 考虑CopyOnWriteMap

注意事项:

  • 复合操作需要额外同步
  • 迭代过程中的并发修改
  • 性能测试验证选择

HashMap并发面试官视角​

该题考察候选人对并发编程的理解：

  • 要点清单: 理解HashMap并发问题；知道各种解决方案优缺点；了解ConcurrentHashMap原理；有实际并发编程经验

  • 加分项: 深入理解JDK版本差异；能分析性能影响；有线程安全设计经验；了解其他并发数据结构

  • 常见失误: 不了解死循环问题；混淆不同解决方案；忽视性能考量；缺乏实际并发经验

HashMap并发延伸阅读​