哈希表

Hash，x。这个词没有定义——没有人知道什么是hash。

安布罗斯·比尔斯，《魔鬼的无删减词典》

在我们为新生的虚拟机添加变量之前，我们需要一种方法，能够根据变量名查找其对应的值。稍后，当我们添加类时，还需要一种方法来存储实例上的字段。哈希表是解决这些问题和其他问题的完美数据结构。

你可能已经知道什么是哈希表，即使你不知道它的名字。如果你是一名Java程序员，你称之为“HashMap”。C#和Python用户称之为“字典”。在C++中，它是一个“无序映射”。JavaScript中的“对象”和Lua中的“表”在底层都是哈希表，这也是它们如此灵活的原因。

哈希表，无论你的语言称之为何，都将一组**键**与一组**值**关联起来。每个键/值对都是表中的一个**条目**。给定一个键，你可以查找其对应的值。你可以添加新的键/值对，也可以按键删除条目。如果你为现有键添加一个新值，它将替换之前的条目。

哈希表出现在许多语言中，因为它们非常强大。这种强大的功能很大程度上来自一个指标：给定一个键，哈希表会在恒定时间内返回其对应的值，无论哈希表中存在多少键。

当你仔细想想，这真的很了不起。想象一下，你有一堆名片，我让你找到某个人。堆越大，花费的时间就越长。即使堆被很好地排序，你手动进行二分查找，你仍然需要O(log n)时间。但是使用哈希表，无论堆有10张名片还是100万张名片，找到那张名片所需的时间都是一样的。

20 . 1一组桶

一个完整的，快速的哈希表包含几个移动部件。我将通过解决几个玩具问题及其解决方案来逐一介绍它们。最终，我们将构建一个能够将任意一组名称与其值关联起来的数据结构。

现在，假设Lox对变量名的限制非常严格。如果变量名只能是单个小写字母。我们如何非常高效地表示一组变量名及其值呢？

由于只有26个可能的变量（如果将下划线视为一个“字母”，那么就有27个），答案很简单。声明一个大小为26的固定大小数组。我们将遵循传统，将每个元素称为一个**桶**。每个桶表示一个变量，从索引为零的a开始。如果数组中某个字母索引处的值存在，那么该键存在，其值为该值。否则，该桶为空，该键/值对不在数据结构中。

内存使用量非常棒——只是一个合理大小的数组。空桶会浪费一些空间，但并不多。没有节点指针、填充或其他你在使用链表或树时会遇到的东西。

性能甚至更好。给定一个变量名——它的字符——你可以减去a的ASCII值，并将结果用作数组索引。然后，你可以查找现有值，或者直接将新值存储到该位置。不会比这更快了。

这有点像我们对数据结构的柏拉图式理想。闪电般快，非常简单，内存紧凑。当我们添加对更复杂键的支持时，我们必须做出一些让步，但这是我们的目标。即使在添加哈希函数、动态调整大小和冲突解决之后，这仍然是每个哈希表的核心——一个你可以直接索引的连续桶数组。

20 . 1 . 1负载因子和包装键

将Lox限制为单个字母变量将使我们作为实现者的工作变得更容易，但它可能不是一种只提供26个存储位置的语言的有趣编程体验。如果我们稍微放松一下限制，允许变量最多八个字符长呢？

它足够小，我们可以将所有八个字符打包成一个64位整数，并轻松地将字符串转换为数字。然后，我们可以将其用作数组索引。或者，至少，如果我们能以某种方式分配一个295,148拍字节的数组，就能做到。随着时间的推移，内存变得越来越便宜，但还没有便宜到那种程度。即使我们可以创建一个那么大的数组，它也会非常浪费。除非用户开始编写比我们预期的更大的Lox程序，否则几乎每个桶都会为空。

即使我们的变量键覆盖了完整的64位数字范围，我们显然不需要那么大的数组。相反，我们分配一个数组，它的容量足以存储我们需要的条目，但不会过大。我们通过取值模数组大小来将完整的64位键映射到较小的范围。这样做本质上将较大的数字范围折叠到自身，直到它适合较小的数组元素范围。

例如，假设我们要存储“bagel”。我们分配一个包含八个元素的数组，足够存储它以及以后的更多内容。我们将键字符串视为一个64位整数。在像英特尔这样的低端机器上，将这些字符打包到一个64位字中会将第一个字母“b”（ASCII值为98）放在最低有效字节中。我们将该整数模数组大小（8）以将其限制在边界内，并得到一个桶索引2。然后，我们像往常一样在该位置存储值。

使用数组大小作为模数使我们能够将键的数字范围映射到适合任意大小数组的范围。因此，我们可以独立于键范围控制桶的数量。这解决了我们的浪费问题，但引入了新的问题。任何两个键的数字在除以数组大小时有相同余数的变量最终都将落入同一个桶中。键可能会发生**冲突**。例如，如果我们尝试添加“jam”，它也会最终落入桶2中。

我们可以通过调整数组大小来控制这种情况。数组越大，映射到同一个桶的索引就越少，发生冲突的可能性就越低。哈希表实现者通过衡量表的**负载因子**来跟踪这种冲突的可能性。它被定义为条目数量除以桶数量。因此，一个具有五个条目和16个元素数组的哈希表，其负载因子为0.3125。负载因子越高，发生冲突的可能性就越大。

我们减轻冲突的一种方法是调整数组大小。就像我们之前实现的动态数组一样，当哈希表填满时，我们将重新分配并增大它。但是，与普通的动态数组不同，我们不会等到数组完全填满才重新分配。相反，我们选择一个期望的负载因子，并在负载因子超过该因子时增大数组。

20 . 2冲突解决

即使负载因子非常低，冲突也可能发生。生日悖论告诉我们，随着哈希表中条目数量的增加，发生冲突的概率会非常快地增加。我们可以选择一个大的数组大小来降低概率，但这是一场输掉的游戏。假设我们要在哈希表中存储100个项目。为了将冲突的概率保持在仍然相当高的10%以下，我们需要一个至少包含47,015个元素的数组。为了将概率降到1%以下，我们需要一个包含492,555个元素的数组，对于每个正在使用的桶，需要超过4,000个空桶。

较低的负载因子可以使冲突更罕见，但鸽巢原理告诉我们，我们永远无法完全消除冲突。如果你有五只宠物鸽子，四个洞来存放它们，至少有一个洞最终会放超过一只鸽子。对于18,446,744,073,709,551,616个不同的变量名，任何合理大小的数组都有可能最终在同一个桶中包含多个键。

因此，当冲突发生时，我们仍然需要优雅地处理它们。用户不喜欢他们的编程语言只在大多数情况下才能正确查找变量。

20 . 2 . 1分离链接

解决冲突的技术分为两大类。第一种是**分离链接**。我们不将每个桶设置为包含单个条目，而是让它包含多个条目。在经典的实现中，每个桶都指向一个条目链表。要查找一个条目，你找到它的桶，然后遍历链表，直到找到一个具有匹配键的条目。

在所有条目都冲突到同一个桶中的灾难性情况下，数据结构会退化为一个单一的无序链表，其查找时间为O(n)。在实践中，通过控制负载因子和条目在桶之间的散布方式，很容易避免这种情况。在典型的分离链接哈希表中，一个桶中只有一个或两个条目的情况很少见。

分离链接在概念上很简单——它实际上是一个链表数组。大多数操作都很容易实现，即使是删除，我们将在后面看到，这可能是一个难题。但它不适合现代CPU。它有许多来自指针的开销，并且倾向于将小的链表节点散布在内存中，这对缓存使用不利。

20 . 2 . 2开地址散列

另一种技术称为 **开地址散列** 或（令人困惑的是）**闭散列**。使用此技术，所有条目都直接位于桶数组中，每个桶一个条目。如果两个条目在同一个桶中发生冲突，我们会找到一个不同的空桶来使用。

将所有条目存储在一个大而连续的数组中非常适合保持内存表示简单且快速。但这会使散列表上的所有操作都变得更加复杂。在插入条目时，其桶可能已满，导致我们查看另一个桶。该桶本身也可能已被占用，依此类推。寻找可用桶的过程称为 **探测**，您检查桶的顺序是 **探测序列**。

有几种算法可以确定要探测哪些桶以及如何决定哪个条目放在哪个桶中。这方面已经进行了大量的研究，因为即使是细微的调整也会对性能产生重大影响。而且，在像散列表这样使用广泛的数据结构中，这种性能影响会影响各种硬件能力的一大批实际程序。

与本书中通常的做法一样，我们将选择最简单的可以有效完成工作的方法。那就是传统的 **线性探测**。在查找条目时，我们会查看其键映射到的第一个桶。如果它不在那里，我们查看数组中的下一个元素，依此类推。如果我们到达数组的末尾，我们会绕回开头。

线性探测的优点是它对缓存友好。由于您直接按内存顺序遍历数组，因此它可以使 CPU 的缓存行保持满载且高效。缺点是它容易发生 **聚集**。如果您有很多键值在数值上相似的条目，您最终可能会得到许多彼此相邻的冲突、溢出桶。

与分离链接相比，开地址散列可能更难理解。我认为开地址散列类似于分离链接，只是节点的“链表”通过桶数组本身连接。而不是在指针中存储它们之间的链接，而是通过您查看桶的顺序隐式计算连接。

棘手的部分是，这些隐式列表中的多个列表可能交织在一起。让我们看一个涵盖所有有趣情况的示例。现在我们将忽略值，只关注一组键。我们从一个包含 8 个空桶的数组开始。

我们决定插入“bagel”。第一个字母“b”（ASCII 值 98），模数组大小（8）将其放入桶 2 中。

接下来，我们插入“jam”。它也希望进入桶 2（106 mod 8 = 2），但该桶已满。我们继续探测到下一个桶。它是空的，所以我们把它放在那里。

我们插入“fruit”，它顺利地进入了桶 6。

同样，"migas" 可以进入它首选的桶 5。

当我们尝试插入“eggs”时，它也希望进入桶 5。该桶已满，所以我们跳到桶 6。桶 6 也已满。请注意，其中的条目不属于同一个探测序列。“Fruit” 位于其首选的桶 6 中。因此，5 和 6 序列发生了冲突，并且已交织在一起。我们跳过它，最后将“eggs” 放入桶 7。

我们遇到了“nuts” 的类似问题。它不能进入它想要的桶 6。它也不能进入桶 7。所以我们继续前进。但我们已经到达数组的末尾，所以我们绕回桶 0 并将其放在那里。

在实践中，交织实际上并不构成太大问题。即使在分离链接中，我们也需要遍历链表以检查每个条目的键，因为多个键可以减少到同一个桶。对于开地址散列，我们需要进行相同的检查，这也涵盖了您跨越属于不同原始桶的条目的情况。

20 . 3散列函数

现在我们可以构建一个用于存储最长 8 个字符的变量名的相当有效的表，但这个限制仍然令人讨厌。为了放宽最后一个约束，我们需要一种方法来获取任意长度的字符串并将其转换为固定大小的整数。

最后，我们到达“散列表”的“散列”部分。**散列函数** 获取一些较大的数据块并将其“散列”以生成一个固定大小的整数 **散列码**，其值取决于原始数据的全部位。一个 **良好** 的散列函数具有三个主要目标

• **它必须是** **确定性** **的。** 相同的输入必须始终散列到相同的数字。如果同一个变量在不同时间点最终位于不同的桶中，那么找到它将非常困难。

• **它必须是** **均匀** **的。** 对于典型的输入集，它应该产生一个广泛且均匀分布的输出数字范围，尽可能减少聚集或模式。我们希望它将值 **分散** 到整个数字范围内，以最大限度地减少冲突和聚集。

• **它必须是** **快速** **的。** 散列表上的每次操作都需要我们先散列键。如果散列速度很慢，它可能会抵消底层数组存储的速度。

那里存在一大堆散列函数。有些是旧的，针对不再使用的架构进行了优化。有些旨在快速，另一些旨在加密安全。有些利用特定芯片的向量指令和缓存大小，另一些旨在最大限度地提高可移植性。

有些人将设计和评估散列函数视为他们的 **爱好**。我佩服他们，但我对数学不够精通，无法 **成为** 其中一员。因此，对于 clox，我选择了简单的，久经考验的散列函数，称为 FNV-1a，它多年来一直为我服务。考虑在您的代码中 **尝试** 不同的散列函数，看看它们是否会产生影响。

好的，这是一个关于桶、负载因子、开地址散列、冲突解决和散列函数的快速回顾。这篇文章有很多文字，但没有多少实际代码。如果您仍然觉得它很模糊，请不要担心。在我们完成编码后，一切都将变得清晰。

20 . 4构建散列表

与平衡搜索树等其他经典技术相比，散列表的优点是其实际数据结构非常简单。我们的散列表将进入一个新的模块。

#ifndef clox_table_h
#define clox_table_h

#include "common.h"
#include "value.h"

typedef struct {
  int count;
  int capacity;
  Entry* entries;
} Table;

#endif

散列表是条目的数组。与我们之前的动态数组一样，我们跟踪数组的已分配大小（capacity）和当前存储在其中的键/值对的数量（count）。计数与容量之比恰好是散列表的负载因子。

每个条目都是以下之一

#include "value.h"

typedef struct {
  ObjString* key;
  Value value;
} Entry;

typedef struct {

它是一个简单的键/值对。由于键始终是 **字符串**，因此我们直接存储 ObjString 指针，而不是将其包装在 Value 中。这样会更快一些，而且更小。

要创建一个新的空散列表，我们声明一个类似构造函数的函数。

} Table;

void initTable(Table* table);

#endif

我们需要一个新的实现文件来定义它。趁此机会，让我们把所有讨厌的包含文件都处理掉。

#include <stdlib.h>
#include <string.h>

#include "memory.h"
#include "object.h"
#include "table.h"
#include "value.h"

void initTable(Table* table) {
  table->count = 0;
  table->capacity = 0;
  table->entries = NULL;
}

与我们的动态值数组类型一样，散列表最初从零容量和一个 NULL 数组开始。我们只在需要时分配内存。假设我们最终分配了一些内存，我们需要能够释放它。

void initTable(Table* table);

void freeTable(Table* table);

#endif

以及它的辉煌实现

void freeTable(Table* table) {
  FREE_ARRAY(Entry, table->entries, table->capacity);
  initTable(table);
}

再次，它看起来就像动态数组。事实上，您可以将散列表视为一个动态数组，它有一个非常奇怪的插入项目策略。我们不需要在这里检查 NULL，因为 FREE_ARRAY() 已经优雅地处理了这种情况。

20 . 4 . 1散列字符串

在我们开始将条目放入表中之前，我们需要，嗯，散列它们。为了确保条目均匀地分布在整个数组中，我们希望有一个良好的散列函数，它查看键字符串的所有位。如果它只查看例如前几个字符，那么一系列共享相同前缀的字符串最终会在同一个桶中发生冲突。

另一方面，遍历整个字符串来计算散列速度有点慢。如果我们每次在表中查找键时都必须遍历字符串，那么我们会失去散列表的一些性能优势。因此，我们将做显而易见的事情：缓存它。

在 “object” 模块的 ObjString 中，我们添加

  char* chars;

  uint32_t hash;

};

每个 ObjString 存储其字符串的散列码。由于字符串在 Lox 中是不可变的，因此我们可以在最前面计算一次散列码，并确保它永远不会失效。尽早缓存它有一定意义：分配字符串并将它的字符复制过去已经是 O(n) 操作，因此在进行 O(n) 的字符串散列计算时，这也算是一个好时机。

每当我们调用内部函数来分配字符串时，我们都会传递它的散列码。

static ObjString* allocateString(char* chars, int length,
                                 uint32_t hash) {

  ObjString* string = ALLOCATE_OBJ(ObjString, OBJ_STRING);

该函数只是将散列存储在结构中。

  string->chars = chars;

  string->hash = hash;

  return string;
}

有趣的代码在这里

ObjString* copyString(const char* chars, int length) {

  uint32_t hash = hashString(chars, length);

  char* heapChars = ALLOCATE(char, length + 1);

没有魔法。我们计算散列码，然后将其传递过去。

  memcpy(heapChars, chars, length);
  heapChars[length] = '\0';

  return allocateString(heapChars, length, hash);

}

另一个字符串函数类似。

ObjString* takeString(char* chars, int length) {

  uint32_t hash = hashString(chars, length);
  return allocateString(chars, length, hash);

}

有趣的代码在这里

static uint32_t hashString(const char* key, int length) {
  uint32_t hash = 2166136261u;
  for (int i = 0; i < length; i++) {
    hash ^= (uint8_t)key[i];
    hash *= 16777619;
  }
  return hash;
}

这是 clox 中实际的、真正的“哈希函数”。该算法称为“FNV-1a”，是我知道的简短且不错的哈希函数。简洁性对于旨在向您展示每行代码的书籍来说无疑是一种美德。

基本思想非常简单，许多哈希函数遵循相同的模式。您从某个初始哈希值开始，通常是一个具有特定精心挑选的数学属性的常量。然后您遍历要哈希的数据。对于每个字节（或有时是字），您以某种方式将位混合到哈希值中，然后对结果位进行一些重新排列。

“混合”和“重新排列”的含义可能非常复杂。但是，最终的基本目标是均匀性—我们希望得到的哈希值尽可能地分散在数值范围内，以避免冲突和聚类。

20 . 4 . 2插入条目

现在字符串对象已经知道它们的哈希码，我们可以开始将它们放入哈希表中。

void freeTable(Table* table);

bool tableSet(Table* table, ObjString* key, Value value);

#endif

此函数将给定的键/值对添加到给定的哈希表中。如果该键的条目已经存在，则新值将覆盖旧值。如果添加了新条目，则该函数返回true。以下是实现

bool tableSet(Table* table, ObjString* key, Value value) {
  Entry* entry = findEntry(table->entries, table->capacity, key);
  bool isNewKey = entry->key == NULL;
  if (isNewKey) table->count++;

  entry->key = key;
  entry->value = value;
  return isNewKey;
}

大多数有趣的逻辑都在findEntry()中，我们很快就会讲到。该函数的作用是获取一个键，并确定它应该放在数组中的哪个桶中。它返回指向该桶的指针—数组中条目的地址。

一旦我们有了桶，插入就很简单。我们更新哈希表的尺寸，注意如果覆盖了已存在键的值，则不增加计数。然后我们将键和值复制到条目中相应的字段。

但是，这里还缺少一些东西。我们还没有实际分配条目数组。糟糕！在我们能够插入任何内容之前，我们需要确保我们有数组，并且它足够大。

bool tableSet(Table* table, ObjString* key, Value value) {

  if (table->count + 1 > table->capacity * TABLE_MAX_LOAD) {
    int capacity = GROW_CAPACITY(table->capacity);
    adjustCapacity(table, capacity);
  }

  Entry* entry = findEntry(table->entries, table->capacity, key);

这类似于我们之前为增长动态数组编写的代码。如果我们没有足够的容量插入项目，我们将重新分配并增长数组。GROW_CAPACITY()宏采用现有容量，并将其增长一个倍数，以确保我们在一系列插入中获得摊销的恒定性能。

这里有趣的是TABLE_MAX_LOAD常量。

#include "value.h"

#define TABLE_MAX_LOAD 0.75

void initTable(Table* table) {

这就是我们管理表负载因子的方式。当容量完全满时，我们不会增长。相反，我们会提前增长数组，当数组至少填充 75% 时。

我们很快就会讲到adjustCapacity()的实现。首先，让我们看看您一直在想的那findEntry()函数。

static Entry* findEntry(Entry* entries, int capacity,
                        ObjString* key) {
  uint32_t index = key->hash % capacity;
  for (;;) {
    Entry* entry = &entries[index];
    if (entry->key == key || entry->key == NULL) {
      return entry;
    }

    index = (index + 1) % capacity;
  }
}

此函数是哈希表的真正核心。它负责获取一个键和一个桶数组，并确定条目属于哪个桶。此函数也是线性探测和冲突处理发挥作用的地方。我们将使用findEntry()来查找哈希表中现有的条目，并决定在何处插入新的条目。

对于所有这些，它没有多少内容。首先，我们使用取模运算将键的哈希码映射到数组边界内的索引。这给了我们一个桶索引，理想情况下，我们可以在其中找到或放置条目。

有几个情况需要检查

• 如果该数组索引处条目的键为NULL，则该桶为空。如果我们使用findEntry()来查找哈希表中的内容，这意味着它不存在。如果我们使用它来插入，这意味着我们找到了一个添加新条目的位置。

• 如果桶中的键等于我们正在查找的键，则该键已经存在于表中。如果我们正在执行查找，这很好—我们找到了我们正在查找的键。如果我们正在执行插入，这意味着我们将替换该键的值，而不是添加新条目。

• 否则，该桶中有一个条目，但键不同。这是一个冲突。在这种情况下，我们开始探测。这就是for循环的作用。我们从条目理想情况下应该进入的桶开始。如果该桶为空或具有相同的键，我们就完成了。否则，我们前进到下一个元素—这是“线性探测”的线性部分—并在那里进行检查。如果我们越过数组的末尾，第二个取模运算符会将我们绕回开头。

当我们找到一个空桶或一个与我们正在查找的桶具有相同键的桶时，我们退出循环。您可能想知道无限循环。如果我们与每个桶发生冲突怎么办？幸运的是，由于我们的负载因子，这种情况不会发生。因为我们会在数组接近满时增长数组，所以我们知道总会有空桶。

我们直接从循环中返回，生成指向找到的条目的指针，以便调用者可以向其中插入内容或从中读取内容。在很久以前的tableSet()中，首先启动此操作的函数，我们将新条目存储在返回的桶中，我们就完成了。

20 . 4 . 3分配和调整大小

在我们能够将条目放入哈希表中之前，我们确实需要一个地方来实际存储它们。我们需要分配一个桶数组。这在以下函数中发生

static void adjustCapacity(Table* table, int capacity) {
  Entry* entries = ALLOCATE(Entry, capacity);
  for (int i = 0; i < capacity; i++) {
    entries[i].key = NULL;
    entries[i].value = NIL_VAL;
  }

  table->entries = entries;
  table->capacity = capacity;
}

我们使用capacity个条目创建一个桶数组。在分配数组之后，我们将每个元素初始化为空桶，然后将数组（及其容量）存储在哈希表的主结构中。此代码适用于我们在表中插入第一个条目时，并且我们要求第一次分配数组。但是，当我们已经有一个并需要增长它时该怎么办呢？

当我们做动态数组时，我们可以直接使用realloc()并让 C 标准库将所有内容复制过去。这对哈希表不起作用。请记住，为了选择每个条目的桶，我们对它的哈希键进行取模运算，以得到数组的大小。这意味着当数组大小发生变化时，条目可能会进入不同的桶。

这些新桶可能会有新的冲突，我们需要处理这些冲突。所以，最简单的方法是从头开始重建表，通过将每个条目重新插入新的空数组来实现。

    entries[i].value = NIL_VAL;
  }

  for (int i = 0; i < table->capacity; i++) {
    Entry* entry = &table->entries[i];
    if (entry->key == NULL) continue;

    Entry* dest = findEntry(entries, capacity, entry->key);
    dest->key = entry->key;
    dest->value = entry->value;
  }

  table->entries = entries;

我们从头到尾遍历旧数组。每当我们找到一个非空桶时，我们将该条目插入到新数组中。我们使用findEntry()，传入新数组而不是当前存储在 Table 中的数组。（这就是findEntry()直接指向 Entry 数组的指针而不是整个Table结构的原因。这样，我们可以在将这些内容存储在结构中之前，传入新的数组和容量。）

完成后，我们可以释放旧数组的内存。

    dest->value = entry->value;
  }

  FREE_ARRAY(Entry, table->entries, table->capacity);

  table->entries = entries;

有了它，我们就可以将任意数量的条目放入哈希表中。它会处理覆盖现有键，并在需要时增长自身以维护所需的负载容量。

顺便说一下，让我们也定义一个辅助函数，用于将一个哈希表的所有条目复制到另一个哈希表中。

bool tableSet(Table* table, ObjString* key, Value value);

void tableAddAll(Table* from, Table* to);

#endif

在很长一段时间后，在我们支持方法继承之前，我们才需要它，但我们现在可以实现它，因为我们对哈希表的所有内容都记忆犹新。

void tableAddAll(Table* from, Table* to) {
  for (int i = 0; i < from->capacity; i++) {
    Entry* entry = &from->entries[i];
    if (entry->key != NULL) {
      tableSet(to, entry->key, entry->value);
    }
  }
}

关于这一点没什么好说的。它遍历源哈希表的桶数组。每当它找到一个非空桶时，它就会使用我们最近定义的tableSet()函数将该条目添加到目标哈希表中。

20 . 4 . 4检索值

现在我们的哈希表中包含了一些内容，让我们开始将它们取出来。给定一个键，我们可以使用此函数查找相应的键值（如果有的话）

void freeTable(Table* table);

bool tableGet(Table* table, ObjString* key, Value* value);

bool tableSet(Table* table, ObjString* key, Value value);

您传入一个表和一个键。如果它找到具有该键的条目，则返回true，否则返回false。如果条目存在，则value输出参数指向结果值。

由于findEntry()已经完成了繁重的工作，因此实现并不差。

bool tableGet(Table* table, ObjString* key, Value* value) {
  if (table->count == 0) return false;

  Entry* entry = findEntry(table->entries, table->capacity, key);
  if (entry->key == NULL) return false;

  *value = entry->value;
  return true;
}

如果该表完全为空，我们肯定不会找到该条目，因此我们首先检查这一点。这不仅仅是一种优化—它还确保我们在数组为NULL时不会尝试访问桶数组。否则，我们让findEntry()发挥作用。它返回指向桶的指针。如果该桶为空，我们通过查看键是否为NULL来检测这一点，那么我们没有找到具有我们键的条目。如果findEntry()确实返回一个非空条目，那么就是我们的匹配项。我们获取条目的值，并将它复制到输出参数，以便调用者可以获取它。轻而易举。

20 . 4 . 5删除条目

一个功能齐全的哈希表需要支持的另一个基本操作是：删除条目。这似乎很明显，如果你可以添加东西，你应该能够取消添加它们，对吧？但你会惊讶于有多少关于哈希表的教程省略了这一点。

我也可能走这条路。事实上，我们只在 VM 中的一个微不足道的边缘情况下使用删除。但如果你想真正了解如何完全实现哈希表，这感觉很重要。我可以理解他们希望忽略它的愿望。正如我们将看到的，从使用开放寻址的哈希表中删除很棘手。

至少声明很简单。

bool tableSet(Table* table, ObjString* key, Value value);

bool tableDelete(Table* table, ObjString* key);

void tableAddAll(Table* from, Table* to);

显而易见的方法是镜像插入。使用findEntry()查找条目的桶。然后清空该桶。完成了！

在没有冲突的情况下，这工作得很好。但如果发生了冲突，则条目所在的桶可能是一个或多个隐式探测序列的一部分。例如，这是一个包含三个键的哈希表，所有键都具有相同的首选桶 2

请记住，当我们沿着探测序列查找条目时，我们知道当我们遇到一个空桶时，我们已经到达了序列的末尾，并且条目不存在。这就像探测序列是一个条目列表，一个空条目终止该列表。

如果我们只是清除 Entry 来删除“biscuit”，那么我们就会在中间断开探测序列，留下尾随的条目成为孤儿，无法访问。这就像从链表中删除一个节点，却没有将前一个节点的指针重新链接到下一个节点一样。

如果我们稍后尝试查找“jam”，我们将从“bagel”开始，在下一个空 Entry 处停止，并且永远找不到它。

为了解决这个问题，大多数实现使用一个名为墓碑的技巧。在删除时，我们不会清除条目，而是用一个称为“墓碑”的特殊哨兵条目替换它。当我们在查找期间遵循探测序列时，如果遇到墓碑，我们不将其视为空槽并停止迭代。相反，我们继续进行，这样删除一个条目就不会破坏任何隐式碰撞链，我们仍然可以找到它后面的条目。

代码如下所示

bool tableDelete(Table* table, ObjString* key) {
  if (table->count == 0) return false;

  // Find the entry.
  Entry* entry = findEntry(table->entries, table->capacity, key);
  if (entry->key == NULL) return false;

  // Place a tombstone in the entry.
  entry->key = NULL;
  entry->value = BOOL_VAL(true);
  return true;
}

首先，我们找到包含要删除的条目的桶。（如果我们没有找到它，就没有任何东西需要删除，所以我们退出。）我们将条目替换为一个墓碑。在 clox 中，我们使用 NULL 键和 true 值来表示它，但任何不能与空桶或有效条目混淆的表示都可行。

这就是我们删除一个条目所需做的所有工作。简单快捷。但所有其他操作都需要正确处理墓碑。墓碑是一种“半”条目。它具有一些现有条目的特性，也具有一些空条目的特性。

当我们在查找期间遵循探测序列时，如果遇到墓碑，我们注意到它并继续进行。

  for (;;) {
    Entry* entry = &entries[index];

    if (entry->key == NULL) {
      if (IS_NIL(entry->value)) {
        // Empty entry.
        return tombstone != NULL ? tombstone : entry;
      } else {
        // We found a tombstone.
        if (tombstone == NULL) tombstone = entry;
      }
    } else if (entry->key == key) {
      // We found the key.
      return entry;
    }

    index = (index + 1) % capacity;

我们第一次经过一个墓碑时，将它存储在这个局部变量中

  uint32_t index = key->hash % capacity;

  Entry* tombstone = NULL;

  for (;;) {

如果我们遇到一个真正的空条目，那么该键就不存在。在这种情况下，如果我们经过一个墓碑，我们将返回它的桶，而不是后面的空桶。如果我们正在调用 findEntry() 来插入一个节点，那么这将使我们能够将墓碑桶视为空桶，并将其重新用于新条目。

像这样自动重用墓碑槽有助于减少墓碑浪费的桶数组空间数量。在典型的用例中，插入和删除混合在一起，墓碑的数量会增长一段时间，然后趋于稳定。

即便如此，也不能保证大量删除不会导致数组充满了墓碑。在最坏的情况下，我们最终可能会没有空桶。这将很糟糕，因为请记住，findEntry() 中唯一阻止无限循环的事情是假设我们最终会遇到一个空桶。

因此，我们需要仔细考虑墓碑与表负载因子和调整大小之间的交互方式。关键问题是，在计算负载因子时，我们应该将墓碑视为满桶还是空桶？

20 . 4 . 6计算墓碑

如果我们将墓碑视为满桶，那么我们最终可能会得到一个比我们可能需要的更大的数组，因为它会人为地夸大负载因子。我们有一些可以重用的墓碑，但它们不被视为未用，所以我们最终会过早地增长数组。

但如果我们将墓碑视为空桶，并且不将它们包含在负载因子中，那么我们就会冒最终没有实际的空桶来终止查找的风险。无限循环比几个额外的数组槽位糟糕得多，因此对于负载因子，我们将墓碑视为满桶。

这就是为什么我们在前面代码中删除一个条目时不减少计数的原因。计数不再是哈希表中的条目数量，而是条目数量加上墓碑数量。这意味着我们只有在新的条目进入一个完全空的桶时，才会在插入期间增加计数。

  bool isNewKey = entry->key == NULL;

  if (isNewKey && IS_NIL(entry->value)) table->count++;

  entry->key = key;

如果我们用一个新的条目替换一个墓碑，那么该桶已经被计算在内，计数不会改变。

当我们调整数组大小的时候，我们会分配一个新的数组，并将所有现有的条目重新插入到其中。在这个过程中，我们不复制墓碑。它们没有增加任何价值，因为我们无论如何都要重建探测序列，并且只会减慢查找速度。这意味着我们需要重新计算计数，因为计数可能会在调整大小期间发生变化。所以我们将其清除

  }

  table->count = 0;

  for (int i = 0; i < table->capacity; i++) {

然后，每次我们找到一个非墓碑条目时，我们都会将其增加。

    dest->value = entry->value;

    table->count++;

  }

这意味着当我们增加容量时，我们最终在结果更大的数组中可能会有更少的条目，因为所有墓碑都被丢弃了。这有点浪费，但不是一个重大的实际问题。

我发现很有趣的是，支持删除条目的许多工作都在 findEntry() 和 adjustCapacity() 中。实际的删除逻辑非常简单快捷。在实践中，删除操作往往很少见，所以你期望哈希表在删除函数中尽可能多地工作，而让其他函数保持原样以保持它们的快速性。通过我们的墓碑方法，删除操作很快，但查找操作会受到惩罚。

我做了一些基准测试，在几个不同的删除场景中测试了这一点。我惊讶地发现，与在删除期间进行所有工作来重新插入受影响的条目相比，墓碑最终总体上更快。

但是，如果你仔细想想，墓碑方法并不是将完全删除一个条目的工作推迟到其他操作，而是使删除变得延迟。首先，它做最少的工作将条目变成一个墓碑。这可能会导致以后的查找必须跳过它时出现性能下降。但它也允许以后的插入重新使用该墓碑桶。这种重用是一种非常有效的方式，可以避免重新排列所有后续受影响的条目的成本。你基本上是在探测条目链中回收一个节点。这是一个巧妙的技巧。

20 . 5字符串驻留

我们已经得到了一个基本有效的哈希表，尽管它的核心存在一个致命缺陷。此外，我们还没有将它用于任何目的。现在是解决这两个问题的时候了，在这个过程中，我们将学习解释器使用的一种经典技术。

哈希表不能完全正常工作的原因是，当 findEntry() 检查现有键是否与它要查找的键匹配时，它使用 == 来比较两个字符串是否相等。只有当这两个键是内存中的同一个字符串时，它才会返回 true。两个具有相同字符的独立字符串应该被视为相等，但实际上并非如此。

请记住，在我们上一章中添加字符串时，我们在显式地添加了对逐字符比较字符串的支持，以便获得真正的值相等性。我们可以在 findEntry() 中做到这一点，但这很慢。

相反，我们将使用一种称为字符串驻留的技术。核心问题是，内存中可能存在具有相同字符的不同字符串。即使它们是不同的对象，也需要像等效值一样表现。它们本质上是重复的，我们必须比较所有它们的字节才能检测到这一点。

字符串驻留是一个去重过程。我们创建了一个“驻留”字符串的集合。该集合中的任何字符串都保证在文本上与所有其他字符串不同。当你驻留一个字符串时，你将在集合中查找匹配的字符串。如果找到，你将使用原始的那个。否则，你拥有的字符串是唯一的，所以你将它添加到集合中。

通过这种方式，你知道每个字符序列在内存中只由一个字符串表示。这使得值相等变得微不足道。如果两个字符串指向内存中的同一个地址，那么它们显然是同一个字符串，并且必须相等。而且，因为我们知道字符串是唯一的，所以如果两个字符串指向不同的地址，那么它们就必须是不同的字符串。

因此，指针相等与值相等完全匹配。这反过来意味着我们在 findEntry() 中现有的 == 做了正确的事情。或者，至少，它会在我们驻留所有字符串之后做正确的事情。为了可靠地对所有字符串进行去重，VM 需要能够找到创建的每个字符串。我们通过给它一个哈希表来存储它们来做到这一点。

  Value* stackTop;

  Table strings;

  Obj* objects;

像往常一样，我们需要一个包含文件。

#include "chunk.h"

#include "table.h"

#include "value.h"

当我们启动一个新的 VM 时，字符串表是空的。

  vm.objects = NULL;

  initTable(&vm.strings);

}

当我们关闭 VM 时，我们会清理表使用的所有资源。

void freeVM() {

  freeTable(&vm.strings);

  freeObjects();

一些语言有一个单独的类型或一个显式的步骤来驻留一个字符串。对于 clox，我们将会自动地驻留每一个字符串。这意味着每当我们创建一个新的唯一字符串时，我们都会将它添加到表中。

  string->hash = hash;

  tableSet(&vm.strings, string, NIL_VAL);

  return string;

我们更多地将表用作哈希集，而不是哈希表。键是字符串，而这些是我们唯一关心的内容，所以我们只是对值使用 nil。

这将一个字符串放入表中，假设它是唯一的，但我们需要在到达这里之前实际检查是否有重复。我们在调用 allocateString() 的两个更高级别的函数中做到这一点。这里有一个

  uint32_t hash = hashString(chars, length);

  ObjString* interned = tableFindString(&vm.strings, chars, length,
                                        hash);
  if (interned != NULL) return interned;

  char* heapChars = ALLOCATE(char, length + 1);

当我们将一个字符串复制到一个新的 LoxString 时，我们首先在字符串表中查找它。如果我们找到了它，我们不会“复制”，而是只返回对该字符串的引用。否则，我们将继续执行，分配一个新的字符串，并将它存储在字符串表中。

获取字符串的所有权有点不同。

  uint32_t hash = hashString(chars, length);

  ObjString* interned = tableFindString(&vm.strings, chars, length,
                                        hash);
  if (interned != NULL) {
    FREE_ARRAY(char, chars, length + 1);
    return interned;
  }

  return allocateString(chars, length, hash);

同样，我们首先在字符串表中查找字符串。如果我们找到了它，在我们返回它之前，我们会释放传入的字符串的内存。由于所有权正在被传递给这个函数，而且我们不再需要重复的字符串，因此由我们来释放它。

在我们开始编写新的函数之前，还需要添加一个包含文件。

#include "object.h"

#include "table.h"

#include "value.h"

为了在表中查找一个字符串，我们不能使用普通的 tableGet() 函数，因为该函数会调用 findEntry()，而 findEntry() 正好存在我们要解决的重复字符串问题。相反，我们使用这个新函数

void tableAddAll(Table* from, Table* to);

ObjString* tableFindString(Table* table, const char* chars,
                           int length, uint32_t hash);

#endif

实现如下所示

ObjString* tableFindString(Table* table, const char* chars,
                           int length, uint32_t hash) {
  if (table->count == 0) return NULL;

  uint32_t index = hash % table->capacity;
  for (;;) {
    Entry* entry = &table->entries[index];
    if (entry->key == NULL) {
      // Stop if we find an empty non-tombstone entry.
      if (IS_NIL(entry->value)) return NULL;
    } else if (entry->key->length == length &&
        entry->key->hash == hash &&
        memcmp(entry->key->chars, chars, length) == 0) {
      // We found it.
      return entry->key;
    }

    index = (index + 1) % table->capacity;
  }
}

看起来我们复制粘贴了 findEntry()。有很多冗余，但也有几个关键区别。首先，我们传递了要查找的键的原始字符数组，而不是 ObjString。在我们调用它的时候，我们还没有创建 ObjString。

其次，在检查是否找到密钥时，我们会查看实际的字符串。我们首先查看它们的长度和哈希值是否匹配。这些检查起来很快，如果它们不相同，那么字符串肯定也不相同。

如果出现哈希冲突，我们会进行实际的逐字符字符串比较。这是 VM 中唯一一个我们实际测试字符串文本相等性的位置。我们在这里这样做是为了对字符串进行去重，这样 VM 的其余部分就可以认为内存中不同地址的任何两个字符串的内容都不同。

事实上，现在我们已经对所有字符串进行了驻留，我们可以在字节码解释器中利用它。当用户对两个恰好是字符串的对象执行 `==` 操作时，我们不再需要测试字符。

    case VAL_NUMBER: return AS_NUMBER(a) == AS_NUMBER(b);

    case VAL_OBJ:    return AS_OBJ(a) == AS_OBJ(b);

    default:         return false; // Unreachable.

我们在创建字符串时添加了一点开销来对它们进行驻留。但作为回报，在运行时，字符串上的等号操作速度快得多。有了它，我们有一个功能齐全的哈希表，可以用来跟踪变量、实例或任何其他可能出现的键值对。

我们还加快了字符串相等性测试的速度。这在用户对字符串进行 `==` 操作时很有用。但在像 Lox 这样的动态类型语言中，方法调用和实例字段是在运行时按名称查找的，这一点更为关键。如果测试字符串的相等性很慢，那么按名称查找方法也很慢。如果在你的面向对象语言中 *那* 很慢，那么 *一切* 都很慢。