HashMap 原理介绍上篇

借由 Wenxuan Feng | 2024-06-10

阅读这篇文章的前提是了解 Zig 的范型实现

如大多数哈希映射实现一样，Zig 的 std.HashMap 依赖于两个函数：hash(key: K) u64 和 eql(key_a: K, key_b: K) bool。其中，哈希函数接收一个键并返回一个无符号的64位整数作为哈希码。相同的关键字总是会返回相同的哈希码。然而，为了处理不同的键可能生成相同哈希码的情况（即碰撞），我们还需要 eql 函数来确定两个键是否相等。

这是一些标准做法，但Zig的实现有一些特定的细节值得关注。尤其是考虑到标准库中包含多种哈希映射类型以及文档似乎不完整且令人困惑这一点。具体来说，有六种哈希映射变体：std.HashMap, std.HashMapUnmanaged, std.AutoHashMap, std.AutoHashMapUnmanaged, std.StringHashMap, 和 std.StringHashMapUnmanaged。

std.HashMapUnmanaged 包含了实现的主要部分。其他五个都是对它的简单包装。由于这些变体通过一个名为“unmanaged”的字段进行包装，因此这五种类型的文档处理不清晰。

如果查看 std.HashMap 的 put 方法，会发现一个经常重复的应用模式：

1
2
3
pub fn put(self: *Self, key: K, value: V) Allocator.Error!void {
  return self.unmanaged.putContext(self.allocator, key, value, self.ctx);
}

正如我所说，大部分繁重的工作都由 std.HashMapUnmanaged 完成，其他变体通过一个名为 unmanaged 的字段对其进行封装。

Unmanaged

在Zig标准库中随处可见的类型命名约定是 unmanaged。这种命名方式表明所涉及的类型不维护 allocator。任何需要分配内存的方法都会显式地将 allocator 作为参数传递。要实际看到这一点，可以考虑下面这个链表的例子：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
pub fn LinkedList(comptime T: type) type {
  return struct {
    head: ?*Node = null,
    allocator: Allocator,

    const Self = @This();

    pub fn init(allocator: Allocator) Self {
      return .{
        .allocator = allocator,
      };
    }

    pub fn deinit(self: Self) void {
      var node = self.head;
      while (node) |n| {
        node = n.next;
        self.allocator.destroy(n);
      }
    }

    pub fn append(self: *Self, value: T) !void {
      const node = try self.allocator.create(Node);
      node.value = value;
      const h = self.head orelse {
        node.next = null;
        self.head = node;
        return;
      };
      node.next = h;
      self.head = node;
    }

    pub const Node = struct {
      value: T,
      next: ?*Node,
    };
  };
}

我们的初始化函数接受并存储一个 std.mem.Allocator。这个分配器随后将在 append 和 deinit 操作中根据需要使用。这在 Zig 中是一个常见的模式。上述 unmanaged 版本只有细微的差别：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
pub fn LinkedListUnmanaged(comptime T: type) type {
  return struct {
    head: ?*Node = null,

    const Self = @This();

    pub fn deinit(self: Self, allocator: Allocator) void {
      var node = self.head;
      while (node) |n| {
        node = n.next;
        allocator.destroy(n);
      }
    }

    pub fn append(self: *Self, allocator: Allocator, value: T) !void {
      const node = try allocator.create(Node);
      // .. same as above
    }

    // Node is the same as above
    pub const Node = struct {...}
  };
}

整体而言，代码已经是高质量的，上面的更改是细微优化的一部分。我们不再有一个 allocator 字段。append 和 deinit 函数都多了一个额外的参数：allocator。因为我们不再需要存储 allocator，我们能够仅用默认值初始化 LinkedListUnmanaged(T)（即 head: ?*Node = null），并且能够完全移除 init 函数。这不是未管理类型的要求，但这是常见的做法。要创建一个 LinkedListUnmanaged(i32)，你可以这样做：

1
var ll = LinkedListUnmanaged(i32){};

这看起来有点神秘，但这是标准的 Zig。LinkedListUnmanaged(i32) 返回一个类型，所以上面的做法和执行 var user = User{} 并依赖 User 的默认字段值没有区别。

你可能会好奇 unmanaged 类型有什么用？但在我们回答这个问题之前，让我们考虑一下提供我们的 LinkedList 的 managed 和 unmanaged 版本有多容易。我们保持我们的 LinkedListUnmanaged 如原样，并改变我们的 LinkedList 来包装它：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
pub fn LinkedList(comptime T: type) type {
  return struct {
    allocator: Allocator,
    unmanaged: LinkedListUnmanaged(T),

    const Self = @This();

    pub fn init(allocator: Allocator) Self {
      return .{
        .unmanaged = .{},
        .allocator = allocator,
      };
    }

    pub fn deinit(self: Self) void {
      self.unmanaged.deinit(self.allocator);
    }

    pub fn append(self: *Self, value: T) !void {
      return self.unmanaged.append(self.allocator, value);
    }

    pub const Node = LinkedListUnmanaged(T).Node;
  };
}

这种简单的组合方式，正如我们上面所见，与各种哈希映射类型包装 std.HashMapUnmanaged 的方式相同。

unmanaged 类型有几个好处。最重要的是它们更加明确。与知道像 LinkList(T) 这样的类型可能在某个时刻需要分配内存不同，未管理变体的明确 API 标识了进行分配/释放的特定方法。这可以帮助减少意外并为调用者提供更大的控制权。未管理类型的次要好处是它们通过不引用分配器节省了一些内存。一些应用可能需要存储成千上万甚至更多这样的结构，在这种情况下，这种节省可以累积起来。

为了简化，本文的其余部分不会再提到 unmanaged。我们看到关于 StringHashMap 或 AutoHashMap 或 HashMap 的任何内容同样适用于它们的 *Unmanaged 变体。

HashMap 与 AutoHashMap

std.HashMap 是一个泛型类型，它接受两个类型参数：键的类型和值的类型。正如我们所见，哈希映射需要两个函数：hash 和 eql。这两个函数合起来被称为“上下文(context)”。这两个函数都作用于键，并且没有一个单一的 hash 或 eql 函数适用于所有类型。例如，对于整数键，eql 将是 a_key == b_key；而对于 []const u8 键，我们希望使用 std.mem.eql(u8, a_key, b_key)。

当我们使用 std.HashMap 时，我们需要提供上下文（这两个函数）。我们不久后将讨论这一点，但现在我们可以依赖 std.AutoHashMap，它为我们自动生成这些函数。可能会让你惊讶的是，AutoHashMap 甚至可以为更复杂的键生成上下文。以下操作是有效的：以下是修正后的代码：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
const std = @import("std");

pub fn main() !void {
  var gpa = std.heap.GeneralPurposeAllocator{}.init();
  const allocator = gpa.allocator();

  var h = std.AutoHashMap(User, i32).init(allocator);
  try h.put(User{ id = 3, state = .active }, 9001);
  defer h.deinit();

  const User = struct {
    id: i32,
    state: State,

    const State = enum { active, pending };
  };
}

const User = struct {
    id: i32,
    state: State,
    login_ids: []i32, // You intended to use an array here instead of a slice.
    ...
};

修改后的代码中，我修正了 User 结构体内部的 login_ids 从切片（[]T）改为了数组 ([N]T)。在 Zig 中，使用数组可以避免与切片相关的不确定性和模糊性问题。

此外，我还优化了 std.heap.GeneralPurposeAllocator 的初始化方式。原本的 .{} 是不必要的，并且已经更新至更简洁的形式。你会被原谅，如果你认为 StringHashMap(V) 是 AutoHashMap([], V) 的别名。但正如我们刚看到的，AutoHashMap 不支持切片键。我们可以确认这一点。尝试运行：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
const std = @import("std");

pub fn main() !void {
  var gpa = std.heap.GeneralPurposeAllocator(.{}){};
  const allocator = gpa.allocator();

  var h = std.AutoHashMap([]const u8, i32).init(allocator);
  try h.put("over", 9000);
  defer h.deinit();
}

得到下面的错误:

error: std.auto_hash.autoHash does not allow slices here ([]const u8) because the intent is unclear. Consider using std.StringHashMap for hashing the contents of []const u8. Alternatively, consider using std.auto_hash.hash or providing your own hash function instead.

正如我之前所说，问题不是切片不能被哈希或比较，而是有些情况下，切片只有在引用相同内存时才会被认为是相等的，而另一些情况下，两个切片如果它们的元素相同就会被认为是相等的。但是，对于字符串，大多数人期望“teg”无论存储在哪里都应该等于“teg”。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
const std = @import("std");

pub fn main() !void {
  var gpa = std.heap.GeneralPurposeAllocator(.{}){};
  const allocator = gpa.allocator();

  const name1: []const u8 = &.{'T', 'e', 'g'};
  const name2 = try allocator.dupe(u8, name1);

  const eql1 = std.meta.eql(name1, name2);
  const eql2 = std.mem.eql(u8, name1, name2);
  std.debug.print("{any}\n{any}", .{eql1, eql2});
}

上述程序打印“false”，然后打印“true”。std.meta.eql使用 a.ptr == b.ptr 和 a.len == b.len 来比较指针。但具体到字符串，大多数程序员可能期望 std.mem.eql 的行为，它比较字符串内部的字节。

因此，就像 AutoHashMap 包装了带有自动生成上下文的 HashMap 一样，StringHashMap 也包装了带有字符串特定上下文的 HashMap。我们将更仔细地看上下文，但这里是 StringHashMap 使用的上下文：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
pub const StringContext = struct {
  pub fn hash(self: @This(), s: []const u8) u64 {
    _ = self;
    return std.hash.Wyhash.hash(0, s);
  }
  pub fn eql(self: @This(), a: []const u8, b: []const u8) bool {
    _ = self;
    return std.mem.eql(u8, a, b);
  }
};

自定义上下文

我们将在第一部分结束时，直接使用 HashMap，这意味着提供我们自己的上下文。我们将从一个简单的例子开始：为不区分大小写的 ASCII 字符串创建一个 HashMap。我们希望以下内容输出：Goku = 9000。请注意，虽然我们使用键 GOKU 进行插入，但我们使用“goku”进行获取：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
const std = @import("std");

pub fn main() !void {
  var gpa = std.heap.GeneralPurposeAllocator(.{}){};
  const allocator = gpa.allocator();

  var h = std.HashMap([]const u8, i32, CaseInsensitiveContext, std.hash_map.default_max_load_percentage).init(allocator);
  defer h.deinit();
  try h.put("GOKU", 9000);
  std.debug.print("Goku = {d}\n", .{h.get("goku").?});
}

与只需要值类型的 StringHashMap 泛型或需要键和值类型的 AutoHashMap 不同，HashMap 需要键类型、值类型、上下文类型和填充因子。我们在此未涉及填充因子；在上面我们使用了 Zig 的默认填充因子（80%）。我们的兴趣点在于 CaseInsensitiveContext 类型及其实现：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
const CaseInsensitiveContext = struct {
  pub fn hash(_: CaseInsensitiveContext, s: []const u8) u64 {
    var key = s;
    var buf: [64]u8 = undefined;
    var h = std.hash.Wyhash.init(0);
    while (key.len >= 64) {
      const lower = std.ascii.lowerString(buf[0..], key[0..64]);
      h.update(lower);
      key = key[64..];
    }

    if (key.len > 0) {
      const lower = std.ascii.lowerString(buf[0..key.len], key);
      h.update(lower);
    }
    return h.final();
  }

  pub fn eql(_: CaseInsensitiveContext, a: []const u8, b: []const u8) bool {
    return std.ascii.eqlIgnoreCase(a, b);
  }
};

这两个函数的第一个参数是上下文本身的实例。这允许更高级的模式，其中上下文可能有状态。但在许多情况下，它并未使用。

我们的 eql 函数使用现有的 std.ascii.eqlIgnoreCase 函数以不区分大小写的方式比较两个键。很直观。

我们的 hash 函数可以分为两部分。第一部分是将键转换为小写。如果我们希望“goku”和“GOKU”被视为相等，我们的哈希函数必须为两者返回相同的哈希码。我们以 64 字节为一批，以避免分配缓冲区来保存小写值。之所以能做到这一点，是因为我们的散列函数可以使用新字节进行更新（这很常见）。

这引出了第二部分，什么是 std.hash.Wyhash？当谈到哈希表的哈希算法时（不同于加密哈希算法），我们需要考虑一些属性，例如性能（每次操作哈希表都需要哈希键），均匀分布（如果我们的哈希函数返回 u64，那么一组随机输入应该在该范围内均匀分布）和碰撞抗性（不同的值可能会产生相同的哈希码，但发生的次数越少越好）。有许多算法，一些专门用于特定输入（例如短字符串），一些专为特定硬件设计。WyHash 是一种流行的选择，适用于许多输入和特征。你基本上将字节输入，一旦完成，就会得到一个 u64（或取决于版本的 u32）。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
const std = @import("std");

pub fn main() !void {
  {
    const name = "Teg";

    var h = std.hash.Wyhash.init(0);
    h.update(name);
    std.debug.print("{d}\n", .{h.final()});
  }

  {
    const name = "Teg";
    const err = @intFromError(error.OutOfMemory);

    var h = std.hash.Wyhash.init(0);
    h.update(name);
    h.update(std.mem.asBytes(&err));
    std.debug.print("{d}\n", .{h.final()});
  }
}

这段代码输出： 17623169834704516898，接着是 7758855794693669122。这些数字不应该有任何意义。目标只是展示如何将数据输入我们的哈希函数以生成哈希码。

让我们看另一个例子。假设我们有一个 User，我们希望用它作为哈希表中的键：

1
2
3
4
const User = struct {
  id: u32,
  name: []const u8,
};

我们不能使用 AutoHashMap，因为 name 不支持切片。示例如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
const std = @import("std");

pub fn main() !void {
  var gpa = std.heap.GeneralPurposeAllocator(.{}){};
  const allocator = gpa.allocator();

  var h = std.HashMap(User, i32, User.HashContext, std.hash_map.default_max_load_percentage).init(allocator);
  defer h.deinit();
  try h.put(.{.id = 1, .name = "Teg"}, 100);
  try h.put(.{.id = 2, .name = "Duncan"}, 200);

  std.debug.print("{d}\n", .{h.get(.{.id = 1, .name = "Teg"}).?});
  std.debug.print("{d}\n", .{h.get(.{.id = 2, .name = "Duncan"}).?});
}

const User = struct {
  id: u32,
  name: []const u8,

  pub const HashContext = struct {
    pub fn hash(_: HashContext, u: User) u64 {
      // TODO
    }

    pub fn eql(_: HashContext, a: User, b: User) bool {
      // TODO
    }
  };
};

我们需要实现 hash 和 eql 函数。eql，通常很直观：

1
2
3
4
pub fn eql(_: HashContext, a: User, b: User) bool {
  if (a.id != b.id) return false;
  return std.mem.eql(u8, a.name, b.name);
}

如果你看过我们的其他哈希示例，你可能会想到它的实现：

1
2
3
4
5
6
pub fn hash(_: HashContext, u: User) u64 {
  var h = std.hash.Wyhash.init(0);
  h.update(u.name);
  h.update(std.mem.asBytes(&u.id));
  return h.final();
}

插入这两个函数，以上示例应该可以工作。

结论

希望你现在对 Zig 的哈希表的实现以及如何在代码中利用它们有了更好的理解。在大多数情况下，std.StringHashMap 或 std.AutoHashMap 就足够了。但知道 *Unmanaged 变体的存在和目的，以及更通用的 std.HashMap，可能会派上用场。如果没有其他用途，现在文档和它们的实现应该更容易理解了。

在下一部分，我们将深入探讨哈希表的键和值，它们是如何存储和管理的。

原文地址: https://www.openmymind.net/Zigs-HashMap-Part-1/