跳转到内容

std.array_hash_map

标准库Zig 0.17.0官方原文
源码std/array_hash_map.zig

第 1 行

std.array_hash_map.Allocator

别名

第 9 行

别名目标 std.mem.Allocator

std.array_hash_map.ArrayHashMap

别名

第 45 行

已弃用;使用 Custom。

别名目标 std.array_hash_map.Custom

std.array_hash_map.assert

别名

第 3 行

别名目标 std.debug.assert

std.array_hash_map.Auto

类型函数

第 15 行

使用默认哈希函数和相等比较函数的 ArrayHashMap。

关于哈希及相等比较实现的说明,参见 AutoContext。

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

参数

K: type
V: type

字段

entries: DataList = .{}

允许直接访问此字段。 修改键后,请考虑调用 reIndex。

index_header: ?*IndexHeader = null

条目长度小于 linear_scan_max 时,此字段保持为 null。 条目长度增长到足够大后,分配此字段。 其布局为 IndexHeader,后跟 Index(I) 结构数组; I 根据索引总数确定。

pointer_stability: std.debug.SafetyLock = .{}

用于检测内存安全违规。

std.array_hash_map.AutoContext

类型函数

第 2217 行

pub fn AutoContext(comptime K: type) type

参数

K: type

std.array_hash_map.AutoContext.eql

常量

第 2220 行

std.array_hash_map.AutoContext.hash

常量

第 2219 行

std.array_hash_map.autoEqlIsCheap

函数

第 2249 行

pub fn autoEqlIsCheap(comptime K: type) bool

参数

K: type

std.array_hash_map.autoHash

别名

第 7 行

别名目标 std.hash.autoHash

std.array_hash_map.capacityIndexSize

函数

第 1560 行

fn capacityIndexSize(bit_index: u8) usize

参数

bit_index: u8

std.array_hash_map.capacityIndexType

函数

第 1551 行

fn capacityIndexType(bit_index: u8) CapacityIndexType

参数

bit_index: u8

std.array_hash_map.CapacityIndexType

容器

第 1549 行

字段

u8
u16
u32

std.array_hash_map.Custom

类型函数

第 70 行

键和值分别顺序存储的哈希表。

保留插入顺序。通常,此数据结构支持与 std.ArrayList 相同的操作。

删除操作:

  • swapRemove - O(1)
  • orderedRemove - O(N)

允许在迭代期间修改哈希映射,但必须理解将插入、删除和迭代混用时定义明确的行为。

此类型不存储 Allocator 字段;每次调用需要分配器的函数时,都必须传入 Allocator。

可以直接使用默认字段值初始化。

此类型旨在降低条目较少时的开销。当 store_hash 为 false 且映射条目数小于 9 时,使用 ArrayHashMap 而非 std.ArrayList,仅增加一个指针大小整数的开销。

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

pub fn Custom( comptime K: type, comptime V: type, comptime Context: type, comptime store_hash: bool, ) type

参数

K: type
V: type
Context: type

提供以下两个函数的命名空间:

  • pub fn hash(self, K) u32
  • pub fn eql(self, K, K, usize) bool

eql 函数的最后一个 usize 表示已存在映射中的键索引。

store_hash: bool

为 false 时,此数据结构偏向低成本的 eql 函数,避免在表中存储各个键的哈希值。 将 store_hash 设为 true 会增加内存开销,但可将 eql 限制为每次插入/删除只调用一次,前提是 没有哈希碰撞。

字段

entries: DataList = .{}

允许直接访问此字段。 修改键后,请考虑调用 reIndex。

index_header: ?*IndexHeader = null

条目长度小于 linear_scan_max 时,此字段保持为 null。 条目长度增长到足够大后,分配此字段。 其布局为 IndexHeader,后跟 Index(I) 结构数组; I 根据索引总数确定。

pointer_stability: std.debug.SafetyLock = .{}

用于检测内存安全违规。

std.array_hash_map.Custom.ByIndexContext

类型

第 151 行

某些函数仅在未存储哈希时需要上下文。 为保持 API 简洁,此类型仅供内部使用。

std.array_hash_map.Custom.capacity

函数

第 456 行

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

pub fn capacity(self: Self) usize

参数

self: Self

std.array_hash_map.Custom.checkedEql

函数

第 1483 行

fn checkedEql(ctx: anytype, a: anytype, b: K, b_index: usize) bool

参数

b: K
b_index: usize

std.array_hash_map.Custom.checkedHash

函数

第 1477 行

fn checkedHash(ctx: anytype, key: anytype) u32

std.array_hash_map.Custom.clearAndFree

函数

第 233 行

清空映射并释放底层分配。

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

参数

self: *Self
gpa: Allocator

std.array_hash_map.Custom.clearRetainingCapacity

函数

第 218 行

清空映射,但保留底层分配以供后续使用。

pub fn clearRetainingCapacity(self: *Self) void

参数

self: *Self

std.array_hash_map.Custom.clone

函数

第 833 行

创建可独立修改的哈希映射副本。 副本使用与此实例相同的上下文,但通过 提供的分配器分配。

pub fn clone(self: Self, gpa: Allocator) Oom!Self

参数

self: Self
gpa: Allocator

错误

OutOfMemory Error

std.array_hash_map.Custom.cloneContext

函数

第 838 行

pub fn cloneContext(self: Self, gpa: Allocator, ctx: Context) Oom!Self

参数

self: Self
gpa: Allocator
ctx: Context

错误

OutOfMemory Error

std.array_hash_map.Custom.contains

函数

第 664 行

检查映射中是否存储了指定键

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

参数

self: Self
key: K

std.array_hash_map.Custom.containsAdapted

函数

第 672 行

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

参数

self: Self

std.array_hash_map.Custom.containsContext

函数

第 669 行

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

参数

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.count

函数

第 245 行

返回此映射中存储的键值对数量。

pub fn count(self: Self) usize

参数

self: Self

std.array_hash_map.Custom.Data

容器

第 123 行

支撑此映射的 MultiArrayList 所使用的 Data 类型。

字段

hash: Hash
key: K
value: V

std.array_hash_map.Custom.DataList

类型

第 130 行

支撑此映射的 MultiArrayList 类型

std.array_hash_map.Custom.deinit

函数

第 190 行

释放底层分配,使映射处于未定义状态。 注意,不会释放键或值;若需要释放, 必须在调用此函数前自行完成。

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

参数

self: *Self
gpa: Allocator

std.array_hash_map.Custom.dumpIndex

函数

第 1525 行

fn dumpIndex(header: *IndexHeader, comptime I: type) void

参数

header: *IndexHeader
I: type

std.array_hash_map.Custom.dumpState

函数

第 1489 行

fn dumpState(self: Self, comptime keyFmt: []const u8, comptime valueFmt: []const u8) void

参数

self: Self
keyFmt: []const u8
valueFmt: []const u8

std.array_hash_map.Custom.dumpStateContext

函数

第 1494 行

fn dumpStateContext(self: Self, comptime keyFmt: []const u8, comptime valueFmt: []const u8, ctx: Context) void

参数

self: Self
keyFmt: []const u8
valueFmt: []const u8
ctx: Context

std.array_hash_map.Custom.empty

常量

第 102 行

不含任何键值的映射。

Self

std.array_hash_map.Custom.ensureTotalCapacity

函数

第 412 行

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

pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Oom!void

参数

self: *Self
gpa: Allocator
new_capacity: usize

错误

OutOfMemory Error

std.array_hash_map.Custom.ensureTotalCapacityContext

函数

第 417 行

pub fn ensureTotalCapacityContext(self: *Self, gpa: Allocator, new_capacity: usize, ctx: Context) Oom!void

参数

self: *Self
gpa: Allocator
new_capacity: usize
ctx: Context

错误

OutOfMemory Error

std.array_hash_map.Custom.ensureUnusedCapacity

函数

第 436 行

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

pub fn ensureUnusedCapacity( self: *Self, gpa: Allocator, additional_capacity: usize, ) Oom!void

参数

self: *Self
gpa: Allocator
additional_capacity: usize

错误

OutOfMemory Error

std.array_hash_map.Custom.ensureUnusedCapacityContext

函数

第 445 行

pub fn ensureUnusedCapacityContext( self: *Self, gpa: Allocator, additional_capacity: usize, ctx: Context, ) Oom!void

参数

self: *Self
gpa: Allocator
additional_capacity: usize
ctx: Context

错误

OutOfMemory Error

std.array_hash_map.Custom.Entry

容器

第 111 行

只有不改变哈希值时,才允许修改键。 允许修改值。 此 ArrayHashMap 每次被修改时,条目指针都会失效, 除非此前调用过 ensureTotalCapacity/ensureUnusedCapacity。

字段

key_ptr: *K
value_ptr: *V

std.array_hash_map.Custom.fetchOrderedRemove

函数

第 704 行

如果哈希映射中存在键匹配的 Entry,则将其删除 并从此函数返回。随后将底层数组中的该条目移除:所有元素前移, 从而保持当前顺序。

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

参数

self: *Self
key: K

std.array_hash_map.Custom.fetchOrderedRemoveAdapted

函数

第 712 行

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

参数

self: *Self

std.array_hash_map.Custom.fetchOrderedRemoveContext

函数

第 709 行

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

参数

self: *Self
key: K
ctx: Context

std.array_hash_map.Custom.fetchOrderedRemoveContextAdapted

函数

第 717 行

pub fn fetchOrderedRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) ?KV

参数

self: *Self
ctx: Context

std.array_hash_map.Custom.fetchPut

函数

第 516 行

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

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

参数

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

错误

OutOfMemory Error

std.array_hash_map.Custom.fetchPutAssumeCapacity

函数

第 536 行

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

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

参数

self: *Self
key: K
value: V

std.array_hash_map.Custom.fetchPutAssumeCapacityContext

函数

第 541 行

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

参数

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

std.array_hash_map.Custom.fetchPutContext

函数

第 521 行

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

参数

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

错误

OutOfMemory Error

std.array_hash_map.Custom.fetchRemoveByKey

函数

第 1060 行

fn fetchRemoveByKey( self: *Self, key: anytype, key_ctx: anytype, ctx: ByIndexContext, comptime removal_type: RemovalType, ) ?KV

参数

self: *Self
ctx: ByIndexContext
removal_type: RemovalType

std.array_hash_map.Custom.fetchRemoveByKeyGeneric

函数

第 1095 行

fn fetchRemoveByKeyGeneric( self: *Self, key: anytype, key_ctx: anytype, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType, ) ?KV

参数

self: *Self
ctx: ByIndexContext
header: *IndexHeader
I: type
removal_type: RemovalType

std.array_hash_map.Custom.fetchSwapRemove

函数

第 680 行

若存在键匹配的 Entry,则将其从 哈希映射中删除,并从此函数返回。 通过与最后一个元素交换,将条目从底层数组中移除。

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

参数

self: *Self
key: K

std.array_hash_map.Custom.fetchSwapRemoveAdapted

函数

第 688 行

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

参数

self: *Self

std.array_hash_map.Custom.fetchSwapRemoveContext

函数

第 685 行

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

参数

self: *Self
key: K
ctx: Context

std.array_hash_map.Custom.fetchSwapRemoveContextAdapted

函数

第 693 行

pub fn fetchSwapRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) ?KV

参数

self: *Self
ctx: Context

std.array_hash_map.Custom.get

函数

第 608 行

查找与键关联的值

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

参数

self: Self
key: K

std.array_hash_map.Custom.getAdapted

函数

第 616 行

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

参数

self: Self

std.array_hash_map.Custom.getContext

函数

第 613 行

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

参数

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getEntry

函数

第 555 行

查找与某键关联的键存储及值存储的指针。

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

参数

self: Self
key: K

std.array_hash_map.Custom.getEntryAdapted

函数

第 563 行

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

参数

self: Self

std.array_hash_map.Custom.getEntryContext

函数

第 560 行

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

参数

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getIndex

函数

第 573 行

查找键在 entries 数组中的存储索引。

pub fn getIndex(self: Self, key: K) ?usize

参数

self: Self
key: K

std.array_hash_map.Custom.getIndexAdapted

函数

第 581 行

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

参数

self: Self

std.array_hash_map.Custom.getIndexContext

函数

第 578 行

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

参数

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getIndexWithHeaderGeneric

函数

第 601 行

fn getIndexWithHeaderGeneric(self: Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type) ?usize

参数

self: Self
header: *IndexHeader
I: type

std.array_hash_map.Custom.getKey

函数

第 636 行

查找与适配键关联的实际键

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

参数

self: Self
key: K

std.array_hash_map.Custom.getKeyAdapted

函数

第 644 行

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

参数

self: Self

std.array_hash_map.Custom.getKeyContext

函数

第 641 行

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

参数

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getKeyPtr

函数

第 650 行

查找指向与适配键关联的实际键的指针

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

参数

self: Self
key: K

std.array_hash_map.Custom.getKeyPtrAdapted

函数

第 658 行

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

参数

self: Self

std.array_hash_map.Custom.getKeyPtrContext

函数

第 655 行

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

参数

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getOrPut

函数

第 301 行

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

pub fn getOrPut(self: *Self, gpa: Allocator, key: K) Oom!GetOrPutResult

参数

self: *Self
gpa: Allocator
key: K

错误

OutOfMemory Error

std.array_hash_map.Custom.getOrPutAdapted

函数

第 313 行

pub fn getOrPutAdapted(self: *Self, gpa: Allocator, key: anytype, key_ctx: anytype) Oom!GetOrPutResult

参数

self: *Self
gpa: Allocator

错误

OutOfMemory Error

std.array_hash_map.Custom.getOrPutAssumeCapacity

函数

第 340 行

若已存在键为 key 的元素,则结果 Entry 指针指向该元素,且 found_existing 为 true。 否则插入一个值为 undefined 的新元素,结果 Entry 指针指向它。随后调用者应初始化其值,但不应初始化键。 若需存储新条目,此函数断言容量足够。

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

参数

self: *Self
key: K

std.array_hash_map.Custom.getOrPutAssumeCapacityAdapted

函数

第 359 行

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

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

参数

self: *Self

std.array_hash_map.Custom.getOrPutAssumeCapacityContext

函数

第 345 行

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

参数

self: *Self
key: K
ctx: Context

std.array_hash_map.Custom.getOrPutContext

函数

第 306 行

pub fn getOrPutContext(self: *Self, gpa: Allocator, key: K, ctx: Context) Oom!GetOrPutResult

参数

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

错误

OutOfMemory Error

std.array_hash_map.Custom.getOrPutContextAdapted

函数

第 318 行

pub fn getOrPutContextAdapted(self: *Self, gpa: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Oom!GetOrPutResult

参数

self: *Self
gpa: Allocator
ctx: Context

错误

OutOfMemory Error

std.array_hash_map.Custom.getOrPutInternal

函数

第 1283 行

调用此函数前必须调用 ensureTotalCapacity/ensureUnusedCapacity。

fn getOrPutInternal(self: *Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type) GetOrPutResult

参数

self: *Self
header: *IndexHeader
I: type

std.array_hash_map.Custom.GetOrPutResult

容器

第 142 行

getOrPut 各变体返回此结构体,包含指向 底层存储的指针,以及表示是否 找到已有条目的标志。 仅当不改变哈希值时才允许修改键。 允许修改值。 修改此 ArrayHashMap 时,条目指针会失效, 除非此前调用了 ensureTotalCapacity、ensureUnusedCapacity。

字段

key_ptr: *K
value_ptr: *V
found_existing: bool
index: usize

std.array_hash_map.Custom.getOrPutValue

函数

第 396 行

pub fn getOrPutValue(self: *Self, gpa: Allocator, key: K, value: V) Oom!GetOrPutResult

参数

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

错误

OutOfMemory Error

std.array_hash_map.Custom.getOrPutValueContext

函数

第 401 行

pub fn getOrPutValueContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!GetOrPutResult

参数

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

错误

OutOfMemory Error

std.array_hash_map.Custom.getPtr

函数

第 622 行

查找与键关联的值的指针。

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

参数

self: Self
key: K

std.array_hash_map.Custom.getPtrAdapted

函数

第 630 行

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

参数

self: Self

std.array_hash_map.Custom.getPtrContext

函数

第 627 行

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

参数

self: Self
key: K
ctx: Context

std.array_hash_map.Custom.getSlotByIndex

函数

第 1255 行

fn getSlotByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I)) usize

参数

self: *Self
entry_index: usize
ctx: ByIndexContext
header: *IndexHeader
I: type
indexes: []Index(I)

std.array_hash_map.Custom.getSlotByKey

函数

第 1393 行

fn getSlotByKey(self: Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type, indexes: []Index(I)) ?usize

参数

self: Self
header: *IndexHeader
I: type
indexes: []Index(I)

std.array_hash_map.Custom.Hash

类型

第 133 行

存储的哈希类型,为 u32 或 void。

std.array_hash_map.Custom.init

函数

第 167 行

pub fn init(gpa: Allocator, key_list: []const K, value_list: []const V) Oom!Self

参数

gpa: Allocator
key_list: []const K
value_list: []const V

错误

OutOfMemory Error

std.array_hash_map.Custom.insertAllEntriesIntoNewHeader

函数

第 1421 行

fn insertAllEntriesIntoNewHeader(self: *Self, ctx: ByIndexContext, header: *IndexHeader) void

参数

self: *Self
ctx: ByIndexContext
header: *IndexHeader

std.array_hash_map.Custom.insertAllEntriesIntoNewHeaderGeneric

函数

第 1428 行

fn insertAllEntriesIntoNewHeaderGeneric(self: *Self, ctx: ByIndexContext, header: *IndexHeader, comptime I: type) void

参数

self: *Self
ctx: ByIndexContext
header: *IndexHeader
I: type

std.array_hash_map.Custom.insertEntryIntoNewHeader

函数

第 1438 行

fn insertEntryIntoNewHeader(header: *IndexHeader, h: u32, i: usize) void

参数

header: *IndexHeader
h: u32
i: usize

std.array_hash_map.Custom.insertEntryIntoNewHeaderGeneric

函数

第 1445 行

fn insertEntryIntoNewHeaderGeneric(header: *IndexHeader, h: u32, i: usize, comptime I: type) void

参数

header: *IndexHeader
h: u32
i: usize
I: type

std.array_hash_map.Custom.iterator

函数

第 265 行

返回遍历此映射中键值对的迭代器。 修改映射可能使此迭代器失效。

pub fn iterator(self: Self) Iterator

参数

self: Self

std.array_hash_map.Custom.Iterator

容器

第 273 行

字段

keys: [*]K
values: [*]V
len: u32
index: u32 = 0

std.array_hash_map.Custom.Iterator.next

函数

第 279 行

pub fn next(it: *Iterator) ?Entry

参数

it: *Iterator

std.array_hash_map.Custom.Iterator.reset

函数

第 290 行

将迭代器重置为初始索引

pub fn reset(it: *Iterator) void

参数

it: *Iterator

std.array_hash_map.Custom.keys

函数

第 253 行

返回此映射中键的底层数组。修改映射可能 使此数组失效。若以会改变键哈希值 或相等性判断的方式修改此数组,则在调用 reIndex 之前, 该映射将无法使用。

pub fn keys(self: Self) []K

参数

self: Self

std.array_hash_map.Custom.KV

容器

第 117 行

已从底层存储复制出来的键值对

字段

key: K
value: V

std.array_hash_map.Custom.linear_scan_max

常量

第 155 行

std.array_hash_map.Custom.lockPointers

函数

第 208 行

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

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

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

pub fn lockPointers(self: *Self) void

参数

self: *Self

std.array_hash_map.Custom.move

函数

第 855 行

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

pub fn move(self: *Self) Self

参数

self: *Self

std.array_hash_map.Custom.Oom

别名

第 165 行

别名目标 std.mem.Allocator.Error

std.array_hash_map.Custom.orderedRemove

函数

第 752 行

如果存在键匹配的 Entry,则从 哈希映射中删除。通过将所有后续元素前移, 从底层数组中移除该条目,因此保留 当前顺序。移除条目时返回 true,否则返回 false。

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

参数

self: *Self
key: K

std.array_hash_map.Custom.orderedRemoveAdapted

函数

第 760 行

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

参数

self: *Self

std.array_hash_map.Custom.orderedRemoveAt

函数

第 791 行

从哈希映射中删除 entries 中指定索引处的条目。 通过将所有元素前移,将条目从底层数组中 移除,从而保持 当前顺序。

pub fn orderedRemoveAt(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.array_hash_map.Custom.orderedRemoveAtContext

函数

第 796 行

pub fn orderedRemoveAtContext(self: *Self, index: usize, ctx: Context) void

参数

self: *Self
index: usize
ctx: Context

std.array_hash_map.Custom.orderedRemoveAtMany

函数

第 811 行

移除 sorted_indexes 索引的条目。待移除索引 对应删除前的状态。

此操作的时间复杂度为 O(N)。

断言每个待移除索引均在范围内。

使首个被删除索引之后的键指针和元素指针失效。

pub fn orderedRemoveAtMany(self: *Self, gpa: Allocator, sorted_indexes: []const usize) Oom!void

参数

self: *Self
gpa: Allocator
sorted_indexes: []const usize

错误

OutOfMemory Error

std.array_hash_map.Custom.orderedRemoveAtManyContext

函数

第 817 行

pub fn orderedRemoveAtManyContext( self: *Self, gpa: Allocator, sorted_indexes: []const usize, ctx: Context, ) Oom!void

参数

self: *Self
gpa: Allocator
sorted_indexes: []const usize
ctx: Context

错误

OutOfMemory Error

std.array_hash_map.Custom.orderedRemoveContext

函数

第 757 行

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

参数

self: *Self
key: K
ctx: Context

std.array_hash_map.Custom.orderedRemoveContextAdapted

函数

第 765 行

pub fn orderedRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) bool

参数

self: *Self
ctx: Context

std.array_hash_map.Custom.pop

函数

第 1040 行

移除并返回哈希映射中最后插入的 Entry。 否则返回 null。

pub fn pop(self: *Self) ?KV

参数

self: *Self

std.array_hash_map.Custom.popContext

函数

第 1045 行

pub fn popContext(self: *Self, ctx: Context) ?KV

参数

self: *Self
ctx: Context

std.array_hash_map.Custom.put

函数

第 465 行

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

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

参数

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

错误

OutOfMemory Error

std.array_hash_map.Custom.putAssumeCapacity

函数

第 491 行

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

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

参数

self: *Self
key: K
value: V

std.array_hash_map.Custom.putAssumeCapacityContext

函数

第 496 行

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

参数

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

std.array_hash_map.Custom.putAssumeCapacityNoClobber

函数

第 504 行

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

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

参数

self: *Self
key: K
value: V

std.array_hash_map.Custom.putAssumeCapacityNoClobberContext

函数

第 509 行

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

参数

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

std.array_hash_map.Custom.putContext

函数

第 470 行

pub fn putContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!void

参数

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

错误

OutOfMemory Error

std.array_hash_map.Custom.putNoClobber

函数

第 477 行

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

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

参数

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

错误

OutOfMemory Error

std.array_hash_map.Custom.putNoClobberContext

函数

第 482 行

pub fn putNoClobberContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!void

参数

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

错误

OutOfMemory Error

std.array_hash_map.Custom.rebuildIndex

函数

第 911 行

fn rebuildIndex(self: *Self, gpa: Allocator, ctx: Context) Oom!void

参数

self: *Self
gpa: Allocator
ctx: Context

错误

OutOfMemory Error

std.array_hash_map.Custom.reIndex

函数

第 872 行

重新计算已存储的哈希并重建键索引。若直接修改了底层键,应调用此方法,重新计算按键查找条目的映射方法所需的反规范化元数据。

一个用例是直接调用 entries.resize() 扩大底层存储,再直接设置 keys 与 values,而不经由此映射的方法。

此操作的时间复杂度为 O(n)。

pub fn reIndex(self: *Self, gpa: Allocator) Oom!void

参数

self: *Self
gpa: Allocator

错误

OutOfMemory Error

std.array_hash_map.Custom.reIndexContext

函数

第 878 行

pub fn reIndexContext(self: *Self, gpa: Allocator, ctx: Context) Oom!void

参数

self: *Self
gpa: Allocator
ctx: Context

错误

OutOfMemory Error

std.array_hash_map.Custom.reinit

函数

第 175 行

可以传入空的 value_list,此时 values 数组会变为 undefined。

pub fn reinit(self: *Self, gpa: Allocator, key_list: []const K, value_list: []const V) Oom!void

参数

self: *Self
gpa: Allocator
key_list: []const K
value_list: []const V

错误

OutOfMemory Error

std.array_hash_map.Custom.RemovalType

容器

第 160 行

字段

swap
ordered

std.array_hash_map.Custom.removeByIndex

函数

第 1153 行

fn removeByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, comptime removal_type: RemovalType) void

参数

self: *Self
entry_index: usize
ctx: ByIndexContext
removal_type: RemovalType

std.array_hash_map.Custom.removeByIndexGeneric

函数

第 1168 行

fn removeByIndexGeneric(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType) void

参数

self: *Self
entry_index: usize
ctx: ByIndexContext
header: *IndexHeader
I: type
removal_type: RemovalType

std.array_hash_map.Custom.removeByKey

函数

第 1115 行

fn removeByKey( self: *Self, key: anytype, key_ctx: anytype, ctx: ByIndexContext, comptime removal_type: RemovalType, ) bool

参数

self: *Self
ctx: ByIndexContext
removal_type: RemovalType

std.array_hash_map.Custom.removeByKeyGeneric

函数

第 1146 行

fn removeByKeyGeneric(self: *Self, key: anytype, key_ctx: anytype, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType) bool

参数

self: *Self
ctx: ByIndexContext
header: *IndexHeader
I: type
removal_type: RemovalType

std.array_hash_map.Custom.removeFromArrayAndUpdateIndex

函数

第 1174 行

fn removeFromArrayAndUpdateIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I), comptime removal_type: RemovalType) void

参数

self: *Self
entry_index: usize
ctx: ByIndexContext
header: *IndexHeader
I: type
indexes: []Index(I)
removal_type: RemovalType

std.array_hash_map.Custom.removeFromIndexByIndex

函数

第 1214 行

fn removeFromIndexByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader) void

参数

self: *Self
entry_index: usize
ctx: ByIndexContext
header: *IndexHeader

std.array_hash_map.Custom.removeFromIndexByIndexGeneric

函数

第 1221 行

fn removeFromIndexByIndexGeneric(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I)) void

参数

self: *Self
entry_index: usize
ctx: ByIndexContext
header: *IndexHeader
I: type
indexes: []Index(I)

std.array_hash_map.Custom.removeFromIndexByKey

函数

第 1226 行

fn removeFromIndexByKey(self: *Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type, indexes: []Index(I)) ?usize

参数

self: *Self
header: *IndexHeader
I: type
indexes: []Index(I)

std.array_hash_map.Custom.removeSlot

函数

第 1233 行

fn removeSlot(removed_slot: usize, header: *IndexHeader, comptime I: type, indexes: []Index(I)) void

参数

removed_slot: usize
header: *IndexHeader
I: type
indexes: []Index(I)

std.array_hash_map.Custom.Self

别名

第 153 行

别名目标 std.array_hash_map.Custom

std.array_hash_map.Custom.setKey

函数

第 890 行

修改条目的键,而不改变任何条目的顺序。

pub fn setKey(self: *Self, index: usize, new_key: K) void

参数

self: *Self
index: usize
new_key: K

std.array_hash_map.Custom.setKeyContext

函数

第 896 行

pub fn setKeyContext(self: *Self, index: usize, new_key: K, ctx: Context) void

参数

self: *Self
index: usize
new_key: K
ctx: Context

std.array_hash_map.Custom.shrinkAndFree

函数

第 1009 行

将底层 Entry 数组缩减为 new_len 个元素, 丢弃所有关联索引条目,并减少已分配容量。

断言被丢弃的条目仍已初始化,且能 进行哈希与相等性检查。如果被丢弃的条目需要反初始化, 则调用此函数属于错误。该场景 可以改用 shrinkRetainingCapacity。

pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void

参数

self: *Self
gpa: Allocator
new_len: usize

std.array_hash_map.Custom.shrinkAndFreeContext

函数

第 1023 行

将底层 Entry 数组缩小到 new_len 个元素,并丢弃所有关联的索引条目。减少已分配容量。

断言被丢弃的条目仍已初始化,且能够执行哈希与相等性检查。 若被丢弃的条目需要反初始化,调用此函数属于错误。该场景可改用 shrinkRetainingCapacityContext。

pub fn shrinkAndFreeContext(self: *Self, gpa: Allocator, new_len: usize, ctx: Context) void

参数

self: *Self
gpa: Allocator
new_len: usize
ctx: Context

std.array_hash_map.Custom.shrinkRetainingCapacity

函数

第 975 行

将底层 Entry 数组缩小为 new_len 个元素,并丢弃所有关联的索引条目。容量保持不变。

断言被丢弃条目仍已初始化,且能够执行哈希与相等性检查。 被丢弃条目的任何反初始化,都必须在调用此函数之后进行。

pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void

参数

self: *Self
new_len: usize

std.array_hash_map.Custom.shrinkRetainingCapacityContext

函数

第 987 行

将底层 Entry 数组缩小为 new_len 个元素,并丢弃所有关联的索引条目。容量保持不变。

断言被丢弃条目仍已初始化,且能够执行哈希与相等性检查。 被丢弃条目的任何反初始化,都必须在调用此函数之后进行。

pub fn shrinkRetainingCapacityContext(self: *Self, new_len: usize, ctx: Context) void

参数

self: *Self
new_len: usize
ctx: Context

std.array_hash_map.Custom.sort

函数

第 927 行

排序条目,然后重建索引。 sort_ctx 必须具有此方法: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool 采用稳定排序算法。

pub inline fn sort(self: *Self, sort_ctx: anytype) void

参数

self: *Self

std.array_hash_map.Custom.sortContext

函数

第 943 行

pub inline fn sortContext(self: *Self, sort_ctx: anytype, ctx: Context) void

参数

self: *Self
ctx: Context

std.array_hash_map.Custom.sortContextInternal

函数

第 951 行

fn sortContextInternal( self: *Self, comptime mode: std.sort.Mode, sort_ctx: anytype, ctx: Context, ) void

参数

self: *Self
mode: std.sort.Mode
ctx: Context

std.array_hash_map.Custom.sortUnstable

函数

第 937 行

对条目排序,随后重建索引。 sort_ctx 必须具有此方法: fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool 使用不稳定排序算法。

pub inline fn sortUnstable(self: *Self, sort_ctx: anytype) void

参数

self: *Self

std.array_hash_map.Custom.sortUnstableContext

函数

第 947 行

pub inline fn sortUnstableContext(self: *Self, sort_ctx: anytype, ctx: Context) void

参数

self: *Self
ctx: Context

std.array_hash_map.Custom.swapRemove

函数

第 728 行

若存在键匹配的 Entry,则从哈希表中 删除它。通过将其与末尾元素交换, 从底层数组移除该条目。移除条目时返回 true, 否则返回 false。

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

参数

self: *Self
key: K

std.array_hash_map.Custom.swapRemoveAdapted

函数

第 736 行

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

参数

self: *Self

std.array_hash_map.Custom.swapRemoveAt

函数

第 775 行

从哈希表删除 entries 中指定索引处的元素。 通过将该条目与末尾元素交换, 从底层数组中移除。

pub fn swapRemoveAt(self: *Self, index: usize) void

参数

self: *Self
index: usize

std.array_hash_map.Custom.swapRemoveAtContext

函数

第 780 行

pub fn swapRemoveAtContext(self: *Self, index: usize, ctx: Context) void

参数

self: *Self
index: usize
ctx: Context

std.array_hash_map.Custom.swapRemoveContext

函数

第 733 行

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

参数

self: *Self
key: K
ctx: Context

std.array_hash_map.Custom.swapRemoveContextAdapted

函数

第 741 行

pub fn swapRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) bool

参数

self: *Self
ctx: Context

std.array_hash_map.Custom.unlockPointers

函数

第 213 行

撤销一次 lockPointers 调用。

pub fn unlockPointers(self: *Self) void

参数

self: *Self

std.array_hash_map.Custom.updateEntryIndex

函数

第 1201 行

fn updateEntryIndex( self: *Self, header: *IndexHeader, old_entry_index: usize, new_entry_index: usize, ctx: ByIndexContext, comptime I: type, indexes: []Index(I), ) void

参数

self: *Self
header: *IndexHeader
old_entry_index: usize
new_entry_index: usize
ctx: ByIndexContext
I: type
indexes: []Index(I)

std.array_hash_map.Custom.values

函数

第 259 行

返回此映射中值的底层数组。修改映射 可能使该数组失效。允许修改 该数组中的值。

pub fn values(self: Self) []V

参数

self: Self

std.array_hash_map.debug

别名

第 2 行

别名目标 std.debug

std.array_hash_map.eqlString

函数

第 36 行

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

参数

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

std.array_hash_map.f

函数

第 1871 行

pub fn f(allocator: Allocator) !void

参数

allocator: Allocator

std.array_hash_map.getAutoEqlFn

函数

第 2239 行

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

参数

K: type
Context: type

std.array_hash_map.getAutoEqlFn.eql

函数

第 2241 行

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

参数

ctx: Context
a: K
b: K
b_index: usize

std.array_hash_map.getAutoHashFn

函数

第 2224 行

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

参数

K: type
Context: type

std.array_hash_map.getAutoHashFn.hash

函数

第 2226 行

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

参数

ctx: Context
key: K

std.array_hash_map.getAutoHashStratFn

函数

第 2267 行

pub fn getAutoHashStratFn(comptime K: type, comptime Context: type, comptime strategy: std.hash.Strategy) (fn (Context, K) u32)

参数

K: type
Context: type
strategy: std.hash.Strategy

std.array_hash_map.getAutoHashStratFn.hash

函数

第 2269 行

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

参数

ctx: Context
key: K

std.array_hash_map.getHashPtrAddrFn

函数

第 2199 行

pub fn getHashPtrAddrFn(comptime K: type, comptime Context: type) (fn (Context, K) u32)

参数

K: type
Context: type

std.array_hash_map.getHashPtrAddrFn.hash

函数

第 2201 行

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

参数

ctx: Context
key: K

std.array_hash_map.getTrivialEqlFn

函数

第 2208 行

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

参数

K: type
Context: type

std.array_hash_map.getTrivialEqlFn.eql

函数

第 2210 行

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

参数

ctx: Context
a: K
b: K

std.array_hash_map.hash_map

别名

第 10 行

别名目标 std.array_hash_map

std.array_hash_map.hashString

函数

第 40 行

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

参数

s: []const u8

std.array_hash_map.Index

类型函数

第 1583 行

查找加速结构中的单个条目。这些结构体 存储在 IndexHeader 后的数组中。哈希值用于索引此 数组,冲突通过线性探测解决。

fn Index(comptime I: type) type

参数

I: type

字段

entry_index: I

此条目在底层存储中的索引。如果该索引 为空,则此值为 empty_sentinel。

distance_from_start_index: I

此槽与理想位置之间的距离。用于缩短最大扫描长度。若索引为空,此值未定义。

std.array_hash_map.index_capacities

常量

第 1625 行

std.array_hash_map.Index.empty

常量

第 1600 行

常量空索引

std.array_hash_map.Index.empty_sentinel

常量

第 1597 行

表示空槽的特殊 entry_index 值。

std.array_hash_map.Index.isEmpty

函数

第 1606 行

检查槽是否为空

fn isEmpty(idx: Self) bool

参数

idx: Self

std.array_hash_map.Index.Self

别名

第 1585 行

别名目标 std.array_hash_map.Index

std.array_hash_map.Index.setEmpty

函数

第 1611 行

将槽设为空

fn setEmpty(idx: *Self) void

参数

idx: *Self

std.array_hash_map.IndexHeader

容器

第 1643 行

此结构体之后跟随两个长度均为 indexes_len 的整数数组,其整数大小由 indexes_len 决定。 数组通过 constrainIndex(hash) 索引。entryIndexes 数组存储条目数据在稠密后备存储中的索引;未使用条目的索引值设为 emptySentinel(I)。 entryDistances 数组存储条目与其理想哈希桶之间的距离,添加元素时用它平衡最大扫描长度。

字段

bit_index: u8 align(@alignOf(u32))

此字段跟踪紧随头部之后的各数组中的 元素总数。索引数量是 2 的幂,此值为其位索引。 该值位于 min_bit_index 与 max_bit_index 之间,包含两端。

std.array_hash_map.IndexHeader.alloc

函数

第 1689 行

分配索引头,并将 entryIndexes 数组填为空。 distance 数组内容未定义。

fn alloc(gpa: Allocator, new_bit_index: u8) Allocator.Error!*IndexHeader

参数

gpa: Allocator
new_bit_index: u8

错误

OutOfMemory

std.array_hash_map.IndexHeader.capacity

函数

第 1668 行

fn capacity(self: IndexHeader) u32

参数

self: IndexHeader

std.array_hash_map.IndexHeader.capacityIndexType

函数

第 1664 行

返回索引数组使用的类型。

fn capacityIndexType(header: IndexHeader) CapacityIndexType

参数

header: IndexHeader

std.array_hash_map.IndexHeader.constrainIndex

函数

第 1650 行

从递增索引到所附数组中索引槽的映射。

fn constrainIndex(header: IndexHeader, i: usize) usize

参数

header: IndexHeader
i: usize

std.array_hash_map.IndexHeader.findBitIndex

函数

第 1678 行

fn findBitIndex(desired_capacity: usize) Allocator.Error!u8

参数

desired_capacity: usize

错误

OutOfMemory

std.array_hash_map.IndexHeader.free

函数

第 1703 行

释放头部及其关联数组的内存。

fn free(header: *IndexHeader, gpa: Allocator) void

参数

header: *IndexHeader
gpa: Allocator

std.array_hash_map.IndexHeader.indexes

函数

第 1658 行

返回所附的索引数组。I 必须与 capacityIndexType 返回的类型匹配。

fn indexes(header: *IndexHeader, comptime I: type) []Index(I)

参数

header: *IndexHeader
I: type

std.array_hash_map.IndexHeader.length

函数

第 1671 行

fn length(self: IndexHeader) usize

参数

self: IndexHeader

std.array_hash_map.IndexHeader.mask

函数

第 1674 行

fn mask(self: IndexHeader) u32

参数

self: IndexHeader

std.array_hash_map.IndexHeader.reset

函数

第 1711 行

将 IndexHeader 置为刚分配完成时应有的状态。

fn reset(header: *IndexHeader) void

参数

header: *IndexHeader

std.array_hash_map.lessThan

函数

第 2083 行

pub fn lessThan(ctx: @This(), a_index: usize, b_index: usize) bool

参数

ctx: @This()
a_index: usize
b_index: usize

std.array_hash_map.math

别名

第 5 行

别名目标 std.math

std.array_hash_map.max_bit_index

常量

第 1622 行

std.array_hash_map.max_capacity

常量

第 1624 行

std.array_hash_map.max_representable_index_len

常量

第 1621 行

索引的字节大小必须能由 usize 表示。其为二的幂长度乘以 Index(u32) 的大小。索引占 8 字节(3 位表示), 而 max_usize + 1 无法表示,因此需减去 4 位。

std.array_hash_map.mem

别名

第 6 行

别名目标 std.mem

std.array_hash_map.min_bit_index

常量

第 1623 行

std.array_hash_map.safeTruncate

函数

第 1574 行

目标类型大于目标值的类型时, @truncate 会失败。当某个类型为 usize 时 便会产生问题,因为不同系统上的 usize 可能大于或小于 u32。此版本的 truncate 在任一 参数大小随平台变化时均可安全使用,并会在需要时执行拓宽转换。 两个参数的符号属性必须相同。

fn safeTruncate(comptime T: type, val: anytype) T

参数

T: type

std.array_hash_map.std

别名

第 1 行

别名目标 std

std.array_hash_map.String

类型函数

第 20 行

以字符串为键的 ArrayHashMap。

pub fn String(comptime V: type) type

参数

V: type

字段

entries: DataList = .{}

允许直接访问此字段。 修改键后,请考虑调用 reIndex。

index_header: ?*IndexHeader = null

条目长度小于 linear_scan_max 时,此字段保持为 null。 条目长度增长到足够大后,分配此字段。 其布局为 IndexHeader,后跟 Index(I) 结构数组; I 根据索引总数确定。

pointer_stability: std.debug.SafetyLock = .{}

用于检测内存安全违规。

std.array_hash_map.StringContext

命名空间

第 24 行

std.array_hash_map.StringContext.eql

函数

第 29 行

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

参数

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

std.array_hash_map.StringContext.hash

函数

第 25 行

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

参数

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

std.array_hash_map.testing

别名

第 4 行

别名目标 std.testing

std.array_hash_map.Wyhash

别名

第 8 行

别名目标 std.hash.Wyhash

源码

std/array_hash_map.zig

const std = @import("std.zig");
const debug = std.debug;
const assert = debug.assert;
const testing = std.testing;
const math = std.math;
const mem = std.mem;
const autoHash = std.hash.autoHash;
const Wyhash = std.hash.Wyhash;
const Allocator = mem.Allocator;
const hash_map = @This();

/// 使用默认哈希函数和相等比较函数的 `ArrayHashMap`。
///
/// 关于哈希及相等比较实现的说明,参见 `AutoContext`。
pub fn Auto(comptime K: type, comptime V: type) type {
    return Custom(K, V, AutoContext(K), !autoEqlIsCheap(K));
}

/// 以字符串为键的 `ArrayHashMap`。
pub fn String(comptime V: type) type {
    return Custom([]const u8, V, StringContext, true);
}

pub const StringContext = struct {
    pub fn hash(self: @This(), s: []const u8) u32 {
        _ = self;
        return hashString(s);
    }
    pub fn eql(self: @This(), a: []const u8, b: []const u8, b_index: usize) bool {
        _ = self;
        _ = b_index;
        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) u32 {
    return @truncate(std.hash.Wyhash.hash(0, s));
}

/// 已弃用;使用 `Custom`。
pub const ArrayHashMap = Custom;

/// 键和值分别顺序存储的哈希表。
///
/// 保留插入顺序。通常,此数据结构支持与 `std.ArrayList` 相同的操作。
///
/// 删除操作:
/// * `swapRemove` - O(1)
/// * `orderedRemove` - O(N)
///
/// 允许在迭代期间修改哈希映射,但必须理解将插入、删除和迭代混用时定义明确的行为。
///
/// 此类型不存储 `Allocator` 字段;每次调用需要分配器的函数时,都必须传入 `Allocator`。
///
/// 可以直接使用默认字段值初始化。
///
/// 此类型旨在降低条目较少时的开销。当 `store_hash` 为 `false` 且映射条目数小于 9 时,使用 `ArrayHashMap` 而非 `std.ArrayList`,仅增加一个指针大小整数的开销。
///
/// 此结构体的默认初始化已弃用,请改用 `.empty`。
///
///
///
///
///
///
pub fn Custom(
    comptime K: type,
    comptime V: type,
    /// 提供以下两个函数的命名空间:
    /// * `pub fn hash(self, K) u32`
    /// * `pub fn eql(self, K, K, usize) bool`
    ///
    /// `eql` 函数的最后一个 `usize` 表示已存在映射中的键索引。
    ///
    comptime Context: type,
    /// 为 `false` 时,此数据结构偏向低成本的 `eql`
    /// 函数,避免在表中存储各个键的哈希值。
    /// 将 `store_hash` 设为 `true` 会增加内存开销,但可将 `eql`
    /// 限制为每次插入/删除只调用一次,前提是
    /// 没有哈希碰撞。
    comptime store_hash: bool,
) type {
    return struct {
        /// 允许直接访问此字段。
        /// 修改键后,请考虑调用 `reIndex`。
        entries: DataList = .{},

        /// 条目长度小于 `linear_scan_max` 时,此字段保持为 `null`。
        /// 条目长度增长到足够大后,分配此字段。
        /// 其布局为 IndexHeader,后跟 Index(I) 结构数组;
        /// I 根据索引总数确定。
        index_header: ?*IndexHeader = null,

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

        /// 不含任何键值的映射。
        pub const empty: Self = .{
            .entries = .{},
            .index_header = null,
        };

        /// 只有不改变哈希值时,才允许修改键。
        /// 允许修改值。
        /// 此 ArrayHashMap 每次被修改时,条目指针都会失效,
        /// 除非此前调用过 `ensureTotalCapacity`/`ensureUnusedCapacity`。
        pub const Entry = struct {
            key_ptr: *K,
            value_ptr: *V,
        };

        /// 已从底层存储复制出来的键值对
        pub const KV = struct {
            key: K,
            value: V,
        };

        /// 支撑此映射的 MultiArrayList 所使用的 Data 类型。
        pub const Data = struct {
            hash: Hash,
            key: K,
            value: V,
        };

        /// 支撑此映射的 MultiArrayList 类型
        pub const DataList = std.MultiArrayList(Data);

        /// 存储的哈希类型,为 u32 或 void。
        pub const Hash = if (store_hash) u32 else void;

        /// getOrPut 各变体返回此结构体,包含指向
        /// 底层存储的指针,以及表示是否
        /// 找到已有条目的标志。
        /// 仅当不改变哈希值时才允许修改键。
        /// 允许修改值。
        /// 修改此 ArrayHashMap 时,条目指针会失效,
        /// 除非此前调用了 `ensureTotalCapacity`、`ensureUnusedCapacity`。
        pub const GetOrPutResult = struct {
            key_ptr: *K,
            value_ptr: *V,
            found_existing: bool,
            index: usize,
        };

        /// 某些函数仅在未存储哈希时需要上下文。
        /// 为保持 API 简洁,此类型仅供内部使用。
        const ByIndexContext = if (store_hash) void else Context;

        const Self = @This();

        const linear_scan_max = @as(comptime_int, @max(1, @as(comptime_int, @min(
            std.atomic.cache_line / @as(comptime_int, @max(1, @sizeOf(Hash))),
            std.atomic.cache_line / @as(comptime_int, @max(1, @sizeOf(K))),
        ))));

        const RemovalType = enum {
            swap,
            ordered,
        };

        const Oom = Allocator.Error;

        pub fn init(gpa: Allocator, key_list: []const K, value_list: []const V) Oom!Self {
            var self: Self = .{};
            errdefer self.deinit(gpa);
            try self.reinit(gpa, key_list, value_list);
            return self;
        }

        /// 可以传入空的 `value_list`,此时 values 数组会变为 `undefined`。
        pub fn reinit(self: *Self, gpa: Allocator, key_list: []const K, value_list: []const V) Oom!void {
            try self.entries.resize(gpa, key_list.len);
            @memcpy(self.keys(), key_list);
            if (value_list.len == 0) {
                @memset(self.values(), undefined);
            } else {
                assert(key_list.len == value_list.len);
                @memcpy(self.values(), value_list);
            }
            try self.reIndex(gpa);
        }

        /// 释放底层分配,使映射处于未定义状态。
        /// 注意,不会释放键或值;若需要释放,
        /// 必须在调用此函数前自行完成。
        pub fn deinit(self: *Self, gpa: Allocator) void {
            self.pointer_stability.assertUnlocked();
            self.entries.deinit(gpa);
            if (self.index_header) |header| {
                header.free(gpa);
            }
            self.* = undefined;
        }

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

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

        /// 清空映射,但保留底层分配以供后续使用。
        pub fn clearRetainingCapacity(self: *Self) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            self.entries.len = 0;
            if (self.index_header) |header| {
                switch (header.capacityIndexType()) {
                    .u8 => @memset(header.indexes(u8), Index(u8).empty),
                    .u16 => @memset(header.indexes(u16), Index(u16).empty),
                    .u32 => @memset(header.indexes(u32), Index(u32).empty),
                }
            }
        }

        /// 清空映射并释放底层分配。
        pub fn clearAndFree(self: *Self, gpa: Allocator) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            self.entries.shrinkAndFree(gpa, 0);
            if (self.index_header) |header| {
                header.free(gpa);
                self.index_header = null;
            }
        }

        /// 返回此映射中存储的键值对数量。
        pub fn count(self: Self) usize {
            return self.entries.len;
        }

        /// 返回此映射中键的底层数组。修改映射可能
        /// 使此数组失效。若以会改变键哈希值
        /// 或相等性判断的方式修改此数组,则在调用 `reIndex` 之前,
        /// 该映射将无法使用。
        pub fn keys(self: Self) []K {
            return self.entries.items(.key);
        }
        /// 返回此映射中值的底层数组。修改映射
        /// 可能使该数组失效。允许修改
        /// 该数组中的值。
        pub fn values(self: Self) []V {
            return self.entries.items(.value);
        }

        /// 返回遍历此映射中键值对的迭代器。
        /// 修改映射可能使此迭代器失效。
        pub fn iterator(self: Self) Iterator {
            const slice = self.entries.slice();
            return .{
                .keys = slice.items(.key).ptr,
                .values = slice.items(.value).ptr,
                .len = @as(u32, @intCast(slice.len)),
            };
        }
        pub const Iterator = struct {
            keys: [*]K,
            values: [*]V,
            len: u32,
            index: u32 = 0,

            pub fn next(it: *Iterator) ?Entry {
                if (it.index >= it.len) return null;
                const result = Entry{
                    .key_ptr = &it.keys[it.index],
                    .value_ptr = &it.values[it.index],
                };
                it.index += 1;
                return result;
            }

            /// 将迭代器重置为初始索引
            pub fn reset(it: *Iterator) void {
                it.index = 0;
            }
        };

        /// 若键已存在,此函数不会失败。
        /// 若已存在键为 `key` 的元素,结果 `Entry` 指针指向它,且 found_existing 为 true。
        /// 否则插入一个值为 undefined 的新元素,`Entry` 指针指向它。随后调用者应初始化值,但不应初始化键。
        ///
        ///
        ///
        pub fn getOrPut(self: *Self, gpa: Allocator, key: K) Oom!GetOrPutResult {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead.");
            return self.getOrPutContext(gpa, key, undefined);
        }
        pub fn getOrPutContext(self: *Self, gpa: Allocator, key: K, ctx: Context) Oom!GetOrPutResult {
            const gop = try self.getOrPutContextAdapted(gpa, key, ctx, ctx);
            if (!gop.found_existing) {
                gop.key_ptr.* = key;
            }
            return gop;
        }
        pub fn getOrPutAdapted(self: *Self, gpa: Allocator, key: anytype, key_ctx: anytype) Oom!GetOrPutResult {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContextAdapted instead.");
            return self.getOrPutContextAdapted(gpa, key, key_ctx, undefined);
        }
        pub fn getOrPutContextAdapted(self: *Self, gpa: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Oom!GetOrPutResult {
            self.ensureTotalCapacityContext(gpa, self.entries.len + 1, ctx) catch |err| {
                // “如果键已存在,此函数就不会失败。”
                const index = self.getIndexAdapted(key, key_ctx) orelse return err;
                const slice = self.entries.slice();
                return GetOrPutResult{
                    .key_ptr = &slice.items(.key)[index],
                    .value_ptr = &slice.items(.value)[index],
                    .found_existing = true,
                    .index = index,
                };
            };
            return self.getOrPutAssumeCapacityAdapted(key, key_ctx);
        }

        /// 若已存在键为 `key` 的元素,则结果 `Entry` 指针指向该元素,且 found_existing 为 true。
        /// 否则插入一个值为 undefined 的新元素,结果 `Entry` 指针指向它。随后调用者应初始化其值,但不应初始化键。
        /// 若需存储新条目,此函数断言容量足够。
        ///
        ///
        ///
        ///
        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 gop = self.getOrPutAssumeCapacityAdapted(key, ctx);
            if (!gop.found_existing) {
                gop.key_ptr.* = key;
            }
            return gop;
        }
        /// 如果已有键为 `key` 的元素,则结果中的
        /// `Entry` 指针指向该元素,且 found_existing 为 true。
        /// 否则,插入键和值均未定义的新元素,
        /// `Entry` 指针指向该元素。调用方随后必须初始化
        /// 键和值。
        /// 如果需要存储新条目,此函数断言
        /// 容量足以容纳它。
        pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
            const header = self.index_header orelse {
                // 线性扫描。
                const h = if (store_hash) checkedHash(ctx, key) else {};
                const slice = self.entries.slice();
                const hashes_array = slice.items(.hash);
                const keys_array = slice.items(.key);
                for (keys_array, 0..) |*item_key, i| {
                    if (hashes_array[i] == h and checkedEql(ctx, key, item_key.*, i)) {
                        return GetOrPutResult{
                            .key_ptr = item_key,
                            .value_ptr = &slice.items(.value)[i],
                            .found_existing = true,
                            .index = i,
                        };
                    }
                }

                const index = self.entries.addOneAssumeCapacity();
                // 切片长度发生变化,因此直接对指针进行索引。
                if (store_hash) hashes_array.ptr[index] = h;

                return GetOrPutResult{
                    .key_ptr = &keys_array.ptr[index],
                    .value_ptr = &slice.items(.value).ptr[index],
                    .found_existing = false,
                    .index = index,
                };
            };

            switch (header.capacityIndexType()) {
                .u8 => return self.getOrPutInternal(key, ctx, header, u8),
                .u16 => return self.getOrPutInternal(key, ctx, header, u16),
                .u32 => return self.getOrPutInternal(key, ctx, header, u32),
            }
        }

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

        /// 增加容量,保证在达到
        /// `expected_count` 之前的插入不会分配内存,因此不会失败。
        pub fn ensureTotalCapacity(self: *Self, gpa: Allocator, new_capacity: usize) Oom!void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead.");
            return self.ensureTotalCapacityContext(gpa, new_capacity, undefined);
        }
        pub fn ensureTotalCapacityContext(self: *Self, gpa: Allocator, new_capacity: usize, ctx: Context) Oom!void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            try self.entries.ensureTotalCapacity(gpa, new_capacity);
            if (new_capacity <= linear_scan_max) return;
            if (self.index_header) |header| if (new_capacity <= header.capacity()) return;

            const new_bit_index = try IndexHeader.findBitIndex(new_capacity);
            const new_header = try IndexHeader.alloc(gpa, new_bit_index);

            if (self.index_header) |old_header| old_header.free(gpa);
            self.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, new_header);
            self.index_header = new_header;
        }

        /// 增加容量,保证再插入最多 `additional_count` 个项目都不会触发分配,因此不会失败。
        ///
        ///
        pub fn ensureUnusedCapacity(
            self: *Self,
            gpa: Allocator,
            additional_capacity: usize,
        ) Oom!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead.");
            return self.ensureUnusedCapacityContext(gpa, additional_capacity, undefined);
        }
        pub fn ensureUnusedCapacityContext(
            self: *Self,
            gpa: Allocator,
            additional_capacity: usize,
            ctx: Context,
        ) Oom!void {
            return self.ensureTotalCapacityContext(gpa, self.count() + additional_capacity, ctx);
        }

        /// 返回元素总数上限;超过此值后,就不再保证不会发生分配。
        ///
        pub fn capacity(self: Self) usize {
            const entry_cap = self.entries.capacity;
            const header = self.index_header orelse return @min(linear_scan_max, entry_cap);
            const indexes_cap = header.capacity();
            return @min(entry_cap, indexes_cap);
        }

        /// 覆盖任何已有数据。要检测 put 是否会覆盖
        /// 已有数据,请参见 `getOrPut`。
        pub fn put(self: *Self, gpa: Allocator, key: K, value: V) Oom!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putContext instead.");
            return self.putContext(gpa, key, value, undefined);
        }
        pub fn putContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!void {
            const result = try self.getOrPutContext(gpa, key, ctx);
            result.value_ptr.* = value;
        }

        /// 向哈希映射插入键值对,断言映射中
        /// 不存在键相同的条目。
        pub fn putNoClobber(self: *Self, gpa: Allocator, key: K, value: V) Oom!void {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putNoClobberContext instead.");
            return self.putNoClobberContext(gpa, key, value, undefined);
        }
        pub fn putNoClobberContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!void {
            const result = try self.getOrPutContext(gpa, key, ctx);
            assert(!result.found_existing);
            result.value_ptr.* = value;
        }

        /// 断言容量足以存储新键值对。
        /// 覆盖任何已有数据。要检测插入是否会覆盖
        /// 已有数据,请参见 `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 result = self.getOrPutAssumeCapacityContext(key, ctx);
            result.value_ptr.* = value;
        }

        /// 断言容量足以存储新的键值对。
        /// 断言不会覆盖任何现有数据。
        /// 若要检测 put 是否会覆盖现有数据,参见 `getOrPutAssumeCapacity`。
        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 {
            const result = self.getOrPutAssumeCapacityContext(key, ctx);
            assert(!result.found_existing);
            result.value_ptr.* = value;
        }

        /// 将新 `Entry` 插入哈希映射,并返回之前的条目(如果存在)。
        pub fn fetchPut(self: *Self, gpa: Allocator, key: K, value: V) Oom!?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutContext instead.");
            return self.fetchPutContext(gpa, key, value, undefined);
        }
        pub fn fetchPutContext(self: *Self, gpa: Allocator, key: K, value: V, ctx: Context) Oom!?KV {
            const gop = try self.getOrPutContext(gpa, 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;
        }

        /// 查找与某键关联的键存储及值存储的指针。
        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 {
            const index = self.getIndexAdapted(key, ctx) orelse return null;
            const slice = self.entries.slice();
            return Entry{
                .key_ptr = &slice.items(.key)[index],
                .value_ptr = &slice.items(.value)[index],
            };
        }

        /// 查找键在 `entries` 数组中的存储索引。
        pub fn getIndex(self: Self, key: K) ?usize {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getIndexContext instead.");
            return self.getIndexContext(key, undefined);
        }
        pub fn getIndexContext(self: Self, key: K, ctx: Context) ?usize {
            return self.getIndexAdapted(key, ctx);
        }
        pub fn getIndexAdapted(self: Self, key: anytype, ctx: anytype) ?usize {
            const header = self.index_header orelse {
                // 线性扫描。
                const h = if (store_hash) checkedHash(ctx, key) else {};
                const slice = self.entries.slice();
                const hashes_array = slice.items(.hash);
                const keys_array = slice.items(.key);
                for (keys_array, 0..) |*item_key, i| {
                    if (hashes_array[i] == h and checkedEql(ctx, key, item_key.*, i)) {
                        return i;
                    }
                }
                return null;
            };
            switch (header.capacityIndexType()) {
                .u8 => return self.getIndexWithHeaderGeneric(key, ctx, header, u8),
                .u16 => return self.getIndexWithHeaderGeneric(key, ctx, header, u16),
                .u32 => return self.getIndexWithHeaderGeneric(key, ctx, header, u32),
            }
        }
        fn getIndexWithHeaderGeneric(self: Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type) ?usize {
            const indexes = header.indexes(I);
            const slot = self.getSlotByKey(key, ctx, header, I, indexes) orelse return null;
            return indexes[slot].entry_index;
        }

        /// 查找与键关联的值
        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 {
            const index = self.getIndexAdapted(key, ctx) orelse return null;
            return self.values()[index];
        }

        /// 查找与键关联的值的指针。
        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 {
            const index = self.getIndexAdapted(key, ctx) orelse return null;
            return &self.values()[index];
        }

        /// 查找与适配键关联的实际键
        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 {
            const index = self.getIndexAdapted(key, ctx) orelse return null;
            return self.keys()[index];
        }

        /// 查找指向与适配键关联的实际键的指针
        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 {
            const index = self.getIndexAdapted(key, ctx) orelse return null;
            return &self.keys()[index];
        }

        /// 检查映射中是否存储了指定键
        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.getIndexAdapted(key, ctx) != null;
        }

        /// 若存在键匹配的 `Entry`,则将其从
        /// 哈希映射中删除,并从此函数返回。
        /// 通过与最后一个元素交换,将条目从底层数组中移除。
        ///
        pub fn fetchSwapRemove(self: *Self, key: K) ?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchSwapRemoveContext instead.");
            return self.fetchSwapRemoveContext(key, undefined);
        }
        pub fn fetchSwapRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
            return self.fetchSwapRemoveContextAdapted(key, ctx, ctx);
        }
        pub fn fetchSwapRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchSwapRemoveContextAdapted instead.");
            return self.fetchSwapRemoveContextAdapted(key, ctx, undefined);
        }
        pub fn fetchSwapRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) ?KV {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            return self.fetchRemoveByKey(key, key_ctx, if (store_hash) {} else ctx, .swap);
        }

        /// 如果哈希映射中存在键匹配的 `Entry`,则将其删除
        /// 并从此函数返回。随后将底层数组中的该条目移除:所有元素前移,
        /// 从而保持当前顺序。
        ///
        pub fn fetchOrderedRemove(self: *Self, key: K) ?KV {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchOrderedRemoveContext instead.");
            return self.fetchOrderedRemoveContext(key, undefined);
        }
        pub fn fetchOrderedRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
            return self.fetchOrderedRemoveContextAdapted(key, ctx, ctx);
        }
        pub fn fetchOrderedRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchOrderedRemoveContextAdapted instead.");
            return self.fetchOrderedRemoveContextAdapted(key, ctx, undefined);
        }
        pub fn fetchOrderedRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) ?KV {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            return self.fetchRemoveByKey(key, key_ctx, if (store_hash) {} else ctx, .ordered);
        }

        /// 若存在键匹配的 `Entry`,则从哈希表中
        /// 删除它。通过将其与末尾元素交换,
        /// 从底层数组移除该条目。移除条目时返回 true,
        /// 否则返回 false。
        pub fn swapRemove(self: *Self, key: K) bool {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call swapRemoveContext instead.");
            return self.swapRemoveContext(key, undefined);
        }
        pub fn swapRemoveContext(self: *Self, key: K, ctx: Context) bool {
            return self.swapRemoveContextAdapted(key, ctx, ctx);
        }
        pub fn swapRemoveAdapted(self: *Self, key: anytype, ctx: anytype) bool {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call swapRemoveContextAdapted instead.");
            return self.swapRemoveContextAdapted(key, ctx, undefined);
        }
        pub fn swapRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) bool {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            return self.removeByKey(key, key_ctx, if (store_hash) {} else ctx, .swap);
        }

        /// 如果存在键匹配的 `Entry`,则从
        /// 哈希映射中删除。通过将所有后续元素前移,
        /// 从底层数组中移除该条目,因此保留
        /// 当前顺序。移除条目时返回 true,否则返回 false。
        pub fn orderedRemove(self: *Self, key: K) bool {
            if (@sizeOf(Context) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveContext instead.");
            return self.orderedRemoveContext(key, undefined);
        }
        pub fn orderedRemoveContext(self: *Self, key: K, ctx: Context) bool {
            return self.orderedRemoveContextAdapted(key, ctx, ctx);
        }
        pub fn orderedRemoveAdapted(self: *Self, key: anytype, ctx: anytype) bool {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveContextAdapted instead.");
            return self.orderedRemoveContextAdapted(key, ctx, undefined);
        }
        pub fn orderedRemoveContextAdapted(self: *Self, key: anytype, key_ctx: anytype, ctx: Context) bool {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            return self.removeByKey(key, key_ctx, if (store_hash) {} else ctx, .ordered);
        }

        /// 从哈希表删除 `entries` 中指定索引处的元素。
        /// 通过将该条目与末尾元素交换,
        /// 从底层数组中移除。
        pub fn swapRemoveAt(self: *Self, index: usize) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call swapRemoveAtContext instead.");
            return self.swapRemoveAtContext(index, undefined);
        }
        pub fn swapRemoveAtContext(self: *Self, index: usize, ctx: Context) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            self.removeByIndex(index, if (store_hash) {} else ctx, .swap);
        }

        /// 从哈希映射中删除 `entries` 中指定索引处的条目。
        /// 通过将所有元素前移,将条目从底层数组中
        /// 移除,从而保持
        /// 当前顺序。
        pub fn orderedRemoveAt(self: *Self, index: usize) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveAtContext instead.");
            return self.orderedRemoveAtContext(index, undefined);
        }
        pub fn orderedRemoveAtContext(self: *Self, index: usize, ctx: Context) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            self.removeByIndex(index, if (store_hash) {} else ctx, .ordered);
        }

        /// 移除 `sorted_indexes` 索引的条目。待移除索引
        /// 对应删除前的状态。
        ///
        /// 此操作的时间复杂度为 O(N)。
        ///
        /// 断言每个待移除索引均在范围内。
        ///
        /// 使首个被删除索引之后的键指针和元素指针失效。
        pub fn orderedRemoveAtMany(self: *Self, gpa: Allocator, sorted_indexes: []const usize) Oom!void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call orderedRemoveAtContext instead.");
            return self.orderedRemoveAtManyContext(gpa, sorted_indexes, undefined);
        }

        pub fn orderedRemoveAtManyContext(
            self: *Self,
            gpa: Allocator,
            sorted_indexes: []const usize,
            ctx: Context,
        ) Oom!void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            self.entries.orderedRemoveMany(sorted_indexes);
            try self.reIndexContext(gpa, ctx);
        }

        /// 创建可独立修改的哈希映射副本。
        /// 副本使用与此实例相同的上下文,但通过
        /// 提供的分配器分配。
        pub fn clone(self: Self, gpa: Allocator) Oom!Self {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call cloneContext instead.");
            return self.cloneContext(gpa, undefined);
        }
        pub fn cloneContext(self: Self, gpa: Allocator, ctx: Context) Oom!Self {
            var other: Self = .{};
            other.entries = try self.entries.clone(gpa);
            errdefer other.entries.deinit(gpa);

            if (self.index_header) |header| {
                // TODO: 此处应该可以直接 memcpy,而无需完成这些操作。
                //
                const new_header = try IndexHeader.alloc(gpa, header.bit_index);
                other.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, new_header);
                other.index_header = new_header;
            }
            return other;
        }

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

        /// 重新计算已存储的哈希并重建键索引。若直接修改了底层键,应调用此方法,重新计算按键查找条目的映射方法所需的反规范化元数据。
        ///
        /// 一个用例是直接调用 `entries.resize()` 扩大底层存储,再直接设置 `keys` 与 `values`,而不经由此映射的方法。
        ///
        /// 此操作的时间复杂度为 O(n)。
        ///
        ///
        ///
        ///
        ///
        pub fn reIndex(self: *Self, gpa: Allocator) Oom!void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call reIndexContext instead.");
            return self.reIndexContext(gpa, undefined);
        }

        pub fn reIndexContext(self: *Self, gpa: Allocator, ctx: Context) Oom!void {
            // 重新计算所有哈希值。
            if (store_hash) {
                for (self.keys(), self.entries.items(.hash)) |key, *hash| {
                    const h = checkedHash(ctx, key);
                    hash.* = h;
                }
            }
            try rebuildIndex(self, gpa, ctx);
        }

        /// 修改条目的键,而不改变任何条目的顺序。
        pub fn setKey(self: *Self, index: usize, new_key: K) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call setKeyContext instead.");
            return setKeyContext(self, index, new_key, undefined);
        }

        pub fn setKeyContext(self: *Self, index: usize, new_key: K, ctx: Context) void {
            if (self.index_header) |header| {
                self.removeFromIndexByIndex(index, if (store_hash) {} else ctx, header);

                self.entries.items(.key)[index] = new_key;
                const h = checkedHash(ctx, new_key);
                if (store_hash) self.entries.items(.hash)[index] = h;

                insertEntryIntoNewHeader(header, h, index);
            } else {
                self.entries.items(.key)[index] = new_key;
                if (store_hash) self.entries.items(.hash)[index] = checkedHash(ctx, new_key);
            }
        }

        fn rebuildIndex(self: *Self, gpa: Allocator, ctx: Context) Oom!void {
            if (self.entries.capacity <= linear_scan_max) return;

            // 将重建索引头部并替换现有头部(若有)。索引大小应保证其填充率最多为 60%。
            //
            const bit_index = try IndexHeader.findBitIndex(self.entries.capacity);
            const new_header = try IndexHeader.alloc(gpa, bit_index);
            if (self.index_header) |header| header.free(gpa);
            self.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, new_header);
            self.index_header = new_header;
        }

        /// 排序条目,然后重建索引。
        /// `sort_ctx` 必须具有此方法:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        /// 采用稳定排序算法。
        pub inline fn sort(self: *Self, sort_ctx: anytype) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call sortContext instead.");
            return sortContextInternal(self, .stable, sort_ctx, undefined);
        }

        /// 对条目排序,随后重建索引。
        /// `sort_ctx` 必须具有此方法:
        /// `fn lessThan(ctx: @TypeOf(ctx), a_index: usize, b_index: usize) bool`
        /// 使用不稳定排序算法。
        pub inline fn sortUnstable(self: *Self, sort_ctx: anytype) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call sortUnstableContext instead.");
            return self.sortContextInternal(.unstable, sort_ctx, undefined);
        }

        pub inline fn sortContext(self: *Self, sort_ctx: anytype, ctx: Context) void {
            return sortContextInternal(self, .stable, sort_ctx, ctx);
        }

        pub inline fn sortUnstableContext(self: *Self, sort_ctx: anytype, ctx: Context) void {
            return sortContextInternal(self, .unstable, sort_ctx, ctx);
        }

        fn sortContextInternal(
            self: *Self,
            comptime mode: std.sort.Mode,
            sort_ctx: anytype,
            ctx: Context,
        ) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            switch (mode) {
                .stable => self.entries.sort(sort_ctx),
                .unstable => self.entries.sortUnstable(sort_ctx),
            }
            const header = self.index_header orelse return;
            header.reset();
            self.insertAllEntriesIntoNewHeader(if (store_hash) {} else ctx, header);
        }

        /// 将底层 `Entry` 数组缩小为 `new_len` 个元素,并丢弃所有关联的索引条目。容量保持不变。
        ///
        /// 断言被丢弃条目仍已初始化,且能够执行哈希与相等性检查。
        /// 被丢弃条目的任何反初始化,都必须在调用此函数之后进行。
        ///
        ///
        pub fn shrinkRetainingCapacity(self: *Self, new_len: usize) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call shrinkRetainingCapacityContext instead.");
            return self.shrinkRetainingCapacityContext(new_len, undefined);
        }

        /// 将底层 `Entry` 数组缩小为 `new_len` 个元素,并丢弃所有关联的索引条目。容量保持不变。
        ///
        /// 断言被丢弃条目仍已初始化,且能够执行哈希与相等性检查。
        /// 被丢弃条目的任何反初始化,都必须在调用此函数之后进行。
        ///
        ///
        pub fn shrinkRetainingCapacityContext(self: *Self, new_len: usize, ctx: Context) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            // 移除从新长度开始的所有索引条目。
            // 此处明确只移除索引条目,不移除底层数组列表的条目,
            // 因为后续的收缩调用会将其移除。
            if (self.index_header) |header| {
                var i: usize = new_len;
                while (i < self.entries.len) : (i += 1)
                    self.removeFromIndexByIndex(i, if (store_hash) {} else ctx, header);
            }
            self.entries.shrinkRetainingCapacity(new_len);
        }

        /// 将底层 `Entry` 数组缩减为 `new_len` 个元素,
        /// 丢弃所有关联索引条目,并减少已分配容量。
        ///
        /// 断言被丢弃的条目仍已初始化,且能
        /// 进行哈希与相等性检查。如果被丢弃的条目需要反初始化,
        /// 则调用此函数属于错误。该场景
        /// 可以改用 `shrinkRetainingCapacity`。
        pub fn shrinkAndFree(self: *Self, gpa: Allocator, new_len: usize) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call shrinkAndFreeContext instead.");
            return self.shrinkAndFreeContext(gpa, new_len, undefined);
        }

        /// 将底层 `Entry` 数组缩小到 `new_len` 个元素,并丢弃所有关联的索引条目。减少已分配容量。
        ///
        /// 断言被丢弃的条目仍已初始化,且能够执行哈希与相等性检查。
        /// 若被丢弃的条目需要反初始化,调用此函数属于错误。该场景可改用 `shrinkRetainingCapacityContext`。
        ///
        ///
        ///
        ///
        pub fn shrinkAndFreeContext(self: *Self, gpa: Allocator, new_len: usize, ctx: Context) void {
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            // 移除从新长度开始的所有索引条目。
            // 此处明确只移除索引条目,不移除底层数组列表的条目,
            // 因为后续的收缩调用会将其移除。
            if (self.index_header) |header| {
                var i: usize = new_len;
                while (i < self.entries.len) : (i += 1)
                    self.removeFromIndexByIndex(i, if (store_hash) {} else ctx, header);
            }
            self.entries.shrinkAndFree(gpa, new_len);
        }

        /// 移除并返回哈希映射中最后插入的 `Entry`。
        /// 否则返回 null。
        pub fn pop(self: *Self) ?KV {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call popContext instead.");
            return self.popContext(undefined);
        }
        pub fn popContext(self: *Self, ctx: Context) ?KV {
            if (self.entries.len == 0) return null;
            self.pointer_stability.lock();
            defer self.pointer_stability.unlock();

            const item = self.entries.get(self.entries.len - 1);
            if (self.index_header) |header|
                self.removeFromIndexByIndex(self.entries.len - 1, if (store_hash) {} else ctx, header);
            self.entries.len -= 1;
            return .{
                .key = item.key,
                .value = item.value,
            };
        }

        fn fetchRemoveByKey(
            self: *Self,
            key: anytype,
            key_ctx: anytype,
            ctx: ByIndexContext,
            comptime removal_type: RemovalType,
        ) ?KV {
            const header = self.index_header orelse {
                // 线性扫描。
                const key_hash = if (store_hash) key_ctx.hash(key) else {};
                const slice = self.entries.slice();
                const hashes_array = if (store_hash) slice.items(.hash) else {};
                const keys_array = slice.items(.key);
                for (keys_array, 0..) |*item_key, i| {
                    const hash_match = if (store_hash) hashes_array[i] == key_hash else true;
                    if (hash_match and key_ctx.eql(key, item_key.*, i)) {
                        const removed_entry: KV = .{
                            .key = keys_array[i],
                            .value = slice.items(.value)[i],
                        };
                        switch (removal_type) {
                            .swap => self.entries.swapRemove(i),
                            .ordered => self.entries.orderedRemove(i),
                        }
                        return removed_entry;
                    }
                }
                return null;
            };
            return switch (header.capacityIndexType()) {
                .u8 => self.fetchRemoveByKeyGeneric(key, key_ctx, ctx, header, u8, removal_type),
                .u16 => self.fetchRemoveByKeyGeneric(key, key_ctx, ctx, header, u16, removal_type),
                .u32 => self.fetchRemoveByKeyGeneric(key, key_ctx, ctx, header, u32, removal_type),
            };
        }
        fn fetchRemoveByKeyGeneric(
            self: *Self,
            key: anytype,
            key_ctx: anytype,
            ctx: ByIndexContext,
            header: *IndexHeader,
            comptime I: type,
            comptime removal_type: RemovalType,
        ) ?KV {
            const indexes = header.indexes(I);
            const entry_index = self.removeFromIndexByKey(key, key_ctx, header, I, indexes) orelse return null;
            const slice = self.entries.slice();
            const removed_entry: KV = .{
                .key = slice.items(.key)[entry_index],
                .value = slice.items(.value)[entry_index],
            };
            self.removeFromArrayAndUpdateIndex(entry_index, ctx, header, I, indexes, removal_type);
            return removed_entry;
        }

        fn removeByKey(
            self: *Self,
            key: anytype,
            key_ctx: anytype,
            ctx: ByIndexContext,
            comptime removal_type: RemovalType,
        ) bool {
            const header = self.index_header orelse {
                // 线性扫描。
                const key_hash = if (store_hash) key_ctx.hash(key) else {};
                const slice = self.entries.slice();
                const hashes_array = if (store_hash) slice.items(.hash) else {};
                const keys_array = slice.items(.key);
                for (keys_array, 0..) |*item_key, i| {
                    const hash_match = if (store_hash) hashes_array[i] == key_hash else true;
                    if (hash_match and key_ctx.eql(key, item_key.*, i)) {
                        switch (removal_type) {
                            .swap => self.entries.swapRemove(i),
                            .ordered => self.entries.orderedRemove(i),
                        }
                        return true;
                    }
                }
                return false;
            };
            return switch (header.capacityIndexType()) {
                .u8 => self.removeByKeyGeneric(key, key_ctx, ctx, header, u8, removal_type),
                .u16 => self.removeByKeyGeneric(key, key_ctx, ctx, header, u16, removal_type),
                .u32 => self.removeByKeyGeneric(key, key_ctx, ctx, header, u32, removal_type),
            };
        }
        fn removeByKeyGeneric(self: *Self, key: anytype, key_ctx: anytype, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType) bool {
            const indexes = header.indexes(I);
            const entry_index = self.removeFromIndexByKey(key, key_ctx, header, I, indexes) orelse return false;
            self.removeFromArrayAndUpdateIndex(entry_index, ctx, header, I, indexes, removal_type);
            return true;
        }

        fn removeByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, comptime removal_type: RemovalType) void {
            assert(entry_index < self.entries.len);
            const header = self.index_header orelse {
                switch (removal_type) {
                    .swap => self.entries.swapRemove(entry_index),
                    .ordered => self.entries.orderedRemove(entry_index),
                }
                return;
            };
            switch (header.capacityIndexType()) {
                .u8 => self.removeByIndexGeneric(entry_index, ctx, header, u8, removal_type),
                .u16 => self.removeByIndexGeneric(entry_index, ctx, header, u16, removal_type),
                .u32 => self.removeByIndexGeneric(entry_index, ctx, header, u32, removal_type),
            }
        }
        fn removeByIndexGeneric(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, comptime removal_type: RemovalType) void {
            const indexes = header.indexes(I);
            self.removeFromIndexByIndexGeneric(entry_index, ctx, header, I, indexes);
            self.removeFromArrayAndUpdateIndex(entry_index, ctx, header, I, indexes, removal_type);
        }

        fn removeFromArrayAndUpdateIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I), comptime removal_type: RemovalType) void {
            const last_index = self.entries.len - 1; // 溢出时从空映射中移除
            switch (removal_type) {
                .swap => {
                    if (last_index != entry_index) {
                        // 由于采用交换删除,现在需要更新原本
                        // 指向最后一个条目、现在指向被删除项槽位的索引。
                        self.updateEntryIndex(header, last_index, entry_index, ctx, I, indexes);
                    }
                    // updateEntryIndex 会读取旧条目索引,因此必须在移除之前运行。
                    //
                    self.entries.swapRemove(entry_index);
                },
                .ordered => {
                    var i: usize = entry_index;
                    while (i < last_index) : (i += 1) {
                        // 由于采用有序删除,条目索引及之后的所有内容均已
                        // 前移,因此需要更新索引条目。
                        self.updateEntryIndex(header, i + 1, i, ctx, I, indexes);
                    }
                    // updateEntryIndex 会读取旧条目索引,因此必须在移除之前运行。
                    //
                    self.entries.orderedRemove(entry_index);
                },
            }
        }

        fn updateEntryIndex(
            self: *Self,
            header: *IndexHeader,
            old_entry_index: usize,
            new_entry_index: usize,
            ctx: ByIndexContext,
            comptime I: type,
            indexes: []Index(I),
        ) void {
            const slot = self.getSlotByIndex(old_entry_index, ctx, header, I, indexes);
            indexes[slot].entry_index = @as(I, @intCast(new_entry_index));
        }

        fn removeFromIndexByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader) void {
            switch (header.capacityIndexType()) {
                .u8 => self.removeFromIndexByIndexGeneric(entry_index, ctx, header, u8, header.indexes(u8)),
                .u16 => self.removeFromIndexByIndexGeneric(entry_index, ctx, header, u16, header.indexes(u16)),
                .u32 => self.removeFromIndexByIndexGeneric(entry_index, ctx, header, u32, header.indexes(u32)),
            }
        }
        fn removeFromIndexByIndexGeneric(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I)) void {
            const slot = self.getSlotByIndex(entry_index, ctx, header, I, indexes);
            removeSlot(slot, header, I, indexes);
        }

        fn removeFromIndexByKey(self: *Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type, indexes: []Index(I)) ?usize {
            const slot = self.getSlotByKey(key, ctx, header, I, indexes) orelse return null;
            const removed_entry_index = indexes[slot].entry_index;
            removeSlot(slot, header, I, indexes);
            return removed_entry_index;
        }

        fn removeSlot(removed_slot: usize, header: *IndexHeader, comptime I: type, indexes: []Index(I)) void {
            const start_index = removed_slot +% 1;
            const end_index = start_index +% indexes.len;

            var last_slot = removed_slot;
            var index: usize = start_index;
            while (index != end_index) : (index +%= 1) {
                const slot = header.constrainIndex(index);
                const slot_data = indexes[slot];
                if (slot_data.isEmpty() or slot_data.distance_from_start_index == 0) {
                    indexes[last_slot].setEmpty();
                    return;
                }
                indexes[last_slot] = .{
                    .entry_index = slot_data.entry_index,
                    .distance_from_start_index = slot_data.distance_from_start_index - 1,
                };
                last_slot = slot;
            }
            unreachable;
        }

        fn getSlotByIndex(self: *Self, entry_index: usize, ctx: ByIndexContext, header: *IndexHeader, comptime I: type, indexes: []Index(I)) usize {
            const slice = self.entries.slice();
            const h = if (store_hash) slice.items(.hash)[entry_index] else checkedHash(ctx, slice.items(.key)[entry_index]);
            const start_index = safeTruncate(usize, h);
            const end_index = start_index +% indexes.len;

            var index = start_index;
            var distance_from_start_index: I = 0;
            while (index != end_index) : ({
                index +%= 1;
                distance_from_start_index += 1;
            }) {
                const slot = header.constrainIndex(index);
                const slot_data = indexes[slot];

                // 这是数组哈希映射索引的基本性质。如果此
                // 断言失败,很可能意味着该条目不在索引中。
                assert(!slot_data.isEmpty());
                assert(slot_data.distance_from_start_index >= distance_from_start_index);

                if (slot_data.entry_index == entry_index) {
                    return slot;
                }
            }
            unreachable;
        }

        /// 调用此函数前必须调用 `ensureTotalCapacity`/`ensureUnusedCapacity`。
        fn getOrPutInternal(self: *Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type) GetOrPutResult {
            const slice = self.entries.slice();
            const hashes_array = if (store_hash) slice.items(.hash) else {};
            const keys_array = slice.items(.key);
            const values_array = slice.items(.value);
            const indexes = header.indexes(I);

            const h = checkedHash(ctx, key);
            const start_index = safeTruncate(usize, h);
            const end_index = start_index +% indexes.len;

            var index = start_index;
            var distance_from_start_index: I = 0;
            while (index != end_index) : ({
                index +%= 1;
                distance_from_start_index += 1;
            }) {
                var slot = header.constrainIndex(index);
                var slot_data = indexes[slot];

                // 如果槽为空,则此连续区段中不可能再有更多条目。
                // 未找到匹配条目,因此它必定是新条目。
                // 将其放入空槽。
                if (slot_data.isEmpty()) {
                    const new_index = self.entries.addOneAssumeCapacity();
                    indexes[slot] = .{
                        .distance_from_start_index = distance_from_start_index,
                        .entry_index = @as(I, @intCast(new_index)),
                    };

                    // 适用时更新哈希
                    if (store_hash) hashes_array.ptr[new_index] = h;

                    return .{
                        .found_existing = false,
                        .key_ptr = &keys_array.ptr[new_index],
                        .value_ptr = &values_array.ptr[new_index],
                        .index = new_index,
                    };
                }

                // 此指针在后续追加后仍有效,因为在 getOrPutInternal 前
                // 调用了 entries.ensureTotalCapacity。
                const i = slot_data.entry_index;
                const hash_match = if (store_hash) h == hashes_array[i] else true;
                if (hash_match and checkedEql(ctx, key, keys_array[i], i)) {
                    return .{
                        .found_existing = true,
                        .key_ptr = &keys_array[slot_data.entry_index],
                        .value_ptr = &values_array[slot_data.entry_index],
                        .index = slot_data.entry_index,
                    };
                }

                // 如果此条目距其目标位置的距离比我们的当前距离更近,
                // 则要查找的条目不存在。若它存在于此,
                // 它应该位于这个槽位。因此停止查找,
                // 切换到插入模式。
                if (slot_data.distance_from_start_index < distance_from_start_index) {
                    // 此处未找到该条目,因此将插入新条目。
                    // 但新条目将使用此索引,并把
                    // 之前的索引后移,以尽可能减小最大 distance_from_start_index。
                    //
                    const new_index = self.entries.addOneAssumeCapacity();
                    if (store_hash) hashes_array.ptr[new_index] = h;
                    indexes[slot] = .{
                        .entry_index = @as(I, @intCast(new_index)),
                        .distance_from_start_index = distance_from_start_index,
                    };
                    distance_from_start_index = slot_data.distance_from_start_index;
                    var displaced_index = slot_data.entry_index;

                    // 通过将后续索引向后移,
                    // 为被替换的索引寻找存放位置。
                    index +%= 1;
                    distance_from_start_index += 1;
                    while (index != end_index) : ({
                        index +%= 1;
                        distance_from_start_index += 1;
                    }) {
                        slot = header.constrainIndex(index);
                        slot_data = indexes[slot];
                        if (slot_data.isEmpty()) {
                            indexes[slot] = .{
                                .entry_index = displaced_index,
                                .distance_from_start_index = distance_from_start_index,
                            };
                            return .{
                                .found_existing = false,
                                .key_ptr = &keys_array.ptr[new_index],
                                .value_ptr = &values_array.ptr[new_index],
                                .index = new_index,
                            };
                        }

                        if (slot_data.distance_from_start_index < distance_from_start_index) {
                            indexes[slot] = .{
                                .entry_index = displaced_index,
                                .distance_from_start_index = distance_from_start_index,
                            };
                            displaced_index = slot_data.entry_index;
                            distance_from_start_index = slot_data.distance_from_start_index;
                        }
                    }
                    unreachable;
                }
            }
            unreachable;
        }

        fn getSlotByKey(self: Self, key: anytype, ctx: anytype, header: *IndexHeader, comptime I: type, indexes: []Index(I)) ?usize {
            const slice = self.entries.slice();
            const hashes_array = if (store_hash) slice.items(.hash) else {};
            const keys_array = slice.items(.key);
            const h = checkedHash(ctx, key);

            const start_index = safeTruncate(usize, h);
            const end_index = start_index +% indexes.len;

            var index = start_index;
            var distance_from_start_index: I = 0;
            while (index != end_index) : ({
                index +%= 1;
                distance_from_start_index += 1;
            }) {
                const slot = header.constrainIndex(index);
                const slot_data = indexes[slot];
                if (slot_data.isEmpty() or slot_data.distance_from_start_index < distance_from_start_index)
                    return null;

                const i = slot_data.entry_index;
                const hash_match = if (store_hash) h == hashes_array[i] else true;
                if (hash_match and checkedEql(ctx, key, keys_array[i], i))
                    return slot;
            }
            unreachable;
        }

        fn insertAllEntriesIntoNewHeader(self: *Self, ctx: ByIndexContext, header: *IndexHeader) void {
            switch (header.capacityIndexType()) {
                .u8 => return self.insertAllEntriesIntoNewHeaderGeneric(ctx, header, u8),
                .u16 => return self.insertAllEntriesIntoNewHeaderGeneric(ctx, header, u16),
                .u32 => return self.insertAllEntriesIntoNewHeaderGeneric(ctx, header, u32),
            }
        }
        fn insertAllEntriesIntoNewHeaderGeneric(self: *Self, ctx: ByIndexContext, header: *IndexHeader, comptime I: type) void {
            const slice = self.entries.slice();
            const items = if (store_hash) slice.items(.hash) else slice.items(.key);

            for (items, 0..) |hash_or_key, i| {
                const h = if (store_hash) hash_or_key else checkedHash(ctx, hash_or_key);
                insertEntryIntoNewHeaderGeneric(header, h, i, I);
            }
        }

        fn insertEntryIntoNewHeader(header: *IndexHeader, h: u32, i: usize) void {
            switch (header.capacityIndexType()) {
                .u8 => insertEntryIntoNewHeaderGeneric(header, h, i, u8),
                .u16 => insertEntryIntoNewHeaderGeneric(header, h, i, u16),
                .u32 => insertEntryIntoNewHeaderGeneric(header, h, i, u32),
            }
        }
        fn insertEntryIntoNewHeaderGeneric(header: *IndexHeader, h: u32, i: usize, comptime I: type) void {
            const indexes = header.indexes(I);
            const start_index = safeTruncate(usize, h);
            const end_index = start_index +% indexes.len;
            var index = start_index;
            var entry_index: I = @intCast(i);
            var distance_from_start_index: I = 0;
            while (index != end_index) : ({
                index +%= 1;
                distance_from_start_index += 1;
            }) {
                const slot = header.constrainIndex(index);
                const next_index = indexes[slot];
                if (next_index.isEmpty()) {
                    indexes[slot] = .{
                        .distance_from_start_index = distance_from_start_index,
                        .entry_index = entry_index,
                    };
                    return;
                }
                if (next_index.distance_from_start_index < distance_from_start_index) {
                    indexes[slot] = .{
                        .distance_from_start_index = distance_from_start_index,
                        .entry_index = entry_index,
                    };
                    distance_from_start_index = next_index.distance_from_start_index;
                    entry_index = next_index.entry_index;
                }
            }
            unreachable;
        }

        fn checkedHash(ctx: anytype, key: anytype) u32 {
            // 若下一行产生编译错误,表示泛型哈希函数
            // 不接受该键。
            return ctx.hash(key);
        }

        fn checkedEql(ctx: anytype, a: anytype, b: K, b_index: usize) bool {
            // 若下一行出现编译错误,表示泛型 eql 函数不接受 (self, adapt key, K, index)。
            //
            return ctx.eql(a, b, b_index);
        }

        fn dumpState(self: Self, comptime keyFmt: []const u8, comptime valueFmt: []const u8) void {
            if (@sizeOf(ByIndexContext) != 0)
                @compileError("Cannot infer context " ++ @typeName(Context) ++ ", call dumpStateContext instead.");
            self.dumpStateContext(keyFmt, valueFmt, undefined);
        }
        fn dumpStateContext(self: Self, comptime keyFmt: []const u8, comptime valueFmt: []const u8, ctx: Context) void {
            const p = std.debug.print;
            p("{s}:\n", .{@typeName(Self)});
            const slice = self.entries.slice();
            const hash_status = if (store_hash) "stored" else "computed";
            p("  len={} capacity={} hashes {s}\n", .{ slice.len, slice.capacity, hash_status });
            var i: usize = 0;
            const mask: u32 = if (self.index_header) |header| header.mask() else ~@as(u32, 0);
            while (i < slice.len) : (i += 1) {
                const hash = if (store_hash) slice.items(.hash)[i] else checkedHash(ctx, slice.items(.key)[i]);
                if (store_hash) {
                    p(
                        "  [{}]: key=" ++ keyFmt ++ " value=" ++ valueFmt ++ " hash=0x{x} slot=[0x{x}]\n",
                        .{ i, slice.items(.key)[i], slice.items(.value)[i], hash, hash & mask },
                    );
                } else {
                    p(
                        "  [{}]: key=" ++ keyFmt ++ " value=" ++ valueFmt ++ " slot=[0x{x}]\n",
                        .{ i, slice.items(.key)[i], slice.items(.value)[i], hash & mask },
                    );
                }
            }
            if (self.index_header) |header| {
                p("\n", .{});
                switch (header.capacityIndexType()) {
                    .u8 => dumpIndex(header, u8),
                    .u16 => dumpIndex(header, u16),
                    .u32 => dumpIndex(header, u32),
                }
            }
        }
        fn dumpIndex(header: *IndexHeader, comptime I: type) void {
            const p = std.debug.print;
            p("  index len=0x{x} type={}\n", .{ header.length(), header.capacityIndexType() });
            const indexes = header.indexes(I);
            if (indexes.len == 0) return;
            var is_empty = false;
            for (indexes, 0..) |idx, i| {
                if (idx.isEmpty()) {
                    is_empty = true;
                } else {
                    if (is_empty) {
                        is_empty = false;
                        p("  ...\n", .{});
                    }
                    p("  [0x{x}]: [{}] +{}\n", .{ i, idx.entry_index, idx.distance_from_start_index });
                }
            }
            if (is_empty) {
                p("  ...\n", .{});
            }
        }
    };
}

const CapacityIndexType = enum { u8, u16, u32 };

fn capacityIndexType(bit_index: u8) CapacityIndexType {
    if (bit_index <= 8)
        return .u8;
    if (bit_index <= 16)
        return .u16;
    assert(bit_index <= 32);
    return .u32;
}

fn capacityIndexSize(bit_index: u8) usize {
    switch (capacityIndexType(bit_index)) {
        .u8 => return @sizeOf(Index(u8)),
        .u16 => return @sizeOf(Index(u16)),
        .u32 => return @sizeOf(Index(u32)),
    }
}

/// 目标类型大于目标值的类型时,
/// @truncate 会失败。当某个类型为 usize 时
/// 便会产生问题,因为不同系统上的 usize
/// 可能大于或小于 u32。此版本的 truncate 在任一
/// 参数大小随平台变化时均可安全使用,并会在需要时执行拓宽转换。
/// 两个参数的符号属性必须相同。
fn safeTruncate(comptime T: type, val: anytype) T {
    if (@bitSizeOf(T) >= @bitSizeOf(@TypeOf(val)))
        return val;
    return @as(T, @truncate(val));
}

/// 查找加速结构中的单个条目。这些结构体
/// 存储在 IndexHeader 后的数组中。哈希值用于索引此
/// 数组,冲突通过线性探测解决。
fn Index(comptime I: type) type {
    return extern struct {
        const Self = @This();

        /// 此条目在底层存储中的索引。如果该索引
        /// 为空,则此值为 empty_sentinel。
        entry_index: I,

        /// 此槽与理想位置之间的距离。用于缩短最大扫描长度。若索引为空,此值未定义。
        ///
        ///
        distance_from_start_index: I,

        /// 表示空槽的特殊 entry_index 值。
        const empty_sentinel = ~@as(I, 0);

        /// 常量空索引
        const empty = Self{
            .entry_index = empty_sentinel,
            .distance_from_start_index = undefined,
        };

        /// 检查槽是否为空
        fn isEmpty(idx: Self) bool {
            return idx.entry_index == empty_sentinel;
        }

        /// 将槽设为空
        fn setEmpty(idx: *Self) void {
            idx.entry_index = empty_sentinel;
            idx.distance_from_start_index = undefined;
        }
    };
}

/// 索引的字节大小必须能由 usize 表示。其为二的幂长度乘以
/// Index(u32) 的大小。索引占 8 字节(3 位表示),
/// 而 max_usize + 1 无法表示,因此需减去 4 位。
const max_representable_index_len = @bitSizeOf(usize) - 4;
const max_bit_index = @min(32, max_representable_index_len);
const min_bit_index = 5;
const max_capacity = (1 << max_bit_index) - 1;
const index_capacities = blk: {
    var caps: [max_bit_index + 1]u32 = undefined;
    for (caps[0..max_bit_index], 0..) |*item, i| {
        item.* = (1 << i) * 3 / 5;
    }
    caps[max_bit_index] = max_capacity;
    break :blk caps;
};

/// 此结构体之后跟随两个长度均为 indexes_len 的整数数组,其整数大小由 indexes_len 决定。
/// 数组通过 constrainIndex(hash) 索引。entryIndexes 数组存储条目数据在稠密后备存储中的索引;未使用条目的索引值设为 emptySentinel(I)。
/// entryDistances 数组存储条目与其理想哈希桶之间的距离,添加元素时用它平衡最大扫描长度。
///
///
///
///
///
///
const IndexHeader = struct {
    /// 此字段跟踪紧随头部之后的各数组中的
    /// 元素总数。索引数量是 2 的幂,此值为其位索引。
    /// 该值位于 min_bit_index 与 max_bit_index 之间,包含两端。
    bit_index: u8 align(@alignOf(u32)),

    /// 从递增索引到所附数组中索引槽的映射。
    fn constrainIndex(header: IndexHeader, i: usize) usize {
        // 针对以 2 的幂为模的取模优化;
        // 要求 `indexes_len` 始终为 2 的幂。
        return @as(usize, @intCast(i & header.mask()));
    }

    /// 返回所附的索引数组。I 必须与
    /// capacityIndexType 返回的类型匹配。
    fn indexes(header: *IndexHeader, comptime I: type) []Index(I) {
        const start_ptr: [*]Index(I) = @ptrCast(@alignCast(@as([*]u8, @ptrCast(header)) + @sizeOf(IndexHeader)));
        return start_ptr[0..header.length()];
    }

    /// 返回索引数组使用的类型。
    fn capacityIndexType(header: IndexHeader) CapacityIndexType {
        return hash_map.capacityIndexType(header.bit_index);
    }

    fn capacity(self: IndexHeader) u32 {
        return index_capacities[self.bit_index];
    }
    fn length(self: IndexHeader) usize {
        return @as(usize, 1) << @as(math.Log2Int(usize), @intCast(self.bit_index));
    }
    fn mask(self: IndexHeader) u32 {
        return @as(u32, @intCast(self.length() - 1));
    }

    fn findBitIndex(desired_capacity: usize) Allocator.Error!u8 {
        if (desired_capacity > max_capacity) return error.OutOfMemory;
        var new_bit_index: u8 = @intCast(std.math.log2_int_ceil(usize, desired_capacity));
        if (desired_capacity > index_capacities[new_bit_index]) new_bit_index += 1;
        if (new_bit_index < min_bit_index) new_bit_index = min_bit_index;
        assert(desired_capacity <= index_capacities[new_bit_index]);
        return new_bit_index;
    }

    /// 分配索引头,并将 entryIndexes 数组填为空。
    /// distance 数组内容未定义。
    fn alloc(gpa: Allocator, new_bit_index: u8) Allocator.Error!*IndexHeader {
        const len = @as(usize, 1) << @as(math.Log2Int(usize), @intCast(new_bit_index));
        const index_size = hash_map.capacityIndexSize(new_bit_index);
        const nbytes = @sizeOf(IndexHeader) + index_size * len;
        const bytes = try gpa.alignedAlloc(u8, .of(IndexHeader), nbytes);
        @memset(bytes[@sizeOf(IndexHeader)..], 0xff);
        const result: *IndexHeader = @ptrCast(@alignCast(bytes.ptr));
        result.* = .{
            .bit_index = new_bit_index,
        };
        return result;
    }

    /// 释放头部及其关联数组的内存。
    fn free(header: *IndexHeader, gpa: Allocator) void {
        const index_size = hash_map.capacityIndexSize(header.bit_index);
        const ptr: [*]align(@alignOf(IndexHeader)) u8 = @ptrCast(header);
        const slice = ptr[0 .. @sizeOf(IndexHeader) + header.length() * index_size];
        gpa.free(slice);
    }

    /// 将 IndexHeader 置为刚分配完成时应有的状态。
    fn reset(header: *IndexHeader) void {
        const index_size = hash_map.capacityIndexSize(header.bit_index);
        const ptr: [*]align(@alignOf(IndexHeader)) u8 = @ptrCast(header);
        const nbytes = @sizeOf(IndexHeader) + header.length() * index_size;
        @memset(ptr[@sizeOf(IndexHeader)..nbytes], 0xff);
    }

    // 验证头部具有足够的对齐,以生成已对齐的数组。
    comptime {
        if (@alignOf(u32) > @alignOf(IndexHeader))
            @compileError("IndexHeader must have a larger alignment than its indexes!");
    }
};

test "basic hash map usage" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

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

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

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

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

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

    const gop4 = try map.getOrPutValue(gpa, 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.fetchSwapRemove(2);
    try testing.expect(rmv1.?.key == 2);
    try testing.expect(rmv1.?.value == 22);
    try testing.expect(map.fetchSwapRemove(2) == null);
    try testing.expect(map.swapRemove(2) == false);
    try testing.expect(map.getEntry(2) == null);
    try testing.expect(map.get(2) == null);

    // 由于上面使用了 `swapRemove`,此条目的索引应保持不变。
    try testing.expect(map.getIndex(100).? == 1);
    const gop5 = try map.getOrPut(gpa, 5);
    try testing.expect(gop5.found_existing == true);
    try testing.expect(gop5.value_ptr.* == 77);
    try testing.expect(gop5.index == 4);

    // 若执行 `orderedRemove`,则应将索引向前移动一个位置。
    const rmv2 = map.fetchOrderedRemove(100);
    try testing.expect(rmv2.?.key == 100);
    try testing.expect(rmv2.?.value == 41);
    try testing.expect(map.fetchOrderedRemove(100) == null);
    try testing.expect(map.orderedRemove(100) == false);
    try testing.expect(map.getEntry(100) == null);
    try testing.expect(map.get(100) == null);
    const gop6 = try map.getOrPut(gpa, 5);
    try testing.expect(gop6.found_existing == true);
    try testing.expect(gop6.value_ptr.* == 77);
    try testing.expect(gop6.index == 3);

    try testing.expect(map.swapRemove(3));
}

test "iterator hash map" {
    const gpa = testing.allocator;

    var reset_map: Auto(i32, i32) = .empty;
    defer reset_map.deinit(gpa);

    // 测试以 0 为参数的 ensureTotalCapacity
    try reset_map.ensureTotalCapacity(gpa, 0);

    try reset_map.putNoClobber(gpa, 0, 11);
    try reset_map.putNoClobber(gpa, 1, 22);
    try reset_map.putNoClobber(gpa, 2, 33);

    const keys = [_]i32{
        0, 2, 1,
    };

    const values = [_]i32{
        11, 33, 22,
    };

    var buffer = [_]i32{
        0, 0, 0,
    };

    var it = reset_map.iterator();
    const first_entry = it.next().?;
    it.reset();

    var count: usize = 0;
    while (it.next()) |entry| : (count += 1) {
        buffer[@as(usize, @intCast(entry.key_ptr.*))] = entry.value_ptr.*;
    }
    try testing.expect(count == 3);
    try testing.expect(it.next() == null);

    for (buffer, 0..) |_, i| {
        try testing.expect(buffer[@as(usize, @intCast(keys[i]))] == values[i]);
    }

    it.reset();
    count = 0;
    while (it.next()) |entry| {
        buffer[@as(usize, @intCast(entry.key_ptr.*))] = entry.value_ptr.*;
        count += 1;
        if (count >= 2) break;
    }

    for (buffer[0..2], 0..) |_, i| {
        try testing.expect(buffer[@as(usize, @intCast(keys[i]))] == values[i]);
    }

    it.reset();
    const entry = it.next().?;
    try testing.expect(entry.key_ptr.* == first_entry.key_ptr.*);
    try testing.expect(entry.value_ptr.* == first_entry.value_ptr.*);
}

test "ensure capacity" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

    try map.ensureTotalCapacity(gpa, 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 "ensure capacity leak" {
    try testing.checkAllAllocationFailures(std.testing.allocator, struct {
        pub fn f(allocator: Allocator) !void {
            var map: Auto(i32, i32) = .empty;
            defer map.deinit(allocator);

            var i: i32 = 0;
            // 放入超过 `linear_scan_max` 项,使 index_header 得到分配。
            while (i <= 20) : (i += 1) try map.put(allocator, i, i);
        }
    }.f, .{});
}

test "big map" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

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

    i = 0;
    while (i < 8) : (i += 1) {
        try testing.expectEqual(@as(?i32, i + 10), map.get(i));
    }
    while (i < 16) : (i += 1) {
        try testing.expectEqual(@as(?i32, null), map.get(i));
    }

    i = 4;
    while (i < 12) : (i += 1) {
        try map.put(gpa, i, i + 12);
    }

    i = 0;
    while (i < 4) : (i += 1) {
        try testing.expectEqual(@as(?i32, i + 10), map.get(i));
    }
    while (i < 12) : (i += 1) {
        try testing.expectEqual(@as(?i32, i + 12), map.get(i));
    }
    while (i < 16) : (i += 1) {
        try testing.expectEqual(@as(?i32, null), map.get(i));
    }

    i = 0;
    while (i < 4) : (i += 1) {
        try testing.expect(map.orderedRemove(i));
    }
    while (i < 8) : (i += 1) {
        try testing.expect(map.swapRemove(i));
    }

    i = 0;
    while (i < 8) : (i += 1) {
        try testing.expectEqual(@as(?i32, null), map.get(i));
    }
    while (i < 12) : (i += 1) {
        try testing.expectEqual(@as(?i32, i + 12), map.get(i));
    }
    while (i < 16) : (i += 1) {
        try testing.expectEqual(@as(?i32, null), map.get(i));
    }
}

test "clone" {
    const gpa = testing.allocator;

    var original: Auto(i32, i32) = .empty;
    defer original.deinit(gpa);

    // 放入超过 `linear_scan_max` 项,以测试索引头是否被正确克隆
    var i: u8 = 0;
    while (i < 10) : (i += 1) {
        try original.putNoClobber(gpa, i, i * 10);
    }

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

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

    while (i < 20) : (i += 1) {
        try testing.expect(original.get(i) == null);
        try testing.expect(copy.get(i) == null);
    }
}

test "shrink" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

    // 若插入足够多条目以分配索引头部,此测试会更有意义。
    const num_entries = 200;
    var i: i32 = 0;
    while (i < num_entries) : (i += 1)
        try testing.expect((try map.fetchPut(gpa, i, i * 10)) == null);

    try testing.expect(map.index_header != null);
    try testing.expect(map.count() == num_entries);

    // 测试 `shrinkRetainingCapacity`。
    map.shrinkRetainingCapacity(17);
    try testing.expect(map.count() == 17);
    try testing.expect(map.capacity() >= num_entries);
    i = 0;
    while (i < num_entries) : (i += 1) {
        const gop = try map.getOrPut(gpa, i);
        if (i < 17) {
            try testing.expect(gop.found_existing == true);
            try testing.expect(gop.value_ptr.* == i * 10);
        } else try testing.expect(gop.found_existing == false);
    }

    // 测试 `shrinkAndFree`。
    map.shrinkAndFree(gpa, 15);
    try testing.expect(map.count() == 15);
    try testing.expect(map.capacity() == 15);
    i = 0;
    while (i < num_entries) : (i += 1) {
        const gop = try map.getOrPut(gpa, i);
        if (i < 15) {
            try testing.expect(gop.found_existing == true);
            try testing.expect(gop.value_ptr.* == i * 10);
        } else try testing.expect(gop.found_existing == false);
    }
}

test "pop()" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

    // 插入恰好足以使映射扩容的条目。之后,
    // 从映射中弹出所有条目。

    var i: i32 = 0;
    while (i < 9) : (i += 1) {
        try testing.expect((try map.fetchPut(gpa, i, i)) == null);
    }

    while (map.pop()) |pop| {
        try testing.expect(pop.key == i - 1 and pop.value == i - 1);
        i -= 1;
    }

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

test "reIndex" {
    const gpa = testing.allocator;

    var map: Custom(i32, i32, AutoContext(i32), true) = .empty;
    defer map.deinit(gpa);

    // 通过 API 填充。
    const num_indexed_entries = 200;
    var i: i32 = 0;
    while (i < num_indexed_entries) : (i += 1)
        try testing.expect((try map.fetchPut(gpa, i, i * 10)) == null);

    // 确保已分配索引头。
    try testing.expect(map.index_header != null);

    // 现在直接写入数组。
    const num_unindexed_entries = 20;
    try map.entries.resize(std.testing.allocator, num_indexed_entries + num_unindexed_entries);
    for (map.keys()[num_indexed_entries..], map.values()[num_indexed_entries..], num_indexed_entries..) |*key, *value, j| {
        key.* = @intCast(j);
        value.* = @intCast(j * 10);
    }

    // 重新建立索引后,应能看到全部内容。
    try map.reIndex(gpa);
    i = 0;
    while (i < num_indexed_entries + num_unindexed_entries) : (i += 1) {
        const gop = try map.getOrPut(gpa, i);
        try testing.expect(gop.found_existing == true);
        try testing.expect(gop.value_ptr.* == i * 10);
        try testing.expect(gop.index == i);
    }
}

test "auto store_hash" {
    const HasCheapEql = Auto(i32, i32);
    const HasExpensiveEql = Auto([32]i32, i32);
    try testing.expect(@FieldType(HasCheapEql.Data, "hash") == void);
    try testing.expect(@FieldType(HasExpensiveEql.Data, "hash") != void);
}

test "sort" {
    const gpa = testing.allocator;

    var map: Auto(i32, i32) = .empty;
    defer map.deinit(gpa);

    for ([_]i32{ 8, 3, 12, 10, 2, 4, 9, 5, 6, 13, 14, 15, 16, 1, 11, 17, 7 }) |x| {
        try map.put(gpa, x, x * 3);
    }

    const C = struct {
        keys: []i32,

        pub fn lessThan(ctx: @This(), a_index: usize, b_index: usize) bool {
            return ctx.keys[a_index] < ctx.keys[b_index];
        }
    };

    map.sort(C{ .keys = map.keys() });

    var x: i32 = 1;
    for (map.keys(), 0..) |key, i| {
        try testing.expect(key == x);
        try testing.expect(map.values()[i] == x * 3);
        x += 1;
    }
}

test "0 sized key" {
    const gpa = testing.allocator;

    var map: Auto(u0, i32) = .empty;
    defer map.deinit(gpa);

    try testing.expectEqual(map.get(0), null);

    try map.put(gpa, 0, 5);
    try testing.expectEqual(map.get(0), 5);

    try map.put(gpa, 0, 10);
    try testing.expectEqual(map.get(0), 10);

    try testing.expectEqual(map.swapRemove(0), true);
    try testing.expectEqual(map.get(0), null);
}

test "0 sized key and 0 sized value" {
    const gpa = testing.allocator;

    var map: Auto(u0, u0) = .empty;
    defer map.deinit(gpa);

    try testing.expectEqual(map.get(0), null);

    try map.put(gpa, 0, 0);
    try testing.expectEqual(map.get(0), 0);

    try testing.expectEqual(map.swapRemove(0), true);
    try testing.expectEqual(map.get(0), null);
}

test "setKey storehash true" {
    const gpa = std.testing.allocator;

    var map: Custom(i32, i32, AutoContext(i32), true) = .empty;
    defer map.deinit(gpa);

    try map.put(gpa, 12, 34);
    try map.put(gpa, 56, 78);

    map.setKey(0, 42);
    try testing.expectEqual(2, map.count());
    try testing.expectEqual(false, map.contains(12));
    try testing.expectEqual(34, map.get(42));
    try testing.expectEqual(78, map.get(56));
}

test "setKey storehash false" {
    const gpa = std.testing.allocator;

    var map: Custom(i32, i32, AutoContext(i32), false) = .empty;
    defer map.deinit(gpa);

    try map.put(gpa, 12, 34);
    try map.put(gpa, 56, 78);

    map.setKey(0, 42);
    try testing.expectEqual(2, map.count());
    try testing.expectEqual(false, map.contains(12));
    try testing.expectEqual(34, map.get(42));
    try testing.expectEqual(78, map.get(56));
}

test "setKey storehash false with index" {
    const gpa = std.testing.allocator;

    const T = Custom(usize, usize, AutoContext(usize), false);

    var map: T = .empty;
    defer map.deinit(gpa);

    for (0..T.linear_scan_max + 1) |i| try map.put(gpa, i, i);

    map.setKey(0, 42);
    try testing.expectEqual(T.linear_scan_max + 1, map.count());
    try testing.expectEqual(false, map.contains(0));
    try testing.expectEqual(0, map.get(42));

    for (1..T.linear_scan_max + 1) |i| try testing.expectEqual(i, map.get(i));
}

test "setKey storehash true with index" {
    const gpa = std.testing.allocator;

    const T = Custom(usize, usize, AutoContext(usize), false);

    var map: Custom(usize, usize, AutoContext(usize), true) = .empty;
    defer map.deinit(gpa);

    for (0..T.linear_scan_max + 1) |i| try map.put(gpa, i, i);

    map.setKey(0, 42);
    try testing.expectEqual(T.linear_scan_max + 1, map.count());
    try testing.expectEqual(false, map.contains(0));
    try testing.expectEqual(0, map.get(42));

    for (1..T.linear_scan_max + 1) |i| try testing.expectEqual(i, map.get(i));
}

pub fn getHashPtrAddrFn(comptime K: type, comptime Context: type) (fn (Context, K) u32) {
    return struct {
        fn hash(ctx: Context, key: K) u32 {
            _ = ctx;
            return getAutoHashFn(usize, void)({}, @intFromPtr(key));
        }
    }.hash;
}

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

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

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

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

pub fn autoEqlIsCheap(comptime K: type) bool {
    return switch (@typeInfo(K)) {
        .bool,
        .int,
        .float,
        .pointer,
        .comptime_float,
        .comptime_int,
        .@"enum",
        .@"fn",
        .error_set,
        .@"anyframe",
        .enum_literal,
        => true,
        else => false,
    };
}

pub fn getAutoHashStratFn(comptime K: type, comptime Context: type, comptime strategy: std.hash.Strategy) (fn (Context, K) u32) {
    return struct {
        fn hash(ctx: Context, key: K) u32 {
            _ = ctx;
            var hasher = Wyhash.init(0);
            std.hash.autoHashStrat(&hasher, key, strategy);
            return @as(u32, @truncate(hasher.final()));
        }
    }.hash;
}

test "orderedRemoveAtMany" {
    const gpa = testing.allocator;

    var map: Auto(usize, void) = .empty;
    defer map.deinit(gpa);

    for (0..10) |n| {
        try map.put(gpa, n, {});
    }

    try map.orderedRemoveAtMany(gpa, &.{ 1, 5, 5, 7, 9 });
    try testing.expectEqualSlices(usize, &.{ 0, 2, 3, 4, 6, 8 }, map.keys());

    try map.orderedRemoveAtMany(gpa, &.{0});
    try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, map.keys());

    try map.orderedRemoveAtMany(gpa, &.{});
    try testing.expectEqualSlices(usize, &.{ 2, 3, 4, 6, 8 }, map.keys());

    try map.orderedRemoveAtMany(gpa, &.{ 1, 2, 3, 4 });
    try testing.expectEqualSlices(usize, &.{2}, map.keys());

    try map.orderedRemoveAtMany(gpa, &.{0});
    try testing.expectEqualSlices(usize, &.{}, map.keys());
}