JavaScript算法学习疑问：哈希表底层原理及findSumBetter函数解析

一、先掰扯清楚哈希表（Hashtable）的底层原理 #

哈希表本质就是个**键值对（Key-Value）**存储结构，核心思路是用哈希函数把键（Key）转换成数组的索引，这样就能直接通过索引快速定位对应的值，平均查找时间复杂度能达到O(1)，比普通遍历数组、链表快不止一个量级。

具体工作流程大概是这样：

• 1. 哈希函数转换：把要存储的键丢给哈希函数处理，得到一个整数（也就是数组的索引位置）。比如把字符串"orange"转成数字6，那就在数组第6个位置存对应的值。
• 2. 快速存取：存的时候直接把键值对放到哈希函数算出的索引位置；找的时候再用同一个哈希函数算键的索引，直接去对应位置取，不用遍历整个结构。
• 3. 冲突处理：难免会出现不同的键算出同一个索引的情况（这叫哈希冲突），常见的解决办法是链地址法：把同一个索引位置的元素改成链表，新元素就挂在链表后面；查找的时候先找到索引，再遍历链表找目标键。

说白了，哈希表就是用“空间换时间”的思路，把查找速度拉满的存储工具～

二、拆解findSumBetter函数的实现逻辑 #

先把完整代码贴出来：

function findSumBetter(arr, weight) { 
  var hashtable = {}; 
  for (var i = 0; i < arr.length; i++) { 
    var currentElement = arr[i], 
        difference = weight - currentElement; 
    if (hashtable[currentElement] != undefined) { 
      return [i, hashtable[currentElement]]; 
    } else { 
      hashtable[difference] = i; 
    } 
  } 
  return -1; 
}
console.log(findSumBetter([1,2,3,4,5], 9)); // 输出 [4, 3]

咱们逐行拆解，再结合例子走一遍：

1. 初始化哈希表 #

第一行var hashtable = {};创建了一个空对象（JS里的对象本身就是哈希表的一种实现），用来存“差值-索引”的映射关系。

2. 遍历数组的每一步 #

循环for (var i = 0; i < arr.length; i++)逐个处理数组元素，咱们拿arr = [1,2,3,4,5]、weight = 9来一步步看：

• 第1次循环（i=0，currentElement=1）：
  difference = 9 - 1 = 8
  此时哈希表是空的，hashtable[1]不存在，所以执行else：把hashtable[8] = 0，现在哈希表是{8: 0}

• 第2次循环（i=1，currentElement=2）：
  difference = 9 - 2 =7
  hashtable[2]不存在，执行else：hashtable[7] =1，哈希表变成{8:0, 7:1}

• 第3次循环（i=2，currentElement=3）：
  difference=9-3=6
  hashtable[3]不存在，执行else：hashtable[6] =2，哈希表是{8:0,7:1,6:2}

• 第4次循环（i=3，currentElement=4）：
  difference=9-4=5
  hashtable[4]不存在，执行else：hashtable[5] =3，哈希表变成{8:0,7:1,6:2,5:3}

• 第5次循环（i=4，currentElement=5）：
  difference=9-5=4
  这时候检查hashtable[5]——哎，哈希表里有这个键！对应的值是3（也就是元素4的索引）。所以直接返回[i, hashtable[currentElement]]也就是[4,3]，循环结束。

3. 核心逻辑 #

这个函数的巧妙之处在于：不用嵌套循环找配对元素，而是提前把“当前元素需要的配对值（weight - currentElement）”和它的索引存进哈希表。当遍历到某个元素时，如果它正好是之前某个元素需要的配对值，那直接就能从哈希表里拿到之前元素的索引，瞬间找到结果，时间复杂度降到O(n)，比暴力法的O(n²)高效太多。

如果遍历完整个数组都没找到配对，就返回-1。

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