Zig HashMap 原理介紹上篇

引言

如大多數哈希映射實現一樣，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 方法，會發現一個經常重複的應用模式：

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 作爲參數傳遞。要實際看到這一點，可以考慮下面這個鏈表的例子：

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 版本只有細微的差別：

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)，你可以這樣做：

var ll = LinkedListUnmanaged(i32){};

這看起來有點神祕，但這是標準的 Zig。LinkedListUnmanaged(i32) 返回一個類型，所以上面的做法和執行 var user = User{} 並依賴 User 的默認字段值沒有區別。

你可能會好奇 unmanaged 類型有什麼用？但在我們回答這個問題之前，讓我們考慮一下提供我們的 LinkedList 的 managed 和 unmanaged 版本有多容易。我們保持我們的 LinkedListUnmanaged 如原樣，並改變我們的 LinkedList 來包裝它：

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 甚至可以爲更復雜的鍵生成上下文。以下操作是有效的：以下是修正後的代碼：

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 不支持切片鍵。我們可以確認這一點。嘗試運行：

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.autoHashdoes not allow slices here ([]const u8) because the intent is unclear. Consider using std.StringHashMapfor hashing the contents of []const u8. Alternatively, consider using std.auto_hash.hash or providing your own hash function instead.

正如我之前所說，問題不是切片不能被哈希或比較，而是有些情況下，切片只有在引用相同內存時纔會被認爲是相等的，而另一些情況下，兩個切片如果它們的元素相同就會被認爲是相等的。但是，對於字符串，大多數人期望 “teg” 無論存儲在哪裏都應該等於“teg”。

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 使用的上下文：

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” 進行獲取：

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 類型及其實現：

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）。

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，我們希望用它作爲哈希表中的鍵：

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

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

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，通常很直觀：

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);
}

如果你看過我們的其他哈希示例，你可能會想到它的實現：

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，可能會派上用場。如果沒有其他用途，現在文檔和它們的實現應該更容易理解了。

在下一部分，我們將深入探討哈希表的鍵和值，它們是如何存儲和管理的。

建議 / 反饋 ✉️

• 關注微信公衆號，實時獲取更多 Zig 乾貨文章
• 想要分享 Zig 使用經驗，歡迎給我們供稿 [1]
• 論壇地址：https://ask.ziglang.cc/

引用鏈接

[1] 歡迎給我們供稿: https://ziglang.cc/post/2023/09/05/hello-world/

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/z5HjvUEjT0UPcMy43rj2dw

引言

Unmanaged

HashMap 與 AutoHashMap

自定義上下文

結論

建議 / 反饋 ✉️

引用鏈接

猜你喜歡