第4章 哈希表

4.1 哈希表基础与特性

哈希表的诞生可以追溯到20世纪50年代，当时计算机科学家们正在寻找一种能够实现快速数据访问的数据结构。1953年，IBM的研究员汉斯·彼得·卢恩首次提出了"散列"这一概念，他当时正在研究如何快速检索信息。卢恩意识到，如果能够通过某种数学函数直接将键转换为存储地址，就能实现近乎即时的数据访问，这种想法彻底改变了传统的数据检索方式。

在随后的发展中，1956年 Arnold Dumey 在《美国计算机协会通讯》上发表了一篇开创性论文，首次系统地描述了哈希技术的基本原理。Dumey提出了将键转换为整数索引的核心思想，并讨论了如何处理不同键映射到同一位置的冲突问题。这一时期的研究主要集中在理论探索上，研究人员试图找到能够均匀分布键的哈希函数，同时设计有效的冲突解决策略。

到了20世纪60年代末70年代初，随着计算机内存成本的下降和容量的增加，哈希表开始从理论走向实践。1968年，Wesley Peterson在其著作中详细分析了各种哈希方法的性能，为哈希表的实际应用奠定了理论基础。同时期，链地址法被广泛采纳作为解决冲突的主要方法，这种方法通过在哈希冲突的位置建立链表来存储多个元素，既简单又有效。

1980年代，随着关系数据库的兴起，哈希表迎来了大规模应用的黄金时期。数据库系统需要快速的数据检索能力，而哈希表的O(1)平均时间复杂度使其成为索引结构的理想选择。这一时期还出现了动态哈希和可扩展哈希等技术，解决了早期哈希表固定大小的限制。这些创新使得哈希表能够在使用过程中动态调整大小，进一步提升了其实用性和性能表现。

进入21世纪，哈希表已成为所有主流编程语言的标准配置，如Java的HashMap、Python的dict、C++的unordered_map等。现代哈希表结合了先进的哈希函数、优化的冲突解决策略和动态扩容机制，在保持高效性能的同时提供了丰富的API接口。从最初的学术概念到如今无处不在的基础数据结构，哈希表的发展历程体现了计算机科学中理论创新与实际应用的完美结合。

4.1.1 哈希表介绍与优势分析

通过对哈希表诞生过程的了解，我们知道了哈希表是一种非常重要的数据结构，但是很多学习编程的人一直搞不懂哈希表到底是如何实现的。在这一章节中，我们就一点点来实现一个自己的哈希表。通过实现来理解哈希表背后的原理和它的优势，正如刚才所说，21世纪几乎所有的编程语言都有直接或者间接的应用这种数据结构，应用非常广泛，这也是我们需要学习它的原因之一。

哈希表通常是基于数组进行实现的，但是相对于数组，它也很多的优势，如以下4点：

（1）它可以提供非常快速的插入-删除-查找操作。

（2）无论多少数据，插入和删除值都接近常量的时间：即O(1)的时间复杂度。实际上，只需要几个机器指令即可完成。

（3）哈希表的速度比树还要快，基本可以瞬间查找到想要的元素。

（4）哈希表相对于树来说编码要容易很多。

数组的这些操作对应的时间复杂度在O(n)左右，这时间复杂度并不算高，但基于数组的哈希表，对应的时间复杂度却能达到O(1)级别，这是怎么做到的？在第2点有说明通过机器指令，那什么是机器指令呢？这是我们本章所要学习的。

但所有的数据结构都不是完美的，他们都有特定的应用场景，所以哈希表相对于数组的也有一些不足，如以下2点：

（1）哈希表中的数据是没有顺序的，所以不能以一种固定的方式(比如从小到大)来遍历其中的元素（没有特殊处理情况下）。

（2）通常情况下，哈希表中的key是不允许重复的（哈希表的结构是key/value），不能放置相同的key，用于保存不同的元素。

因此不存在只用哈希表，不用数组的情况，他们之间的关系并不是上下位替代，在学习数据结构中，所遇到的所有数据结构都是如此。但我们只是说了哈希表的诞生背景与优劣势，却依旧不知道哈希表到底长什么样子。这也是哈希表不好理解的地方，不像数组和链表，甚至是树一样直接画出你就知道它的结构，甚至是原理了。哈希表的结构就是数组，但是哈希表神奇的地方在于对数组索引值的一种变换，这种变换我们可以使用哈希函数，通过哈希函数可以获取到HashCode（散列码）。不着急，我们慢慢来认识它到底是什么。

哈希表映射如图4-1所示。想要真正理解哈希表并不容易，图例只能作为一个简单的参考。

图4-1 哈希表映射

假设我们有一些数据（keys）：John Smith、Lisa Smith，Sandra Dee。由于哈希表实际就是一个数组，我们将这三个数据放入数组之中，然后需要在不利用数组索引的情况下，找到我们想要的值。

▼
ts
复制代码
const arr: string[] = ["John Smith", "Lisa Smith", "Sandra Dee"]

为什么有好好的索引不用？这是一个很好的问题！数据结构与算法存在一个内蕴的精神：极致优化。对于这一点的触动，我最早是在学习操作系统时所感受到的。无所不用其极的去优化结构，去节省哪怕一点点的空间，提高哪怕一点点的性能等等。正是极致优化的思想，让人不禁锢于满足"能用"，永远追问"能不能更好"。通过数组索引访问所需数据的时间复杂度是O(n)，如果还想优化，就只能往O(1)去考虑。

我很钦佩计算机科学家们的这种思想精神，打破原有的思维定式。那么当我们已经知道哈希表确实是能在数组的基础上做到将时间复杂度优化到O(1)级别，在抛弃数组索引的优势后，我要怎么样更快的找到想要的值？在这个过程中，我需要舍弃哪些部分来换取对应的成果？（由于哈希表并不能上位替代数组，这意味着哈希表必然是牺牲了部分，来换取在某一方向更极致的提升）

能对数组进行二分查找吗？时间复杂度虽不能提升到O(1)，但也达到了对数级别。很可惜不行，因为我们数组内填充的是字符串，是很难像数字那样排序的，当填充的不是字符串而是对象时，就更难做到了，所以这条路是不通的。这好像只能一个个的查找（顺序查找），回到O(n)的原点，毫无头绪确实令人气馁。

如果我们有一个函数（hash function），能将数组中的这些值，一个个的直接映射到某个整理好的地方（不按照顺序）。那么我就能在知道数组某个值的情况下，直接去整理好的映射处找到对应的位置。但这时候我有疑惑了，去映射处找，那不还得一个个找？除非我们不一个个去找，这让我想起来数组的访问级别为什么是O(1)，是通过计算内存地址直接拿到对应位置。那我们能不能在映射处做出同样的处理，使其位置能够被计算？

这很有意思，如果做到能计算，那么查找的过程就从一个个查找跨越到直击目标。在已经实现哈希表的当下，可以明确说，这是可以的，我们已经走在正确的道路上了，哈希表计算位置如图4-2所示。

图4-2 哈希表计算位置

4.1.2 现实案例与存储需求

我们通过二个案例，案例需要你挑选某种数据结构，而你会发现最好的选择就是哈希表。

案例一：公司使用一种数据结构来保存所有员工。

案例二：使用一种数据结构存储单词信息，比如有50000个单词。找到单词后每个单词有自己的翻译&读音&应用等等。

我们先来说明案例一：假如一家公司有1000个员工，现在我们需要将这些员工的信息使用某种数据结构来保存起来，你会采用什么数据结构呢？到目前为止，我们学习过4种数据结构，即数组、栈、队列、链表。适合存储数据的有数组和链表，那这两种方案适合案例一的需求吗？

（1）方案一，数组。可以按照顺序将所有的员工依次存入一个长度为1000的数组中，每个员工的信息都保存在数组的某个位置上。但是我们要查看某个具体员工的信息怎么办呢？一个个找吗？不太好找。数组最大的优势是通过索引值去获取信息，所以为了可以通过数组快速定位到某个员工，最好给员工信息中添加一个员工编号(工号)，而编号对应的就是员工的索引值。当查找某个员工的信息时，通过员工编号可以快速定位到员工的信息位置。

（2）方案二，链表。链表对应插入和删除数据有一定的优势。但是对于获取员工的信息，每次都必须从头节点遍历到尾节点，这种方式显然不是特别适合我们这里。

这样看最终方案似乎就是数组了。但是数组还是有缺点，什么缺点呢？如果我们只知道员工的姓名，比如coderwhy，但是不知道coderwhy的员工编号，我们怎么办呢？那只能线性查找了，效率就非常的低。能不能有一种办法，让coderwhy的名字和他的员工编号产生直接的关系呢？也许是通过和数组查询类似的计算方式，如图4-3所示。

图4-3 员工姓名与员工数据信息关联

在不知道数组索引的情况下，JS查询到数组具体某个数据的方式对应时间复杂度如下代码块。

▼
ts
复制代码
const arr: string[] = ["John Smith", "Lisa Smith", "Sandra Dee", "coderwhy"]

// 知道具体索引的查询-时间复杂度 O(1)
const element = arr[3];

//不知道具体索引的查询-时间复杂度O(n)
// 1. find() 方法 - 推荐用于查找单个元素
// 时间复杂度: O(n) - 最坏情况遍历整个数组
const element1 = arr.find(item => item === "coderwhy");
console.log(element1); // "coderwhy"

// 2. findIndex() + 索引访问
// 时间复杂度: O(n) - 查找索引 + O(1) 访问
const index1 = arr.findIndex(item => item === "coderwhy");
const element2 = index1 !== -1 ? arr[index1] : undefined;

// 3. indexOf() + 索引访问 (适合简单值匹配)
// 时间复杂度: O(n) - 查找索引 + O(1) 访问
const index2 = arr.indexOf("coderwhy");
const element3 = index2 !== -1 ? arr[index2] : undefined;

// 4. for 循环 + break (性能最佳的手动查找)
// 时间复杂度: 最好 O(1), 最坏 O(n), 平均 O(n/2)
let element4;
for (let i = 0; i < arr.length; i++) {
  if (arr[i] === "coderwhy") {
    element4 = arr[i];
    break; // 关键：找到后立即退出
  }
}

// 5. for...of 循环 + break
// 时间复杂度: 最好 O(1), 最坏 O(n), 平均 O(n/2)
let element5;
for (const item of arr) {
  if (item === "coderwhy") {
    element5 = item;
    break;
  }
}

// 6. includes() + find() 组合 (不推荐，效率低)
// 时间复杂度: O(n) + O(n) = O(2n) ≈ O(n)
const element6 = arr.includes("coderwhy")
  ? arr.find(item => item === "coderwhy")
  : undefined;

// 7. filter() 方法 (适合查找多个匹配项)
// 时间复杂度: O(n) - 总是遍历整个数组
const elements = arr.filter(item => item === "coderwhy");
const element7 = elements[0]; // 取第一个匹配项

// 8. reduce() 方法 (复杂场景使用)
// 时间复杂度: O(n) - 遍历整个数组
const element8 = arr.reduce((found, item) => {
  return found || (item === "coderwhy" ? item : null);
}, null);

// 9. some() 方法 + find() (测试存在性后查找)
// 时间复杂度: O(n) + O(n) = O(2n) ≈ O(n)
let element9;
if (arr.some(item => item === "coderwhy")) {
  element9 = arr.find(item => item === "coderwhy");
}

即当我们知道员工姓名时，我们就能获取到它的索引值（将员工姓名直接转换为数组索引？），而再通过索引值我就能获取到coderwhy的信息呢？这样的方案已经存在了，就是使用哈希函数，让某个key的信息和索引值对应起来。并且员工姓名与数组索引之间的关联需要是固定的，不固定所产生的无序将导致我们无法进行寻找行为。

其次是案例二：我们使用一种数据结构存储单词信息，比如有50000个单词，找到单词后每个单词有自己的翻译&读音&应用等等。

这个案例更加明显能感受到数组的缺陷，我拿到一个单词 Iridescent，我想知道这个单词的翻译/读音/应用，怎么才能从数组中查到这个单词的位置呢？线性查找吗？那最多的情况有50000次比较，如果我们使用数组来实现这个功能，效率会非常非常低，这只能证明我们一定没有学习过数据结构。

那么链表呢？链表更是必须从头节点开始遍历查找，因此直接不考虑。

数组与链表的方案都无法满足我们的需求，有没有一种方案，可以将单词转成数组的索引值呢？如果单词转成数组的索引，那么以后我们要查找某个单词的信息，直接按照索引值一步即可访问到想要的元素。

4.2 哈希化与哈希函数

4.2.1 字母转数字方案

在4.1.2小节的两个案例中，似乎都指向了同一目标：将字符串转成索引值。因为索引值通过计算的方式能以O(1)级别的时间复杂度达成寻找目的。但是，怎么样才能将一个字符串转成数组的索引值呢？

数组的索引值是以数字的形式体现的，因此可以将问题转化为：怎么样才能将一个字符串转成数字？

现在我们需要设计一种方案，可以将单词转成适当的下标值：其实计算机中有很多的编码方案就是用数字代替单词的字符，即字符编码。例如ASCII编码：a是97，b是98，依次类推122代表z。我们也可以设计一个自己的编码系统，比如a是1，b是2，c是3，依次类推，z是26。当然我们可以加上空格用0代替，就是27个字符(不考虑大写问题)，但是，有了编码系统后，一个单词如何转成数字呢？

方案一：数字相加。我们可以将每个单词字符的编码求和，例如单词cats转成数字为：3+1+20+19为43，那么43就作为cats单词的下标存在数组中。

但方案一有一个很明显的问题：很多单词最终的下标可能都是43，例如如was/tin/give/tend/moan/tick等等，如果存入后来的数据，就会造成数据覆盖的问题。一个下标存储这么多单词显然是不合理的。我们有两个选择，要么做到每个单词通过编码所产生的数字都不同，要么就解决数据覆盖问题并降低重复冲突的情况。

方案二：幂的连乘。数组相加的方案过于普通，重合度极高。幂的连乘可以基本上保证它的唯一性，例如：7654 = 7*10³+6*10²+5*10+4。我们的单词也可以使用这种方案来表示，例如cats = 3*27³+1*27²+20*27+17= 60337，这样得到的数字可以基本保证它的唯一性，不会和别的单词重复，是科学计数法的一种变种实践表达。

问题是如果一个单词是zzzzzzzzzz(一般英文单词不会超过10个字符)，那么得到的数字超过7000000000000（13位），这种方式所产生的数字大小与将编码拼接起来也不逞多让。这让我们怀疑数组可以表示这么大的下标值吗？就算能创建这么大的数组，事实上有很多是无效的单词，数组绝大多数开辟的空间都是浪费的（空槽），创建这么大的数组是没有意义的。

第一种方案(把数字相加求和)产生的数组下标太少。第二种方案(与27的幂相乘求和)产生的数组下标又太多。所以，我们是不是需要考虑牺牲一下唯一性，为了唯一性所需要付出的代价有些过大了。解决数据覆盖问题并降低重复冲突的做法似乎更容易实现。

4.2.2 索引压缩算法

我们需要考虑是否能够解决内容覆盖的问题，以及对唯一性的要求有多高。我们需要在唯一性和空间效率之间找到平衡。

如果能解决内容覆盖的问题，那唯一性并不是必要的要求，不需要追求绝对唯一性，只需要在有限范围内尽可能均匀分布，分布得越散，查找性能就越无限接近于O(1)，处在一个O(1)~O(n)的状态，n的大小取决于均匀分布得有多好。如果通过计算的方式，最多只有两三个内容的重复，那对只有两三个内容进行顺序查找，其性能实际也极其接近O(1)。

因此能否将两种方案结合一下，现在需要一种压缩方法，把幂的连乘方案系统中得到的巨大整数范围压缩到可接受的数组范围中。对于英文词典，多大的数组才合适呢？如果只有5万个单词，我们可能会定义一个长度为5万的数组，那样就可以完美利用所有空间。但是实际情况中，往往需要更大的空间来存储这些单词，因为我们不能保证单词会映射到每一个位置。在如今硬件发展迅猛的时代，空间复杂度相对于时间复杂度是更宽容的，因此我们有限考虑牺牲一部分空间性能。定义长度5万的数组是理想情况，那么我们定义两倍大小，即长度为10万的数组空间，留下足够的稀释分布的缓冲余地，又不至于让空间浪费到幂的连乘那种程度。

那么如何压缩呢？现在要找一种方法，把0到超过7000000000000的范围，压缩为从0到100000。有一种简单的方法就是使用取余操作符，它的作用是得到一个数被另外一个数整除后的余数。

取余操作能够将大范围的数字映射到有限的小范围空间中。具体来说，如果我们希望将0199这样的大数字范围压缩到09的小范围中，只需通过简单的取余运算：index = largeNumber % smallRange。例如，13除以10余数为3，157除以10余数为7，这样任何数字经过取余运算后都会落在0~9的范围内。虽然这种方法仍可能产生重复的索引值，但重复的概率已经显著降低。

在实际的哈希表设计中，当我们拥有一个长度为100000的数组却只需要存储50000个单词时，通过取余操作可以将单词哈希值的大范围映射到有限的数组索引范围内。这就好比从0~199的数字范围内随机选取5个数字放入长度为10的数组中，虽然理论上可能发生重复，但实际概率很小。更重要的是，即使发生了索引重复的情况，我们也有冲突解决机制来应对，即我们前面所说的解决数据覆盖问题的需求。

这种基于取余运算的压缩方法体现了对需求与限制的抉择，既不追求绝对的唯一性而浪费大量空间，也不因过度压缩而导致无法接受的冲突率。通过合理的参数选择和冲突处理策略，我们能够在有限的空间内实现高效的键值存储和检索。

理解上述内容，我们就理解了哈希表的原理了，像取余操作实际上是实现哈希表范围压缩的核心技术，我们来看看以下3个概念：

（1）哈希化：将大数字转化成数组范围内下标的过程，我们就称之为哈希化。

（2）哈希函数：通常我们会将单词转成大数字，大数字在进行哈希化的代码实现放在一个函数中，这个函数我们成为哈希函数。在4.5.1小节会详细说明。

（3）哈希表：最终将数据插入到的这个数组，对整个结构的封装，我们就称之为是一个哈希表。

如果我希望通过一个单词，查找到单词所对应的翻译&读音&应用，会怎么做？通过4.2.1与4.2.2小节的思考学习，我们会先获取到这一个单词，将单词通过幂的连乘转化为一个大数字，再通过哈希化将大数字变成一个索引值，最后通过索引值能够以接近O(1)的时间复杂度去查询单词对应的翻译&读音&应用。我们所做的是通过单词能计算出一个固定的索引值，往索引值内存放数据再进行读取。

我们将单词转为索引值的过程封装到一个函数中，这个函数就被称为哈希函数。

▼
ts
复制代码
// 哈希函数伪代码
function hashFn(str: string): number {
  cats => 幂的连乘 => 大的数字 => 哈希化 => 索引值
}

但是，我们还有问题需要解决：虽然，我们在一个100000的数组中，放50000个单词已经足够。但是通过哈希化后的下标值依然可能会 重复，如何解决这种重复所导致的内容覆盖问题呢？

4.3 地址冲突解决方案

什么是冲突？尽管5万个单词，我们使用了10万个位置来存储，并且通过一种相对比较好的哈希函数来完成。但是依然有可能会发生冲突。比如Hope这个单词，通过哈希函数得到它数组的下标值后，发现那个位置上已经存在一个单词Happy，因为Hope经过哈希化后和Happy得到的下标是相同的（此处为随手举例，未经验证，因此实际情况不一定相同）。出现下标相同的情况称为冲突。

虽然我们不希望这种情况发生，当然更希望每个下标对应一个数据项，但是通常这是不可能的。冲突不可避免，我们只能解决冲突。数组索引重复导致的覆盖问题如图4-4所示。

图4-4 数组索引重复-覆盖问题

就像之前0~199的数字选取5个放在长度为10的单元格中，如果我们随机选出来的是33，82，11，45，90，那么最终它们的位置会是3-2-1-5-0，没有发生冲突。但是如果其中有一个33，还有一个73呢？那么就会发生了冲突。我们需要针对这种冲突提出一些解决方案，虽然冲突的可能性比较小，但我们依然需要考虑到这种情况，以便发生的时候进行对应的处理代码。

有两种常见的方案来解决这类冲突：

（1）链地址法。

（2）开放地址法。

最主要的是链地址法，是需要着重理解学习的，而开放地址法毕竟难理解，而且在如今已经很少使用了，因此不追求必须掌握。

4.3.1 链地址法

链地址法是一种比较常见的解决冲突的方案。(也称为拉链法)。当不同的键（key）通过哈希函数映射到同一个数组索引位置时，链地址法不是覆盖原有数据，而是在该位置创建一个链表结构，将所有映射到同一位置的键值对以链表节点的方式串联存储。

具体实现时，哈希表的每个数组元素不再直接存储单个键值对，而是存储一个链表头节点或指针。当发生哈希冲突时，新的键值对会以节点形式添加到对应位置的链表中。在查找操作时，系统先通过哈希函数定位到特定索引，然后遍历该位置的链表，通过键的比较来找到目标数据。如果我们理解了为什么产生冲突，当看到图就能立马理解链地址法是什么含义，链地址法如图4-5所示。

图4-5 链地址法

链地址法的最大优势在于它平衡了时间与空间效率。虽然最坏情况下所有键都映射到同一位置会导致退化为线性查找，但在良好的哈希函数设计和合理的负载因子控制下，每个链表的平均长度会保持很短，使得查找效率依然接近常数时间。链地址法实现相对简单，且能自然地处理动态数据增长，因此成为大多数编程语言中哈希表实现的首选冲突解决机制。

从图4-5中可以看出，链地址法解决冲突的办法是每个数组单元中存储的不再是单个数据，而是一个链条，这也是链地址法名称的由来。那这个链条使用什么数据结构呢？常见的是数组或者链表，例如是链表，也就是每个数组单元中存储着一个链表。一旦发现重复，将重复的元素插入到链表的首端或者末端即可，当查询时，先根据哈希化后的下标值找到对应的位置，再取出链表，依次查询找寻找的数据。

那么选择数组还是链表呢？其实都可以，效率上差不多，因为根据哈希化的index找出这个数组或者链表时，通常就会使用线性查找，这个时候数组和链表的效率是差不多的，大多数情况下并不需要在任意位置进行删除插入，链表的优势无法体现。当然在某些实现中，会将新插入的数据放在数组或者链表的最前面，因为觉得新插入的数据用于取出的可能性更大。这种情况最好采用链表，因为数组在首位插入数据是需要所有其他项后移的，链表就没有这样的问题。

当然，我觉得出于这个也看业务需求，不见得新的数据就访问次数会更多：比如我们微信新添加的好友，可能是刚认识的，联系的频率不见得比我们的老朋友更多，甚至新加的只是聊一两句。所以选择数据或者链表都是可以的，根据实际的业务需求去判断。

4.3.2 开放地址法

开放地址法是不好理解（难）以及现如今使用很少，所以不感兴趣可以直接跳过。

开放地址法的主要工作方式是寻找空白的单元格来添加重复的数据。其核心思想在于当哈希冲突发生时，不借助额外的链表结构，而是在原始数组内部通过系统性的探测序列寻找下一个可用的空槽位。具体来说，当目标位置已被占用时，算法会按照预先设定的探测方法（如线性探测的依次检查、二次探测的平方偏移或双重哈希的再散列）在数组中继续寻找，直到成功找到空位插入或确认元素不存在。开放地址法如图4-6所示。

图4-6 开放地址法

这种方法的最大优势在于所有数据都直接存储在数组内部，无需额外的指针开销，数据局部性更好，缓存性能更高。然而，开放地址法对负载因子（装填因子）更为敏感，当数组接近填满时性能会急剧下降，且删除操作较为复杂，通常需要采用特殊的标记机制而非直接清空槽位。

4.3.3 线性探测与二次探测

线性探测非常好理解：线性的查找空白的单元。例如我们插入数字32，经过哈希化得到的index=2，但是在插入的时候，发现该位置已经有了82。怎么办呢？线性探测就是从index位置+1开始一点点查找合适的位置来放置32，什么是合适的位置呢？空的位置就是合适的位置，在我们上面的例子中就是index=3的位置，这个时候32就会放在该位置。如果没有空的位置就会一直对index+1，直到找到空的位置为止。

那我们如何查询32呢？查询32和插入32比较相似。首先经过哈希化得到index=2，比如2的位置结果和查询的数值是否相同，相同那么就直接返回。不相同呢？线性查找，从index位置+1开始查找和32一样的。这里有一个特别需要注意的地方：如果32的位置我们之前没有插入，是否将整个哈希表查询一遍来确定32存不存在吗？并不是这样的，查询过程有一个约定，就是查询到空位置，就停止。因为查询到这里有空位置，32之前不可能跳过空位置去其他的位置。

如果我们想要删除32，虽然删除操作与插入查询类似，但需要注意删除操作一个数据项时，不可以将这个位置下标的内容设置为null，这是为什么呢？因为将它设置为null可能会影响我们之后查询其他操作，所以通常删除一个位置的数据项时，我们可以将它进行特殊处理(例如设置为-1，但这个内容一定要足够特殊唯一，不能和我们数据项有重复)。当我们之后看到-1位置的数据项时，就知道查询时要继续查询，但是插入时这个位置可以放置数据。

线性探测看起来好像很不错，对空间的利用率很高。但线性探测有一个比较严重的问题，就是聚集。什么是聚集呢？例如我在没有任何数据的时候，插入的是22-23-24-25-26，那么意味着下标值：2-3-4-5-6的位置都有元素。这种一连串填充单元就叫做聚集。聚集会影响哈希表的性能，无论是插入/查询/删除都会影响。例如我们插入一个32，会发现连续的单元都不允许我们放置数据，并且在这个过程中我们需要探索多次。

一旦需要探索多次，时间复杂度就会开始提升，探索次数越多，效率就越接近线性查找。也可以理解为一旦出现聚集效果，线性探测的效率就会大幅下降，那有没有办法解决聚集效果呢？二次探测可以解决一部分这个问题，我们一起来看一看。

我们刚才谈到，线性探测存在的问题：如果之前的数据是连续插入的，那么新插入的一个数据可能需要探测很长的距离。

二次探测在线性探测的基础上进行了优化，二次探测主要优化的是探测时的步长，什么意思呢？线性探测，我们可以看成是步长为1的探测，比如从下标值x开始，那么线性测试就是x+1，x+2，x+3依次探测。而二次探测，对步长做了优化，比如从下标值x开始，x+1²，x+2²，x+3²。这样就可以一次性探测比较长的距离，可以避免聚集带来的影响。二次探测实际思路与4.2.1小节中的字母转数字方案二的幂的阶乘类似，但数字跨越幅度没有那么夸张，虽然做不到极其接近唯一存储，对空间也不会那么浪费，也能减轻正常线性探测所导致的聚集效果。

但二次探测依然存在问题，例如我们连续插入的是32-112-82-2-192，那么它们依次累加的时候步长的相同的。也就是这种情况下会造成步长不一的一种聚集。还是会影响效率。(当然这种可能性相对于连续的数字会小一些)怎么根本解决这个问题呢？让每个人的步长不一样，一起来看看再哈希法吧。

4.3.4 再哈希法

为了消除线性探测和二次探测中无论步长+1还是步长+平法中存在的问题, 还有一种最常用的解决方案: 再哈希法。再哈希法是在开放地址法框架下为解决线性探测和二次探测中存在的聚集问题而提出的一种优化方案。

二次探测的算法产生的探测序列步长是固定的: 1, 4, 9, 16, 依次类推。现在需要一种方法: 产生一种依赖关键字的探测序列, 而不是每个关键字都一样。那么, 不同的关键字即使映射到相同的数组下标, 也可以使用不同的探测序列。再哈希法的做法就是: 把关键字用另外一个哈希函数, 再做一次哈希化, 用这次哈希化的结果作为步长，对于指定的关键字, 步长在整个探测中是不变的, 不过不同的关键字使用不同的步长。

想象一下，我们在一个巨大的停车场里停车，你的停车位是根据你的车牌号算出来的。但当你开到那个位置时，发现已经有一辆车停在那里了。

• 线性探测：就像你启动车子，一个接一个地查看后面的车位（+1, +1, +1...）。如果很多人都在做同样的事，停车场入口处就会堵成一团，这就是“聚集”。
• 二次探测：你不再一个个地找。第一次，你跳过1个车位去看看（+1²）；如果还满着，你就跳过4个车位去看看（+2²）；再满，就跳过9个（+3²）。这比线性探测跳得快，但如果很多人同时开始跳，还是会在某些区域形成新的“拥堵圈”。

现在，再哈希法登场了。它解决的核心问题是：“凭什么所有人的跳法都要一样？”

它的做法非常聪明：第一次计算还是用你的车牌号算出你“本该停”的第一个车位（比如是第5号车位）。第二次计算（关键）是当第5号车位被占后，它不再使用固定的“跳1个”或“跳4个”模式。而是把你的车牌号再输入另一个计算公式，算出一个专属于你的“跳远步长”。例如，你的车牌算出的步长是 3，另一辆车的车牌算出的步长可能是 7。

那么，大家的找车位路径就完全不同了：

（1）你的路线是：5号（被占）→ 5+3=8号 → 8+3=11号 → 11+3=14号 ...

（2）另一辆车的路线是：5号（被占）→ 5+7=12号 → 12+7=19号 ...

这个步长由第二个哈希函数决定，对于同一辆车（关键字）是固定不变的，但不同的车会得到不同的步长。这样，即使两辆车第一眼都看中了同一个车位，它们之后也会“分道扬镳”，各找各的，从而极大地分散了拥堵，解决了聚集问题。

第二次哈希化需要具备如下2点特点：

（1）和第一个哈希函数不同。（不要再使用上一次的哈希函数了, 不然结果还是原来的位置）

（2）不能输出为0。（否则, 将没有步长. 每次探测都是原地踏步, 算法就进入了死循环）

其实, 我们不用费脑细胞来设计了, 计算机专家已经设计出一种工作很好的哈希函数：stepSize= constant -(key % constant)。其中constant是质数, 且小于数组的容量。例如: stepSize= 5 -(key % 5), 满足需求, 并且结果不可能为0。

4.4 哈希表效率分析

对于链地址法来说，既然通过在数组中继续放数组或者链表，可以解决覆盖原有内容的问题，那么就能够做到在同一位置一直存放内容。可一直在同一位置存放内容，随着内容越多，链表就会越来越长，其后续查询、放置的效率就会越低（时间复杂度会提升），那么这会失去我们的优化初衷，因此使用链地址法一定不能存入无限个元素。

而对于开放地址法来说，如果有10个位置，我将这10个位置全部塞满，这基本上意味着无论我是线性探测还是二次探测亦或者再哈希法，我都不可能避免第一次的索引位置是与人重复，哪怕不断变换跳步规则，也会因为位置已经塞满而依旧出现重复问题，聚集效应在位置塞满之后已经变成必然的事情了。

无论哪种方法，由于我们做不到通过计算位置一步到位将每个元素放入到唯一的索引中，因此当空间利用效率越高，其可腾转的余地就越少，其时间复杂度就会飙升。而时间复杂度的优先度是高于空间复杂度的，在硬件不断升级的当下，牺牲部分空间来降低时间复杂度是一件划算的买卖。

4.4.1 装填因子概念

那我们要如何计算牺牲部分空间的比例呢？假设容量是10，元素是8，那么对空间的利用率是0.8，这个空间利用率我们称为装填因子。当状态因子越高，其时间复杂度就越高。比如在链地址法中出现了容量是10，元素是200的情况，那么装填因子就为20，意味着时间复杂度已经飙升到非常高的程度了，那么这时候最好牺牲一定的空间来扩容，从而降低时间复杂度。

在这里我们了解一个概念：装填因子。

装填因子表示当前哈希表中已经包含的数据项和整个哈希表长度的比值。装填因子= 总数据项/ 哈希表长度。

对于开放地址法来说，装填因子必须 < 1（因为每个位置只能放一个元素），当装填因子接近1时，会出现无法避免的聚集效应，性能急剧下降；而对于链地址法来说，装填因子可以 > 1（因为每个位置可以放多个元素），但装填因子过大会导致链表过长。

通过装填因子，我们能开始把握空间复杂度与时间复杂度之间的平衡标准。

总结下来，哈希表中执行插入和搜索操作效率是非常高的，如果没有产生冲突，那么效率就会更高。如果发生冲突，存取时间就依赖后来的探测长度。平均探测长度以及平均存取时间，取决于填装因子，随着填装因子变大，探测长度也越来越长。随着填装因子变大，效率下降的情况，在不同开放地址法方案中比链地址法更严重，所以我们来对比一下他们的效率，再决定我们选取的方案。

4.4.2 不同冲突解决方案效率对比

线性探测效率如图4-7所示。显示了线性探测时，探测序列(P)和填装因子(L)的关系，装填因子变化规律如下2点：

（1）当填装因子是1/2时，成功的搜索需要1.5次比较，不成功的搜索需要2.5次。

（2）当填装因子为2/3时，分别需要2.0次和5.0次比较。

如果填装因子更大，比较次数会非常大。应该使填装因子保持在2/3以下，最好在1/2以下，另一方面，填装因子越低，对于给定数量的数据项，就需要越多的空间。实际情况中，最好的填装因子取决于存储效率和速度之间的平衡，随着填装因子变小，存储效率下降，而速度上升。

图4-7 线性探索的性能

二次探测和再哈希法的性能相当。它们的性能比线性探测略好，对应性能图如图4-8所示。装填因子变化规律如下3点：

（1）当填装因子是0.5时，成功和不成的查找平均需要2次比较

（2）当填装因子为2/3时，分别需要2.37和3.0次比较

（3）当填装因子为0.8时，分别需要2.9和5.0次

因此对于较高的填装因子，对比线性探测，二次探测和再哈希法还是可以忍受的。

图4-8 二次探测和再哈希法的性能

链地址法的效率分析有些不同，一般来说比开放地址法简单。我们来分析一下这个公式应该是怎么样的。假如哈希表包含arraySize个数据项，每个数据项有一个链表，在表中一共包含N个数据项。那么，平均起来每个链表有多少个数据项呢？非常简单，N / arraySize。有没有发现这个公式有点眼熟？其实就是装填因子。

那么我们现在就可以求出查找成功和不成功的次数了，成功可能只需要查找链表的一半即可：1 + loadFactor/2；不成功呢？可能需要将整个链表查询完才知道不成功：1 + loadFactor。链地址法性能如图4-9所示。

图4-9 链地址法性能

经过上面的比较我们可以发现，链地址法相对来说效率是好于开放地址法的，变化更为均匀（稳定的优先度很高）。所以在真实开发中，使用链地址法的情况较多，因为它不会因为添加了某元素后性能急剧下降。例如在Java的HashMap中使用的就是链地址法。

以上就是哈希表的演变过程与理论知识，接下来我们就要来手写实现哈希表。

4.5 哈希表实现

4.5.1 哈希函数实现与霍纳法则

1.哈希函数设计

学习了很久的哈希表理论知识，我们发现在整个哈希表的演变过程中有一个非常重要的东西：哈希函数。好的哈希函数应该尽可能让计算的过程变得简单，提高计算的效率。因为哈希表的主要优点是它的速度，所以如果在速度上不能满足，那么就达不到哈希表设计的目的了。提高速度的一个办法就是让哈希函数中尽量少的有乘法和除法，因为它们的性能是比较低的。

那么设计好的哈希函数应该具备哪些优点呢？主要有以下2点：

（1）快速的计算：哈希表的优势就在于效率，所以快速获取到对应的hashCode非常重要，我们需要通过快速的计算来获取到元素对应的hashCode。

（2）均匀的分布：哈希表中，无论是链地址法还是开放地址法，当多个元素映射到同一个位置的时候，都会影响效率。所以，优秀的哈希函数应该尽可能将元素映射到不同的位置，让元素在哈希表中均匀的分布。

hashCode（哈希码）是什么？是通过哈希函数计算得到的整数值，在我们的单词案例中，是将单词转为数字的中间结果，这个数字随后会被进一步处理（如取模运算）以得到数组索引。在4.2小节与4.3小节中，我们详细学习了如何通过计算尽量得到不重复的数字。但除了注意聚集效应所导致的性能影响之外，我们还可以尽量去提高计算的速度与效率，也就是少使用乘除法。

哈希表通过哈希函数进行映射的图可参考一开始的图4-1。我们在4.2小节对哈希函数主要的操作为幂的连乘与取余操作，但这些操作能否还能优化？例如调整其中的乘法部分。

2.霍纳法则

在前面，我们计算哈希值的时候使用的方式是幂的连乘，即cats = 3*27³+1*27²+20*27+17= 60337。这种方式是直观的计算结果，那么这种计算方式会进行几次乘法几次加法呢？当然，我们可能不止4项（c、a、t、s），可能有更多项，如果抽象一下，这个表达式其实是一个多项式：a(n)x^n+a(n-1)x^(n-1)+…+a(1)x+a(0)。

现在问题就变成了多项式有多少次乘法和加法：

（1）乘法次数：n＋(n－1)＋…＋1＝n(n+1)/2。

（2）加法次数：n次。

那么，乘法运算的次数是O(N²)级别，而加法运算的次数是O(N)级别，因此幂的连乘对应的性能并不算高。对于这类多项式，可以采用秦九韶算法。秦九韶算法是中国南宋数学家秦九韶提出的一种多项式求值的高效算法，在西方被称为霍纳法则（后续统称霍纳法则）。它是一种通过递归的乘加操作来减少多项式求值计算量的优化方法。

霍纳法则的核心做法是通过嵌套的乘加运算来减少计算量。具体而言，算法从多项式的最高次项系数开始，初始化一个结果值，然后依次将当前结果乘以自变量x并加上下一个低次项系数，重复这一过程直到处理完所有常数项。例如，对于多项式P(x) = aₙxⁿ + aₙ₋₁xⁿ⁻¹ + ... + a₁x + a₀，霍纳法则将其重组为P(x) = a₀ + x(a₁ + x(a₂ + ... + x(aₙ₋₁ + x·aₙ)...))，这样只需进行n次乘法和n次加法即可完成计算，将乘法复杂度从传统的O(n²)降低到O(n)。这种简洁的迭代方式，不仅提升了计算速度，还保持了数值稳定性。

传统计算多项式的方式就像是一个笨拙的建筑师，他要计算一座大楼的总造价。这座楼有不同层高的房间（对应x的不同次幂），每种房型有各自的单价（对应系数）。他的做法是：先孤零零地盖好一个100层的房间，算出它的造价；再单独盖一个50层的房间，算出造价；接着盖一个10层的房间……最后把所有独立建筑的造价加起来。这种方法的问题在于，他每盖一种房型都从平地开始，重复计算了地基和底层结构，做了大量无用功，乘法次数自然就多了。

而霍纳法则是一位聪明的建筑师，他采用“从顶层开始，逐层向下叠加”的智慧策略。他先拿着最高层（比如100层）的图纸，但只计算单层的成本，然后他意识到：“既然100层是在99层之上加盖的，我何不利用这个结构呢？”于是，他的计算过程变成了：先假设一个基础成本（最高次项系数），然后乘以“单层成本系数”（x），再加上下一层的建设成本（低一次项的系数）；接着，把这个结果再乘以“单层成本系数”，再加入更下一层的成本……如此循环，直到把大堂（常数项）的成本也加进去。

这个过程的精妙之处在于，每一次乘法都在为后续所有低次项“预留”了空间。我们当前的计算结果，已经包含了之前所有高次项累积放大后的效应，我们只需要在此基础上做一次乘法和一次加法，就能把下一个低次项“吸纳”进来。这样一来，原本需要独立、重复计算的幂次（如x¹⁰⁰, x⁹⁹, ...），现在全部被巧妙地融合进一个滚雪球式的迭代过程中。最终，盖完整个大楼所需的“乘法操作”次数，仅仅等于大楼的层数（多项式的最高次数），从而将计算复杂度从平方级（O(n²)）奇迹般地降到了线性级（O(n)）。

经过变换之后，我们只需要N次乘法次数和N次加法次数。最核心的做法在于对乘法的复用，n的二次方是在n的基础上复乘一次，而n的三次方是在n的二次方基础上复乘一次，之前的低次项基础是能够运用上的，没必要每次都重新开始。霍纳法则本质上也只是复用了成果，这也算是一种抽象的过程，去除了重复的部分，如果从代码设计的角度来看，这其实就是一个递归函数。

通过霍纳法则，我们成功优化了优秀的哈希函数所需要具备的第一个条件：快速计算。那么接下来，我们要优化哈希函数尽可能将元素映射到不同位置，使其元素在哈希表中均匀分布。

4. 均匀分布

在设计哈希表时，我们已经有办法处理映射到相同下标值的情况：链地址法或者开放地址法。但是无论哪种方案，为了提供效率，最好的情况还是让数据在哈希表中均匀分布。因此，我们需要在使用常量的地方，尽量使用质数。在哈希表中使用质数进行取余操作能够使数据分布更加均匀，这主要源于质数的数学特性。质数是指除了1和自身外没有其他因数的数字，这种独特性使得当哈希表容量为质数时，对任意输入值取模后得到的结果分布更为分散。如果使用合数作为容量，输入数据中的某些规律性模式（如偶数列、特定倍数等）会与合数的因数产生共振，导致大量数据聚集在少数几个余数上，形成不均匀分布。

具体来说，当哈希表大小为质数时，取余操作相当于在一个数学上的"循环群"中进行运算，这确保了无论输入数据存在何种内在规律，计算结果都能最大程度地分散在整个值域范围内。例如，如果表大小为合数10，那么所有以0结尾的键都会映射到同一位置；而如果使用质数11，这种规律性就被打破，数据分布自然更加均匀。

哪些地方我们会使用到常量呢？主要有两个地方：

（1）哈希表的长度。

（2）N次幂的底数。

在哈希表的长度上使用质数，是为了在取模运算时打破数据规律性，使键值对能在数组中均匀分布，减少哈希冲突。在N次幂的底数上使用质数，是为了在计算哈希值时增加随机性（为了产生的数据不按照某种规律递增），避免不同键的相似部分产生相同的哈希模式，确保分布均匀性。

总之，质数是一个非常神奇的数字。我们建立这两处地方都使用质数。

5. Java中的HashMap

Java中的HashMap采用链地址法来解决哈希冲突，其设计中的一大特色是哈希表的初始长度设定为16，并且在每次自动扩容（我们还没聊到扩容，例如当装填因子>0.75时会自动扩容）时都严格要求长度必须保持为2的次幂。这一设计选择的核心目的在于优化键(key)到数组索引(index)的映射计算效率。HashMap通过一个巧妙的位运算公式来计算索引值：index = HashCode(Key) & (Length - 1)。这种计算方式本质上是利用位运算来替代传统的取模运算，因为计算机执行位运算的速度远快于除法取模运算。

以一个具体实例来说明，假设需要计算键"book"的索引位置。首先，"book"的哈希码计算结果为十进制的3029737，转换为二进制是101110001110101110 1001。当HashMap的初始长度为16时，Length - 1的结果是15，其二进制表示为1111。将这两个二进制数进行按位与运算：101110001110101110 1001 & 1111，由于15的二进制前导位都是0，这个运算实际上就是截取哈希码二进制的后四位，得到1001，即十进制的9，这就是该键在哈希表中的存储位置。这种设计确保了索引值始终落在数组范围内，同时利用2的次幂减一的特性（所有位均为1）使得哈希码的每一位都能参与索引计算，最大程度地保证数据分布的均匀性，既提高了计算效率，又维持了良好的哈希分布特性。

那为什么Java中的哈希表的初始长度为什么设为16（2的次幂）而非质数？主要基于性能优化和实际工程权衡的考虑。虽然质数作为哈希表长度在理论上能提供更好的分布均匀性，但HashMap采用了独特的索引计算方式index = HashCode(Key) & (Length - 1)，这种位运算在计算机底层的执行效率远高于传统的取模运算。当长度为2的次幂时，Length - 1的二进制形式恰好是一串连续的1（例如16-1=15，二进制为1111），这使得按位与运算能够高效地截取哈希码的低位作为索引，其效果等同于取模运算但速度更快。

HashMap通过精心设计的哈希函数来弥补非质数长度可能带来的分布缺陷，例如在Java 8中引入了树化机制，当链表长度超过阈值时会转换为红黑树，确保即使在冲突较多时性能也不会急剧下降。同时，扩容机制仍然保持长度为2的次幂，使得重新哈希时元素的新位置可以通过简单的位运算确定，大大提升了扩容效率。体现的是以空间换时间、以优化换均匀的设计哲学。

JavaScript中进行较大数据的位运算时容易会出问题，所以后续代码实现中还是使用了取模。另外，为了方便代码之后向开放地址法中迁移，容量还是选择使用质数。

如果我们来实现一个哈希函数，需要接收哪些参数，又返回哪些内容呢？现在由我们来设计一个哈希函数：

（1）接收参数：需要转换的数据，数据长度的最大值限制。

（2）返回参数：索引值。

▼
ts
复制代码
/**
 * 哈希函数, 将key映射成index
 * @param key 转换的key
 * @param max 数组的长度(最大的数值)
 * @returns 索引值
 */
function hashFunc(key: string, max: number): number {

}

export default hashFunc

通过以上代码我们完成哈希函数的初始化，接下来需要处理传入的数据，即使用霍纳法则将数据转为数字。需要经过以下3个步骤：

（1）初始化hashCode。

（2）通过霍纳法则将传入的数据转为HashCode（加快计算速度）。

（3）对hashCode取模（缩减数字大小到数组长度）。

在4.5.1小节中，说明了hashCode（哈希码）是通过哈希函数计算得到的整数值，即单词案例中的将单词转为数字的中间结果，最后将中间结果进行取模得出最终结果。

▼
ts
复制代码
/**
 * 哈希函数, 将key映射成index
 * @param key 转换的key
 * @param max 数组的长度(最大的数值)
 * @returns 索引值
 */
function hashFunc(key: string, max: number): number {
  // 1. 初始化HashCode
  let hashCode = 0;
  // 2. 使用霍纳法则将数据转为数字
  const length = key.length
  for (let i = 0; i < length; i++) {
    hashCode = 31 * hashCode + key.charCodeAt(i)
  }
  // 3. 对HashCode取模，返回最终结果
  const index = hashCode % max
  return index
}

export default hashFunc

代码中使用霍纳法则，我们一共循环具体乘法次数，每次都在原有基础上继续叠加相乘。并且在这里采用const length = key.length提前记录数据的长度，后续每次遍历就不需要重复的进行获取长度操作，而是直接获取已经计算好的长度。31实际为N次幂的底数，采用质数，实际情况不一定为31，根据实际需求决定。

然后根据以下测试函数来验证我们缩写的哈希函数是否正确无误。

▼
ts
复制代码
// 测试哈希函数
// loadFactor（装填因子） = 4 / 7 = 0.57...
console.log(hashFunc("coderwhy", 7)) // 0
console.log(hashFunc("XiaoYu", 7)) // 4
console.log(hashFunc("JavaScript", 7)) // 5
console.log(hashFunc("TypeScript", 7)) // 1

4.5.2 哈希表类创建

经过前面那么多内容的学习，我们现在可以真正实现自己的哈希表了。可能你学到这里的时候，已经感觉到数据结构的一些复杂性；但是如果你仔细品味，你也会发现它在设计时候的巧妙和优美；当你爱上它的那一刻，你也真正爱上了编程，爱上数据结构。

我们采用链地址法来实现哈希表：哈希表中的每个索引位置对应一个数组（称为桶，bucket）。需要注意的是，虽然也可以使用链表结构，但这里我们选择使用数组来实现每个桶。我们都已经实现过链表结构了，为什么不用链表作为桶呢？最主要的原因是不希望哈希表再去依赖一个从零实现的数据结构，尽量使用JavaScript已经提供给我们的数据结构，会更纯粹稳定。

每个桶中应存储什么内容？我们建议将键（key）和值（value）一并存入，为此，可以使用一个数组来存储每一组键值对（在其他编程语言中，使用元组可能是更合适的选择）。因此，最终形成的哈希表数据结构如下所示：哈希表的每个索引值指向一个桶（索引值实际是桶的内存地址），桶内包含若干键值对数组（元组），整体结构形如：[[ [k, v], [k, v], [k, v] ], [ [k, v], [k, v] ], [ [k, v] ]]。三层数组，第一层是哈希表，第二层是哈希表里的桶，第三层是桶内的每组键值对。哈希表结构组成如图4-10所示。

图4-10 哈希表构造组成

因此，如果创建一个哈希表类，我们需要定义三个属性：

（1）storage作为我们的数组，数组中存放相关的元素。

（2）count表示当前已经存在了多少数据。

（3）length用于定义数组长度。

其中storage是作为哈希表的存在，其本身是三维数组，内部应该是一个二维数组（桶），桶内是以[key,value]的键值对形式存在（元组），其中key为string类型，value不固定则可以使用泛型交由开发者自主决定。count与length属性是必要的，是用于计算装填因子的，当装填因子达到0.75以上时，就可以对数组进行扩容，防止出现高频的聚集效应。

▼
ts
复制代码
class HashTable<T = any> {
  // 创建一个数组, 用来存放链地址法中的链(数组)
  private storage: [string, T][][] = []
  // 定义数组的长度
  private length: number = 7
  // 记录已经存放元素的个数
  private count: number = 0
}

const hashTable = new HashTable()

4.5.3 插入与修改数据

哈希表的插入和修改操作是通过同一个函数进行，因为当使用者传入一个<Key,Value>时，如果原来不存在该key，那么就是插入操作；如果已经存在该key，那么就是修改操作。哦？为什么会是这样设计，难道不会导致功能耦合度过高吗？修改难道不是基于已有元素才修改的吗？如果功能重合在一起，我们自己也不知道这一操作下去是修改还是插入（新增）。

这种设计源于哈希表的本质特性——键的唯一性。在哈希表中，每个键都对应唯一的值，这就自然形成了一个"全有或全无"的操作语义：当我们向哈希表存入一个键值对时，系统不需要使用者预先声明这是新增还是修改，而是根据键是否已存在来自动决定操作类型。这种设计实际上降低了使用者的认知负担，因为使用者无需在调用前先检查键是否存在，也不必维护两套不同的操作逻辑。从使用体验来看，开发者只需关心"我希望这个键对应的值是什么"，而不必纠结于"这个键是新增的还是已有的"这种实现细节。

更重要的是，这种合并操作在性能上具有显著优势。如果分开设计，先检查存在性再决定执行插入或修改，会导致两次哈希计算和查找过程。而合并操作只需一次哈希计算和一次查找就能完成，在底层实现上更加高效。许多哈希表实现还会通过返回值来告知使用者实际操作类型（如返回旧值或null），让使用者能够在需要时获知操作结果，这样就既保证了接口的简洁性，又提供了足够的信息透明度。这种设计哲学体现了"让常见用例简单"的理念，虽然在理论上存在功能耦合，但在实际工程中却被证明是更优解。

哈希表的这种设计很有意思，也提醒了我们一定不要重复出现键，保证键的唯一性是插入与修改操作能够通过同一个函数实现的关键。因此我们在实现插入与修改数据时，需要先检查一遍哈希表中有没有对应的键，有则覆盖，无则插入，从而避免出现第二个重复的键。

插入与修改数据的该方法为put()方法，应该接收一个键值对，然后将该键值对插入到桶中。

▼
ts
复制代码
put(key: string, value: T) {

}

我们已经定义了storage属性（哈希表）了，但还不能直接将键值对数据插入到桶中（找不到对应的桶），因为哈希表中的每个索引值都指向一个桶，我们的键值对插入到桶中是需要经过霍纳法则计算出index索引值，从而决定插入的桶的位置。因此我们在实现put()方法时，需要先实现hashFunc()方法（哈希函数），将数据转为数字索引值。

hashFunc()方法应该是私有方法，计算索引值只作为内部计算使用，不应开放给使用者。

▼
ts
复制代码
private hashFunc(key: string, max: number) {
    // 1.计算hashCode cats => 60337(27为底的时候)
    let hashCode = 0
    const length = key.length
    for (let i = 0; i < length; i++) {
      // 霍纳法则计算hashCode
      hashCode = 31 * hashCode + key.charCodeAt(i)
    }

    // 2.求出索引值
    const index = hashCode % max

    return index
  }

然后我们可以继续来实现put()方法，需要实现以下3个步骤：

（1）传入的数据通过哈希函数转为数字索引值，获取插入的桶位置。

（2）检查插入的桶内键值对的key值是否有与传入的键值对的key值重复。

（3）有重复的key值则覆盖原有数据，无重复的key值则在桶内插入数据。

▼
ts
复制代码
// 插入/修改
put(key: string, value: T) {
  // 1.根据key获取数组中对应的索引值
  const index = this.hashFunc(key, this.length)

  // 2.取出索引值对应位置的数组(桶)
  let bucket = this.storage[index]

  // 3.判断bucket是否有值
  if (!bucket) {
    bucket = []
    this.storage[index] = bucket
  }

  // 4.确定已经有一个数组了, 但是数组中是否已经存在key是不确定的
  let isUpdate = false
  for (let i = 0; i < bucket.length; i++) {
    // 获取元组
    const tuple = bucket[i]
    // 获取元组中的key值
    const tupleKey = tuple[0]
    // 比对桶内key值与传入键值对的key值是否冲突
    if (tupleKey === key) {
      // 修改/更新的操作，key值冲突则覆盖元组的value
      tuple[1] = value
      // 判断key值已经冲突修改过，后续不再执行插入操作
      isUpdate = true
    }
  }

  // 5.如果上面的代码没有进行覆盖, 那么在该位置进行添加
  if (!isUpdate) {
    bucket.push([key, value])
    // 哈希表中的存放元素加1
    this.count++
  }
}

在检查插入的桶位置的key是否有与数据重复之前，我们需要先确认桶本身是否存在。因为哈希表本身是由数组构成，而初始化的数组内部都默认由undefined的构成，undefined是无法插入[key,value]数据的，因此根据key值获取到对应的索引值后，需要顺着索引值先去判断桶是否为undefined，若为undefined则创建桶（创建数组或者链表，这里创建的是数组）。桶存在之后，将[key,value]插入桶之中。

这里有一处思考，我们是否要在判断桶不存在之后，创建桶的同时，将数据直接插入？答案是不要这么做，因为这是后续往桶内插入或者修改数据的职能，如果在创建桶的同时进行插入，那么后续的插入与覆盖就会判断出桶内已经有对应的key了，多走一步覆盖操作，虽然结果是不变的，但步骤却多了。

遍历桶内数组（元组），提取其中每一对键值对的key值来与插入键值对的key值比对，若key值相同则执行覆盖操作。若未执行覆盖操作（key值未冲突），则往桶内push该键值对实现插入操作。

以上为put()方法的实现，通过以下测试用例判断是否可行。

▼
ts
复制代码
const hashTable = new HashTable()
hashTable.put("aaa", 100)
hashTable.put("aaa", 200)
hashTable.put("bbb", 300)

4.5.4 获取与删除数据

获取数据即通过键值对的key值获取到value值，我们创建get()方法，应具备key值参数，返回value值；若哈希表内无该key值（无法获取value值），则返回undefined或者-1。

▼
ts
复制代码
// 获取值
get(key: string): T | undefined {

}

获取value值过程为以下3步：

（1）将key值通过哈希函数转为数字索引值

（2）通过数字索引值锁定key值所对应的桶。

（3）遍历桶内的元组，比对元组的key值与传入的key值，锁定对应的value值并返回。

遍历桶内的元组是顺序查找，但由于均匀分布以及通过装填因子扩容，所以同一个桶内的元组数量是不会多的，顺序查找的损耗可接近忽略不计。

▼
ts
复制代码
get(key: string): T | undefined {
  // 1.根据key获取索引值index
  const index = this.hashFunc(key, this.length)

  // 2.获取bucket(桶)
  const bucket = this.storage[index]
  if (!bucket) return undefined

  // 3.对bucket进行遍历
  for (let i = 0; i < bucket.length; i++) {
    const tuple = bucket[i]
    const tupleKey = tuple[0]
    const tupleValue = tuple[1]
    if (tupleKey === key) {
      return tupleValue
    }
  }

  return undefined
}

get()方法对应的测试代码如下。

▼
ts
复制代码
console.log(hashTable.get('bbb'));

delete()删除数据方法需要根据键值对所对应的key值，删除对应的键值对。思路与获取数据类似，遍历桶内元组，对key值进行判断，找到对应目标后，调用Array.prototype.splice()实例方法删除目标对象，然后count属性减1。

▼
ts
复制代码
// 删除操作
delete(key: string): T | undefined {
  // 1.获取索引值的位置
  const index = this.hashFunc(key, this.length)

  // 2.获取bucket(桶)
  const bucket = this.storage[index]
  if (!bucket) return undefined

  // 3.遍历桶数组
  for (let i = 0; i < bucket.length; i++) {
    const tuple = bucket[i]
    const tupleKey = tuple[0]
    const tupleValue = tuple[1]
    if (tupleKey === key) {
      bucket.splice(i, 1)
      this.count--
      return tupleValue
    }
  }

  return undefined
}

测试用例可结合get()方法。即删除目标元组后（会返回删除的目标结果），使用get()方法获取目标元组。对比get()返回结果判断delete()方法效果是否生效。

4.5.5 哈希表扩容机制

目前哈希表的默认长度为质数7，我们是将所有的数据项放在长度为7的数组中的，因为我们使用的是链地址法，loadFactor可以大于1，所以这个哈希表可以无限制的插入新数据。但是，随着数据量的增多，每一个index对应的bucket会越来越长，也就造成效率的降低。所以需要在合适的情况对数组进行扩容，例如扩容两倍。

那么如何进行扩容？我们可以将哈希表容量简单的增大两倍（难道增大后不应该继续为质数吗？在4.6.1小节进行优化），但是这种情况下，所有的数据项一定要同时进行修改(重新调用哈希函数，来获取到不同的位置)，比如hashCode=12的数据项，在length=8的时候，index=4。在长度为16的时候呢？index=12。扩容所导致的所有数据项同时进行修改是一个耗时的过程，但是如果数组需要扩容，那么这个过程是必要的。

什么情况下应当进行扩容操作？比较常见的是当装填因子大于0.75时，我们希望哈希表自动扩容，从而消除聚集效果，保持哈希表的高性能。

要如何实现扩容机制？我有一个想法，每一次count属性加1变动时，就计算一次装填因子，当装填因子大于0.75时就进行扩容操作。而扩容操作需要实现以下两点：

（1）哈希表数组容量翻倍（长度*2）。

（2）对哈希表原有的所有数据重新哈希化后存放到正确位置。

由于哈希函数是通过哈希表长度来取余，因此当哈希表长度变化时，通过哈希函数计算的位置也会全部发生变化。但除了扩容，我们也可能缩容，因此步骤2中对哈希表原有的所有数据重新哈希化所基于的哈希表长度不应该是固定的，我们可以实现一个动态扩容缩容的resize()方法，该resize()方法传入扩容缩容后的哈希表所应具备的长度，并搭建临时数组存储扩容前的哈希表数据，再对原哈希表进行初始化并重新构建。

▼
ts
复制代码
private resize(newLength: number) {
  // 设置新的长度
  this.length = newLength

  // 获取原来所有的数据, 并且重新放入到新的容量数组中
  // 1.对数据进行初始化操作
  const oldStorage = this.storage
  this.storage = []
  this.count = 0

  // 2.获取原来数据, 放入新的数组中
  oldStorage.forEach(bucket => {
    if (!bucket) return

    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i]
      this.put(tuple[0], tuple[1])
    }
  })
}

resize()方法本质上是将原有哈希表迁移到新哈希表之中，但由于哈希表本身存在固定属性storage，因此我们并没有创建新的哈希表，而是将原哈希表备份之后，将原哈希表直接初始化清空作为新哈希表。重置新的哈希表长度之后，对新哈希表进行put()插入原哈希表的元组键值对数据操作。当resize()方法执行结束后，原哈希表备份会因临时变量而被直接垃圾回收。

当实现resize()方法之后，我们只需要判断装填因子大于0.75时，调用resize()方法，传入当前哈希表长度*2的数据即可完成扩容。而判断装填因子的时机正如我们一开始的想法，在count属性加1的时候，即put(()方法之中的插入数据操作部分。

▼
ts
复制代码
// 5.如果上面的代码没有进行覆盖, 那么在该位置进行添加
if (!isUpdate) {
  bucket.push([key, value])
  this.count++

  // 发现loadFactor比例已经大于0.75, 那么就直接扩容
  const loadFactor = this.count / this.length
  if (loadFactor > 0.75) {
    this.resize(this.length * 2)
  }
}

那么缩容也是同样的思路，当delete()方法删除数据时，count属性会不断的减1，这时候我们可以重新计算装填因子，当装填因子小于0.25的时候，将哈希表长度折半，且哈希表长度最短为7。且由于长度折半的话，是有可能出现无法整除的情况的，因此我们调用Math.floor()静态方法用于返回小于等于一个给定数字的最大整数。PS：使用Math.trunc()静态方法将数字的小数部分去掉，只保留整数部分也可以。

▼
ts
复制代码
// 删除操作
delete(key: string): T | undefined {
  // 1.获取索引值的位置
  const index = this.hashFunc(key, this.length)

  // 2.获取bucket(桶)
  const bucket = this.storage[index]
  if (!bucket) return undefined

  // 3.遍历桶数组
  for (let i = 0; i < bucket.length; i++) {
    const tuple = bucket[i]
    const tupleKey = tuple[0]
    const tupleValue = tuple[1]
    if (tupleKey === key) {
      bucket.splice(i, 1)
      this.count--

      // 如果loadFactor小于0.25, 缩容操作
      const loadFactor = this.count / this.length
      if (loadFactor < 0.25 && this.length > 7) {
        this.resize(Math.floor(this.length / 2))
      }

      return tupleValue
    }
  }

  return undefined
}

以上就是哈希表实现扩容与缩容的操作，核心是每次在count属性发生变化的时候重新计算装填因子，并立刻对装填因子进行判断操作，当装填因子达到临界点后，对哈希表进行扩容或者缩容操作。

4.6 哈希表优化

在完成哈希表的基本功能之后，我们可以对哈希表实现进行优化处理。这里存在一个很重要的技巧，当我们去实现一项功能时，优先度最高的是先将功能实现，然后再去考虑迭代优化。因此我们虽然知道扩容或者缩容是可以考虑使用质数的，但质数是不规律的，远没有直接将哈希表长度翻倍或者折半简单，因此在4.5.5小节中，我们并没有直接通过质数来实现扩容缩容。在接下来，我们会基于原有哈希表进行优化处理，也包括了使用质数扩容缩容。

4.6.1 质数判断算法

虽然在链地址法中将容量设置为质数，没有在开放地址法中重要，但是其实链地址法中质数作为容量也更利于数据的均匀分布。所以，我们还是完成一下这个步骤。那么我们要如何实现质数的扩容？最容易想到的是预定义质数表，提前写死一份包含能运用上的所有质数。每次扩容缩容时，直接从预定义质数表中拿到所需的质数。但我们所实现的哈希表想抽象成足够弹性的工具，就不能预定义质数表，因为我们无法预估使用者会将哈希表长度延长到什么程度。

实现质数扩容前，可以先讨论一个常见的面试题：如何判断一个数是质数？质数也称为素数，表示大于1的自然数中，只能被1和自己整除的数。那这其实可以看作一道数学题，对传入的数字从2开始整除，整除到自己之前最大的整数为止，如果传入的数字可以被整除则不是质数，反之是质数。

▼
ts
复制代码
/**
 * 根据传入的数字, 判断是否是一个质数
 * @param num 要判断的数字
 * @returns 是否是一个质数
 */
function isPrime(num: number): boolean {
  // 质数的特点: 只能被1和num整除
  // 如果传入的是8
  // 2~7
  for (let i = 2; i < num; i++) {
    if (num % i === 0) {
      return false
    }
  }

  // 2~7都遍历完成后, 依然是没有返回false
  return true
}

// 测试用例
console.log(isPrime(8))
console.log(isPrime(14))
console.log(isPrime(15))

console.log(isPrime(17))
console.log(isPrime(23))

export {}

4.6.2 容量质数优化

我们实现了isPrime()方法用于判断传入数字是否为质数，但该方法的效率并不高，还存在着性能提升的空间，对于isPrime()方法来说，每个数n都需要从2判断到n-1。假如我们需要判断135123是否为质数，是否意味着我们需要执行十几万次循环判断？这判断性能的损耗是否过大了？而如果只为了判断小数字的质数，还不如直接使用预定义质数表。

实际上并不需要判断这么多次，判断一个大数是否为质数时，确实不需要遍历所有可能的因数，只需要检查到该数的平方根即可。这种方法基于一个重要的数学原理：如果一个数n不是质数，那么它一定可以分解为两个因数a和b，即n = a * b。此时，a和b中必然有一个小于或等于√n，另一个大于或等于√n。这意味着，如果n存在任何因数（除了1和它本身），那么这些因数中至少有一个不会超过√n（后续部分其实都是√n以内的倍数）。

因此，在判断一个数是否为质数时，我们只需要检查从2到√n之间的整数是否能整除n即可。如果在这个范围内找不到任何因数，那么n就是质数；反之，如果在2到√n之间找到了任何一个能整除n的数，那么n就不是质数。这种优化方法将时间复杂度从O(n)降低到了O(√n)，对于大数判断来说性能提升是巨大的。

比如我们提到的135123为例，使用原始方法需要执行约13万次循环判断，而采用平方根优化后，只需要检查到约367（√135123的整数部分）即可，循环次数减少了99%以上。这种优化对于大数质数判断至关重要，使得我们能够在合理时间内完成大规模数据的质数检测任务。

Math.sqrt()静态方法可以返回一个数的平方根，我们只需要遍历判断到Math.sqrt(传入数字)即可，在原有代码基础上更改如下。

▼
ts
复制代码
/**
 * 根据传入的数字, 判断是否是一个质数
 * @param num 要判断的数字
 * @returns 是否是一个质数
 */
function isPrime(num: number): boolean {
  // 质数的特点: 只能被1和num整除
  // 11是否是一个质数
  // 平方根 3.xxx
  // 循环次数: 2~10
  // 16 = 2x8
  // 16 = 4x4
  const sqrt = Math.sqrt(num)
  for (let i = 2; i <= sqrt; i++) {
    if (num % i === 0) {
      return false
    }
  }

  // 2~7都遍历完成后, 依然是没有返回false
  return true
}


console.log(isPrime(8))
console.log(isPrime(14))
console.log(isPrime(15))

console.log(isPrime(17))
console.log(isPrime(23))


export {}

通过该重要的数学原理，我们实现了大数的质数判断，当判断的质数越大，性能提升的效果就越显著，因此该做法可以完全超越僵板的预定义质数表

4.6.3 完整哈希表实现

我们的优化目的是扩容哈希表长度时，是以质数为标准，那为什么要持续的去完成一个判断质数的方法并持续的优化呢？

因此动态的扩容缩容哈希表长度，我们更希望的是在哈希表长度翻倍或者折半的基础上，去拿到一个最近的质数来作为实际的扩容缩容哈希表长度。那么假如我们现在想要扩容，完全可以将哈希表长度直接翻倍（翻倍后的数字本身一定不是质数），然后加1判断是否为质数，返回false就继续对数字加1，直到数字为质数为止。将该质数在装填因子大于0.75时传入resize()方法中。缩容的原理同理。

将以上思路实现成一个getNextPrime()方法，接收一个数字，返回该数字往上最近的一个质数。

▼
ts
复制代码
private getNextPrime(num: number) {
  let newPrime = num
  while (!this.isPrime(newPrime)) {
    newPrime++
  }

  return newPrime
}

然后将getNextPrime()方法运用在扩容与缩容的put()方法和delete()方法中的判断装填因子临界点部分。完整哈希表实现代码如下：

▼
ts
复制代码
class HashTable<T = any> {
  // 创建一个数组, 用来存放链地址法中的链(数组)
  storage: [string, T][][] = []
  // 定义数组的长度
  private length: number = 7
  // 记录已经存放元素的个数
  private count: number = 0

  private hashFunc(key: string, max: number) {
    // 1.计算hashCode cats => 60337(27为底的时候)
    let hashCode = 0
    const length = key.length
    for (let i = 0; i < length; i++) {
      // 霍纳法则计算hashCode
      hashCode = 31 * hashCode + key.charCodeAt(i)
    }

    // 2.求出索引值
    const index = hashCode % max

    return index
  }

  isPrime(num: number): boolean {
    const sqrt = Math.sqrt(num)
    for (let i = 2; i <= sqrt; i++) {
      if (num % i === 0) {
        return false
      }
    }
  
    return true
  }

  private getNextPrime(num: number) {
    let newPrime = num
    while (!this.isPrime(newPrime)) {
      newPrime++
    }

    return newPrime
  }

  private resize(newLength: number) {
    // 设置新的长度
    let newPrime = this.getNextPrime(newLength)
    if (newPrime < 7) newPrime = 7
    this.length = newPrime

    // 获取原来所有的数据, 并且重新放入到新的容量数组中
    // 1.对数据进行初始化操作
    const oldStorage = this.storage
    this.storage = []
    this.count = 0

    // 2.获取原来数据, 放入新的数组中
    oldStorage.forEach(bucket => {
      if (!bucket) return

      for (let i = 0; i < bucket.length; i++) {
        const tuple = bucket[i]
        this.put(tuple[0], tuple[1])
      }
    })
  }

  // 插入/修改
  put(key: string, value: T) {
    // 1.根据key获取数组中对应的索引值
    const index = this.hashFunc(key, this.length)

    // 2.取出索引值对应位置的数组(桶)
    let bucket = this.storage[index]

    // 3.判断bucket是否有值
    if (!bucket) {
      bucket = []
      this.storage[index] = bucket
    }

    // 4.确定已经有一个数组了, 但是数组中是否已经存在key是不确定的
    let isUpdate = false
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i]
      const tupleKey = tuple[0]
      if (tupleKey === key) {
        // 修改/更新的操作
        tuple[1] = value
        isUpdate = true
      }
    }

    // 5.如果上面的代码没有进行覆盖, 那么在该位置进行添加
    if (!isUpdate) {
      bucket.push([key, value])
      this.count++

      // 发现loadFactor比例已经大于0.75, 那么就直接扩容
      const loadFactor = this.count / this.length
      if (loadFactor > 0.75) {
        this.resize(this.length * 2)
      }
    }
  }

  // 获取值
  get(key: string): T | undefined {
    // 1.根据key获取索引值index
    const index = this.hashFunc(key, this.length)

    // 2.获取bucket(桶)
    const bucket = this.storage[index]
    if (!bucket) return undefined

    // 3.对bucket进行遍历
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i]
      const tupleKey = tuple[0]
      const tupleValue = tuple[1]
      if (tupleKey === key) {
        return tupleValue
      }
    }

    return undefined
  }

  // 删除操作
  delete(key: string): T | undefined {
    // 1.获取索引值的位置
    const index = this.hashFunc(key, this.length)

    // 2.获取bucket(桶)
    const bucket = this.storage[index]
    if (!bucket) return undefined

    // 3.遍历桶数组
    for (let i = 0; i < bucket.length; i++) {
      const tuple = bucket[i]
      const tupleKey = tuple[0]
      const tupleValue = tuple[1]
      if (tupleKey === key) {
        bucket.splice(i, 1)
        this.count--

        // 如果loadFactor小于0.25, 缩容操作
        const loadFactor = this.count / this.length
        if (loadFactor < 0.25 && this.length > 7) {
          this.resize(Math.floor(this.length / 2))
        }

        return tupleValue
      }
    }

    return undefined
  }
}

const hashTable = new HashTable()
// length: 7
// count: 8
// loadFactor: 8 / 7 = 1.1xxxxx
hashTable.put("aaa", 100)
hashTable.put("aaa", 200)
hashTable.put("bbb", 300)
hashTable.put("ccc", 400)
hashTable.put("abc", 111)
hashTable.put("cba", 222)

console.log(hashTable.storage)

hashTable.put("nba", 333)
hashTable.put("mba", 444)
console.log(hashTable.storage)

// 如果loadFactor > 0.75进行扩容操作


hashTable.delete("nba")
hashTable.delete("mba")
hashTable.delete("abc")
hashTable.delete("cba")
hashTable.delete("aaa")

console.log(hashTable.storage)

export default HashTable

哈希表的理论与实现就到此为止，下一章我们会开始学习数据结构与算法中的树的知识。