如何使用Hash table在JavaScript中统计日期出现次数并生成对应数组
实现方案
用哈希表可以把时间复杂度从原嵌套循环方案的O(n²)降到O(n),实现逻辑如下:
- 以「年-月-日」拼接的唯一字符串作为哈希表key,value存储对应日期对象和累计出现次数
- 单次遍历所有日期完成计数统计,最后提取哈希表内容得到目标数组
完整实现代码
// 已有初始变量 var arrayDay= []; var arrayMonth = []; var arrayYear = []; // 目标数组:第一个存储日期对象,第二个存储对应出现次数 var dateList = []; var countAppears = []; // 初始化哈希表,此处用JS原生Map,也可替换为普通对象 var dateHash = new Map(); // 单次遍历完成计数统计 for(var i = 0; i < arrayYear.length; i++) { var year = arrayYear[i]; var month = arrayMonth[i]; var day = arrayDay[i]; // 生成日期唯一标识作为key var key = `${year}-${month}-${day}`; if(dateHash.has(key)) { // 已存在的日期直接计数+1 dateHash.get(key).count += 1; } else { // 新日期新增到哈希表,注意Date构造函数月份为0起始,需减1 var dateObj = new Date(year, month - 1, day); dateHash.set(key, { date: dateObj, count: 1 }) } } // 提取哈希表内容到目标数组 dateHash.forEach(item => { dateList.push(item.date); countAppears.push(item.count); })
注意事项
- 原嵌套循环代码存在拼写错误:
arrayYear.lenght应为arrayYear.length,会导致逻辑报错 - JS原生
Date对象的月份参数是0起始(0代表1月,11代表12月),创建日期对象时注意把存储的月份值减1,避免日期生成错误 - 如果需要兼容非常旧的JS环境,用普通对象
{}替代Map作为哈希表使用,逻辑完全一致
内容的提问来源于stack exchange,提问作者Ra1Ca7 eM
相关产品推荐
相关产品推荐

