跳转到内容
标准库Zig 0.17.0官方原文
源码std/hash_map.zig

第 1 行

std.hash_map.Alignment

别名

第 9 行

别名目标 std.mem.Alignment

std.hash_map.Allocator

别名

第 7 行

别名目标 std.mem.Allocator

std.hash_map.assert

别名

第 3 行

别名目标 std.debug.assert

std.hash_map.AutoContext

类型函数

第 54 行

pub fn AutoContext(comptime K: type) type

参数

K: type

std.hash_map.AutoContext.eql

常量

第 57 行

std.hash_map.AutoContext.hash

常量

第 56 行

std.hash_map.autoHash

别名

第 4 行

别名目标 std.hash.autoHash

std.hash_map.AutoHashMap

类型函数

第 46 行

pub fn AutoHashMap(comptime K: type, comptime V: type) type

参数

K: type
V: type

字段

unmanaged: Unmanaged
allocator: Allocator
ctx: Context

std.hash_map.AutoHashMapUnmanaged

类型函数

第 50 行

pub fn AutoHashMapUnmanaged(comptime K: type, comptime V: type) type

参数

K: type
V: type

std.hash_map.builtin

常量

第 2 行

std.hash_map.Custom

类型函数

第 507 行

fn Custom( comptime K: type, comptime V: type, comptime Context: type, comptime max_load_percentage: u64, ) type

参数

K: type
V: type
Context: type
max_load_percentage: u64

字段

metadata: ?[*]Metadata = null

指向元数据的指针。

size: Size = 0

哈希映射中当前的元素数。

available: Size = 0

在为满足 max_load_percentage 而必须扩容之前, 可用的槽位数量。

pointer_stability: std.debug.SafetyLock = .{}

用于检测内存安全违规。

std.hash_map.Custom.allocate

函数

第 1462 行

fn allocate(self: *Self, allocator: Allocator, new_capacity: Size) Allocator.Error!void

参数

self: *Self
allocator: Allocator
new_capacity: Size

错误

OutOfMemory

std.hash_map.Custom.capacity

函数

第 798 行

pub fn capacity(self: Self) Size

参数

self: Self

std.hash_map.Custom.capacityForSize

函数

第 737 行

fn capacityForSize(size: Size) Size

参数

size: Size

std.hash_map.Custom.clearAndFree

函数

第 774 行

pub fn clearAndFree(self: *Self, allocator: Allocator) void

参数

self: *Self
allocator: Allocator

std.hash_map.Custom.clearRetainingCapacity

函数

第 764 行

pub fn clearRetainingCapacity(self: *Self) void

参数

self: *Self

std.hash_map.Custom.clone

函数

第 1302 行

pub fn clone(self: Self, allocator: Allocator) Allocator.Error!Self

参数

self: Self
allocator: Allocator

错误

OutOfMemory

std.hash_map.Custom.cloneContext

函数

第 1307 行

pub fn cloneContext(self: Self, allocator: Allocator, new_ctx: anytype) Allocator.Error!HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage)

参数

self: Self
allocator: Allocator

错误

OutOfMemory

std.hash_map.Custom.contains

函数

第 1217 行

若映射中存在与 key 关联的值,则返回 true。

pub fn contains(self: Self, key: K) bool

参数

self: Self
key: K

std.hash_map.Custom.containsAdapted

函数

第 1225 行

pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool

参数

self: Self

std.hash_map.Custom.containsContext

函数

第 1222 行

pub fn containsContext(self: Self, key: K, ctx: Context) bool

参数

self: Self
key: K
ctx: Context

std.hash_map.Custom.count

函数

第 782 行

pub fn count(self: Self) Size

参数

self: Self

std.hash_map.Custom.dbHelper

函数

第 1525 行

lib/lldb/ 中的调试器美化格式化器使用此函数获取头部类型,以便为该类型提供格式化调试输出。

fn dbHelper(self: *Self, hdr: *Header, entry: *Entry) void

参数

self: *Self
hdr: *Header
entry: *Entry

std.hash_map.Custom.deallocate

函数

第 1496 行

fn deallocate(self: *Self, allocator: Allocator) void

参数

self: *Self
allocator: Allocator

std.hash_map.Custom.deinit

函数

第 731 行

pub fn deinit(self: *Self, allocator: Allocator) void

参数

self: *Self
allocator: Allocator

std.hash_map.Custom.empty

常量

第 545 行

不含任何键值的映射。

Self

std.hash_map.Custom.ensureTotalCapacity

函数

第 743 行

pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_size: Size) Allocator.Error!void

参数

self: *Self
allocator: Allocator
new_size: Size

错误

OutOfMemory

std.hash_map.Custom.ensureTotalCapacityContext

函数

第 748 行

pub fn ensureTotalCapacityContext(self: *Self, allocator: Allocator, new_size: Size, ctx: Context) Allocator.Error!void

参数

self: *Self
allocator: Allocator
new_size: Size
ctx: Context

错误

OutOfMemory

std.hash_map.Custom.ensureUnusedCapacity

函数

第 755 行

pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_size: Size) Allocator.Error!void

参数

self: *Self
allocator: Allocator
additional_size: Size

错误

OutOfMemory

std.hash_map.Custom.ensureUnusedCapacityContext

函数

第 760 行

pub fn ensureUnusedCapacityContext(self: *Self, allocator: Allocator, additional_size: Size, ctx: Context) Allocator.Error!void

参数

self: *Self
allocator: Allocator
additional_size: Size
ctx: Context

错误

OutOfMemory

std.hash_map.Custom.Entry

容器

第 558 行

字段

key_ptr: *K
value_ptr: *V

std.hash_map.Custom.fetchPut

函数

第 900 行

将新 Entry 插入哈希映射,并返回之前的条目(如果存在)。

pub fn fetchPut(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!?KV

参数

self: *Self
allocator: Allocator
key: K
value: V

错误

OutOfMemory

std.hash_map.Custom.fetchPutAssumeCapacity

函数

第 920 行

向哈希表插入新的 Entry,若存在旧条目则返回旧条目。 若执行插入,断言容量足够且不分配内存。

pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV

参数

self: *Self
key: K
value: V

std.hash_map.Custom.fetchPutAssumeCapacityContext

函数

第 925 行

pub fn fetchPutAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) ?KV

参数

self: *Self
key: K
value: V
ctx: Context

std.hash_map.Custom.fetchPutContext

函数

第 905 行

pub fn fetchPutContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!?KV

参数

self: *Self
allocator: Allocator
key: K
value: V
ctx: Context

错误

OutOfMemory

std.hash_map.Custom.fetchRemove

函数

第 940 行

若存在键匹配的 Entry,则从 哈希映射中删除,并由此函数返回。

pub fn fetchRemove(self: *Self, key: K) ?KV

参数

self: *Self
key: K

std.hash_map.Custom.fetchRemoveAdapted

函数

第 948 行

pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV

参数

self: *Self

std.hash_map.Custom.fetchRemoveContext

函数

第 945 行

pub fn fetchRemoveContext(self: *Self, key: K, ctx: Context) ?KV

参数

self: *Self
key: K
ctx: Context

std.hash_map.Custom.FieldIterator

类型函数

第 665 行

fn FieldIterator(comptime T: type) type

参数

T: type

字段

len: usize
metadata: [*]const Metadata
items: [*]T

std.hash_map.Custom.FieldIterator.next

函数

第 671 行

pub fn next(self: *@This()) ?*T

参数

self: *@This()

std.hash_map.Custom.get

函数

第 1082 行

若键存在,则获取与其关联的值的副本。

pub fn get(self: Self, key: K) ?V

参数

self: Self
key: K

std.hash_map.Custom.getAdapted

函数

第 1090 行

pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V

参数

self: Self

std.hash_map.Custom.getContext

函数

第 1087 行

pub fn getContext(self: Self, key: K, ctx: Context) ?V

参数

self: Self
key: K
ctx: Context

std.hash_map.Custom.getEntry

函数

第 1004 行

pub fn getEntry(self: Self, key: K) ?Entry

参数

self: Self
key: K

std.hash_map.Custom.getEntryAdapted

函数

第 1012 行

pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry

参数

self: Self

std.hash_map.Custom.getEntryContext

函数

第 1009 行

pub fn getEntryContext(self: Self, key: K, ctx: Context) ?Entry

参数

self: Self
key: K
ctx: Context

std.hash_map.Custom.getIndex

函数

第 968 行

查找包含给定键对应数据的索引。

fn getIndex(self: Self, key: anytype, ctx: anytype) ?usize

参数

self: Self

std.hash_map.Custom.getKey

函数

第 1050 行

若存在,获取与适配键对应的实际键的副本。

pub fn getKey(self: Self, key: K) ?K

参数

self: Self
key: K

std.hash_map.Custom.getKeyAdapted

函数

第 1058 行

pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K

参数

self: Self

std.hash_map.Custom.getKeyContext

函数

第 1055 行

pub fn getKeyContext(self: Self, key: K, ctx: Context) ?K

参数

self: Self
key: K
ctx: Context

std.hash_map.Custom.getKeyPtr

函数

第 1034 行

若存在与适配键关联的实际键,获取指向该键的可选指针。

pub fn getKeyPtr(self: Self, key: K) ?*K

参数

self: Self
key: K

std.hash_map.Custom.getKeyPtrAdapted

函数

第 1042 行

pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K

参数

self: Self

std.hash_map.Custom.getKeyPtrContext

函数

第 1039 行

pub fn getKeyPtrContext(self: Self, key: K, ctx: Context) ?*K

参数

self: Self
key: K
ctx: Context

std.hash_map.Custom.getOrPut

函数

第 1097 行

pub fn getOrPut(self: *Self, allocator: Allocator, key: K) Allocator.Error!GetOrPutResult

参数

self: *Self
allocator: Allocator
key: K

错误

OutOfMemory

std.hash_map.Custom.getOrPutAdapted

函数

第 1109 行

pub fn getOrPutAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype) Allocator.Error!GetOrPutResult

参数

self: *Self
allocator: Allocator

错误

OutOfMemory

std.hash_map.Custom.getOrPutAssumeCapacity

函数

第 1133 行

pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult

参数

self: *Self
key: K

std.hash_map.Custom.getOrPutAssumeCapacityAdapted

函数

第 1145 行

pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult

参数

self: *Self

std.hash_map.Custom.getOrPutAssumeCapacityContext

函数

第 1138 行

pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult

参数

self: *Self
key: K
ctx: Context

std.hash_map.Custom.getOrPutContext

函数

第 1102 行

pub fn getOrPutContext(self: *Self, allocator: Allocator, key: K, ctx: Context) Allocator.Error!GetOrPutResult

参数

self: *Self
allocator: Allocator
key: K
ctx: Context

错误

OutOfMemory

std.hash_map.Custom.getOrPutContextAdapted

函数

第 1114 行

pub fn getOrPutContextAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Allocator.Error!GetOrPutResult

参数

self: *Self
allocator: Allocator
ctx: Context

错误

OutOfMemory

std.hash_map.Custom.GetOrPutResult

容器

第 687 行

字段

key_ptr: *K
value_ptr: *V
found_existing: bool

std.hash_map.Custom.getOrPutValue

函数

第 1202 行

pub fn getOrPutValue(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!Entry

参数

self: *Self
allocator: Allocator
key: K
value: V

错误

OutOfMemory

std.hash_map.Custom.getOrPutValueContext

函数

第 1207 行

pub fn getOrPutValueContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!Entry

参数

self: *Self
allocator: Allocator
key: K
value: V
ctx: Context

错误

OutOfMemory

std.hash_map.Custom.getPtr

函数

第 1066 行

若存在与键关联的值,则获取指向它的可选指针。

pub fn getPtr(self: Self, key: K) ?*V

参数

self: Self
key: K

std.hash_map.Custom.getPtrAdapted

函数

第 1074 行

pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V

参数

self: Self

std.hash_map.Custom.getPtrContext

函数

第 1071 行

pub fn getPtrContext(self: Self, key: K, ctx: Context) ?*V

参数

self: Self
key: K
ctx: Context

std.hash_map.Custom.grow

函数

第 1430 行

fn grow(self: *Self, allocator: Allocator, new_capacity: Size, ctx: Context) Allocator.Error!void

参数

self: *Self
allocator: Allocator
new_capacity: Size
ctx: Context

错误

OutOfMemory

std.hash_map.Custom.growIfNeeded

函数

第 1296 行

fn growIfNeeded(self: *Self, allocator: Allocator, new_count: Size, ctx: Context) Allocator.Error!void

参数

self: *Self
allocator: Allocator
new_count: Size
ctx: Context

错误

OutOfMemory

std.hash_map.Custom.Hash

类型

第 556 行

std.hash_map.Custom.header

函数

第 786 行

fn header(self: Self) *Header

参数

self: Self

std.hash_map.Custom.Header

容器

第 568 行

字段

values: [*]V
keys: [*]K
capacity: Size

std.hash_map.Custom.initMetadatas

函数

第 1284 行

fn initMetadatas(self: *Self) void

参数

self: *Self

std.hash_map.Custom.isUnderMaxLoadPercentage

函数

第 727 行

fn isUnderMaxLoadPercentage(size: Size, cap: Size) bool

参数

size: Size
cap: Size

std.hash_map.Custom.iterator

函数

第 804 行

pub fn iterator(self: *const Self) Iterator

参数

self: *const Self

std.hash_map.Custom.Iterator

容器

第 634 行

字段

hm: *const Self
index: Size = 0

std.hash_map.Custom.Iterator.next

函数

第 638 行

pub fn next(it: *Iterator) ?Entry

参数

it: *Iterator

std.hash_map.Custom.keyIterator

函数

第 808 行

pub fn keyIterator(self: Self) KeyIterator

参数

self: Self

std.hash_map.Custom.KeyIterator

类型

第 662 行

std.hash_map.Custom.keys

函数

第 790 行

fn keys(self: Self) [*]K

参数

self: Self

std.hash_map.Custom.KV

容器

第 563 行

字段

key: K
value: V

std.hash_map.Custom.load

函数

第 1290 行

fn load(self: Self) Size

参数

self: Self

std.hash_map.Custom.lockPointers

函数

第 718 行

将哈希映射置于特殊状态:任何会使现有键或值指针失效的方法调用,都改为触发断言。

lockPointers 可以多次调用,使多个独立使用者能同时保持哈希映射锁定。

unlockPointers 在调用次数与 lockPointers 相同时,将哈希映射恢复为原先状态。

pub fn lockPointers(self: *Self) void

参数

self: *Self

std.hash_map.Custom.Managed

类型

第 693 行

std.hash_map.Custom.Metadata

容器

第 588 行

槽位的元数据,有空闲、已使用和 墓碑三种状态。墓碑表示条目曾经被使用过, 是处理删除操作的一种简单方式。 除状态外,还保存槽位键的哈希值中的 7 位。 利用这几位可以快速区分条目, 不必调用相等性比较函数。如果两个指纹 不同,就完全不必比较键。 这 7 位取自 64 位哈希值的最高位。因此, 除了用哈希值的最低 log2(capacity) 位确定 槽位索引外,还额外利用 7 位快速消解 哈希值不同的多个元素竞争同一槽位时的冲突。 不调用相等性比较函数意味着无需读取 条目数组,从而可能避免缓存未命中和 开销较大的函数调用。

字段

fingerprint: FingerPrint = free
used: u1 = 0

std.hash_map.Custom.Metadata.fill

函数

第 618 行

pub fn fill(self: *Metadata, fp: FingerPrint) void

参数

self: *Metadata
fp: FingerPrint

std.hash_map.Custom.Metadata.FingerPrint

类型

第 589 行

std.hash_map.Custom.Metadata.free

常量

第 591 行

FingerPrint

std.hash_map.Custom.Metadata.isFree

函数

第 608 行

pub fn isFree(self: Metadata) bool

参数

self: Metadata

std.hash_map.Custom.Metadata.isTombstone

函数

第 604 行

pub fn isTombstone(self: Metadata) bool

参数

self: Metadata

std.hash_map.Custom.Metadata.isUsed

函数

第 600 行

pub fn isUsed(self: Metadata) bool

参数

self: Metadata

std.hash_map.Custom.Metadata.remove

函数

第 623 行

pub fn remove(self: *Metadata) void

参数

self: *Metadata

std.hash_map.Custom.Metadata.slot_free

常量

第 597 行

u8

std.hash_map.Custom.Metadata.slot_tombstone

常量

第 598 行

u8

std.hash_map.Custom.Metadata.takeFingerprint

函数

第 612 行

pub fn takeFingerprint(hash: Hash) FingerPrint

参数

hash: Hash

std.hash_map.Custom.Metadata.tombstone

常量

第 592 行

FingerPrint

std.hash_map.Custom.minimal_capacity

常量

第 542 行

哈希映射引导初始化时首次扩容的容量。

std.hash_map.Custom.move

函数

第 1334 行

将映射置为空状态,使反初始化变为空操作, 并返回原映射的副本。

pub fn move(self: *Self) Self

参数

self: *Self

std.hash_map.Custom.promote

函数

第 695 行

pub fn promote(self: Self, allocator: Allocator) Managed

参数

self: Self
allocator: Allocator

std.hash_map.Custom.promoteContext

函数

第 701 行

pub fn promoteContext(self: Self, allocator: Allocator, ctx: Context) Managed

参数

self: Self
allocator: Allocator
ctx: Context

std.hash_map.Custom.put

函数

第 1023 行

如果关联键尚不存在,则插入条目;否则更新现有值。

pub fn put(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void

参数

self: *Self
allocator: Allocator
key: K
value: V

错误

OutOfMemory

std.hash_map.Custom.putAssumeCapacity

函数

第 858 行

断言容量足以存储新键值对。 覆盖任何已有数据。要检测插入是否会覆盖 已有数据,请参见 getOrPutAssumeCapacity。

pub fn putAssumeCapacity(self: *Self, key: K, value: V) void

参数

self: *Self
key: K
value: V

std.hash_map.Custom.putAssumeCapacityContext

函数

第 863 行

pub fn putAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) void

参数

self: *Self
key: K
value: V
ctx: Context

std.hash_map.Custom.putAssumeCapacityNoClobber

函数

第 870 行

向映射插入条目。假定条目尚不存在, 且无需分配内存。

pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void

参数

self: *Self
key: K
value: V

std.hash_map.Custom.putAssumeCapacityNoClobberContext

函数

第 875 行

pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void

参数

self: *Self
key: K
value: V
ctx: Context

std.hash_map.Custom.putContext

函数

第 1028 行

pub fn putContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void

参数

self: *Self
allocator: Allocator
key: K
value: V
ctx: Context

错误

OutOfMemory

std.hash_map.Custom.putNoClobber

函数

第 841 行

将条目插入映射。假定该条目尚不存在。

pub fn putNoClobber(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void

参数

self: *Self
allocator: Allocator
key: K
value: V

错误

OutOfMemory

std.hash_map.Custom.putNoClobberContext

函数

第 846 行

pub fn putNoClobberContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void

参数

self: *Self
allocator: Allocator
key: K
value: V
ctx: Context

错误

OutOfMemory

std.hash_map.Custom.rehash

函数

第 1352 行

原地重新哈希映射。

由于当前使用基于墓碑的实现, 长期使用后,HashMap 可能因墓碑条目 不断积累而产生碎片,过量探测 导致性能下降。可能触发此情况的模式是 长时间存在且反复插入、删除的 HashMap。

调用此函数后,HashMap 中不再存在墓碑, 所有条目均重新哈希,且任何已有的 指向 HashMap 内键或值的指针均失效。

pub fn rehash(self: *Self, ctx: anytype) void

参数

self: *Self

std.hash_map.Custom.remove

函数

第 1243 行

如果哈希映射中存在键匹配的 Entry,则将其删除 并返回 true。否则 返回 false。

TODO: 回答此文档注释中的问题,删除该条目后未使用容量是否会增加一?

pub fn remove(self: *Self, key: K) bool

参数

self: *Self
key: K

std.hash_map.Custom.removeAdapted

函数

第 1257 行

TODO: 回答这些文档注释中的问题:这是否 使未使用容量增加了一个?

pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool

参数

self: *Self

std.hash_map.Custom.removeByIndex

函数

第 1229 行

fn removeByIndex(self: *Self, idx: usize) void

参数

self: *Self
idx: usize

std.hash_map.Custom.removeByPtr

函数

第 1272 行

从哈希映射中删除键由 key_ptr 指向的条目。 假定 key_ptr 是指向哈希映射中 已有键的有效指针。

TODO: 回答这些文档注释中的问题:这是否 使未使用容量增加了一个?

pub fn removeByPtr(self: *Self, key_ptr: *K) void

参数

self: *Self
key_ptr: *K

std.hash_map.Custom.removeContext

函数

第 1251 行

TODO: 回答这些文档注释中的问题:这是否 使未使用容量增加了一个?

pub fn removeContext(self: *Self, key: K, ctx: Context) bool

参数

self: *Self
key: K
ctx: Context

std.hash_map.Custom.Self

别名

第 516 行

别名目标 std.hash_map.Custom

std.hash_map.Custom.Size

类型

第 552 行

std.hash_map.Custom.unlockPointers

函数

第 723 行

撤销一次 lockPointers 调用。

pub fn unlockPointers(self: *Self) void

参数

self: *Self

std.hash_map.Custom.valueIterator

函数

第 824 行

pub fn valueIterator(self: Self) ValueIterator

参数

self: Self

std.hash_map.Custom.ValueIterator

类型

第 663 行

std.hash_map.Custom.values

函数

第 794 行

fn values(self: Self) [*]V

参数

self: Self

std.hash_map.default_max_load_percentage

常量

第 118 行

std.hash_map.eql

函数

第 2020 行

fn eql(self: @This(), adapted_key: []const u8, test_key: u64) bool

参数

self: @This()
adapted_key: []const u8
test_key: u64

std.hash_map.eqlString

函数

第 85 行

pub fn eqlString(a: []const u8, b: []const u8) bool

参数

a: []const u8
b: []const u8

std.hash_map.expect

别名

第 1542 行

别名目标 std.testing.expect

std.hash_map.expectEqual

别名

第 1543 行

别名目标 std.testing.expectEqual

std.hash_map.getAutoEqlFn

函数

第 37 行

pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool)

参数

K: type
Context: type

std.hash_map.getAutoEqlFn.eql

函数

第 39 行

fn eql(ctx: Context, a: K, b: K) bool

参数

ctx: Context
a: K
b: K

std.hash_map.getAutoHashFn

函数

第 11 行

pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u64)

参数

K: type
Context: type

std.hash_map.getAutoHashFn.hash

函数

第 24 行

fn hash(ctx: Context, key: K) u64

参数

ctx: Context
key: K

std.hash_map.hash

函数

第 2024 行

fn hash(self: @This(), adapted_key: []const u8) u64

参数

self: @This()
adapted_key: []const u8

std.hash_map.HashMap

类型函数

第 135 行

通用哈希表。 不保证顺序,任何修改都会使现有迭代器失效。 它在较高负载因子下(默认最高 80%)仍能提供快速的查找、插入和删除操作,从而降低内存占用。 不存储 Allocator 字段、可直接初始化的哈希映射见 HashMapUnmanaged。 如果遍历表条目是重要用例且要求高性能,优先使用 std.ArrayHashMap。 上下文必须是具有以下两个成员函数的结构体类型: hash(self, K) u64 eql(self, K, K) bool 许多函数还提供适配版本。这些版本接受伪键而非键,其上下文必须具有以下函数: hash(self, PseudoKey) u64 eql(self, PseudoKey, K) bool

pub fn HashMap( comptime K: type, comptime V: type, comptime Context: type, comptime max_load_percentage: u64, ) type

参数

K: type
V: type
Context: type
max_load_percentage: u64

字段

unmanaged: Unmanaged
allocator: Allocator
ctx: Context

std.hash_map.HashMap.capacity

函数

第 317 行

返回元素总数上限;超过此值后,就不再保证不会发生分配。

pub fn capacity(self: Self) Size

参数

self: Self

std.hash_map.HashMap.clearAndFree

函数

第 229 行

清空映射并释放底层分配。 这不会释放键或值!若它们需要反初始化, 务必先释放它们,再 调用此函数。

pub fn clearAndFree(self: *Self) void

参数

self: *Self

std.hash_map.HashMap.clearRetainingCapacity

函数

第 221 行

清空映射,但保留底层分配以供后续使用。 不会释放键或值!若它们需要反初始化, 务必在调用此函数之前 释放它们。

pub fn clearRetainingCapacity(self: *Self) void

参数

self: *Self

std.hash_map.HashMap.clone

函数

第 442 行

使用同一分配器创建此映射的副本

pub fn clone(self: Self) Allocator.Error!Self

参数

self: Self

错误

OutOfMemory

std.hash_map.HashMap.cloneWithAllocator

函数

第 448 行

使用指定分配器创建此映射的副本

pub fn cloneWithAllocator(self: Self, new_allocator: Allocator) Allocator.Error!Self

参数

self: Self
new_allocator: Allocator

错误

OutOfMemory

std.hash_map.HashMap.cloneWithAllocatorAndContext

函数

第 460 行

使用指定分配器及上下文创建此映射的副本。

pub fn cloneWithAllocatorAndContext( self: Self, new_allocator: Allocator, new_ctx: anytype, ) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage)

参数

self: Self
new_allocator: Allocator

错误

OutOfMemory

std.hash_map.HashMap.cloneWithContext

函数

第 454 行

使用指定上下文创建此映射的副本。

pub fn cloneWithContext(self: Self, new_ctx: anytype) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage)

参数

self: Self

错误

OutOfMemory

std.hash_map.HashMap.contains

函数

第 407 行

检查映射是否包含某个键

pub fn contains(self: Self, key: K) bool

参数

self: Self
key: K

std.hash_map.HashMap.containsAdapted

函数

第 411 行

pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool

参数

self: Self

std.hash_map.HashMap.count

函数

第 234 行

返回映射中的元素数。

pub fn count(self: Self) Size

参数

self: Self

std.hash_map.HashMap.deinit

函数

第 212 行

释放底层数组,并使此映射失效。 不会对键、值或上下文执行 deinit! 若键或值需要释放,必须确保 在调用此函数前完成释放。

pub fn deinit(self: *Self) void

参数

self: *Self

std.hash_map.HashMap.ensureTotalCapacity

函数

第 304 行

增加容量,保证在达到 expected_count 之前的插入不会分配内存,因此不会失败。

pub fn ensureTotalCapacity(self: *Self, expected_count: Size) Allocator.Error!void

参数

self: *Self
expected_count: Size

错误

OutOfMemory

std.hash_map.HashMap.ensureUnusedCapacity

函数

第 311 行

增加容量,保证再插入最多 additional_count 个项目都不会触发分配,因此不会失败。

pub fn ensureUnusedCapacity(self: *Self, additional_count: Size) Allocator.Error!void

参数

self: *Self
additional_count: Size

错误

OutOfMemory

std.hash_map.HashMap.Entry

常量

第 149 行

条目,包含指向映射中存储的键和值的指针。

std.hash_map.HashMap.fetchPut

函数

第 348 行

将新 Entry 插入哈希映射,并返回之前的条目(如果存在)。

pub fn fetchPut(self: *Self, key: K, value: V) Allocator.Error!?KV

参数

self: *Self
key: K
value: V

错误

OutOfMemory

std.hash_map.HashMap.fetchPutAssumeCapacity

函数

第 354 行

向哈希表插入新的 Entry,若存在旧条目则返回旧条目。 若执行插入,断言容量足够且不分配内存。

pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV

参数

self: *Self
key: K
value: V

std.hash_map.HashMap.fetchRemove

函数

第 359 行

从映射中移除一个值,并返回被移除的键值对。

pub fn fetchRemove(self: *Self, key: K) ?KV

参数

self: *Self
key: K

std.hash_map.HashMap.fetchRemoveAdapted

函数

第 363 行

pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV

参数

self: *Self

std.hash_map.HashMap.get

函数

第 368 行

在映射中查找与某键关联的值

pub fn get(self: Self, key: K) ?V

参数

self: Self
key: K

std.hash_map.HashMap.getAdapted

函数

第 371 行

pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V

参数

self: Self

std.hash_map.HashMap.getEntry

函数

第 398 行

在映射中查找与某键关联的键和值

pub fn getEntry(self: Self, key: K) ?Entry

参数

self: Self
key: K

std.hash_map.HashMap.getEntryAdapted

函数

第 402 行

pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry

参数

self: Self

std.hash_map.HashMap.getKey

函数

第 383 行

查找映射中与适配键对应的实际键

pub fn getKey(self: Self, key: K) ?K

参数

self: Self
key: K

std.hash_map.HashMap.getKeyAdapted

函数

第 386 行

pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K

参数

self: Self

std.hash_map.HashMap.getKeyPtr

函数

第 390 行

pub fn getKeyPtr(self: Self, key: K) ?*K

参数

self: Self
key: K

std.hash_map.HashMap.getKeyPtrAdapted

函数

第 393 行

pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K

参数

self: Self

std.hash_map.HashMap.getOrPut

函数

第 262 行

如果键已存在,此函数不可能失败。 如果已有键为 key 的元素,则结果中的 Entry 指针指向该元素,且 found_existing 为 true。 否则,插入值未定义的新元素, Entry 指针指向该元素。调用方随后应初始化 值,但不初始化键。

pub fn getOrPut(self: *Self, key: K) Allocator.Error!GetOrPutResult

参数

self: *Self
key: K

错误

OutOfMemory

std.hash_map.HashMap.getOrPutAdapted

函数

第 272 行

若键已存在,此函数不会失败。 若已存在键为 key 的元素,结果中的 Entry 指针指向它,且 found_existing 为 true。 否则插入键和值均为 undefined 的新元素,Entry 指针指向它。随后调用者必须初始化键和值。

pub fn getOrPutAdapted(self: *Self, key: anytype, ctx: anytype) Allocator.Error!GetOrPutResult

参数

self: *Self

错误

OutOfMemory

std.hash_map.HashMap.getOrPutAssumeCapacity

函数

第 283 行

若已存在 key 对应的项目,结果的 Entry 指针指向该项目,found_existing 为 true。 否则,插入值为 undefined 的新项目, Entry 指针指向新项目。调用方应随后初始化 其值,但不初始化键。 若需要保存新条目,此函数断言 已有足够容量。

pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult

参数

self: *Self
key: K

std.hash_map.HashMap.getOrPutAssumeCapacityAdapted

函数

第 294 行

如果已存在具有 key 的条目,则结果中的 Entry 指针指向该条目,found_existing 为 true。 否则插入一个值未定义的新条目, Entry 指针指向该条目。随后调用方必须初始化 键和值。 如果需要存储新条目,此函数断言 容量足以容纳它。

pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult

参数

self: *Self

std.hash_map.HashMap.GetOrPutResult

常量

第 163 行

getOrPut 及其变体返回的类型

std.hash_map.HashMap.getOrPutValue

函数

第 298 行

pub fn getOrPutValue(self: *Self, key: K, value: V) Allocator.Error!Entry

参数

self: *Self
key: K
value: V

错误

OutOfMemory

std.hash_map.HashMap.getPtr

函数

第 375 行

pub fn getPtr(self: Self, key: K) ?*V

参数

self: Self
key: K

std.hash_map.HashMap.getPtrAdapted

函数

第 378 行

pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V

参数

self: Self

std.hash_map.HashMap.Hash

常量

第 153 行

哈希计算结果使用的整数类型

std.hash_map.HashMap.init

函数

第 170 行

使用空上下文创建托管哈希映射。 若上下文大小非零,则必须改用 initContext(allocator, ctx)。

pub fn init(allocator: Allocator) Self

参数

allocator: Allocator

std.hash_map.HashMap.initContext

函数

第 182 行

使用上下文创建带内存管理的哈希映射

pub fn initContext(allocator: Allocator, ctx: Context) Self

参数

allocator: Allocator
ctx: Context

std.hash_map.HashMap.iterator

函数

第 240 行

创建遍历映射条目的迭代器。 修改映射会使迭代器失效。

pub fn iterator(self: *const Self) Iterator

参数

self: *const Self

std.hash_map.HashMap.Iterator

常量

第 155 行

iterator() 返回的迭代器类型

std.hash_map.HashMap.keyIterator

函数

第 246 行

创建遍历映射中键的迭代器。 修改映射会使迭代器失效。

pub fn keyIterator(self: Self) KeyIterator

参数

self: Self

std.hash_map.HashMap.KeyIterator

常量

第 157 行

std.hash_map.HashMap.KV

常量

第 151 行

已从映射中移除的键和值的副本。

std.hash_map.HashMap.lockPointers

函数

第 199 行

将哈希映射置于特殊状态:任何会使现有键或值指针失效的方法调用,都改为触发断言。

lockPointers 可以多次调用,使多个独立使用者能同时保持哈希映射锁定。

unlockPointers 在调用次数与 lockPointers 相同时,将哈希映射恢复为原先状态。

pub fn lockPointers(self: *Self) void

参数

self: *Self

std.hash_map.HashMap.move

函数

第 471 行

将映射置为空状态,使反初始化变为空操作, 并返回原映射的副本。

pub fn move(self: *Self) Self

参数

self: *Self

std.hash_map.HashMap.put

函数

第 323 行

覆盖任何已有数据。要检测 put 是否会覆盖 已有数据,请参见 getOrPut。

pub fn put(self: *Self, key: K, value: V) Allocator.Error!void

参数

self: *Self
key: K
value: V

错误

OutOfMemory

std.hash_map.HashMap.putAssumeCapacity

函数

第 336 行

断言容量足以存储新键值对。 覆盖任何已有数据。要检测插入是否会覆盖 已有数据,请参见 getOrPutAssumeCapacity。

pub fn putAssumeCapacity(self: *Self, key: K, value: V) void

参数

self: *Self
key: K
value: V

std.hash_map.HashMap.putAssumeCapacityNoClobber

函数

第 343 行

断言容量足以存储新的键值对。 断言不会覆盖任何现有数据。 若要检测 put 是否会覆盖现有数据,参见 getOrPutAssumeCapacity。

pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void

参数

self: *Self
key: K
value: V

std.hash_map.HashMap.putNoClobber

函数

第 329 行

向哈希映射插入键值对,断言映射中 不存在键相同的条目。

pub fn putNoClobber(self: *Self, key: K, value: V) Allocator.Error!void

参数

self: *Self
key: K
value: V

错误

OutOfMemory

std.hash_map.HashMap.rehash

函数

第 489 行

原地重新哈希映射。

由于当前使用基于墓碑的实现, 长期使用后,HashMap 可能因墓碑条目 不断积累而产生碎片,过量探测 导致性能下降。可能触发此情况的模式是 长时间存在且反复插入、删除的 HashMap。

调用此函数后,HashMap 中不再存在墓碑, 所有条目均重新哈希,且任何已有的 指向 HashMap 内键或值的指针均失效。

pub fn rehash(self: *Self) void

参数

self: *Self

std.hash_map.HashMap.remove

函数

第 421 行

如果哈希映射中存在键匹配的 Entry,则将其删除 并返回 true。否则 返回 false。

TODO: 回答此文档注释中的问题,删除该条目后未使用容量是否会增加一?

pub fn remove(self: *Self, key: K) bool

参数

self: *Self
key: K

std.hash_map.HashMap.removeAdapted

函数

第 427 行

TODO: 回答这些文档注释中的问题:这是否 使未使用容量增加了一个?

pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool

参数

self: *Self

std.hash_map.HashMap.removeByPtr

函数

第 437 行

从哈希映射中删除键由 key_ptr 指向的条目。 假定 key_ptr 是指向哈希映射中 已有键的有效指针。

TODO: 回答这些文档注释中的问题:这是否 使未使用容量增加了一个?

pub fn removeByPtr(self: *Self, key_ptr: *K) void

参数

self: *Self
key_ptr: *K

std.hash_map.HashMap.Self

别名

第 165 行

别名目标 std.hash_map.HashMap

std.hash_map.HashMap.Size

常量

第 161 行

用于存储映射大小的整数类型。

std.hash_map.HashMap.unlockPointers

函数

第 204 行

撤销一次 lockPointers 调用。

pub fn unlockPointers(self: *Self) void

参数

self: *Self

std.hash_map.HashMap.Unmanaged

类型

第 147 行

此封装底层的非托管哈希映射类型。

std.hash_map.HashMap.valueIterator

函数

第 252 行

创建遍历映射值的迭代器。 修改映射会使迭代器失效。

pub fn valueIterator(self: Self) ValueIterator

参数

self: Self

std.hash_map.HashMap.ValueIterator

常量

第 158 行

std.hash_map.HashMapUnmanaged

别名

第 506 行

采用开放寻址和线性探测的 HashMap。 一次查找或修改通常仅产生 2 次缓存未命中。 不保证顺序,任何修改都会使活动迭代器失效。 它在相当高的负载因子下仍具有良好性能,默认 填充率达 80% 时扩容,每个元素仅有一个字节的额外开销。 结构体本身仅占 16 字节,内存占用小。代价是 使用 u32 处理大小;对于几乎所有用途, 这应当足够合理。 删除通过墓碑标记实现。

已弃用此结构体的默认初始化;请改用 .empty。

别名目标 std.hash_map.Custom

std.hash_map.hashString

函数

第 89 行

pub fn hashString(s: []const u8) u64

参数

s: []const u8

std.hash_map.math

别名

第 5 行

别名目标 std.math

std.hash_map.mem

别名

第 6 行

别名目标 std.mem

std.hash_map.std

别名

第 1 行

别名目标 std

std.hash_map.StringContext

命名空间

第 74 行

std.hash_map.StringContext.eql

函数

第 79 行

pub fn eql(self: @This(), a: []const u8, b: []const u8) bool

参数

self: @This()
a: []const u8
b: []const u8

std.hash_map.StringContext.hash

函数

第 75 行

pub fn hash(self: @This(), s: []const u8) u64

参数

self: @This()
s: []const u8

std.hash_map.StringHashMap

类型函数

第 64 行

以字符串为键的内置哈希映射。 键的内存由调用方管理。键和值 不会自动释放。

pub fn StringHashMap(comptime V: type) type

参数

V: type

字段

unmanaged: Unmanaged
allocator: Allocator
ctx: Context

std.hash_map.StringHashMapUnmanaged

类型函数

第 70 行

键内存由调用方管理。 键和值均不会自动释放。

pub fn StringHashMapUnmanaged(comptime V: type) type

参数

V: type

std.hash_map.StringIndexAdapter

容器

第 105 行

字段

bytes: *const std.ArrayList(u8)

std.hash_map.StringIndexAdapter.eql

函数

第 108 行

pub fn eql(ctx: @This(), a: []const u8, b: u32) bool

参数

ctx: @This()
a: []const u8
b: u32

std.hash_map.StringIndexAdapter.hash

函数

第 112 行

pub fn hash(_: @This(), adapted_key: []const u8) u64

参数

_: @This()
adapted_key: []const u8

std.hash_map.StringIndexContext

容器

第 93 行

字段

bytes: *const std.ArrayList(u8)

std.hash_map.StringIndexContext.eql

函数

第 96 行

pub fn eql(_: @This(), a: u32, b: u32) bool

参数

_: @This()
a: u32
b: u32

std.hash_map.StringIndexContext.hash

函数

第 100 行

pub fn hash(ctx: @This(), key: u32) u64

参数

ctx: @This()
key: u32

std.hash_map.testing

别名

第 1541 行

别名目标 std.testing

std.hash_map.Wyhash

别名

第 8 行

别名目标 std.hash.Wyhash

源码

std/hash_map.zig

const std = @import("std.zig");
const builtin = @import("builtin");
const assert = std.debug.assert;
const autoHash = std.hash.autoHash;
const math = std.math;
const mem = std.mem;
const Allocator = mem.Allocator;
const Wyhash = std.hash.Wyhash;
const Alignment = std.mem.Alignment;

pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u64) {
    comptime {
        assert(@hasDecl(std, "StringHashMap")); // 检测何时需要更新下面的消息
        if (K == []const u8) {
            @compileError("std.hash.autoHash does not allow slices here (" ++
                @typeName(K) ++
                ") because the intent is unclear. " ++
                "Consider using std.StringHashMap for hashing the contents of []const u8. " ++
                "Alternatively, consider using std.hash.autoHashStrat or providing your own hash function instead.");
        }
    }

    return struct {
        fn hash(ctx: Context, key: K) u64 {
            _ = ctx;
            if (std.meta.hasUniqueRepresentation(K)) {
                return Wyhash.hash(0, std.mem.asBytes(&key));
            } else {
                var hasher = Wyhash.init(0);
                autoHash(&hasher, key);
                return hasher.final();
            }
        }
    }.hash;
}

pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool) {
    return struct {
        fn eql(ctx: Context, a: K, b: K) bool {
            _ = ctx;
            return std.meta.eql(a, b);
        }
    }.eql;
}

pub fn AutoHashMap(comptime K: type, comptime V: type) type {
    return HashMap(K, V, AutoContext(K), default_max_load_percentage);
}

pub fn AutoHashMapUnmanaged(comptime K: type, comptime V: type) type {
    return HashMapUnmanaged(K, V, AutoContext(K), default_max_load_percentage);
}

pub fn AutoContext(comptime K: type) type {
    return struct {
        pub const hash = getAutoHashFn(K, @This());
        pub const eql = getAutoEqlFn(K, @This());
    };
}

/// 以字符串为键的内置哈希映射。
/// 键的内存由调用方管理。键和值
/// 不会自动释放。
pub fn StringHashMap(comptime V: type) type {
    return HashMap([]const u8, V, StringContext, default_max_load_percentage);
}

/// 键内存由调用方管理。
/// 键和值均不会自动释放。
pub fn StringHashMapUnmanaged(comptime V: type) type {
    return HashMapUnmanaged([]const u8, V, StringContext, default_max_load_percentage);
}

pub const StringContext = struct {
    pub fn hash(self: @This(), s: []const u8) u64 {
        _ = self;
        return hashString(s);
    }
    pub fn eql(self: @This(), a: []const u8, b: []const u8) bool {
        _ = self;
        return eqlString(a, b);
    }
};

pub fn eqlString(a: []const u8, b: []const u8) bool {
    return mem.eql(u8, a, b);
}

pub fn hashString(s: []const u8) u64 {
    return std.hash.Wyhash.hash(0, s);
}

pub const StringIndexContext = struct {
    bytes: *const std.ArrayList(u8),

    pub fn eql(_: @This(), a: u32, b: u32) bool {
        return a == b;
    }

    pub fn hash(ctx: @This(), key: u32) u64 {
        return hashString(mem.sliceTo(ctx.bytes.items[key..], 0));
    }
};

pub const StringIndexAdapter = struct {
    bytes: *const std.ArrayList(u8),

    pub fn eql(ctx: @This(), a: []const u8, b: u32) bool {
        return mem.eql(u8, a, mem.sliceTo(ctx.bytes.items[b..], 0));
    }

    pub fn hash(_: @This(), adapted_key: []const u8) u64 {
        assert(mem.findScalar(u8, adapted_key, 0) == null);
        return hashString(adapted_key);
    }
};

pub const default_max_load_percentage = 80;

/// 通用哈希表。
/// 不保证顺序,任何修改都会使现有迭代器失效。
/// 它在较高负载因子下(默认最高 80%)仍能提供快速的查找、插入和删除操作,从而降低内存占用。
/// 不存储 Allocator 字段、可直接初始化的哈希映射见 `HashMapUnmanaged`。
/// 如果遍历表条目是重要用例且要求高性能,优先使用 `std.ArrayHashMap`。
/// 上下文必须是具有以下两个成员函数的结构体类型:
///   hash(self, K) u64
///   eql(self, K, K) bool
/// 许多函数还提供适配版本。这些版本接受伪键而非键,其上下文必须具有以下函数:
///   hash(self, PseudoKey) u64
///   eql(self, PseudoKey, K) bool
///
///
///
///
pub fn HashMap(
    comptime K: type,
    comptime V: type,
    comptime Context: type,
    comptime max_load_percentage: u64,
) type {
    return struct {
        unmanaged: Unmanaged,
        allocator: Allocator,
        ctx: Context,

        /// 此封装底层的非托管哈希映射类型。
        pub const Unmanaged = HashMapUnmanaged(K, V, Context, max_load_percentage);
        /// 条目,包含指向映射中存储的键和值的指针。
        pub const Entry = Unmanaged.Entry;
        /// 已从映射中移除的键和值的副本。
        pub const KV = Unmanaged.KV;
        /// 哈希计算结果使用的整数类型
        pub const Hash = Unmanaged.Hash;
        /// iterator() 返回的迭代器类型
        pub const Iterator = Unmanaged.Iterator;

        pub const KeyIterator = Unmanaged.KeyIterator;
        pub const ValueIterator = Unmanaged.ValueIterator;

        /// 用于存储映射大小的整数类型。
        pub const Size = Unmanaged.Size;
        /// getOrPut 及其变体返回的类型
        pub const GetOrPutResult = Unmanaged.GetOrPutResult;

        const Self = @This();

        /// 使用空上下文创建托管哈希映射。
        /// 若上下文大小非零,则必须改用 initContext(allocator, ctx)。
        ///
        pub fn init(allocator: Allocator) Self {
            if (@sizeOf(Context) != 0) {
                @compileError("Context must be specified! Call initContext(allocator, ctx) instead.");
            }
            return .{
                .unmanaged = .empty,
                .allocator = allocator,
                .ctx = undefined, // ctx 大小为零,因此这是安全的。
            };
        }

        /// 使用上下文创建带内存管理的哈希映射
        pub fn initContext(allocator: Allocator, ctx: Context) Self {
            return .{
                .unmanaged = .empty,
                .allocator = allocator,
                .ctx = ctx,
            };
        }

        /// 将哈希映射置于特殊状态:任何会使现有键或值指针失效的方法调用,都改为触发断言。
        ///
        /// `lockPointers` 可以多次调用,使多个独立使用者能同时保持哈希映射锁定。
        ///
        /// `unlockPointers` 在调用次数与 `lockPointers` 相同时,将哈希映射恢复为原先状态。
        ///
        ///
        ///
        ///
        pub fn lockPointers(self: *Self) void {
            self.unmanaged.lockPointers();
        }

        /// 撤销一次 `lockPointers` 调用。
        pub fn unlockPointers(self: *Self) void {
            self.unmanaged.unlockPointers();
        }

        /// 释放底层数组,并使此映射失效。
        /// 不会对键、值或上下文执行 deinit!
        /// 若键或值需要释放,必须确保
        /// 在调用此函数前完成释放。
        pub fn deinit(self: *Self) void {
            self.unmanaged.deinit(self.allocator);
            self.* = undefined;
        }

        /// 清空映射,但保留底层分配以供后续使用。
        /// 不会释放键或值!若它们需要反初始化,
        /// 务必在调用此函数之前
        /// 释放它们。
        pub fn clearRetainingCapacity(self: *Self) void {
            return self.unmanaged.clearRetainingCapacity();
        }

        /// 清空映射并释放底层分配。
        /// 这*不会*释放键或值!若它们需要反初始化,
        /// 务必先释放它们,再
        /// 调用此函数。
        pub fn clearAndFree(self: *Self) void {
            return self.unmanaged.clearAndFree(self.allocator);
        }

        /// 返回映射中的元素数。
        pub fn count(self: Self) Size {
            return self.unmanaged.count();
        }

        /// 创建遍历映射条目的迭代器。
        /// 修改映射会使迭代器失效。
        pub fn iterator(self: *const Self) Iterator {
            return self.unmanaged.iterator();
        }

        /// 创建遍历映射中键的迭代器。
        /// 修改映射会使迭代器失效。
        pub fn keyIterator(self: Self) KeyIterator {
            return self.unmanaged.keyIterator();
        }

        /// 创建遍历映射值的迭代器。
        /// 修改映射会使迭代器失效。
        pub fn valueIterator(self: Self) ValueIterator {
            return self.unmanaged.valueIterator();
        }

        /// 如果键已存在,此函数不可能失败。
        /// 如果已有键为 `key` 的元素,则结果中的
        /// `Entry` 指针指向该元素,且 found_existing 为 true。
        /// 否则,插入值未定义的新元素,
        /// `Entry` 指针指向该元素。调用方随后应初始化
        /// 值,但不初始化键。
        pub fn getOrPut(self: *Self, key: K) Allocator.Error!GetOrPutResult {
            return self.unmanaged.getOrPutContext(self.allocator, key, self.ctx);
        }

        /// 若键已存在,此函数不会失败。
        /// 若已存在键为 `key` 的元素,结果中的 `Entry` 指针指向它,且 found_existing 为 true。
        /// 否则插入键和值均为 undefined 的新元素,`Entry` 指针指向它。随后调用者必须初始化键和值。
        ///
        ///
        ///
        pub fn getOrPutAdapted(self: *Self, key: anytype, ctx: anytype) Allocator.Error!GetOrPutResult {
            return self.unmanaged.getOrPutContextAdapted(self.allocator, key, ctx, self.ctx);
        }

        /// 若已存在 `key` 对应的项目,结果的
        /// `Entry` 指针指向该项目,found_existing 为 true。
        /// 否则,插入值为 undefined 的新项目,
        /// `Entry` 指针指向新项目。调用方应随后初始化
        /// 其值,但不初始化键。
        /// 若需要保存新条目,此函数断言
        /// 已有足够容量。
        pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
            return self.unmanaged.getOrPutAssumeCapacityContext(key, self.ctx);
        }

        /// 如果已存在具有 `key` 的条目,则结果中的
        /// `Entry` 指针指向该条目,found_existing 为 true。
        /// 否则插入一个值未定义的新条目,
        /// `Entry` 指针指向该条目。随后调用方必须初始化
        /// 键和值。
        /// 如果需要存储新条目,此函数断言
        /// 容量足以容纳它。
        pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
            return self.unmanaged.getOrPutAssumeCapacityAdapted(key, ctx);
        }

        pub fn getOrPutValue(self: *Self, key: K, value: V) Allocator.Error!Entry {
            return self.unmanaged.getOrPutValueContext(self.allocator, key, value, self.ctx);
        }

        /// 增加容量,保证在达到
        /// `expected_count` 之前的插入不会分配内存,因此不会失败。
        pub fn ensureTotalCapacity(self: *Self, expected_count: Size) Allocator.Error!void {
            return self.unmanaged.ensureTotalCapacityContext(self.allocator, expected_count, self.ctx);
        }

        /// 增加容量,保证再插入最多 `additional_count` 个项目都不会触发分配,因此不会失败。
        ///
        ///
        pub fn ensureUnusedCapacity(self: *Self, additional_count: Size) Allocator.Error!void {
            return self.unmanaged.ensureUnusedCapacityContext(self.allocator, additional_count, self.ctx);
        }

        /// 返回元素总数上限;超过此值后,就不再保证不会发生分配。
        ///
        pub fn capacity(self: Self) Size {
            return self.unmanaged.capacity();
        }

        /// 覆盖任何已有数据。要检测 put 是否会覆盖
        /// 已有数据,请参见 `getOrPut`。
        pub fn put(self: *Self, key: K, value: V) Allocator.Error!void {
            return self.unmanaged.putContext(self.allocator, key, value, self.ctx);
        }

        /// 向哈希映射插入键值对,断言映射中
        /// 不存在键相同的条目。
        pub fn putNoClobber(self: *Self, key: K, value: V) Allocator.Error!void {
            return self.unmanaged.putNoClobberContext(self.allocator, key, value, self.ctx);
        }

        /// 断言容量足以存储新键值对。
        /// 覆盖任何已有数据。要检测插入是否会覆盖
        /// 已有数据,请参见 `getOrPutAssumeCapacity`。
        pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
            return self.unmanaged.putAssumeCapacityContext(key, value, self.ctx);
        }

        /// 断言容量足以存储新的键值对。
        /// 断言不会覆盖任何现有数据。
        /// 若要检测 put 是否会覆盖现有数据,参见 `getOrPutAssumeCapacity`。
        pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
            return self.unmanaged.putAssumeCapacityNoClobberContext(key, value, self.ctx);
        }

        /// 将新 `Entry` 插入哈希映射,并返回之前的条目(如果存在)。
        pub fn fetchPut(self: *Self, key: K, value: V) Allocator.Error!?KV {
            return self.unmanaged.fetchPutContext(self.allocator, key, value, self.ctx);
        }

        /// 向哈希表插入新的 `Entry`,若存在旧条目则返回旧条目。
        /// 若执行插入,断言容量足够且不分配内存。
        pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
            return self.unmanaged.fetchPutAssumeCapacityContext(key, value, self.ctx);
        }

        /// 从映射中移除一个值,并返回被移除的键值对。
        pub fn fetchRemove(self: *Self, key: K) ?KV {
            return self.unmanaged.fetchRemoveContext(key, self.ctx);
        }

        pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
            return self.unmanaged.fetchRemoveAdapted(key, ctx);
        }

        /// 在映射中查找与某键关联的值
        pub fn get(self: Self, key: K) ?V {
            return self.unmanaged.getContext(key, self.ctx);
        }
        pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
            return self.unmanaged.getAdapted(key, ctx);
        }

        pub fn getPtr(self: Self, key: K) ?*V {
            return self.unmanaged.getPtrContext(key, self.ctx);
        }
        pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
            return self.unmanaged.getPtrAdapted(key, ctx);
        }

        /// 查找映射中与适配键对应的实际键
        pub fn getKey(self: Self, key: K) ?K {
            return self.unmanaged.getKeyContext(key, self.ctx);
        }
        pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
            return self.unmanaged.getKeyAdapted(key, ctx);
        }

        pub fn getKeyPtr(self: Self, key: K) ?*K {
            return self.unmanaged.getKeyPtrContext(key, self.ctx);
        }
        pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
            return self.unmanaged.getKeyPtrAdapted(key, ctx);
        }

        /// 在映射中查找与某键关联的键和值
        pub fn getEntry(self: Self, key: K) ?Entry {
            return self.unmanaged.getEntryContext(key, self.ctx);
        }

        pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
            return self.unmanaged.getEntryAdapted(key, ctx);
        }

        /// 检查映射是否包含某个键
        pub fn contains(self: Self, key: K) bool {
            return self.unmanaged.containsContext(key, self.ctx);
        }

        pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
            return self.unmanaged.containsAdapted(key, ctx);
        }

        /// 如果哈希映射中存在键匹配的 `Entry`,则将其删除
        /// 并返回 true。否则
        /// 返回 false。
        ///
        /// TODO: 回答此文档注释中的问题,删除该条目后未使用容量是否会增加一?
        ///
        pub fn remove(self: *Self, key: K) bool {
            return self.unmanaged.removeContext(key, self.ctx);
        }

        /// TODO: 回答这些文档注释中的问题:这是否
        /// 使未使用容量增加了一个?
        pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
            return self.unmanaged.removeAdapted(key, ctx);
        }

        /// 从哈希映射中删除键由 key_ptr 指向的条目。
        /// 假定 key_ptr 是指向哈希映射中
        /// 已有键的有效指针。
        ///
        /// TODO: 回答这些文档注释中的问题:这是否
        /// 使未使用容量增加了一个?
        pub fn removeByPtr(self: *Self, key_ptr: *K) void {
            self.unmanaged.removeByPtr(key_ptr);
        }

        /// 使用同一分配器创建此映射的副本
        pub fn clone(self: Self) Allocator.Error!Self {
            var other = try self.unmanaged.cloneContext(self.allocator, self.ctx);
            return other.promoteContext(self.allocator, self.ctx);
        }

        /// 使用指定分配器创建此映射的副本
        pub fn cloneWithAllocator(self: Self, new_allocator: Allocator) Allocator.Error!Self {
            var other = try self.unmanaged.cloneContext(new_allocator, self.ctx);
            return other.promoteContext(new_allocator, self.ctx);
        }

        /// 使用指定上下文创建此映射的副本。
        pub fn cloneWithContext(self: Self, new_ctx: anytype) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
            var other = try self.unmanaged.cloneContext(self.allocator, new_ctx);
            return other.promoteContext(self.allocator, new_ctx);
        }

        /// 使用指定分配器及上下文创建此映射的副本。
        pub fn cloneWithAllocatorAndContext(
            self: Self,
            new_allocator: Allocator,
            new_ctx: anytype,
        ) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
            var other = try self.unmanaged.cloneContext(new_allocator, new_ctx);
            return other.promoteContext(new_allocator, new_ctx);
        }

        /// 将映射置为空状态,使反初始化变为空操作,
        /// 并返回原映射的副本。
        pub fn move(self: *Self) Self {
            self.unmanaged.pointer_stability.assertUnlocked();
            const result = self.*;
            self.unmanaged = .empty;
            return result;
        }

        /// 原地重新哈希映射。
        ///
        /// 由于当前使用基于墓碑的实现,
        /// 长期使用后,HashMap 可能因墓碑条目
        /// 不断积累而产生碎片,过量探测
        /// 导致性能下降。可能触发此情况的模式是
        /// 长时间存在且反复插入、删除的 HashMap。
        ///
        /// 调用此函数后,HashMap 中不再存在墓碑,
        /// 所有条目均重新哈希,且任何已有的
        /// 指向 HashMap 内键或值的指针均失效。
        pub fn rehash(self: *Self) void {
            self.unmanaged.rehash(self.ctx);
        }
    };
}

/// 采用开放寻址和线性探测的 HashMap。
/// 一次查找或修改通常仅产生 2 次缓存未命中。
/// 不保证顺序,任何修改都会使活动迭代器失效。
/// 它在相当高的负载因子下仍具有良好性能,默认
/// 填充率达 80% 时扩容,每个元素仅有一个字节的额外开销。
/// 结构体本身仅占 16 字节,内存占用小。代价是
/// 使用 u32 处理大小;对于几乎所有用途,
/// 这应当足够合理。
/// 删除通过墓碑标记实现。
///
/// 已弃用此结构体的默认初始化;请改用 `.empty`。
pub const HashMapUnmanaged = Custom;
fn Custom(
    comptime K: type,
    comptime V: type,
    comptime Context: type,
    comptime max_load_percentage: u64,
) type {
    if (max_load_percentage <= 0 or max_load_percentage >= 100)
        @compileError("max_load_percentage must be between 0 and 100.");
    return struct {
        const Self = @This();

        // 此指针实际上指向单个缓冲区的中间位置,缓冲区包含
        // 一个 `Header` 字段、若干 `Metadata` 和 `Entry`。
        // 偏移 `-@sizeOf(Header)` 处为 Header 字段。
        // 偏移 `sizeOf(Metadata) * capacity + offset` 处,即
        // self.header().entries 指向的位置,为条目数组。
        // 这意味着哈希映射只持有一个活跃分配,
        // 以减少内存碎片和结构体大小。
        /// 指向元数据的指针。
        metadata: ?[*]Metadata = null,

        /// 哈希映射中当前的元素数。
        size: Size = 0,

        // 通过倒计时决定何时扩容,可减少判断哈希映射容量是否足够时执行的指令数。
        //
        /// 在为满足 `max_load_percentage` 而必须扩容之前,
        /// 可用的槽位数量。
        available: Size = 0,

        /// 用于检测内存安全违规。
        pointer_stability: std.debug.SafetyLock = .{},

        // 这完全来自经验,并非某个特别巧妙的魔数。
        /// 哈希映射引导初始化时首次扩容的容量。
        const minimal_capacity = 8;

        /// 不含任何键值的映射。
        pub const empty: Self = .{
            .metadata = null,
            .size = 0,
            .available = 0,
        };

        // 此哈希映射专为大小可由 u32 表示的情况设计。
        pub const Size = u32;

        // u64 哈希保证指纹位不会用于
        // 计算槽位索引,从而充分利用熵。
        pub const Hash = u64;

        pub const Entry = struct {
            key_ptr: *K,
            value_ptr: *V,
        };

        pub const KV = struct {
            key: K,
            value: V,
        };

        const Header = struct {
            values: [*]V,
            keys: [*]K,
            capacity: Size,
        };

        /// 槽位的元数据,有空闲、已使用和
        /// 墓碑三种状态。墓碑表示条目曾经被使用过,
        /// 是处理删除操作的一种简单方式。
        /// 除状态外,还保存槽位键的哈希值中的 7 位。
        /// 利用这几位可以快速区分条目,
        /// 不必调用相等性比较函数。如果两个指纹
        /// 不同,就完全不必比较键。
        /// 这 7 位取自 64 位哈希值的最高位。因此,
        /// 除了用哈希值的最低 `log2(capacity)` 位确定
        /// 槽位索引外,还额外利用 7 位快速消解
        /// 哈希值不同的多个元素竞争同一槽位时的冲突。
        /// 不调用相等性比较函数意味着无需读取
        /// 条目数组,从而可能避免缓存未命中和
        /// 开销较大的函数调用。
        const Metadata = packed struct {
            const FingerPrint = u7;

            const free: FingerPrint = 0;
            const tombstone: FingerPrint = 1;

            fingerprint: FingerPrint = free,
            used: u1 = 0,

            const slot_free: u8 = @bitCast(Metadata{ .fingerprint = free });
            const slot_tombstone: u8 = @bitCast(Metadata{ .fingerprint = tombstone });

            pub fn isUsed(self: Metadata) bool {
                return self.used == 1;
            }

            pub fn isTombstone(self: Metadata) bool {
                return @as(u8, @bitCast(self)) == slot_tombstone;
            }

            pub fn isFree(self: Metadata) bool {
                return @as(u8, @bitCast(self)) == slot_free;
            }

            pub fn takeFingerprint(hash: Hash) FingerPrint {
                const hash_bits = @typeInfo(Hash).int.bits;
                const fp_bits = @typeInfo(FingerPrint).int.bits;
                return @as(FingerPrint, @truncate(hash >> (hash_bits - fp_bits)));
            }

            pub fn fill(self: *Metadata, fp: FingerPrint) void {
                self.used = 1;
                self.fingerprint = fp;
            }

            pub fn remove(self: *Metadata) void {
                self.used = 0;
                self.fingerprint = tombstone;
            }
        };

        comptime {
            assert(@sizeOf(Metadata) == 1);
            assert(@alignOf(Metadata) == 1);
        }

        pub const Iterator = struct {
            hm: *const Self,
            index: Size = 0,

            pub fn next(it: *Iterator) ?Entry {
                assert(it.index <= it.hm.capacity());
                if (it.hm.size == 0) return null;

                const cap = it.hm.capacity();
                const end = it.hm.metadata.? + cap;
                var metadata = it.hm.metadata.? + it.index;

                while (metadata != end) : ({
                    metadata += 1;
                    it.index += 1;
                }) {
                    if (metadata[0].isUsed()) {
                        const key = &it.hm.keys()[it.index];
                        const value = &it.hm.values()[it.index];
                        it.index += 1;
                        return Entry{ .key_ptr = key, .value_ptr = value };
                    }
                }

                return null;
            }
        };

        pub const KeyIterator = FieldIterator(K);
        pub const ValueIterator = FieldIterator(V);

        fn FieldIterator(comptime T: type) type {
            return struct {
                len: usize,
                metadata: [*]const Metadata,
                items: [*]T,

                pub fn next(self: *@This()) ?*T {
                    while (self.len > 0) {
                        self.len -= 1;
                        const used = self.metadata[0].isUsed();
                        const item = &self.items[0];
                        self.metadata += 1;
                        self.items += 1;
                        if (used) {
                            return item;
                        }
                    }
                    return null;
                }
            };
        }

        pub const GetOrPutResult = struct {
            key_ptr: *K,
            value_ptr: *V,
            found_existing: bool,
        };

        pub const Managed = HashMap(K, V, Context, max_load_percentage);

        pub fn promote(self: Self, allocator: Allocator) Managed {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call promoteContext instead.");
            return promoteContext(self, allocator, undefined);
        }

        pub fn promoteContext(self: Self, allocator: Allocator, ctx: Context) Managed {
            return .{
                .unmanaged = self,
                .allocator = allocator,
                .ctx = ctx,
            };
        }

        /// 将哈希映射置于特殊状态:任何会使现有键或值指针失效的方法调用,都改为触发断言。
        ///
        /// `lockPointers` 可以多次调用,使多个独立使用者能同时保持哈希映射锁定。
        ///
        /// `unlockPointers` 在调用次数与 `lockPointers` 相同时,将哈希映射恢复为原先状态。
        ///
        ///
        ///
        ///
        pub fn lockPointers(self: *Self) void {
            self.pointer_stability.lockShared();
        }

        /// 撤销一次 `lockPointers` 调用。
        pub fn unlockPointers(self: *Self) void {
            self.pointer_stability.unlockShared();
        }

        fn isUnderMaxLoadPercentage(size: Size, cap: Size) bool {
            return size * 100 < max_load_percentage * cap;
        }

        pub fn deinit(self: *Self, allocator: Allocator) void {
            self.pointer_stability.assertUnlocked();
            self.deallocate(allocator);
            self.* = undefined;
        }

        fn capacityForSize(size: Size) Size {
            var new_cap: u32 = @intCast((@as(u64, size) * 100) / max_load_percentage + 1);
            new_cap = math.ceilPowerOfTwo(u32, new_cap) catch unreachable;
            return new_cap;
        }

        pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_size: Size) Allocator.Error!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead.");
            return ensureTotalCapacityContext(self, allocator, new_size, undefined);
        }
        pub fn ensureTotalCapacityContext(self: *Self, allocator: Allocator, new_size: Size, ctx: Context) Allocator.Error!void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();
            if (new_size > self.size)
                try self.growIfNeeded(allocator, new_size - self.size, ctx);
        }

        pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_size: Size) Allocator.Error!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureUnusedCapacityContext instead.");
            return ensureUnusedCapacityContext(self, allocator, additional_size, undefined);
        }
        pub fn ensureUnusedCapacityContext(self: *Self, allocator: Allocator, additional_size: Size, ctx: Context) Allocator.Error!void {
            return ensureTotalCapacityContext(self, allocator, self.count() + additional_size, ctx);
        }

        pub fn clearRetainingCapacity(self: *Self) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();
            if (self.metadata) |_| {
                self.initMetadatas();
                self.size = 0;
                self.available = @truncate((self.capacity() * max_load_percentage) / 100);
            }
        }

        pub fn clearAndFree(self: *Self, allocator: Allocator) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();
            self.deallocate(allocator);
            self.size = 0;
            self.available = 0;
        }

        pub fn count(self: Self) Size {
            return self.size;
        }

        fn header(self: Self) *Header {
            return @ptrCast(@as([*]Header, @ptrCast(@alignCast(self.metadata.?))) - 1);
        }

        fn keys(self: Self) [*]K {
            return self.header().keys;
        }

        fn values(self: Self) [*]V {
            return self.header().values;
        }

        pub fn capacity(self: Self) Size {
            if (self.metadata == null) return 0;

            return self.header().capacity;
        }

        pub fn iterator(self: *const Self) Iterator {
            return .{ .hm = self };
        }

        pub fn keyIterator(self: Self) KeyIterator {
            if (self.metadata) |metadata| {
                return .{
                    .len = self.capacity(),
                    .metadata = metadata,
                    .items = self.keys(),
                };
            } else {
                return .{
                    .len = 0,
                    .metadata = undefined,
                    .items = undefined,
                };
            }
        }

        pub fn valueIterator(self: Self) ValueIterator {
            if (self.metadata) |metadata| {
                return .{
                    .len = self.capacity(),
                    .metadata = metadata,
                    .items = self.values(),
                };
            } else {
                return .{
                    .len = 0,
                    .metadata = undefined,
                    .items = undefined,
                };
            }
        }

        /// 将条目插入映射。假定该条目尚不存在。
        pub fn putNoClobber(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putNoClobberContext instead.");
            return self.putNoClobberContext(allocator, key, value, undefined);
        }
        pub fn putNoClobberContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void {
            {
                self.pointer_stability.lock();
                defer self.pointer_stability.unlock();
                try self.growIfNeeded(allocator, 1, ctx);
            }
            self.putAssumeCapacityNoClobberContext(key, value, ctx);
        }

        /// 断言容量足以存储新键值对。
        /// 覆盖任何已有数据。要检测插入是否会覆盖
        /// 已有数据,请参见 `getOrPutAssumeCapacity`。
        pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityContext instead.");
            return self.putAssumeCapacityContext(key, value, undefined);
        }
        pub fn putAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) void {
            const gop = self.getOrPutAssumeCapacityContext(key, ctx);
            gop.value_ptr.* = value;
        }

        /// 向映射插入条目。假定条目尚不存在,
        /// 且无需分配内存。
        pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityNoClobberContext instead.");
            return self.putAssumeCapacityNoClobberContext(key, value, undefined);
        }
        pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void {
            assert(!self.containsContext(key, ctx));

            const hash: Hash = ctx.hash(key);
            const mask = self.capacity() - 1;
            var idx: usize = @truncate(hash & mask);

            var metadata = self.metadata.? + idx;
            while (metadata[0].isUsed()) {
                idx = (idx + 1) & mask;
                metadata = self.metadata.? + idx;
            }

            assert(self.available > 0);
            self.available -= 1;

            const fingerprint = Metadata.takeFingerprint(hash);
            metadata[0].fill(fingerprint);
            self.keys()[idx] = key;
            self.values()[idx] = value;

            self.size += 1;
        }

        /// 将新 `Entry` 插入哈希映射,并返回之前的条目(如果存在)。
        pub fn fetchPut(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutContext instead.");
            return self.fetchPutContext(allocator, key, value, undefined);
        }
        pub fn fetchPutContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!?KV {
            const gop = try self.getOrPutContext(allocator, key, ctx);
            var result: ?KV = null;
            if (gop.found_existing) {
                result = KV{
                    .key = gop.key_ptr.*,
                    .value = gop.value_ptr.*,
                };
            }
            gop.value_ptr.* = value;
            return result;
        }

        /// 向哈希表插入新的 `Entry`,若存在旧条目则返回旧条目。
        /// 若执行插入,断言容量足够且不分配内存。
        pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutAssumeCapacityContext instead.");
            return self.fetchPutAssumeCapacityContext(key, value, undefined);
        }
        pub fn fetchPutAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) ?KV {
            const gop = self.getOrPutAssumeCapacityContext(key, ctx);
            var result: ?KV = null;
            if (gop.found_existing) {
                result = KV{
                    .key = gop.key_ptr.*,
                    .value = gop.value_ptr.*,
                };
            }
            gop.value_ptr.* = value;
            return result;
        }

        /// 若存在键匹配的 `Entry`,则从
        /// 哈希映射中删除,并由此函数返回。
        pub fn fetchRemove(self: *Self, key: K) ?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchRemoveContext instead.");
            return self.fetchRemoveContext(key, undefined);
        }
        pub fn fetchRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
            return self.fetchRemoveAdapted(key, ctx);
        }
        pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
            if (self.getIndex(key, ctx)) |idx| {
                const old_key = &self.keys()[idx];
                const old_val = &self.values()[idx];
                const result = KV{
                    .key = old_key.*,
                    .value = old_val.*,
                };
                self.metadata.?[idx].remove();
                old_key.* = undefined;
                old_val.* = undefined;
                self.size -= 1;
                self.available += 1;
                return result;
            }

            return null;
        }

        /// 查找包含给定键对应数据的索引。
        fn getIndex(self: Self, key: anytype, ctx: anytype) ?usize {
            if (self.size == 0) {
                // 使用 cold 而不是 unlikely,以强制跳转到此分支,
                // 不受另一分支权重的影响。
                @branchHint(.cold);
                return null;
            }

            // 若此行出现编译错误,表示泛型 hash 函数对于这些参数无效。
            //
            const hash: Hash = ctx.hash(key);

            const mask = self.capacity() - 1;
            const fingerprint = Metadata.takeFingerprint(hash);
            // 没有空槽位时,不要无限循环。
            var limit = self.capacity();
            var idx = @as(usize, @truncate(hash & mask));

            var metadata = self.metadata.? + idx;
            while (!metadata[0].isFree() and limit != 0) {
                if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
                    const test_key = &self.keys()[idx];

                    if (ctx.eql(key, test_key.*)) {
                        return idx;
                    }
                }

                limit -= 1;
                idx = (idx + 1) & mask;
                metadata = self.metadata.? + idx;
            }

            return null;
        }

        pub fn getEntry(self: Self, key: K) ?Entry {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getEntryContext instead.");
            return self.getEntryContext(key, undefined);
        }
        pub fn getEntryContext(self: Self, key: K, ctx: Context) ?Entry {
            return self.getEntryAdapted(key, ctx);
        }
        pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
            if (self.getIndex(key, ctx)) |idx| {
                return Entry{
                    .key_ptr = &self.keys()[idx],
                    .value_ptr = &self.values()[idx],
                };
            }
            return null;
        }

        /// 如果关联键尚不存在,则插入条目;否则更新现有值。
        pub fn put(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putContext instead.");
            return self.putContext(allocator, key, value, undefined);
        }
        pub fn putContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void {
            const result = try self.getOrPutContext(allocator, key, ctx);
            result.value_ptr.* = value;
        }

        /// 若存在与适配键关联的实际键,获取指向该键的可选指针。
        pub fn getKeyPtr(self: Self, key: K) ?*K {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyPtrContext instead.");
            return self.getKeyPtrContext(key, undefined);
        }
        pub fn getKeyPtrContext(self: Self, key: K, ctx: Context) ?*K {
            return self.getKeyPtrAdapted(key, ctx);
        }
        pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
            if (self.getIndex(key, ctx)) |idx| {
                return &self.keys()[idx];
            }
            return null;
        }

        /// 若存在,获取与适配键对应的实际键的副本。
        pub fn getKey(self: Self, key: K) ?K {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyContext instead.");
            return self.getKeyContext(key, undefined);
        }
        pub fn getKeyContext(self: Self, key: K, ctx: Context) ?K {
            return self.getKeyAdapted(key, ctx);
        }
        pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
            if (self.getIndex(key, ctx)) |idx| {
                return self.keys()[idx];
            }
            return null;
        }

        /// 若存在与键关联的值,则获取指向它的可选指针。
        pub fn getPtr(self: Self, key: K) ?*V {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getPtrContext instead.");
            return self.getPtrContext(key, undefined);
        }
        pub fn getPtrContext(self: Self, key: K, ctx: Context) ?*V {
            return self.getPtrAdapted(key, ctx);
        }
        pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
            if (self.getIndex(key, ctx)) |idx| {
                return &self.values()[idx];
            }
            return null;
        }

        /// 若键存在,则获取与其关联的值的副本。
        pub fn get(self: Self, key: K) ?V {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getContext instead.");
            return self.getContext(key, undefined);
        }
        pub fn getContext(self: Self, key: K, ctx: Context) ?V {
            return self.getAdapted(key, ctx);
        }
        pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
            if (self.getIndex(key, ctx)) |idx| {
                return self.values()[idx];
            }
            return null;
        }

        pub fn getOrPut(self: *Self, allocator: Allocator, key: K) Allocator.Error!GetOrPutResult {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead.");
            return self.getOrPutContext(allocator, key, undefined);
        }
        pub fn getOrPutContext(self: *Self, allocator: Allocator, key: K, ctx: Context) Allocator.Error!GetOrPutResult {
            const gop = try self.getOrPutContextAdapted(allocator, key, ctx, ctx);
            if (!gop.found_existing) {
                gop.key_ptr.* = key;
            }
            return gop;
        }
        pub fn getOrPutAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype) Allocator.Error!GetOrPutResult {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContextAdapted instead.");
            return self.getOrPutContextAdapted(allocator, key, key_ctx, undefined);
        }
        pub fn getOrPutContextAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Allocator.Error!GetOrPutResult {
            {
                self.pointer_stability.lock();
                defer self.pointer_stability.unlock();
                self.growIfNeeded(allocator, 1, ctx) catch |err| {
                    // 若分配失败,仍尝试查找。
                    // 如果找到现有项,便可以返回它。
                    // 否则返回错误,因为无法再添加一项。
                    const index = self.getIndex(key, key_ctx) orelse return err;
                    return GetOrPutResult{
                        .key_ptr = &self.keys()[index],
                        .value_ptr = &self.values()[index],
                        .found_existing = true,
                    };
                };
            }
            return self.getOrPutAssumeCapacityAdapted(key, key_ctx);
        }

        pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutAssumeCapacityContext instead.");
            return self.getOrPutAssumeCapacityContext(key, undefined);
        }
        pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult {
            const result = self.getOrPutAssumeCapacityAdapted(key, ctx);
            if (!result.found_existing) {
                result.key_ptr.* = key;
            }
            return result;
        }
        pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {

            // 若此行出现编译错误,表示泛型 hash 函数对于这些参数无效。
            //
            const hash: Hash = ctx.hash(key);

            const mask = self.capacity() - 1;
            const fingerprint = Metadata.takeFingerprint(hash);
            var limit = self.capacity();
            var idx = @as(usize, @truncate(hash & mask));

            var first_tombstone_idx: usize = self.capacity(); // 索引无效
            var metadata = self.metadata.? + idx;
            while (!metadata[0].isFree() and limit != 0) {
                if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
                    const test_key = &self.keys()[idx];
                    // 若此行产生编译错误,表示泛型 eql
                    // 函数对这些参数无效。

                    if (ctx.eql(key, test_key.*)) {
                        return GetOrPutResult{
                            .key_ptr = test_key,
                            .value_ptr = &self.values()[idx],
                            .found_existing = true,
                        };
                    }
                } else if (first_tombstone_idx == self.capacity() and metadata[0].isTombstone()) {
                    first_tombstone_idx = idx;
                }

                limit -= 1;
                idx = (idx + 1) & mask;
                metadata = self.metadata.? + idx;
            }

            if (first_tombstone_idx < self.capacity()) {
                // 在删除后低成本地尝试缩短探测长度,回收一个墓碑。
                idx = first_tombstone_idx;
                metadata = self.metadata.? + idx;
            }
            // 正在使用先前空闲或为墓碑的槽位。
            self.available -= 1;

            metadata[0].fill(fingerprint);
            const new_key = &self.keys()[idx];
            const new_value = &self.values()[idx];
            new_key.* = undefined;
            new_value.* = undefined;
            self.size += 1;

            return GetOrPutResult{
                .key_ptr = new_key,
                .value_ptr = new_value,
                .found_existing = false,
            };
        }

        pub fn getOrPutValue(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!Entry {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutValueContext instead.");
            return self.getOrPutValueContext(allocator, key, value, undefined);
        }
        pub fn getOrPutValueContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!Entry {
            const res = try self.getOrPutAdapted(allocator, key, ctx);
            if (!res.found_existing) {
                res.key_ptr.* = key;
                res.value_ptr.* = value;
            }
            return Entry{ .key_ptr = res.key_ptr, .value_ptr = res.value_ptr };
        }

        /// 若映射中存在与 key 关联的值,则返回 true。
        pub fn contains(self: Self, key: K) bool {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call containsContext instead.");
            return self.containsContext(key, undefined);
        }
        pub fn containsContext(self: Self, key: K, ctx: Context) bool {
            return self.containsAdapted(key, ctx);
        }
        pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
            return self.getIndex(key, ctx) != null;
        }

        fn removeByIndex(self: *Self, idx: usize) void {
            self.metadata.?[idx].remove();
            self.keys()[idx] = undefined;
            self.values()[idx] = undefined;
            self.size -= 1;
            self.available += 1;
        }

        /// 如果哈希映射中存在键匹配的 `Entry`,则将其删除
        /// 并返回 true。否则
        /// 返回 false。
        ///
        /// TODO: 回答此文档注释中的问题,删除该条目后未使用容量是否会增加一?
        ///
        pub fn remove(self: *Self, key: K) bool {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call removeContext instead.");
            return self.removeContext(key, undefined);
        }

        /// TODO: 回答这些文档注释中的问题:这是否
        /// 使未使用容量增加了一个?
        pub fn removeContext(self: *Self, key: K, ctx: Context) bool {
            return self.removeAdapted(key, ctx);
        }

        /// TODO: 回答这些文档注释中的问题:这是否
        /// 使未使用容量增加了一个?
        pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
            if (self.getIndex(key, ctx)) |idx| {
                self.removeByIndex(idx);
                return true;
            }

            return false;
        }

        /// 从哈希映射中删除键由 key_ptr 指向的条目。
        /// 假定 key_ptr 是指向哈希映射中
        /// 已有键的有效指针。
        ///
        /// TODO: 回答这些文档注释中的问题:这是否
        /// 使未使用容量增加了一个?
        pub fn removeByPtr(self: *Self, key_ptr: *K) void {
            // 若 @sizeOf(K) == 0,则哈希映射最多只有一个条目;由于 key_ptr 必须有效,假定该条目存在。此条目必定位于索引 0。
            //
            //
            const idx = if (@sizeOf(K) > 0)
                @as([*]K, @ptrCast(key_ptr)) - self.keys()
            else
                0;

            self.removeByIndex(idx);
        }

        fn initMetadatas(self: *Self) void {
            @memset(@as([*]u8, @ptrCast(self.metadata.?))[0 .. @sizeOf(Metadata) * self.capacity()], 0);
        }

        // 计算已占用槽位的数量(不包含墓碑),此数量
        // 必须低于容量的 max_load_percentage。
        fn load(self: Self) Size {
            const max_load = (self.capacity() * max_load_percentage) / 100;
            assert(max_load >= self.available);
            return @as(Size, @truncate(max_load - self.available));
        }

        fn growIfNeeded(self: *Self, allocator: Allocator, new_count: Size, ctx: Context) Allocator.Error!void {
            if (new_count > self.available) {
                try self.grow(allocator, capacityForSize(self.load() + new_count), ctx);
            }
        }

        pub fn clone(self: Self, allocator: Allocator) Allocator.Error!Self {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call cloneContext instead.");
            return self.cloneContext(allocator, @as(Context, undefined));
        }
        pub fn cloneContext(self: Self, allocator: Allocator, new_ctx: anytype) Allocator.Error!HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) {
            var other: HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) = .empty;
            if (self.size == 0)
                return other;

            const new_cap = capacityForSize(self.size);
            try other.allocate(allocator, new_cap);
            other.initMetadatas();
            other.available = @truncate((new_cap * max_load_percentage) / 100);

            var i: Size = 0;
            var metadata = self.metadata.?;
            const keys_ptr = self.keys();
            const values_ptr = self.values();
            while (i < self.capacity()) : (i += 1) {
                if (metadata[i].isUsed()) {
                    other.putAssumeCapacityNoClobberContext(keys_ptr[i], values_ptr[i], new_ctx);
                    if (other.size == self.size)
                        break;
                }
            }

            return other;
        }

        /// 将映射置为空状态,使反初始化变为空操作,
        /// 并返回原映射的副本。
        pub fn move(self: *Self) Self {
            self.pointer_stability.assertUnlocked();
            const result = self.*;
            self.* = .empty;
            return result;
        }

        /// 原地重新哈希映射。
        ///
        /// 由于当前使用基于墓碑的实现,
        /// 长期使用后,HashMap 可能因墓碑条目
        /// 不断积累而产生碎片,过量探测
        /// 导致性能下降。可能触发此情况的模式是
        /// 长时间存在且反复插入、删除的 HashMap。
        ///
        /// 调用此函数后,HashMap 中不再存在墓碑,
        /// 所有条目均重新哈希,且任何已有的
        /// 指向 HashMap 内键或值的指针均失效。
        pub fn rehash(self: *Self, ctx: anytype) void {
            const mask = self.capacity() - 1;

            var metadata = self.metadata.?;
            var keys_ptr = self.keys();
            var values_ptr = self.values();
            var curr: Size = 0;

            // 重新哈希各槽位时,使用指纹将
            // 已使用的桶标记为已使用,并进一步标记为 free
            // (需要重新哈希)或 tombstone(已重新哈希)。

            while (curr < self.capacity()) : (curr += 1) {
                metadata[curr].fingerprint = Metadata.free;
            }

            // 现在遍历所有桶,重新计算其哈希

            curr = 0;
            while (curr < self.capacity()) {
                if (!metadata[curr].isUsed()) {
                    assert(metadata[curr].isFree());
                    curr += 1;
                    continue;
                }

                const hash = ctx.hash(keys_ptr[curr]);
                const fingerprint = Metadata.takeFingerprint(hash);
                var idx = @as(usize, @truncate(hash & mask));

                // 将每个桶重新哈希到某个索引:
                // 1) 游标之前,探测到空闲槽位;或
                // 2) 等于游标,无需移动;或
                // 3) 游标之后,探测时跨过已重新哈希的条目。

                while ((idx < curr and metadata[idx].isUsed()) or
                    (idx > curr and metadata[idx].fingerprint == Metadata.tombstone))
                {
                    idx = (idx + 1) & mask;
                }

                if (idx < curr) {
                    assert(metadata[idx].isFree());
                    metadata[idx].fill(fingerprint);
                    keys_ptr[idx] = keys_ptr[curr];
                    values_ptr[idx] = values_ptr[curr];

                    metadata[curr].used = 0;
                    assert(metadata[curr].isFree());
                    keys_ptr[curr] = undefined;
                    values_ptr[curr] = undefined;

                    curr += 1;
                } else if (idx == curr) {
                    metadata[idx].fingerprint = fingerprint;
                    curr += 1;
                } else {
                    assert(metadata[idx].fingerprint != Metadata.tombstone);
                    metadata[idx].fingerprint = Metadata.tombstone;
                    if (metadata[idx].isUsed()) {
                        std.mem.swap(K, &keys_ptr[curr], &keys_ptr[idx]);
                        std.mem.swap(V, &values_ptr[curr], &values_ptr[idx]);
                    } else {
                        metadata[idx].used = 1;
                        keys_ptr[idx] = keys_ptr[curr];
                        values_ptr[idx] = values_ptr[curr];

                        metadata[curr].fingerprint = Metadata.free;
                        metadata[curr].used = 0;
                        keys_ptr[curr] = undefined;
                        values_ptr[curr] = undefined;

                        curr += 1;
                    }
                }
            }
        }

        fn grow(self: *Self, allocator: Allocator, new_capacity: Size, ctx: Context) Allocator.Error!void {
            @branchHint(.cold);
            const new_cap = @max(new_capacity, minimal_capacity);
            assert(new_cap > self.capacity());
            assert(std.math.isPowerOfTwo(new_cap));

            var map: Self = .{};
            try map.allocate(allocator, new_cap);
            errdefer comptime unreachable;
            map.pointer_stability.lock();
            map.initMetadatas();
            map.available = @truncate((new_cap * max_load_percentage) / 100);

            if (self.size != 0) {
                const old_capacity = self.capacity();
                for (
                    self.metadata.?[0..old_capacity],
                    self.keys()[0..old_capacity],
                    self.values()[0..old_capacity],
                ) |m, k, v| {
                    if (!m.isUsed()) continue;
                    map.putAssumeCapacityNoClobberContext(k, v, ctx);
                    if (map.size == self.size) break;
                }
            }

            self.size = 0;
            self.pointer_stability = .{};
            std.mem.swap(Self, self, &map);
            map.deinit(allocator);
        }

        fn allocate(self: *Self, allocator: Allocator, new_capacity: Size) Allocator.Error!void {
            const header_align = @alignOf(Header);
            const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K);
            const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V);
            const max_align: Alignment = comptime .fromByteUnits(@max(header_align, key_align, val_align));

            const new_cap: usize = new_capacity;
            const meta_size = @sizeOf(Header) + new_cap * @sizeOf(Metadata);
            comptime assert(@alignOf(Metadata) == 1);

            const keys_start = std.mem.alignForward(usize, meta_size, key_align);
            const keys_end = keys_start + new_cap * @sizeOf(K);

            const vals_start = std.mem.alignForward(usize, keys_end, val_align);
            const vals_end = vals_start + new_cap * @sizeOf(V);

            const total_size = max_align.forward(vals_end);

            const slice = try allocator.alignedAlloc(u8, max_align, total_size);
            const ptr: [*]u8 = @ptrCast(slice.ptr);

            const metadata = ptr + @sizeOf(Header);

            const hdr = @as(*Header, @ptrCast(@alignCast(ptr)));
            if (@sizeOf([*]V) != 0) {
                hdr.values = @ptrCast(@alignCast((ptr + vals_start)));
            }
            if (@sizeOf([*]K) != 0) {
                hdr.keys = @ptrCast(@alignCast((ptr + keys_start)));
            }
            hdr.capacity = new_capacity;
            self.metadata = @ptrCast(@alignCast(metadata));
        }

        fn deallocate(self: *Self, allocator: Allocator) void {
            if (self.metadata == null) return;

            const header_align = @alignOf(Header);
            const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K);
            const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V);
            const max_align = comptime @max(header_align, key_align, val_align);

            const cap: usize = self.capacity();
            const meta_size = @sizeOf(Header) + cap * @sizeOf(Metadata);
            comptime assert(@alignOf(Metadata) == 1);

            const keys_start = std.mem.alignForward(usize, meta_size, key_align);
            const keys_end = keys_start + cap * @sizeOf(K);

            const vals_start = std.mem.alignForward(usize, keys_end, val_align);
            const vals_end = vals_start + cap * @sizeOf(V);

            const total_size = std.mem.alignForward(usize, vals_end, max_align);

            const slice = @as([*]align(max_align) u8, @ptrCast(@alignCast(self.header())))[0..total_size];
            allocator.free(slice);

            self.metadata = null;
            self.available = 0;
        }

        /// lib/lldb/ 中的调试器美化格式化器使用此函数获取头部类型,以便为该类型提供格式化调试输出。
        ///
        fn dbHelper(self: *Self, hdr: *Header, entry: *Entry) void {
            _ = self;
            _ = hdr;
            _ = entry;
        }

        comptime {
            if (!builtin.strip_debug_info) switch (builtin.zig_backend) {
                .stage2_llvm => _ = &dbHelper,
                .stage2_x86_64 => _ = @as(KV, undefined),
                else => {},
            };
        }
    };
}

const testing = std.testing;
const expect = std.testing.expect;
const expectEqual = std.testing.expectEqual;

test "basic usage" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    const count = 5;
    var i: u32 = 0;
    var total: u32 = 0;
    while (i < count) : (i += 1) {
        try map.put(i, i);
        total += i;
    }

    var sum: u32 = 0;
    var it = map.iterator();
    while (it.next()) |kv| {
        sum += kv.key_ptr.*;
    }
    try expectEqual(total, sum);

    i = 0;
    sum = 0;
    while (i < count) : (i += 1) {
        try expectEqual(i, map.get(i).?);
        sum += map.get(i).?;
    }
    try expectEqual(total, sum);
}

test "ensureTotalCapacity" {
    var map = AutoHashMap(i32, i32).init(std.testing.allocator);
    defer map.deinit();

    try map.ensureTotalCapacity(20);
    const initial_capacity = map.capacity();
    try testing.expect(initial_capacity >= 20);
    var i: i32 = 0;
    while (i < 20) : (i += 1) {
        try testing.expect(map.fetchPutAssumeCapacity(i, i + 10) == null);
    }
    // putAssumeCapacity 不应调整大小
    try testing.expect(initial_capacity == map.capacity());
}

test "ensureUnusedCapacity with tombstones" {
    var map = AutoHashMap(i32, i32).init(std.testing.allocator);
    defer map.deinit();

    var i: i32 = 0;
    while (i < 100) : (i += 1) {
        try map.ensureUnusedCapacity(1);
        map.putAssumeCapacity(i, i);
        _ = map.remove(i);
    }
}

test "clearRetainingCapacity" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    map.clearRetainingCapacity();

    try map.put(1, 1);
    try expectEqual(map.get(1).?, 1);
    try expectEqual(map.count(), 1);

    map.clearRetainingCapacity();
    map.putAssumeCapacity(1, 1);
    try expectEqual(map.get(1).?, 1);
    try expectEqual(map.count(), 1);

    const cap = map.capacity();
    try expect(cap > 0);

    map.clearRetainingCapacity();
    map.clearRetainingCapacity();
    try expectEqual(map.count(), 0);
    try expectEqual(map.capacity(), cap);
    try expect(!map.contains(1));
}

test "grow" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    const growTo = 12456;

    var i: u32 = 0;
    while (i < growTo) : (i += 1) {
        try map.put(i, i);
    }
    try expectEqual(map.count(), growTo);

    i = 0;
    var it = map.iterator();
    while (it.next()) |kv| {
        try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
        i += 1;
    }
    try expectEqual(i, growTo);

    i = 0;
    while (i < growTo) : (i += 1) {
        try expectEqual(map.get(i).?, i);
    }
}

test "clone" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var a = try map.clone();
    defer a.deinit();

    try expectEqual(a.count(), 0);

    try a.put(1, 1);
    try a.put(2, 2);
    try a.put(3, 3);

    var b = try a.clone();
    defer b.deinit();

    try expectEqual(b.count(), 3);
    try expectEqual(b.get(1).?, 1);
    try expectEqual(b.get(2).?, 2);
    try expectEqual(b.get(3).?, 3);

    var original = AutoHashMap(i32, i32).init(std.testing.allocator);
    defer original.deinit();

    var i: u8 = 0;
    while (i < 10) : (i += 1) {
        try original.putNoClobber(i, i * 10);
    }

    var copy = try original.clone();
    defer copy.deinit();

    i = 0;
    while (i < 10) : (i += 1) {
        try testing.expect(copy.get(i).? == i * 10);
    }
}

test "ensureTotalCapacity with existing elements" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    try map.put(0, 0);
    try expectEqual(map.count(), 1);
    try expectEqual(map.capacity(), @TypeOf(map).Unmanaged.minimal_capacity);

    try map.ensureTotalCapacity(65);
    try expectEqual(map.count(), 1);
    try expectEqual(map.capacity(), 128);
}

test "ensureTotalCapacity satisfies max load factor" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    try map.ensureTotalCapacity(127);
    try expectEqual(map.capacity(), 256);
}

test "remove" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var i: u32 = 0;
    while (i < 16) : (i += 1) {
        try map.put(i, i);
    }

    i = 0;
    while (i < 16) : (i += 1) {
        if (i % 3 == 0) {
            _ = map.remove(i);
        }
    }
    try expectEqual(map.count(), 10);
    var it = map.iterator();
    while (it.next()) |kv| {
        try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
        try expect(kv.key_ptr.* % 3 != 0);
    }

    i = 0;
    while (i < 16) : (i += 1) {
        if (i % 3 == 0) {
            try expect(!map.contains(i));
        } else {
            try expectEqual(map.get(i).?, i);
        }
    }
}

test "reverse removes" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var i: u32 = 0;
    while (i < 16) : (i += 1) {
        try map.putNoClobber(i, i);
    }

    i = 16;
    while (i > 0) : (i -= 1) {
        _ = map.remove(i - 1);
        try expect(!map.contains(i - 1));
        var j: u32 = 0;
        while (j < i - 1) : (j += 1) {
            try expectEqual(map.get(j).?, j);
        }
    }

    try expectEqual(map.count(), 0);
}

test "multiple removes on same metadata" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var i: u32 = 0;
    while (i < 16) : (i += 1) {
        try map.put(i, i);
    }

    _ = map.remove(7);
    _ = map.remove(15);
    _ = map.remove(14);
    _ = map.remove(13);
    try expect(!map.contains(7));
    try expect(!map.contains(15));
    try expect(!map.contains(14));
    try expect(!map.contains(13));

    i = 0;
    while (i < 13) : (i += 1) {
        if (i == 7) {
            try expect(!map.contains(i));
        } else {
            try expectEqual(map.get(i).?, i);
        }
    }

    try map.put(15, 15);
    try map.put(13, 13);
    try map.put(14, 14);
    try map.put(7, 7);
    i = 0;
    while (i < 16) : (i += 1) {
        try expectEqual(map.get(i).?, i);
    }
}

test "put and remove loop in random order" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var keys = std.array_list.Managed(u32).init(std.testing.allocator);
    defer keys.deinit();

    const size = 32;
    const iterations = 100;

    var i: u32 = 0;
    while (i < size) : (i += 1) {
        try keys.append(i);
    }
    var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
    const random = prng.random();

    while (i < iterations) : (i += 1) {
        random.shuffle(u32, keys.items);

        for (keys.items) |key| {
            try map.put(key, key);
        }
        try expectEqual(map.count(), size);

        for (keys.items) |key| {
            _ = map.remove(key);
        }
        try expectEqual(map.count(), 0);
    }
}

test "remove many elements in random order" {
    const Map = AutoHashMap(u32, u32);
    const n = 1000 * 100;
    var map = Map.init(std.heap.page_allocator);
    defer map.deinit();

    var keys = std.array_list.Managed(u32).init(std.heap.page_allocator);
    defer keys.deinit();

    var i: u32 = 0;
    while (i < n) : (i += 1) {
        keys.append(i) catch unreachable;
    }

    var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
    const random = prng.random();
    random.shuffle(u32, keys.items);

    for (keys.items) |key| {
        map.put(key, key) catch unreachable;
    }

    random.shuffle(u32, keys.items);
    i = 0;
    while (i < n) : (i += 1) {
        const key = keys.items[i];
        _ = map.remove(key);
    }
}

test "put" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var i: u32 = 0;
    while (i < 16) : (i += 1) {
        try map.put(i, i);
    }

    i = 0;
    while (i < 16) : (i += 1) {
        try expectEqual(map.get(i).?, i);
    }

    i = 0;
    while (i < 16) : (i += 1) {
        try map.put(i, i * 16 + 1);
    }

    i = 0;
    while (i < 16) : (i += 1) {
        try expectEqual(map.get(i).?, i * 16 + 1);
    }
}

test "putAssumeCapacity" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    try map.ensureTotalCapacity(20);
    var i: u32 = 0;
    while (i < 20) : (i += 1) {
        map.putAssumeCapacityNoClobber(i, i);
    }

    i = 0;
    var sum = i;
    while (i < 20) : (i += 1) {
        sum += map.getPtr(i).?.*;
    }
    try expectEqual(sum, 190);

    i = 0;
    while (i < 20) : (i += 1) {
        map.putAssumeCapacity(i, 1);
    }

    i = 0;
    sum = i;
    while (i < 20) : (i += 1) {
        sum += map.get(i).?;
    }
    try expectEqual(sum, 20);
}

test "repeat putAssumeCapacity/remove" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    try map.ensureTotalCapacity(20);
    const limit = map.unmanaged.available;

    var i: u32 = 0;
    while (i < limit) : (i += 1) {
        map.putAssumeCapacityNoClobber(i, i);
    }

    // 在不调整映射大小的情况下,反复删除/插入条目。
    // 放入不同的键,以免条目落入刚释放的槽位。
    i = 0;
    while (i < 10 * limit) : (i += 1) {
        try testing.expect(map.remove(i));
        if (i % 2 == 0) {
            map.putAssumeCapacityNoClobber(limit + i, i);
        } else {
            map.putAssumeCapacity(limit + i, i);
        }
    }

    i = 9 * limit;
    while (i < 10 * limit) : (i += 1) {
        try expectEqual(map.get(limit + i), i);
    }
    try expectEqual(map.unmanaged.available, 0);
    try expectEqual(map.unmanaged.count(), limit);
}

test "getOrPut" {
    var map = AutoHashMap(u32, u32).init(std.testing.allocator);
    defer map.deinit();

    var i: u32 = 0;
    while (i < 10) : (i += 1) {
        try map.put(i * 2, 2);
    }

    i = 0;
    while (i < 20) : (i += 1) {
        _ = try map.getOrPutValue(i, 1);
    }

    i = 0;
    var sum = i;
    while (i < 20) : (i += 1) {
        sum += map.get(i).?;
    }

    try expectEqual(sum, 30);
}

test "basic hash map usage" {
    var map = AutoHashMap(i32, i32).init(std.testing.allocator);
    defer map.deinit();

    try testing.expect((try map.fetchPut(1, 11)) == null);
    try testing.expect((try map.fetchPut(2, 22)) == null);
    try testing.expect((try map.fetchPut(3, 33)) == null);
    try testing.expect((try map.fetchPut(4, 44)) == null);

    try map.putNoClobber(5, 55);
    try testing.expect((try map.fetchPut(5, 66)).?.value == 55);
    try testing.expect((try map.fetchPut(5, 55)).?.value == 66);

    const gop1 = try map.getOrPut(5);
    try testing.expect(gop1.found_existing == true);
    try testing.expect(gop1.value_ptr.* == 55);
    gop1.value_ptr.* = 77;
    try testing.expect(map.getEntry(5).?.value_ptr.* == 77);

    const gop2 = try map.getOrPut(99);
    try testing.expect(gop2.found_existing == false);
    gop2.value_ptr.* = 42;
    try testing.expect(map.getEntry(99).?.value_ptr.* == 42);

    const gop3 = try map.getOrPutValue(5, 5);
    try testing.expect(gop3.value_ptr.* == 77);

    const gop4 = try map.getOrPutValue(100, 41);
    try testing.expect(gop4.value_ptr.* == 41);

    try testing.expect(map.contains(2));
    try testing.expect(map.getEntry(2).?.value_ptr.* == 22);
    try testing.expect(map.get(2).? == 22);

    const rmv1 = map.fetchRemove(2);
    try testing.expect(rmv1.?.key == 2);
    try testing.expect(rmv1.?.value == 22);
    try testing.expect(map.fetchRemove(2) == null);
    try testing.expect(map.remove(2) == false);
    try testing.expect(map.getEntry(2) == null);
    try testing.expect(map.get(2) == null);

    try testing.expect(map.remove(3) == true);
}

test "getOrPutAdapted" {
    const AdaptedContext = struct {
        fn eql(self: @This(), adapted_key: []const u8, test_key: u64) bool {
            _ = self;
            return std.fmt.parseInt(u64, adapted_key, 10) catch unreachable == test_key;
        }
        fn hash(self: @This(), adapted_key: []const u8) u64 {
            _ = self;
            const key = std.fmt.parseInt(u64, adapted_key, 10) catch unreachable;
            return (AutoContext(u64){}).hash(key);
        }
    };
    var map = AutoHashMap(u64, u64).init(testing.allocator);
    defer map.deinit();

    const keys = [_][]const u8{
        "1231",
        "4564",
        "7894",
        "1132",
        "65235",
        "95462",
        "0112305",
        "00658",
        "0",
        "2",
    };

    var real_keys: [keys.len]u64 = undefined;

    inline for (keys, 0..) |key_str, i| {
        const result = try map.getOrPutAdapted(key_str, AdaptedContext{});
        try testing.expect(!result.found_existing);
        real_keys[i] = std.fmt.parseInt(u64, key_str, 10) catch unreachable;
        result.key_ptr.* = real_keys[i];
        result.value_ptr.* = i * 2;
    }

    try testing.expectEqual(map.count(), keys.len);

    inline for (keys, 0..) |key_str, i| {
        const result = map.getOrPutAssumeCapacityAdapted(key_str, AdaptedContext{});
        try testing.expect(result.found_existing);
        try testing.expectEqual(real_keys[i], result.key_ptr.*);
        try testing.expectEqual(@as(u64, i) * 2, result.value_ptr.*);
        try testing.expectEqual(real_keys[i], map.getKeyAdapted(key_str, AdaptedContext{}).?);
    }
}

test "ensureUnusedCapacity" {
    var map = AutoHashMap(u64, u64).init(testing.allocator);
    defer map.deinit();

    try map.ensureUnusedCapacity(32);
    const capacity = map.capacity();
    try map.ensureUnusedCapacity(32);

    // 连续调用 ensureUnusedCapacity(),期间未插入元素时,
    // 不应改变容量。
    try testing.expectEqual(capacity, map.capacity());
}

test "removeByPtr" {
    var map = AutoHashMap(i32, u64).init(testing.allocator);
    defer map.deinit();

    var i: i32 = undefined;

    i = 0;
    while (i < 10) : (i += 1) {
        try map.put(i, 0);
    }

    try testing.expect(map.count() == 10);

    i = 0;
    while (i < 10) : (i += 1) {
        const key_ptr = map.getKeyPtr(i);
        try testing.expect(key_ptr != null);

        if (key_ptr) |ptr| {
            map.removeByPtr(ptr);
        }
    }

    try testing.expect(map.count() == 0);
}

test "removeByPtr 0 sized key" {
    var map = AutoHashMap(u0, u64).init(testing.allocator);
    defer map.deinit();

    try map.put(0, 0);

    try testing.expect(map.count() == 1);

    const key_ptr = map.getKeyPtr(0);
    try testing.expect(key_ptr != null);

    if (key_ptr) |ptr| {
        map.removeByPtr(ptr);
    }

    try testing.expect(map.count() == 0);
}

test "repeat fetchRemove" {
    var map: AutoHashMapUnmanaged(u64, void) = .empty;
    defer map.deinit(testing.allocator);

    try map.ensureTotalCapacity(testing.allocator, 4);

    map.putAssumeCapacity(0, {});
    map.putAssumeCapacity(1, {});
    map.putAssumeCapacity(2, {});
    map.putAssumeCapacity(3, {});

    // fetchRemove() 应使槽位可用。
    var i: usize = 0;
    while (i < 10) : (i += 1) {
        try testing.expect(map.fetchRemove(3) != null);
        map.putAssumeCapacity(3, {});
    }

    try testing.expect(map.get(0) != null);
    try testing.expect(map.get(1) != null);
    try testing.expect(map.get(2) != null);
    try testing.expect(map.get(3) != null);
}

test "getOrPut allocation failure" {
    var map: std.StringHashMapUnmanaged(void) = .empty;
    try testing.expectError(error.OutOfMemory, map.getOrPut(std.testing.failing_allocator, "hello"));
}

test "rehash" {
    var map = AutoHashMap(usize, usize).init(std.testing.allocator);
    defer map.deinit();

    var prng = std.Random.DefaultPrng.init(0);
    const random = prng.random();

    const count = 4 * random.intRangeLessThan(u32, 100_000, 500_000);

    for (0..count) |i| {
        try map.put(i, i);
        if (i % 3 == 0) {
            try expectEqual(map.remove(i), true);
        }
    }

    map.rehash();

    try expectEqual(map.count(), count * 2 / 3);

    for (0..count) |i| {
        if (i % 3 == 0) {
            try expectEqual(map.get(i), null);
        } else {
            try expectEqual(map.get(i).?, i);
        }
    }
}

test "removeByPtr, key is array" {
    const gpa = testing.allocator;

    var map: AutoHashMapUnmanaged([2]u32, u32) = .empty;
    defer map.deinit(gpa);

    const key: [2]u32 = .{ 1, 2 };
    try map.put(gpa, key, 3);

    try expectEqual(1, map.count());
    try expectEqual(3, map.get(key));

    const key_ptr = map.getKeyPtr(key).?;
    map.removeByPtr(key_ptr);

    try expectEqual(0, map.count());
    try expectEqual(null, map.get(key));
}