stdbuiltinassertautoHashmathmemAllocatorWyhashAlignmentgetAutoHashFngetAutoEqlFnAutoHashMapAutoHashMapUnmanagedAutoContextStringHashMapStringHashMapUnmanagedStringContexteqlStringhashStringStringIndexContextStringIndexAdapterdefault_max_load_percentageHashMapHashMapUnmanagedCustomtestingexpectexpectEqualeqlhash
std.hash_map.Alignment
别名
别名目标 std.mem.Alignment
std.hash_map.Allocator
别名
别名目标 std.mem.Allocator
std.hash_map.assert
别名
别名目标 std.debug.assert
std.hash_map.AutoContext
类型函数
pub fn AutoContext(comptime K: type) type
参数
K: type
std.hash_map.AutoContext.eql
常量
std.hash_map.AutoContext.hash
常量
std.hash_map.autoHash
别名
别名目标 std.hash.autoHash
std.hash_map.AutoHashMap
类型函数
pub fn AutoHashMap(comptime K: type, comptime V: type) type
参数
K: type
V: type
字段
UnmanagedEntryKVHashIteratorKeyIteratorValueIteratorSizeGetOrPutResultSelfinitinitContextlockPointersunlockPointersdeinitclearRetainingCapacityclearAndFreecountiteratorkeyIteratorvalueIteratorgetOrPutgetOrPutAdaptedgetOrPutAssumeCapacitygetOrPutAssumeCapacityAdaptedgetOrPutValueensureTotalCapacityensureUnusedCapacitycapacityputputNoClobberputAssumeCapacityputAssumeCapacityNoClobberfetchPutfetchPutAssumeCapacityfetchRemovefetchRemoveAdaptedgetgetAdaptedgetPtrgetPtrAdaptedgetKeygetKeyAdaptedgetKeyPtrgetKeyPtrAdaptedgetEntrygetEntryAdaptedcontainscontainsAdaptedremoveremoveAdaptedremoveByPtrclonecloneWithAllocatorcloneWithContextcloneWithAllocatorAndContextmoverehash
std.hash_map.AutoHashMapUnmanaged
类型函数
pub fn AutoHashMapUnmanaged(comptime K: type, comptime V: type) type
参数
K: type
V: type
std.hash_map.builtin
常量
std.hash_map.Custom
类型函数
fn Custom( comptime K: type, comptime V: type, comptime Context: type, comptime max_load_percentage: u64, ) type
参数
K: type
V: type
Context: type
max_load_percentage: u64
字段
metadata: ?[*]Metadata = null指向元数据的指针。
size: Size = 0哈希映射中当前的元素数。
available: Size = 0在为满足 max_load_percentage 而必须扩容之前,
可用的槽位数量。
pointer_stability: std.debug.SafetyLock = .{}用于检测内存安全违规。
Selfminimal_capacityemptySizeHashEntryKVHeaderMetadataIteratorKeyIteratorValueIteratorFieldIteratorGetOrPutResultManagedpromotepromoteContextlockPointersunlockPointersisUnderMaxLoadPercentagedeinitcapacityForSizeensureTotalCapacityensureTotalCapacityContextensureUnusedCapacityensureUnusedCapacityContextclearRetainingCapacityclearAndFreecountheaderkeysvaluescapacityiteratorkeyIteratorvalueIteratorputNoClobberputNoClobberContextputAssumeCapacityputAssumeCapacityContextputAssumeCapacityNoClobberputAssumeCapacityNoClobberContextfetchPutfetchPutContextfetchPutAssumeCapacityfetchPutAssumeCapacityContextfetchRemovefetchRemoveContextfetchRemoveAdaptedgetIndexgetEntrygetEntryContextgetEntryAdaptedputputContextgetKeyPtrgetKeyPtrContextgetKeyPtrAdaptedgetKeygetKeyContextgetKeyAdaptedgetPtrgetPtrContextgetPtrAdaptedgetgetContextgetAdaptedgetOrPutgetOrPutContextgetOrPutAdaptedgetOrPutContextAdaptedgetOrPutAssumeCapacitygetOrPutAssumeCapacityContextgetOrPutAssumeCapacityAdaptedgetOrPutValuegetOrPutValueContextcontainscontainsContextcontainsAdaptedremoveByIndexremoveremoveContextremoveAdaptedremoveByPtrinitMetadatasloadgrowIfNeededclonecloneContextmoverehashgrowallocatedeallocatedbHelper
std.hash_map.Custom.allocate
函数
fn allocate(self: *Self, allocator: Allocator, new_capacity: Size) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.Custom.capacity
函数
pub fn capacity(self: Self) Size
参数
self: Self
std.hash_map.Custom.capacityForSize
函数
fn capacityForSize(size: Size) Size
参数
size: Size
std.hash_map.Custom.clearAndFree
函数
pub fn clearAndFree(self: *Self, allocator: Allocator) void
参数
std.hash_map.Custom.clearRetainingCapacity
函数
pub fn clearRetainingCapacity(self: *Self) void
参数
self: *Self
std.hash_map.Custom.clone
函数
pub fn clone(self: Self, allocator: Allocator) Allocator.Error!Self
参数
错误
- OutOfMemory
std.hash_map.Custom.cloneContext
函数
pub fn cloneContext(self: Self, allocator: Allocator, new_ctx: anytype) Allocator.Error!HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage)
参数
错误
- OutOfMemory
std.hash_map.Custom.contains
函数
若映射中存在与 key 关联的值,则返回 true。
pub fn contains(self: Self, key: K) bool
参数
self: Self
key: K
std.hash_map.Custom.containsAdapted
函数
pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool
参数
self: Self
std.hash_map.Custom.containsContext
函数
pub fn containsContext(self: Self, key: K, ctx: Context) bool
参数
std.hash_map.Custom.count
函数
pub fn count(self: Self) Size
参数
self: Self
std.hash_map.Custom.dbHelper
函数
lib/lldb/ 中的调试器美化格式化器使用此函数获取头部类型,以便为该类型提供格式化调试输出。
fn dbHelper(self: *Self, hdr: *Header, entry: *Entry) void
参数
std.hash_map.Custom.deallocate
函数
fn deallocate(self: *Self, allocator: Allocator) void
参数
std.hash_map.Custom.deinit
函数
pub fn deinit(self: *Self, allocator: Allocator) void
参数
std.hash_map.Custom.empty
常量
不含任何键值的映射。
Self
std.hash_map.Custom.ensureTotalCapacity
函数
pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_size: Size) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.Custom.ensureTotalCapacityContext
函数
pub fn ensureTotalCapacityContext(self: *Self, allocator: Allocator, new_size: Size, ctx: Context) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.Custom.ensureUnusedCapacity
函数
pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_size: Size) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.Custom.ensureUnusedCapacityContext
函数
pub fn ensureUnusedCapacityContext(self: *Self, allocator: Allocator, additional_size: Size, ctx: Context) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.Custom.Entry
容器
字段
key_ptr: *K
value_ptr: *V
std.hash_map.Custom.fetchPut
函数
将新 Entry 插入哈希映射,并返回之前的条目(如果存在)。
pub fn fetchPut(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!?KV
参数
错误
- OutOfMemory
std.hash_map.Custom.fetchPutAssumeCapacity
函数
向哈希表插入新的 Entry,若存在旧条目则返回旧条目。
若执行插入,断言容量足够且不分配内存。
pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV
参数
std.hash_map.Custom.fetchPutAssumeCapacityContext
函数
pub fn fetchPutAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) ?KV
参数
std.hash_map.Custom.fetchPutContext
函数
pub fn fetchPutContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!?KV
参数
错误
- OutOfMemory
std.hash_map.Custom.fetchRemove
函数
若存在键匹配的 Entry,则从
哈希映射中删除,并由此函数返回。
pub fn fetchRemove(self: *Self, key: K) ?KV
参数
self: *Self
key: K
std.hash_map.Custom.fetchRemoveAdapted
函数
pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV
参数
self: *Self
std.hash_map.Custom.fetchRemoveContext
函数
pub fn fetchRemoveContext(self: *Self, key: K, ctx: Context) ?KV
参数
std.hash_map.Custom.FieldIterator
类型函数
fn FieldIterator(comptime T: type) type
参数
T: type
字段
std.hash_map.Custom.FieldIterator.next
函数
pub fn next(self: *@This()) ?*T
参数
self: *@This()
std.hash_map.Custom.get
函数
若键存在,则获取与其关联的值的副本。
pub fn get(self: Self, key: K) ?V
参数
self: Self
key: K
std.hash_map.Custom.getAdapted
函数
pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V
参数
self: Self
std.hash_map.Custom.getContext
函数
pub fn getContext(self: Self, key: K, ctx: Context) ?V
参数
std.hash_map.Custom.getEntry
函数
pub fn getEntry(self: Self, key: K) ?Entry
参数
self: Self
key: K
std.hash_map.Custom.getEntryAdapted
函数
pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry
参数
self: Self
std.hash_map.Custom.getEntryContext
函数
pub fn getEntryContext(self: Self, key: K, ctx: Context) ?Entry
参数
std.hash_map.Custom.getIndex
函数
查找包含给定键对应数据的索引。
fn getIndex(self: Self, key: anytype, ctx: anytype) ?usize
参数
self: Self
std.hash_map.Custom.getKey
函数
若存在,获取与适配键对应的实际键的副本。
pub fn getKey(self: Self, key: K) ?K
参数
self: Self
key: K
std.hash_map.Custom.getKeyAdapted
函数
pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K
参数
self: Self
std.hash_map.Custom.getKeyContext
函数
pub fn getKeyContext(self: Self, key: K, ctx: Context) ?K
参数
std.hash_map.Custom.getKeyPtr
函数
若存在与适配键关联的实际键,获取指向该键的可选指针。
pub fn getKeyPtr(self: Self, key: K) ?*K
参数
self: Self
key: K
std.hash_map.Custom.getKeyPtrAdapted
函数
pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K
参数
self: Self
std.hash_map.Custom.getKeyPtrContext
函数
pub fn getKeyPtrContext(self: Self, key: K, ctx: Context) ?*K
参数
std.hash_map.Custom.getOrPut
函数
pub fn getOrPut(self: *Self, allocator: Allocator, key: K) Allocator.Error!GetOrPutResult
参数
错误
- OutOfMemory
std.hash_map.Custom.getOrPutAdapted
函数
pub fn getOrPutAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype) Allocator.Error!GetOrPutResult
参数
错误
- OutOfMemory
std.hash_map.Custom.getOrPutAssumeCapacity
函数
pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult
参数
self: *Self
key: K
std.hash_map.Custom.getOrPutAssumeCapacityAdapted
函数
pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult
参数
self: *Self
std.hash_map.Custom.getOrPutAssumeCapacityContext
函数
pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult
参数
std.hash_map.Custom.getOrPutContext
函数
pub fn getOrPutContext(self: *Self, allocator: Allocator, key: K, ctx: Context) Allocator.Error!GetOrPutResult
参数
错误
- OutOfMemory
std.hash_map.Custom.getOrPutContextAdapted
函数
pub fn getOrPutContextAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Allocator.Error!GetOrPutResult
参数
错误
- OutOfMemory
std.hash_map.Custom.GetOrPutResult
容器
字段
key_ptr: *K
value_ptr: *V
found_existing: bool
std.hash_map.Custom.getOrPutValue
函数
pub fn getOrPutValue(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!Entry
参数
错误
- OutOfMemory
std.hash_map.Custom.getOrPutValueContext
函数
pub fn getOrPutValueContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!Entry
参数
错误
- OutOfMemory
std.hash_map.Custom.getPtr
函数
若存在与键关联的值,则获取指向它的可选指针。
pub fn getPtr(self: Self, key: K) ?*V
参数
self: Self
key: K
std.hash_map.Custom.getPtrAdapted
函数
pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V
参数
self: Self
std.hash_map.Custom.getPtrContext
函数
pub fn getPtrContext(self: Self, key: K, ctx: Context) ?*V
参数
std.hash_map.Custom.grow
函数
fn grow(self: *Self, allocator: Allocator, new_capacity: Size, ctx: Context) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.Custom.growIfNeeded
函数
fn growIfNeeded(self: *Self, allocator: Allocator, new_count: Size, ctx: Context) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.Custom.Hash
类型
std.hash_map.Custom.header
函数
fn header(self: Self) *Header
参数
self: Self
std.hash_map.Custom.Header
容器
字段
std.hash_map.Custom.initMetadatas
函数
fn initMetadatas(self: *Self) void
参数
self: *Self
std.hash_map.Custom.isUnderMaxLoadPercentage
函数
fn isUnderMaxLoadPercentage(size: Size, cap: Size) bool
参数
std.hash_map.Custom.iterator
函数
pub fn iterator(self: *const Self) Iterator
参数
self: *const Self
std.hash_map.Custom.Iterator
容器
字段
std.hash_map.Custom.Iterator.next
函数
pub fn next(it: *Iterator) ?Entry
参数
it: *Iterator
std.hash_map.Custom.keyIterator
函数
pub fn keyIterator(self: Self) KeyIterator
参数
self: Self
std.hash_map.Custom.KeyIterator
类型
std.hash_map.Custom.keys
函数
fn keys(self: Self) [*]K
参数
self: Self
std.hash_map.Custom.KV
容器
字段
key: K
value: V
std.hash_map.Custom.load
函数
fn load(self: Self) Size
参数
self: Self
std.hash_map.Custom.lockPointers
函数
将哈希映射置于特殊状态:任何会使现有键或值指针失效的方法调用,都改为触发断言。
lockPointers 可以多次调用,使多个独立使用者能同时保持哈希映射锁定。
unlockPointers 在调用次数与 lockPointers 相同时,将哈希映射恢复为原先状态。
pub fn lockPointers(self: *Self) void
参数
self: *Self
std.hash_map.Custom.Managed
类型
std.hash_map.Custom.Metadata
容器
槽位的元数据,有空闲、已使用和
墓碑三种状态。墓碑表示条目曾经被使用过,
是处理删除操作的一种简单方式。
除状态外,还保存槽位键的哈希值中的 7 位。
利用这几位可以快速区分条目,
不必调用相等性比较函数。如果两个指纹
不同,就完全不必比较键。
这 7 位取自 64 位哈希值的最高位。因此,
除了用哈希值的最低 log2(capacity) 位确定
槽位索引外,还额外利用 7 位快速消解
哈希值不同的多个元素竞争同一槽位时的冲突。
不调用相等性比较函数意味着无需读取
条目数组,从而可能避免缓存未命中和
开销较大的函数调用。
字段
fingerprint: FingerPrint = free
used: u1 = 0
std.hash_map.Custom.Metadata.fill
函数
pub fn fill(self: *Metadata, fp: FingerPrint) void
参数
self: *Metadata
fp: FingerPrint
std.hash_map.Custom.Metadata.FingerPrint
类型
std.hash_map.Custom.Metadata.free
常量
FingerPrint
std.hash_map.Custom.Metadata.isFree
函数
pub fn isFree(self: Metadata) bool
参数
self: Metadata
std.hash_map.Custom.Metadata.isTombstone
函数
pub fn isTombstone(self: Metadata) bool
参数
self: Metadata
std.hash_map.Custom.Metadata.isUsed
函数
pub fn isUsed(self: Metadata) bool
参数
self: Metadata
std.hash_map.Custom.Metadata.remove
函数
pub fn remove(self: *Metadata) void
参数
self: *Metadata
std.hash_map.Custom.Metadata.slot_free
常量
u8
std.hash_map.Custom.Metadata.slot_tombstone
常量
u8
std.hash_map.Custom.Metadata.takeFingerprint
函数
pub fn takeFingerprint(hash: Hash) FingerPrint
参数
hash: Hash
std.hash_map.Custom.Metadata.tombstone
常量
FingerPrint
std.hash_map.Custom.minimal_capacity
常量
哈希映射引导初始化时首次扩容的容量。
std.hash_map.Custom.move
函数
将映射置为空状态,使反初始化变为空操作, 并返回原映射的副本。
pub fn move(self: *Self) Self
参数
self: *Self
std.hash_map.Custom.promote
函数
pub fn promote(self: Self, allocator: Allocator) Managed
参数
std.hash_map.Custom.promoteContext
函数
pub fn promoteContext(self: Self, allocator: Allocator, ctx: Context) Managed
参数
std.hash_map.Custom.put
函数
如果关联键尚不存在,则插入条目;否则更新现有值。
pub fn put(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.Custom.putAssumeCapacity
函数
断言容量足以存储新键值对。
覆盖任何已有数据。要检测插入是否会覆盖
已有数据,请参见 getOrPutAssumeCapacity。
pub fn putAssumeCapacity(self: *Self, key: K, value: V) void
参数
std.hash_map.Custom.putAssumeCapacityContext
函数
pub fn putAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) void
参数
std.hash_map.Custom.putAssumeCapacityNoClobber
函数
向映射插入条目。假定条目尚不存在, 且无需分配内存。
pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void
参数
std.hash_map.Custom.putAssumeCapacityNoClobberContext
函数
pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void
参数
std.hash_map.Custom.putContext
函数
pub fn putContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.Custom.putNoClobber
函数
将条目插入映射。假定该条目尚不存在。
pub fn putNoClobber(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.Custom.putNoClobberContext
函数
pub fn putNoClobberContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.Custom.rehash
函数
原地重新哈希映射。
由于当前使用基于墓碑的实现, 长期使用后,HashMap 可能因墓碑条目 不断积累而产生碎片,过量探测 导致性能下降。可能触发此情况的模式是 长时间存在且反复插入、删除的 HashMap。
调用此函数后,HashMap 中不再存在墓碑, 所有条目均重新哈希,且任何已有的 指向 HashMap 内键或值的指针均失效。
pub fn rehash(self: *Self, ctx: anytype) void
参数
self: *Self
std.hash_map.Custom.remove
函数
如果哈希映射中存在键匹配的 Entry,则将其删除
并返回 true。否则
返回 false。
TODO: 回答此文档注释中的问题,删除该条目后未使用容量是否会增加一?
pub fn remove(self: *Self, key: K) bool
参数
self: *Self
key: K
std.hash_map.Custom.removeAdapted
函数
TODO: 回答这些文档注释中的问题:这是否 使未使用容量增加了一个?
pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool
参数
self: *Self
std.hash_map.Custom.removeByIndex
函数
fn removeByIndex(self: *Self, idx: usize) void
参数
self: *Self
idx: usize
std.hash_map.Custom.removeByPtr
函数
从哈希映射中删除键由 key_ptr 指向的条目。 假定 key_ptr 是指向哈希映射中 已有键的有效指针。
TODO: 回答这些文档注释中的问题:这是否 使未使用容量增加了一个?
pub fn removeByPtr(self: *Self, key_ptr: *const K) void
参数
self: *Self
key_ptr: *const K
std.hash_map.Custom.removeContext
函数
TODO: 回答这些文档注释中的问题:这是否 使未使用容量增加了一个?
pub fn removeContext(self: *Self, key: K, ctx: Context) bool
参数
std.hash_map.Custom.Self
别名
别名目标 std.hash_map.Custom
std.hash_map.Custom.Size
类型
std.hash_map.Custom.unlockPointers
函数
撤销一次 lockPointers 调用。
pub fn unlockPointers(self: *Self) void
参数
self: *Self
std.hash_map.Custom.valueIterator
函数
pub fn valueIterator(self: Self) ValueIterator
参数
self: Self
std.hash_map.Custom.ValueIterator
类型
std.hash_map.Custom.values
函数
fn values(self: Self) [*]V
参数
self: Self
std.hash_map.default_max_load_percentage
常量
std.hash_map.eql
函数
fn eql(self: @This(), adapted_key: []const u8, test_key: u64) bool
参数
self: @This()
adapted_key: []const u8
test_key: u64
std.hash_map.eqlString
函数
pub fn eqlString(a: []const u8, b: []const u8) bool
参数
a: []const u8
b: []const u8
std.hash_map.expect
别名
别名目标 std.testing.expect
std.hash_map.expectEqual
别名
std.hash_map.getAutoEqlFn
函数
pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool)
参数
K: type
Context: type
std.hash_map.getAutoEqlFn.eql
函数
fn eql(ctx: Context, a: K, b: K) bool
参数
ctx: Context
a: K
b: K
std.hash_map.getAutoHashFn
函数
pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u64)
参数
K: type
Context: type
std.hash_map.getAutoHashFn.hash
函数
fn hash(ctx: Context, key: K) u64
参数
ctx: Context
key: K
std.hash_map.hash
函数
fn hash(self: @This(), adapted_key: []const u8) u64
参数
self: @This()
adapted_key: []const u8
std.hash_map.HashMap
类型函数
通用哈希表。
不保证顺序,任何修改都会使现有迭代器失效。
它在较高负载因子下(默认最高 80%)仍能提供快速的查找、插入和删除操作,从而降低内存占用。
不存储 Allocator 字段、可直接初始化的哈希映射见 HashMapUnmanaged。
如果遍历表条目是重要用例且要求高性能,优先使用 std.ArrayHashMap。
上下文必须是具有以下两个成员函数的结构体类型:
hash(self, K) u64
eql(self, K, K) bool
许多函数还提供适配版本。这些版本接受伪键而非键,其上下文必须具有以下函数:
hash(self, PseudoKey) u64
eql(self, PseudoKey, K) bool
pub fn HashMap( comptime K: type, comptime V: type, comptime Context: type, comptime max_load_percentage: u64, ) type
参数
K: type
V: type
Context: type
max_load_percentage: u64
字段
UnmanagedEntryKVHashIteratorKeyIteratorValueIteratorSizeGetOrPutResultSelfinitinitContextlockPointersunlockPointersdeinitclearRetainingCapacityclearAndFreecountiteratorkeyIteratorvalueIteratorgetOrPutgetOrPutAdaptedgetOrPutAssumeCapacitygetOrPutAssumeCapacityAdaptedgetOrPutValueensureTotalCapacityensureUnusedCapacitycapacityputputNoClobberputAssumeCapacityputAssumeCapacityNoClobberfetchPutfetchPutAssumeCapacityfetchRemovefetchRemoveAdaptedgetgetAdaptedgetPtrgetPtrAdaptedgetKeygetKeyAdaptedgetKeyPtrgetKeyPtrAdaptedgetEntrygetEntryAdaptedcontainscontainsAdaptedremoveremoveAdaptedremoveByPtrclonecloneWithAllocatorcloneWithContextcloneWithAllocatorAndContextmoverehash
std.hash_map.HashMap.capacity
函数
返回元素总数上限;超过此值后,就不再保证不会发生分配。
pub fn capacity(self: Self) Size
参数
self: Self
std.hash_map.HashMap.clearAndFree
函数
清空映射并释放底层分配。 这不会释放键或值!若它们需要反初始化, 务必先释放它们,再 调用此函数。
pub fn clearAndFree(self: *Self) void
参数
self: *Self
std.hash_map.HashMap.clearRetainingCapacity
函数
清空映射,但保留底层分配以供后续使用。 不会释放键或值!若它们需要反初始化, 务必在调用此函数之前 释放它们。
pub fn clearRetainingCapacity(self: *Self) void
参数
self: *Self
std.hash_map.HashMap.clone
函数
使用同一分配器创建此映射的副本
pub fn clone(self: Self) Allocator.Error!Self
参数
self: Self
错误
- OutOfMemory
std.hash_map.HashMap.cloneWithAllocator
函数
使用指定分配器创建此映射的副本
pub fn cloneWithAllocator(self: Self, new_allocator: Allocator) Allocator.Error!Self
参数
错误
- OutOfMemory
std.hash_map.HashMap.cloneWithAllocatorAndContext
函数
使用指定分配器及上下文创建此映射的副本。
pub fn cloneWithAllocatorAndContext( self: Self, new_allocator: Allocator, new_ctx: anytype, ) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage)
参数
错误
- OutOfMemory
std.hash_map.HashMap.cloneWithContext
函数
使用指定上下文创建此映射的副本。
pub fn cloneWithContext(self: Self, new_ctx: anytype) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage)
参数
self: Self
错误
- OutOfMemory
std.hash_map.HashMap.contains
函数
检查映射是否包含某个键
pub fn contains(self: Self, key: K) bool
参数
self: Self
key: K
std.hash_map.HashMap.containsAdapted
函数
pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool
参数
self: Self
std.hash_map.HashMap.count
函数
返回映射中的元素数。
pub fn count(self: Self) Size
参数
self: Self
std.hash_map.HashMap.deinit
函数
释放底层数组,并使此映射失效。 不会对键、值或上下文执行 deinit! 若键或值需要释放,必须确保 在调用此函数前完成释放。
pub fn deinit(self: *Self) void
参数
self: *Self
std.hash_map.HashMap.ensureTotalCapacity
函数
增加容量,保证在达到
expected_count 之前的插入不会分配内存,因此不会失败。
pub fn ensureTotalCapacity(self: *Self, expected_count: Size) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.HashMap.ensureUnusedCapacity
函数
增加容量,保证再插入最多 additional_count 个项目都不会触发分配,因此不会失败。
pub fn ensureUnusedCapacity(self: *Self, additional_count: Size) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.HashMap.Entry
常量
条目,包含指向映射中存储的键和值的指针。
std.hash_map.HashMap.fetchPut
函数
将新 Entry 插入哈希映射,并返回之前的条目(如果存在)。
pub fn fetchPut(self: *Self, key: K, value: V) Allocator.Error!?KV
参数
错误
- OutOfMemory
std.hash_map.HashMap.fetchPutAssumeCapacity
函数
向哈希表插入新的 Entry,若存在旧条目则返回旧条目。
若执行插入,断言容量足够且不分配内存。
pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV
参数
std.hash_map.HashMap.fetchRemove
函数
从映射中移除一个值,并返回被移除的键值对。
pub fn fetchRemove(self: *Self, key: K) ?KV
参数
self: *Self
key: K
std.hash_map.HashMap.fetchRemoveAdapted
函数
pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV
参数
self: *Self
std.hash_map.HashMap.get
函数
在映射中查找与某键关联的值
pub fn get(self: Self, key: K) ?V
参数
self: Self
key: K
std.hash_map.HashMap.getAdapted
函数
pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V
参数
self: Self
std.hash_map.HashMap.getEntry
函数
在映射中查找与某键关联的键和值
pub fn getEntry(self: Self, key: K) ?Entry
参数
self: Self
key: K
std.hash_map.HashMap.getEntryAdapted
函数
pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry
参数
self: Self
std.hash_map.HashMap.getKey
函数
查找映射中与适配键对应的实际键
pub fn getKey(self: Self, key: K) ?K
参数
self: Self
key: K
std.hash_map.HashMap.getKeyAdapted
函数
pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K
参数
self: Self
std.hash_map.HashMap.getKeyPtr
函数
pub fn getKeyPtr(self: Self, key: K) ?*K
参数
self: Self
key: K
std.hash_map.HashMap.getKeyPtrAdapted
函数
pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K
参数
self: Self
std.hash_map.HashMap.getOrPut
函数
如果键已存在,此函数不可能失败。
如果已有键为 key 的元素,则结果中的
Entry 指针指向该元素,且 found_existing 为 true。
否则,插入值未定义的新元素,
Entry 指针指向该元素。调用方随后应初始化
值,但不初始化键。
pub fn getOrPut(self: *Self, key: K) Allocator.Error!GetOrPutResult
参数
self: *Self
key: K
错误
- OutOfMemory
std.hash_map.HashMap.getOrPutAdapted
函数
若键已存在,此函数不会失败。
若已存在键为 key 的元素,结果中的 Entry 指针指向它,且 found_existing 为 true。
否则插入键和值均为 undefined 的新元素,Entry 指针指向它。随后调用者必须初始化键和值。
pub fn getOrPutAdapted(self: *Self, key: anytype, ctx: anytype) Allocator.Error!GetOrPutResult
参数
self: *Self
错误
- OutOfMemory
std.hash_map.HashMap.getOrPutAssumeCapacity
函数
若已存在 key 对应的项目,结果的
Entry 指针指向该项目,found_existing 为 true。
否则,插入值为 undefined 的新项目,
Entry 指针指向新项目。调用方应随后初始化
其值,但不初始化键。
若需要保存新条目,此函数断言
已有足够容量。
pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult
参数
self: *Self
key: K
std.hash_map.HashMap.getOrPutAssumeCapacityAdapted
函数
如果已存在具有 key 的条目,则结果中的
Entry 指针指向该条目,found_existing 为 true。
否则插入一个值未定义的新条目,
Entry 指针指向该条目。随后调用方必须初始化
键和值。
如果需要存储新条目,此函数断言
容量足以容纳它。
pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult
参数
self: *Self
std.hash_map.HashMap.GetOrPutResult
常量
getOrPut 及其变体返回的类型
std.hash_map.HashMap.getOrPutValue
函数
pub fn getOrPutValue(self: *Self, key: K, value: V) Allocator.Error!Entry
参数
错误
- OutOfMemory
std.hash_map.HashMap.getPtr
函数
pub fn getPtr(self: Self, key: K) ?*V
参数
self: Self
key: K
std.hash_map.HashMap.getPtrAdapted
函数
pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V
参数
self: Self
std.hash_map.HashMap.Hash
常量
哈希计算结果使用的整数类型
std.hash_map.HashMap.init
函数
使用空上下文创建托管哈希映射。 若上下文大小非零,则必须改用 initContext(allocator, ctx)。
pub fn init(allocator: Allocator) Self
参数
allocator: Allocator
std.hash_map.HashMap.initContext
函数
使用上下文创建带内存管理的哈希映射
pub fn initContext(allocator: Allocator, ctx: Context) Self
参数
allocator: Allocator
ctx: Context
std.hash_map.HashMap.iterator
函数
创建遍历映射条目的迭代器。 修改映射会使迭代器失效。
pub fn iterator(self: *const Self) Iterator
参数
self: *const Self
std.hash_map.HashMap.Iterator
常量
iterator() 返回的迭代器类型
std.hash_map.HashMap.keyIterator
函数
创建遍历映射中键的迭代器。 修改映射会使迭代器失效。
pub fn keyIterator(self: Self) KeyIterator
参数
self: Self
std.hash_map.HashMap.KeyIterator
常量
std.hash_map.HashMap.KV
常量
已从映射中移除的键和值的副本。
std.hash_map.HashMap.lockPointers
函数
将哈希映射置于特殊状态:任何会使现有键或值指针失效的方法调用,都改为触发断言。
lockPointers 可以多次调用,使多个独立使用者能同时保持哈希映射锁定。
unlockPointers 在调用次数与 lockPointers 相同时,将哈希映射恢复为原先状态。
pub fn lockPointers(self: *Self) void
参数
self: *Self
std.hash_map.HashMap.move
函数
将映射置为空状态,使反初始化变为空操作, 并返回原映射的副本。
pub fn move(self: *Self) Self
参数
self: *Self
std.hash_map.HashMap.put
函数
覆盖任何已有数据。要检测 put 是否会覆盖
已有数据,请参见 getOrPut。
pub fn put(self: *Self, key: K, value: V) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.HashMap.putAssumeCapacity
函数
断言容量足以存储新键值对。
覆盖任何已有数据。要检测插入是否会覆盖
已有数据,请参见 getOrPutAssumeCapacity。
pub fn putAssumeCapacity(self: *Self, key: K, value: V) void
参数
std.hash_map.HashMap.putAssumeCapacityNoClobber
函数
断言容量足以存储新的键值对。
断言不会覆盖任何现有数据。
若要检测 put 是否会覆盖现有数据,参见 getOrPutAssumeCapacity。
pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void
参数
std.hash_map.HashMap.putNoClobber
函数
向哈希映射插入键值对,断言映射中 不存在键相同的条目。
pub fn putNoClobber(self: *Self, key: K, value: V) Allocator.Error!void
参数
错误
- OutOfMemory
std.hash_map.HashMap.rehash
函数
原地重新哈希映射。
由于当前使用基于墓碑的实现, 长期使用后,HashMap 可能因墓碑条目 不断积累而产生碎片,过量探测 导致性能下降。可能触发此情况的模式是 长时间存在且反复插入、删除的 HashMap。
调用此函数后,HashMap 中不再存在墓碑, 所有条目均重新哈希,且任何已有的 指向 HashMap 内键或值的指针均失效。
pub fn rehash(self: *Self) void
参数
self: *Self
std.hash_map.HashMap.remove
函数
如果哈希映射中存在键匹配的 Entry,则将其删除
并返回 true。否则
返回 false。
TODO: 回答此文档注释中的问题,删除该条目后未使用容量是否会增加一?
pub fn remove(self: *Self, key: K) bool
参数
self: *Self
key: K
std.hash_map.HashMap.removeAdapted
函数
TODO: 回答这些文档注释中的问题:这是否 使未使用容量增加了一个?
pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool
参数
self: *Self
std.hash_map.HashMap.removeByPtr
函数
从哈希映射中删除键由 key_ptr 指向的条目。 假定 key_ptr 是指向哈希映射中 已有键的有效指针。
TODO: 回答这些文档注释中的问题:这是否 使未使用容量增加了一个?
pub fn removeByPtr(self: *Self, key_ptr: *const K) void
参数
self: *Self
key_ptr: *const K
std.hash_map.HashMap.Self
别名
别名目标 std.hash_map.HashMap
std.hash_map.HashMap.Size
常量
用于存储映射大小的整数类型。
std.hash_map.HashMap.unlockPointers
函数
撤销一次 lockPointers 调用。
pub fn unlockPointers(self: *Self) void
参数
self: *Self
std.hash_map.HashMap.Unmanaged
类型
此封装底层的非托管哈希映射类型。
std.hash_map.HashMap.valueIterator
函数
创建遍历映射值的迭代器。 修改映射会使迭代器失效。
pub fn valueIterator(self: Self) ValueIterator
参数
self: Self
std.hash_map.HashMap.ValueIterator
常量
std.hash_map.HashMapUnmanaged
别名
采用开放寻址和线性探测的 HashMap。 一次查找或修改通常仅产生 2 次缓存未命中。 不保证顺序,任何修改都会使活动迭代器失效。 它在相当高的负载因子下仍具有良好性能,默认 填充率达 80% 时扩容,每个元素仅有一个字节的额外开销。 结构体本身仅占 16 字节,内存占用小。代价是 使用 u32 处理大小;对于几乎所有用途, 这应当足够合理。 删除通过墓碑标记实现。
已弃用此结构体的默认初始化;请改用 .empty。
别名目标 std.hash_map.Custom
std.hash_map.hashString
函数
pub fn hashString(s: []const u8) u64
参数
s: []const u8
std.hash_map.math
别名
别名目标 std.math
std.hash_map.mem
别名
别名目标 std.mem
std.hash_map.std
别名
别名目标 std
std.hash_map.StringContext
命名空间
std.hash_map.StringContext.eql
函数
pub fn eql(self: @This(), a: []const u8, b: []const u8) bool
参数
self: @This()
a: []const u8
b: []const u8
std.hash_map.StringContext.hash
函数
pub fn hash(self: @This(), s: []const u8) u64
参数
self: @This()
s: []const u8
std.hash_map.StringHashMap
类型函数
以字符串为键的内置哈希映射。 键的内存由调用方管理。键和值 不会自动释放。
pub fn StringHashMap(comptime V: type) type
参数
V: type
字段
UnmanagedEntryKVHashIteratorKeyIteratorValueIteratorSizeGetOrPutResultSelfinitinitContextlockPointersunlockPointersdeinitclearRetainingCapacityclearAndFreecountiteratorkeyIteratorvalueIteratorgetOrPutgetOrPutAdaptedgetOrPutAssumeCapacitygetOrPutAssumeCapacityAdaptedgetOrPutValueensureTotalCapacityensureUnusedCapacitycapacityputputNoClobberputAssumeCapacityputAssumeCapacityNoClobberfetchPutfetchPutAssumeCapacityfetchRemovefetchRemoveAdaptedgetgetAdaptedgetPtrgetPtrAdaptedgetKeygetKeyAdaptedgetKeyPtrgetKeyPtrAdaptedgetEntrygetEntryAdaptedcontainscontainsAdaptedremoveremoveAdaptedremoveByPtrclonecloneWithAllocatorcloneWithContextcloneWithAllocatorAndContextmoverehash
std.hash_map.StringHashMapUnmanaged
类型函数
键内存由调用方管理。 键和值均不会自动释放。
pub fn StringHashMapUnmanaged(comptime V: type) type
参数
V: type
std.hash_map.StringIndexAdapter
容器
字段
std.hash_map.StringIndexAdapter.eql
函数
pub fn eql(ctx: @This(), a: []const u8, b: u32) bool
参数
ctx: @This()
a: []const u8
b: u32
std.hash_map.StringIndexAdapter.hash
函数
pub fn hash(_: @This(), adapted_key: []const u8) u64
参数
_: @This()
adapted_key: []const u8
std.hash_map.StringIndexContext
容器
字段
std.hash_map.StringIndexContext.eql
函数
pub fn eql(_: @This(), a: u32, b: u32) bool
参数
_: @This()
a: u32
b: u32
std.hash_map.StringIndexContext.hash
函数
pub fn hash(ctx: @This(), key: u32) u64
参数
ctx: @This()
key: u32
std.hash_map.testing
别名
别名目标 std.testing
std.hash_map.Wyhash
别名
别名目标 std.hash.Wyhash
源码
std/hash_map.zig
const std = @import("std.zig");
const builtin = @import("builtin");
const assert = std.debug.assert;
const autoHash = std.hash.autoHash;
const math = std.math;
const mem = std.mem;
const Allocator = mem.Allocator;
const Wyhash = std.hash.Wyhash;
const Alignment = std.mem.Alignment;
pub fn getAutoHashFn(comptime K: type, comptime Context: type) (fn (Context, K) u64) {
comptime {
assert(@hasDecl(std, "StringHashMap")); // 检测何时需要更新下面的消息
if (K == []const u8) {
@compileError("std.hash.autoHash does not allow slices here (" ++
@typeName(K) ++
") because the intent is unclear. " ++
"Consider using std.StringHashMap for hashing the contents of []const u8. " ++
"Alternatively, consider using std.hash.autoHashStrat or providing your own hash function instead.");
}
}
return struct {
fn hash(ctx: Context, key: K) u64 {
_ = ctx;
if (std.meta.hasUniqueRepresentation(K)) {
return Wyhash.hash(0, std.mem.asBytes(&key));
} else {
var hasher = Wyhash.init(0);
autoHash(&hasher, key);
return hasher.final();
}
}
}.hash;
}
pub fn getAutoEqlFn(comptime K: type, comptime Context: type) (fn (Context, K, K) bool) {
return struct {
fn eql(ctx: Context, a: K, b: K) bool {
_ = ctx;
return std.meta.eql(a, b);
}
}.eql;
}
pub fn AutoHashMap(comptime K: type, comptime V: type) type {
return HashMap(K, V, AutoContext(K), default_max_load_percentage);
}
pub fn AutoHashMapUnmanaged(comptime K: type, comptime V: type) type {
return HashMapUnmanaged(K, V, AutoContext(K), default_max_load_percentage);
}
pub fn AutoContext(comptime K: type) type {
return struct {
pub const hash = getAutoHashFn(K, @This());
pub const eql = getAutoEqlFn(K, @This());
};
}
/// 以字符串为键的内置哈希映射。
/// 键的内存由调用方管理。键和值
/// 不会自动释放。
pub fn StringHashMap(comptime V: type) type {
return HashMap([]const u8, V, StringContext, default_max_load_percentage);
}
/// 键内存由调用方管理。
/// 键和值均不会自动释放。
pub fn StringHashMapUnmanaged(comptime V: type) type {
return HashMapUnmanaged([]const u8, V, StringContext, default_max_load_percentage);
}
pub const StringContext = struct {
pub fn hash(self: @This(), s: []const u8) u64 {
_ = self;
return hashString(s);
}
pub fn eql(self: @This(), a: []const u8, b: []const u8) bool {
_ = self;
return eqlString(a, b);
}
};
pub fn eqlString(a: []const u8, b: []const u8) bool {
return mem.eql(u8, a, b);
}
pub fn hashString(s: []const u8) u64 {
return std.hash.Wyhash.hash(0, s);
}
pub const StringIndexContext = struct {
bytes: *const std.ArrayList(u8),
pub fn eql(_: @This(), a: u32, b: u32) bool {
return a == b;
}
pub fn hash(ctx: @This(), key: u32) u64 {
return hashString(mem.sliceTo(ctx.bytes.items[key..], 0));
}
};
pub const StringIndexAdapter = struct {
bytes: *const std.ArrayList(u8),
pub fn eql(ctx: @This(), a: []const u8, b: u32) bool {
return mem.eql(u8, a, mem.sliceTo(ctx.bytes.items[b..], 0));
}
pub fn hash(_: @This(), adapted_key: []const u8) u64 {
assert(mem.findScalar(u8, adapted_key, 0) == null);
return hashString(adapted_key);
}
};
pub const default_max_load_percentage = 80;
/// 通用哈希表。
/// 不保证顺序,任何修改都会使现有迭代器失效。
/// 它在较高负载因子下(默认最高 80%)仍能提供快速的查找、插入和删除操作,从而降低内存占用。
/// 不存储 Allocator 字段、可直接初始化的哈希映射见 `HashMapUnmanaged`。
/// 如果遍历表条目是重要用例且要求高性能,优先使用 `std.ArrayHashMap`。
/// 上下文必须是具有以下两个成员函数的结构体类型:
/// hash(self, K) u64
/// eql(self, K, K) bool
/// 许多函数还提供适配版本。这些版本接受伪键而非键,其上下文必须具有以下函数:
/// hash(self, PseudoKey) u64
/// eql(self, PseudoKey, K) bool
///
///
///
///
pub fn HashMap(
comptime K: type,
comptime V: type,
comptime Context: type,
comptime max_load_percentage: u64,
) type {
return struct {
unmanaged: Unmanaged,
allocator: Allocator,
ctx: Context,
/// 此封装底层的非托管哈希映射类型。
pub const Unmanaged = HashMapUnmanaged(K, V, Context, max_load_percentage);
/// 条目,包含指向映射中存储的键和值的指针。
pub const Entry = Unmanaged.Entry;
/// 已从映射中移除的键和值的副本。
pub const KV = Unmanaged.KV;
/// 哈希计算结果使用的整数类型
pub const Hash = Unmanaged.Hash;
/// iterator() 返回的迭代器类型
pub const Iterator = Unmanaged.Iterator;
pub const KeyIterator = Unmanaged.KeyIterator;
pub const ValueIterator = Unmanaged.ValueIterator;
/// 用于存储映射大小的整数类型。
pub const Size = Unmanaged.Size;
/// getOrPut 及其变体返回的类型
pub const GetOrPutResult = Unmanaged.GetOrPutResult;
const Self = @This();
/// 使用空上下文创建托管哈希映射。
/// 若上下文大小非零,则必须改用 initContext(allocator, ctx)。
///
pub fn init(allocator: Allocator) Self {
if (@sizeOf(Context) != 0) {
@compileError("Context must be specified! Call initContext(allocator, ctx) instead.");
}
return .{
.unmanaged = .empty,
.allocator = allocator,
.ctx = undefined, // ctx 大小为零,因此这是安全的。
};
}
/// 使用上下文创建带内存管理的哈希映射
pub fn initContext(allocator: Allocator, ctx: Context) Self {
return .{
.unmanaged = .empty,
.allocator = allocator,
.ctx = ctx,
};
}
/// 将哈希映射置于特殊状态:任何会使现有键或值指针失效的方法调用,都改为触发断言。
///
/// `lockPointers` 可以多次调用,使多个独立使用者能同时保持哈希映射锁定。
///
/// `unlockPointers` 在调用次数与 `lockPointers` 相同时,将哈希映射恢复为原先状态。
///
///
///
///
pub fn lockPointers(self: *Self) void {
self.unmanaged.lockPointers();
}
/// 撤销一次 `lockPointers` 调用。
pub fn unlockPointers(self: *Self) void {
self.unmanaged.unlockPointers();
}
/// 释放底层数组,并使此映射失效。
/// 不会对键、值或上下文执行 deinit!
/// 若键或值需要释放,必须确保
/// 在调用此函数前完成释放。
pub fn deinit(self: *Self) void {
self.unmanaged.deinit(self.allocator);
self.* = undefined;
}
/// 清空映射,但保留底层分配以供后续使用。
/// 不会释放键或值!若它们需要反初始化,
/// 务必在调用此函数之前
/// 释放它们。
pub fn clearRetainingCapacity(self: *Self) void {
return self.unmanaged.clearRetainingCapacity();
}
/// 清空映射并释放底层分配。
/// 这*不会*释放键或值!若它们需要反初始化,
/// 务必先释放它们,再
/// 调用此函数。
pub fn clearAndFree(self: *Self) void {
return self.unmanaged.clearAndFree(self.allocator);
}
/// 返回映射中的元素数。
pub fn count(self: Self) Size {
return self.unmanaged.count();
}
/// 创建遍历映射条目的迭代器。
/// 修改映射会使迭代器失效。
pub fn iterator(self: *const Self) Iterator {
return self.unmanaged.iterator();
}
/// 创建遍历映射中键的迭代器。
/// 修改映射会使迭代器失效。
pub fn keyIterator(self: Self) KeyIterator {
return self.unmanaged.keyIterator();
}
/// 创建遍历映射值的迭代器。
/// 修改映射会使迭代器失效。
pub fn valueIterator(self: Self) ValueIterator {
return self.unmanaged.valueIterator();
}
/// 如果键已存在,此函数不可能失败。
/// 如果已有键为 `key` 的元素,则结果中的
/// `Entry` 指针指向该元素,且 found_existing 为 true。
/// 否则,插入值未定义的新元素,
/// `Entry` 指针指向该元素。调用方随后应初始化
/// 值,但不初始化键。
pub fn getOrPut(self: *Self, key: K) Allocator.Error!GetOrPutResult {
return self.unmanaged.getOrPutContext(self.allocator, key, self.ctx);
}
/// 若键已存在,此函数不会失败。
/// 若已存在键为 `key` 的元素,结果中的 `Entry` 指针指向它,且 found_existing 为 true。
/// 否则插入键和值均为 undefined 的新元素,`Entry` 指针指向它。随后调用者必须初始化键和值。
///
///
///
pub fn getOrPutAdapted(self: *Self, key: anytype, ctx: anytype) Allocator.Error!GetOrPutResult {
return self.unmanaged.getOrPutContextAdapted(self.allocator, key, ctx, self.ctx);
}
/// 若已存在 `key` 对应的项目,结果的
/// `Entry` 指针指向该项目,found_existing 为 true。
/// 否则,插入值为 undefined 的新项目,
/// `Entry` 指针指向新项目。调用方应随后初始化
/// 其值,但不初始化键。
/// 若需要保存新条目,此函数断言
/// 已有足够容量。
pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
return self.unmanaged.getOrPutAssumeCapacityContext(key, self.ctx);
}
/// 如果已存在具有 `key` 的条目,则结果中的
/// `Entry` 指针指向该条目,found_existing 为 true。
/// 否则插入一个值未定义的新条目,
/// `Entry` 指针指向该条目。随后调用方必须初始化
/// 键和值。
/// 如果需要存储新条目,此函数断言
/// 容量足以容纳它。
pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
return self.unmanaged.getOrPutAssumeCapacityAdapted(key, ctx);
}
pub fn getOrPutValue(self: *Self, key: K, value: V) Allocator.Error!Entry {
return self.unmanaged.getOrPutValueContext(self.allocator, key, value, self.ctx);
}
/// 增加容量,保证在达到
/// `expected_count` 之前的插入不会分配内存,因此不会失败。
pub fn ensureTotalCapacity(self: *Self, expected_count: Size) Allocator.Error!void {
return self.unmanaged.ensureTotalCapacityContext(self.allocator, expected_count, self.ctx);
}
/// 增加容量,保证再插入最多 `additional_count` 个项目都不会触发分配,因此不会失败。
///
///
pub fn ensureUnusedCapacity(self: *Self, additional_count: Size) Allocator.Error!void {
return self.unmanaged.ensureUnusedCapacityContext(self.allocator, additional_count, self.ctx);
}
/// 返回元素总数上限;超过此值后,就不再保证不会发生分配。
///
pub fn capacity(self: Self) Size {
return self.unmanaged.capacity();
}
/// 覆盖任何已有数据。要检测 put 是否会覆盖
/// 已有数据,请参见 `getOrPut`。
pub fn put(self: *Self, key: K, value: V) Allocator.Error!void {
return self.unmanaged.putContext(self.allocator, key, value, self.ctx);
}
/// 向哈希映射插入键值对,断言映射中
/// 不存在键相同的条目。
pub fn putNoClobber(self: *Self, key: K, value: V) Allocator.Error!void {
return self.unmanaged.putNoClobberContext(self.allocator, key, value, self.ctx);
}
/// 断言容量足以存储新键值对。
/// 覆盖任何已有数据。要检测插入是否会覆盖
/// 已有数据,请参见 `getOrPutAssumeCapacity`。
pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
return self.unmanaged.putAssumeCapacityContext(key, value, self.ctx);
}
/// 断言容量足以存储新的键值对。
/// 断言不会覆盖任何现有数据。
/// 若要检测 put 是否会覆盖现有数据,参见 `getOrPutAssumeCapacity`。
pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
return self.unmanaged.putAssumeCapacityNoClobberContext(key, value, self.ctx);
}
/// 将新 `Entry` 插入哈希映射,并返回之前的条目(如果存在)。
pub fn fetchPut(self: *Self, key: K, value: V) Allocator.Error!?KV {
return self.unmanaged.fetchPutContext(self.allocator, key, value, self.ctx);
}
/// 向哈希表插入新的 `Entry`,若存在旧条目则返回旧条目。
/// 若执行插入,断言容量足够且不分配内存。
pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
return self.unmanaged.fetchPutAssumeCapacityContext(key, value, self.ctx);
}
/// 从映射中移除一个值,并返回被移除的键值对。
pub fn fetchRemove(self: *Self, key: K) ?KV {
return self.unmanaged.fetchRemoveContext(key, self.ctx);
}
pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
return self.unmanaged.fetchRemoveAdapted(key, ctx);
}
/// 在映射中查找与某键关联的值
pub fn get(self: Self, key: K) ?V {
return self.unmanaged.getContext(key, self.ctx);
}
pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
return self.unmanaged.getAdapted(key, ctx);
}
pub fn getPtr(self: Self, key: K) ?*V {
return self.unmanaged.getPtrContext(key, self.ctx);
}
pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
return self.unmanaged.getPtrAdapted(key, ctx);
}
/// 查找映射中与适配键对应的实际键
pub fn getKey(self: Self, key: K) ?K {
return self.unmanaged.getKeyContext(key, self.ctx);
}
pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
return self.unmanaged.getKeyAdapted(key, ctx);
}
pub fn getKeyPtr(self: Self, key: K) ?*K {
return self.unmanaged.getKeyPtrContext(key, self.ctx);
}
pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
return self.unmanaged.getKeyPtrAdapted(key, ctx);
}
/// 在映射中查找与某键关联的键和值
pub fn getEntry(self: Self, key: K) ?Entry {
return self.unmanaged.getEntryContext(key, self.ctx);
}
pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
return self.unmanaged.getEntryAdapted(key, ctx);
}
/// 检查映射是否包含某个键
pub fn contains(self: Self, key: K) bool {
return self.unmanaged.containsContext(key, self.ctx);
}
pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
return self.unmanaged.containsAdapted(key, ctx);
}
/// 如果哈希映射中存在键匹配的 `Entry`,则将其删除
/// 并返回 true。否则
/// 返回 false。
///
/// TODO: 回答此文档注释中的问题,删除该条目后未使用容量是否会增加一?
///
pub fn remove(self: *Self, key: K) bool {
return self.unmanaged.removeContext(key, self.ctx);
}
/// TODO: 回答这些文档注释中的问题:这是否
/// 使未使用容量增加了一个?
pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
return self.unmanaged.removeAdapted(key, ctx);
}
/// 从哈希映射中删除键由 key_ptr 指向的条目。
/// 假定 key_ptr 是指向哈希映射中
/// 已有键的有效指针。
///
/// TODO: 回答这些文档注释中的问题:这是否
/// 使未使用容量增加了一个?
pub fn removeByPtr(self: *Self, key_ptr: *const K) void {
self.unmanaged.removeByPtr(key_ptr);
}
/// 使用同一分配器创建此映射的副本
pub fn clone(self: Self) Allocator.Error!Self {
var other = try self.unmanaged.cloneContext(self.allocator, self.ctx);
return other.promoteContext(self.allocator, self.ctx);
}
/// 使用指定分配器创建此映射的副本
pub fn cloneWithAllocator(self: Self, new_allocator: Allocator) Allocator.Error!Self {
var other = try self.unmanaged.cloneContext(new_allocator, self.ctx);
return other.promoteContext(new_allocator, self.ctx);
}
/// 使用指定上下文创建此映射的副本。
pub fn cloneWithContext(self: Self, new_ctx: anytype) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
var other = try self.unmanaged.cloneContext(self.allocator, new_ctx);
return other.promoteContext(self.allocator, new_ctx);
}
/// 使用指定分配器及上下文创建此映射的副本。
pub fn cloneWithAllocatorAndContext(
self: Self,
new_allocator: Allocator,
new_ctx: anytype,
) Allocator.Error!HashMap(K, V, @TypeOf(new_ctx), max_load_percentage) {
var other = try self.unmanaged.cloneContext(new_allocator, new_ctx);
return other.promoteContext(new_allocator, new_ctx);
}
/// 将映射置为空状态,使反初始化变为空操作,
/// 并返回原映射的副本。
pub fn move(self: *Self) Self {
self.unmanaged.pointer_stability.assertUnlocked();
const result = self.*;
self.unmanaged = .empty;
return result;
}
/// 原地重新哈希映射。
///
/// 由于当前使用基于墓碑的实现,
/// 长期使用后,HashMap 可能因墓碑条目
/// 不断积累而产生碎片,过量探测
/// 导致性能下降。可能触发此情况的模式是
/// 长时间存在且反复插入、删除的 HashMap。
///
/// 调用此函数后,HashMap 中不再存在墓碑,
/// 所有条目均重新哈希,且任何已有的
/// 指向 HashMap 内键或值的指针均失效。
pub fn rehash(self: *Self) void {
self.unmanaged.rehash(self.ctx);
}
};
}
/// 采用开放寻址和线性探测的 HashMap。
/// 一次查找或修改通常仅产生 2 次缓存未命中。
/// 不保证顺序,任何修改都会使活动迭代器失效。
/// 它在相当高的负载因子下仍具有良好性能,默认
/// 填充率达 80% 时扩容,每个元素仅有一个字节的额外开销。
/// 结构体本身仅占 16 字节,内存占用小。代价是
/// 使用 u32 处理大小;对于几乎所有用途,
/// 这应当足够合理。
/// 删除通过墓碑标记实现。
///
/// 已弃用此结构体的默认初始化;请改用 `.empty`。
pub const HashMapUnmanaged = Custom;
fn Custom(
comptime K: type,
comptime V: type,
comptime Context: type,
comptime max_load_percentage: u64,
) type {
if (max_load_percentage <= 0 or max_load_percentage >= 100)
@compileError("max_load_percentage must be between 0 and 100.");
return struct {
const Self = @This();
// 此指针实际上指向单个缓冲区的中间位置,缓冲区包含
// 一个 `Header` 字段、若干 `Metadata` 和 `Entry`。
// 偏移 `-@sizeOf(Header)` 处为 Header 字段。
// 偏移 `sizeOf(Metadata) * capacity + offset` 处,即
// self.header().entries 指向的位置,为条目数组。
// 这意味着哈希映射只持有一个活跃分配,
// 以减少内存碎片和结构体大小。
/// 指向元数据的指针。
metadata: ?[*]Metadata = null,
/// 哈希映射中当前的元素数。
size: Size = 0,
// 通过倒计时决定何时扩容,可减少判断哈希映射容量是否足够时执行的指令数。
//
/// 在为满足 `max_load_percentage` 而必须扩容之前,
/// 可用的槽位数量。
available: Size = 0,
/// 用于检测内存安全违规。
pointer_stability: std.debug.SafetyLock = .{},
// 这完全来自经验,并非某个特别巧妙的魔数。
/// 哈希映射引导初始化时首次扩容的容量。
const minimal_capacity = 8;
/// 不含任何键值的映射。
pub const empty: Self = .{
.metadata = null,
.size = 0,
.available = 0,
};
// 此哈希映射专为大小可由 u32 表示的情况设计。
pub const Size = u32;
// u64 哈希保证指纹位不会用于
// 计算槽位索引,从而充分利用熵。
pub const Hash = u64;
pub const Entry = struct {
key_ptr: *K,
value_ptr: *V,
};
pub const KV = struct {
key: K,
value: V,
};
const Header = struct {
values: [*]V,
keys: [*]K,
capacity: Size,
};
/// 槽位的元数据,有空闲、已使用和
/// 墓碑三种状态。墓碑表示条目曾经被使用过,
/// 是处理删除操作的一种简单方式。
/// 除状态外,还保存槽位键的哈希值中的 7 位。
/// 利用这几位可以快速区分条目,
/// 不必调用相等性比较函数。如果两个指纹
/// 不同,就完全不必比较键。
/// 这 7 位取自 64 位哈希值的最高位。因此,
/// 除了用哈希值的最低 `log2(capacity)` 位确定
/// 槽位索引外,还额外利用 7 位快速消解
/// 哈希值不同的多个元素竞争同一槽位时的冲突。
/// 不调用相等性比较函数意味着无需读取
/// 条目数组,从而可能避免缓存未命中和
/// 开销较大的函数调用。
const Metadata = packed struct {
const FingerPrint = u7;
const free: FingerPrint = 0;
const tombstone: FingerPrint = 1;
fingerprint: FingerPrint = free,
used: u1 = 0,
const slot_free: u8 = @bitCast(Metadata{ .fingerprint = free });
const slot_tombstone: u8 = @bitCast(Metadata{ .fingerprint = tombstone });
pub fn isUsed(self: Metadata) bool {
return self.used == 1;
}
pub fn isTombstone(self: Metadata) bool {
return @as(u8, @bitCast(self)) == slot_tombstone;
}
pub fn isFree(self: Metadata) bool {
return @as(u8, @bitCast(self)) == slot_free;
}
pub fn takeFingerprint(hash: Hash) FingerPrint {
const hash_bits = @typeInfo(Hash).int.bits;
const fp_bits = @typeInfo(FingerPrint).int.bits;
return @as(FingerPrint, @truncate(hash >> (hash_bits - fp_bits)));
}
pub fn fill(self: *Metadata, fp: FingerPrint) void {
self.used = 1;
self.fingerprint = fp;
}
pub fn remove(self: *Metadata) void {
self.used = 0;
self.fingerprint = tombstone;
}
};
comptime {
assert(@sizeOf(Metadata) == 1);
assert(@alignOf(Metadata) == 1);
}
pub const Iterator = struct {
hm: *const Self,
index: Size = 0,
pub fn next(it: *Iterator) ?Entry {
assert(it.index <= it.hm.capacity());
if (it.hm.size == 0) return null;
const cap = it.hm.capacity();
const end = it.hm.metadata.? + cap;
var metadata = it.hm.metadata.? + it.index;
while (metadata != end) : ({
metadata += 1;
it.index += 1;
}) {
if (metadata[0].isUsed()) {
const key = &it.hm.keys()[it.index];
const value = &it.hm.values()[it.index];
it.index += 1;
return Entry{ .key_ptr = key, .value_ptr = value };
}
}
return null;
}
};
pub const KeyIterator = FieldIterator(K);
pub const ValueIterator = FieldIterator(V);
fn FieldIterator(comptime T: type) type {
return struct {
len: usize,
metadata: [*]const Metadata,
items: [*]T,
pub fn next(self: *@This()) ?*T {
while (self.len > 0) {
self.len -= 1;
const used = self.metadata[0].isUsed();
const item = &self.items[0];
self.metadata += 1;
self.items += 1;
if (used) {
return item;
}
}
return null;
}
};
}
pub const GetOrPutResult = struct {
key_ptr: *K,
value_ptr: *V,
found_existing: bool,
};
pub const Managed = HashMap(K, V, Context, max_load_percentage);
pub fn promote(self: Self, allocator: Allocator) Managed {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call promoteContext instead.");
return promoteContext(self, allocator, undefined);
}
pub fn promoteContext(self: Self, allocator: Allocator, ctx: Context) Managed {
return .{
.unmanaged = self,
.allocator = allocator,
.ctx = ctx,
};
}
/// 将哈希映射置于特殊状态:任何会使现有键或值指针失效的方法调用,都改为触发断言。
///
/// `lockPointers` 可以多次调用,使多个独立使用者能同时保持哈希映射锁定。
///
/// `unlockPointers` 在调用次数与 `lockPointers` 相同时,将哈希映射恢复为原先状态。
///
///
///
///
pub fn lockPointers(self: *Self) void {
self.pointer_stability.lockShared();
}
/// 撤销一次 `lockPointers` 调用。
pub fn unlockPointers(self: *Self) void {
self.pointer_stability.unlockShared();
}
fn isUnderMaxLoadPercentage(size: Size, cap: Size) bool {
return size * 100 < max_load_percentage * cap;
}
pub fn deinit(self: *Self, allocator: Allocator) void {
self.pointer_stability.assertUnlocked();
self.deallocate(allocator);
self.* = undefined;
}
fn capacityForSize(size: Size) Size {
var new_cap: u32 = @intCast((@as(u64, size) * 100) / max_load_percentage + 1);
new_cap = math.ceilPowerOfTwo(u32, new_cap) catch unreachable;
return new_cap;
}
pub fn ensureTotalCapacity(self: *Self, allocator: Allocator, new_size: Size) Allocator.Error!void {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureTotalCapacityContext instead.");
return ensureTotalCapacityContext(self, allocator, new_size, undefined);
}
pub fn ensureTotalCapacityContext(self: *Self, allocator: Allocator, new_size: Size, ctx: Context) Allocator.Error!void {
self.pointer_stability.lock();
defer self.pointer_stability.unlock();
if (new_size > self.size)
try self.growIfNeeded(allocator, new_size - self.size, ctx);
}
pub fn ensureUnusedCapacity(self: *Self, allocator: Allocator, additional_size: Size) Allocator.Error!void {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call ensureUnusedCapacityContext instead.");
return ensureUnusedCapacityContext(self, allocator, additional_size, undefined);
}
pub fn ensureUnusedCapacityContext(self: *Self, allocator: Allocator, additional_size: Size, ctx: Context) Allocator.Error!void {
return ensureTotalCapacityContext(self, allocator, self.count() + additional_size, ctx);
}
pub fn clearRetainingCapacity(self: *Self) void {
self.pointer_stability.lock();
defer self.pointer_stability.unlock();
if (self.metadata) |_| {
self.initMetadatas();
self.size = 0;
self.available = @truncate((self.capacity() * max_load_percentage) / 100);
}
}
pub fn clearAndFree(self: *Self, allocator: Allocator) void {
self.pointer_stability.lock();
defer self.pointer_stability.unlock();
self.deallocate(allocator);
self.size = 0;
self.available = 0;
}
pub fn count(self: Self) Size {
return self.size;
}
fn header(self: Self) *Header {
return @ptrCast(@as([*]Header, @ptrCast(@alignCast(self.metadata.?))) - 1);
}
fn keys(self: Self) [*]K {
return self.header().keys;
}
fn values(self: Self) [*]V {
return self.header().values;
}
pub fn capacity(self: Self) Size {
if (self.metadata == null) return 0;
return self.header().capacity;
}
pub fn iterator(self: *const Self) Iterator {
return .{ .hm = self };
}
pub fn keyIterator(self: Self) KeyIterator {
if (self.metadata) |metadata| {
return .{
.len = self.capacity(),
.metadata = metadata,
.items = self.keys(),
};
} else {
return .{
.len = 0,
.metadata = undefined,
.items = undefined,
};
}
}
pub fn valueIterator(self: Self) ValueIterator {
if (self.metadata) |metadata| {
return .{
.len = self.capacity(),
.metadata = metadata,
.items = self.values(),
};
} else {
return .{
.len = 0,
.metadata = undefined,
.items = undefined,
};
}
}
/// 将条目插入映射。假定该条目尚不存在。
pub fn putNoClobber(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putNoClobberContext instead.");
return self.putNoClobberContext(allocator, key, value, undefined);
}
pub fn putNoClobberContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void {
{
self.pointer_stability.lock();
defer self.pointer_stability.unlock();
try self.growIfNeeded(allocator, 1, ctx);
}
self.putAssumeCapacityNoClobberContext(key, value, ctx);
}
/// 断言容量足以存储新键值对。
/// 覆盖任何已有数据。要检测插入是否会覆盖
/// 已有数据,请参见 `getOrPutAssumeCapacity`。
pub fn putAssumeCapacity(self: *Self, key: K, value: V) void {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityContext instead.");
return self.putAssumeCapacityContext(key, value, undefined);
}
pub fn putAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) void {
const gop = self.getOrPutAssumeCapacityContext(key, ctx);
gop.value_ptr.* = value;
}
/// 向映射插入条目。假定条目尚不存在,
/// 且无需分配内存。
pub fn putAssumeCapacityNoClobber(self: *Self, key: K, value: V) void {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putAssumeCapacityNoClobberContext instead.");
return self.putAssumeCapacityNoClobberContext(key, value, undefined);
}
pub fn putAssumeCapacityNoClobberContext(self: *Self, key: K, value: V, ctx: Context) void {
assert(!self.containsContext(key, ctx));
const hash: Hash = ctx.hash(key);
const mask = self.capacity() - 1;
var idx: usize = @truncate(hash & mask);
var metadata = self.metadata.? + idx;
while (metadata[0].isUsed()) {
idx = (idx + 1) & mask;
metadata = self.metadata.? + idx;
}
assert(self.available > 0);
self.available -= 1;
const fingerprint = Metadata.takeFingerprint(hash);
metadata[0].fill(fingerprint);
self.keys()[idx] = key;
self.values()[idx] = value;
self.size += 1;
}
/// 将新 `Entry` 插入哈希映射,并返回之前的条目(如果存在)。
pub fn fetchPut(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!?KV {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutContext instead.");
return self.fetchPutContext(allocator, key, value, undefined);
}
pub fn fetchPutContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!?KV {
const gop = try self.getOrPutContext(allocator, key, ctx);
var result: ?KV = null;
if (gop.found_existing) {
result = KV{
.key = gop.key_ptr.*,
.value = gop.value_ptr.*,
};
}
gop.value_ptr.* = value;
return result;
}
/// 向哈希表插入新的 `Entry`,若存在旧条目则返回旧条目。
/// 若执行插入,断言容量足够且不分配内存。
pub fn fetchPutAssumeCapacity(self: *Self, key: K, value: V) ?KV {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchPutAssumeCapacityContext instead.");
return self.fetchPutAssumeCapacityContext(key, value, undefined);
}
pub fn fetchPutAssumeCapacityContext(self: *Self, key: K, value: V, ctx: Context) ?KV {
const gop = self.getOrPutAssumeCapacityContext(key, ctx);
var result: ?KV = null;
if (gop.found_existing) {
result = KV{
.key = gop.key_ptr.*,
.value = gop.value_ptr.*,
};
}
gop.value_ptr.* = value;
return result;
}
/// 若存在键匹配的 `Entry`,则从
/// 哈希映射中删除,并由此函数返回。
pub fn fetchRemove(self: *Self, key: K) ?KV {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call fetchRemoveContext instead.");
return self.fetchRemoveContext(key, undefined);
}
pub fn fetchRemoveContext(self: *Self, key: K, ctx: Context) ?KV {
return self.fetchRemoveAdapted(key, ctx);
}
pub fn fetchRemoveAdapted(self: *Self, key: anytype, ctx: anytype) ?KV {
if (self.getIndex(key, ctx)) |idx| {
const old_key = &self.keys()[idx];
const old_val = &self.values()[idx];
const result = KV{
.key = old_key.*,
.value = old_val.*,
};
self.metadata.?[idx].remove();
old_key.* = undefined;
old_val.* = undefined;
self.size -= 1;
self.available += 1;
return result;
}
return null;
}
/// 查找包含给定键对应数据的索引。
fn getIndex(self: Self, key: anytype, ctx: anytype) ?usize {
if (self.size == 0) {
// 使用 cold 而不是 unlikely,以强制跳转到此分支,
// 不受另一分支权重的影响。
@branchHint(.cold);
return null;
}
// 若此行出现编译错误,表示泛型 hash 函数对于这些参数无效。
//
const hash: Hash = ctx.hash(key);
const mask = self.capacity() - 1;
const fingerprint = Metadata.takeFingerprint(hash);
// 没有空槽位时,不要无限循环。
var limit = self.capacity();
var idx = @as(usize, @truncate(hash & mask));
var metadata = self.metadata.? + idx;
while (!metadata[0].isFree() and limit != 0) {
if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
const test_key = &self.keys()[idx];
if (ctx.eql(key, test_key.*)) {
return idx;
}
}
limit -= 1;
idx = (idx + 1) & mask;
metadata = self.metadata.? + idx;
}
return null;
}
pub fn getEntry(self: Self, key: K) ?Entry {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getEntryContext instead.");
return self.getEntryContext(key, undefined);
}
pub fn getEntryContext(self: Self, key: K, ctx: Context) ?Entry {
return self.getEntryAdapted(key, ctx);
}
pub fn getEntryAdapted(self: Self, key: anytype, ctx: anytype) ?Entry {
if (self.getIndex(key, ctx)) |idx| {
return Entry{
.key_ptr = &self.keys()[idx],
.value_ptr = &self.values()[idx],
};
}
return null;
}
/// 如果关联键尚不存在,则插入条目;否则更新现有值。
pub fn put(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!void {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call putContext instead.");
return self.putContext(allocator, key, value, undefined);
}
pub fn putContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!void {
const result = try self.getOrPutContext(allocator, key, ctx);
result.value_ptr.* = value;
}
/// 若存在与适配键关联的实际键,获取指向该键的可选指针。
pub fn getKeyPtr(self: Self, key: K) ?*K {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyPtrContext instead.");
return self.getKeyPtrContext(key, undefined);
}
pub fn getKeyPtrContext(self: Self, key: K, ctx: Context) ?*K {
return self.getKeyPtrAdapted(key, ctx);
}
pub fn getKeyPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*K {
if (self.getIndex(key, ctx)) |idx| {
return &self.keys()[idx];
}
return null;
}
/// 若存在,获取与适配键对应的实际键的副本。
pub fn getKey(self: Self, key: K) ?K {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getKeyContext instead.");
return self.getKeyContext(key, undefined);
}
pub fn getKeyContext(self: Self, key: K, ctx: Context) ?K {
return self.getKeyAdapted(key, ctx);
}
pub fn getKeyAdapted(self: Self, key: anytype, ctx: anytype) ?K {
if (self.getIndex(key, ctx)) |idx| {
return self.keys()[idx];
}
return null;
}
/// 若存在与键关联的值,则获取指向它的可选指针。
pub fn getPtr(self: Self, key: K) ?*V {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getPtrContext instead.");
return self.getPtrContext(key, undefined);
}
pub fn getPtrContext(self: Self, key: K, ctx: Context) ?*V {
return self.getPtrAdapted(key, ctx);
}
pub fn getPtrAdapted(self: Self, key: anytype, ctx: anytype) ?*V {
if (self.getIndex(key, ctx)) |idx| {
return &self.values()[idx];
}
return null;
}
/// 若键存在,则获取与其关联的值的副本。
pub fn get(self: Self, key: K) ?V {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getContext instead.");
return self.getContext(key, undefined);
}
pub fn getContext(self: Self, key: K, ctx: Context) ?V {
return self.getAdapted(key, ctx);
}
pub fn getAdapted(self: Self, key: anytype, ctx: anytype) ?V {
if (self.getIndex(key, ctx)) |idx| {
return self.values()[idx];
}
return null;
}
pub fn getOrPut(self: *Self, allocator: Allocator, key: K) Allocator.Error!GetOrPutResult {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContext instead.");
return self.getOrPutContext(allocator, key, undefined);
}
pub fn getOrPutContext(self: *Self, allocator: Allocator, key: K, ctx: Context) Allocator.Error!GetOrPutResult {
const gop = try self.getOrPutContextAdapted(allocator, key, ctx, ctx);
if (!gop.found_existing) {
gop.key_ptr.* = key;
}
return gop;
}
pub fn getOrPutAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype) Allocator.Error!GetOrPutResult {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutContextAdapted instead.");
return self.getOrPutContextAdapted(allocator, key, key_ctx, undefined);
}
pub fn getOrPutContextAdapted(self: *Self, allocator: Allocator, key: anytype, key_ctx: anytype, ctx: Context) Allocator.Error!GetOrPutResult {
{
self.pointer_stability.lock();
defer self.pointer_stability.unlock();
self.growIfNeeded(allocator, 1, ctx) catch |err| {
// 若分配失败,仍尝试查找。
// 如果找到现有项,便可以返回它。
// 否则返回错误,因为无法再添加一项。
const index = self.getIndex(key, key_ctx) orelse return err;
return GetOrPutResult{
.key_ptr = &self.keys()[index],
.value_ptr = &self.values()[index],
.found_existing = true,
};
};
}
return self.getOrPutAssumeCapacityAdapted(key, key_ctx);
}
pub fn getOrPutAssumeCapacity(self: *Self, key: K) GetOrPutResult {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutAssumeCapacityContext instead.");
return self.getOrPutAssumeCapacityContext(key, undefined);
}
pub fn getOrPutAssumeCapacityContext(self: *Self, key: K, ctx: Context) GetOrPutResult {
const result = self.getOrPutAssumeCapacityAdapted(key, ctx);
if (!result.found_existing) {
result.key_ptr.* = key;
}
return result;
}
pub fn getOrPutAssumeCapacityAdapted(self: *Self, key: anytype, ctx: anytype) GetOrPutResult {
// 若此行出现编译错误,表示泛型 hash 函数对于这些参数无效。
//
const hash: Hash = ctx.hash(key);
const mask = self.capacity() - 1;
const fingerprint = Metadata.takeFingerprint(hash);
var limit = self.capacity();
var idx = @as(usize, @truncate(hash & mask));
var first_tombstone_idx: usize = self.capacity(); // 索引无效
var metadata = self.metadata.? + idx;
while (!metadata[0].isFree() and limit != 0) {
if (metadata[0].isUsed() and metadata[0].fingerprint == fingerprint) {
const test_key = &self.keys()[idx];
// 若此行产生编译错误,表示泛型 eql
// 函数对这些参数无效。
if (ctx.eql(key, test_key.*)) {
return GetOrPutResult{
.key_ptr = test_key,
.value_ptr = &self.values()[idx],
.found_existing = true,
};
}
} else if (first_tombstone_idx == self.capacity() and metadata[0].isTombstone()) {
first_tombstone_idx = idx;
}
limit -= 1;
idx = (idx + 1) & mask;
metadata = self.metadata.? + idx;
}
if (first_tombstone_idx < self.capacity()) {
// 在删除后低成本地尝试缩短探测长度,回收一个墓碑。
idx = first_tombstone_idx;
metadata = self.metadata.? + idx;
}
// 正在使用先前空闲或为墓碑的槽位。
self.available -= 1;
metadata[0].fill(fingerprint);
const new_key = &self.keys()[idx];
const new_value = &self.values()[idx];
new_key.* = undefined;
new_value.* = undefined;
self.size += 1;
return GetOrPutResult{
.key_ptr = new_key,
.value_ptr = new_value,
.found_existing = false,
};
}
pub fn getOrPutValue(self: *Self, allocator: Allocator, key: K, value: V) Allocator.Error!Entry {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call getOrPutValueContext instead.");
return self.getOrPutValueContext(allocator, key, value, undefined);
}
pub fn getOrPutValueContext(self: *Self, allocator: Allocator, key: K, value: V, ctx: Context) Allocator.Error!Entry {
const res = try self.getOrPutAdapted(allocator, key, ctx);
if (!res.found_existing) {
res.key_ptr.* = key;
res.value_ptr.* = value;
}
return Entry{ .key_ptr = res.key_ptr, .value_ptr = res.value_ptr };
}
/// 若映射中存在与 key 关联的值,则返回 true。
pub fn contains(self: Self, key: K) bool {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call containsContext instead.");
return self.containsContext(key, undefined);
}
pub fn containsContext(self: Self, key: K, ctx: Context) bool {
return self.containsAdapted(key, ctx);
}
pub fn containsAdapted(self: Self, key: anytype, ctx: anytype) bool {
return self.getIndex(key, ctx) != null;
}
fn removeByIndex(self: *Self, idx: usize) void {
self.metadata.?[idx].remove();
self.keys()[idx] = undefined;
self.values()[idx] = undefined;
self.size -= 1;
self.available += 1;
}
/// 如果哈希映射中存在键匹配的 `Entry`,则将其删除
/// 并返回 true。否则
/// 返回 false。
///
/// TODO: 回答此文档注释中的问题,删除该条目后未使用容量是否会增加一?
///
pub fn remove(self: *Self, key: K) bool {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call removeContext instead.");
return self.removeContext(key, undefined);
}
/// TODO: 回答这些文档注释中的问题:这是否
/// 使未使用容量增加了一个?
pub fn removeContext(self: *Self, key: K, ctx: Context) bool {
return self.removeAdapted(key, ctx);
}
/// TODO: 回答这些文档注释中的问题:这是否
/// 使未使用容量增加了一个?
pub fn removeAdapted(self: *Self, key: anytype, ctx: anytype) bool {
if (self.getIndex(key, ctx)) |idx| {
self.removeByIndex(idx);
return true;
}
return false;
}
/// 从哈希映射中删除键由 key_ptr 指向的条目。
/// 假定 key_ptr 是指向哈希映射中
/// 已有键的有效指针。
///
/// TODO: 回答这些文档注释中的问题:这是否
/// 使未使用容量增加了一个?
pub fn removeByPtr(self: *Self, key_ptr: *const K) void {
// 若 @sizeOf(K) == 0,则哈希映射最多只有一个条目;由于 key_ptr 必须有效,假定该条目存在。此条目必定位于索引 0。
//
//
const idx = if (@sizeOf(K) > 0)
@as([*]const K, @ptrCast(key_ptr)) - self.keys()
else
0;
self.removeByIndex(idx);
}
fn initMetadatas(self: *Self) void {
@memset(@as([*]u8, @ptrCast(self.metadata.?))[0 .. @sizeOf(Metadata) * self.capacity()], 0);
}
// 计算已占用槽位的数量(不包含墓碑),此数量
// 必须低于容量的 max_load_percentage。
fn load(self: Self) Size {
const max_load = (self.capacity() * max_load_percentage) / 100;
assert(max_load >= self.available);
return @as(Size, @truncate(max_load - self.available));
}
fn growIfNeeded(self: *Self, allocator: Allocator, new_count: Size, ctx: Context) Allocator.Error!void {
if (new_count > self.available) {
try self.grow(allocator, capacityForSize(self.load() + new_count), ctx);
}
}
pub fn clone(self: Self, allocator: Allocator) Allocator.Error!Self {
if (@sizeOf(Context) != 0)
@compileError("Cannot infer context " ++ @typeName(Context) ++ ", call cloneContext instead.");
return self.cloneContext(allocator, @as(Context, undefined));
}
pub fn cloneContext(self: Self, allocator: Allocator, new_ctx: anytype) Allocator.Error!HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) {
var other: HashMapUnmanaged(K, V, @TypeOf(new_ctx), max_load_percentage) = .empty;
if (self.size == 0)
return other;
const new_cap = capacityForSize(self.size);
try other.allocate(allocator, new_cap);
other.initMetadatas();
other.available = @truncate((new_cap * max_load_percentage) / 100);
var i: Size = 0;
var metadata = self.metadata.?;
const keys_ptr = self.keys();
const values_ptr = self.values();
while (i < self.capacity()) : (i += 1) {
if (metadata[i].isUsed()) {
other.putAssumeCapacityNoClobberContext(keys_ptr[i], values_ptr[i], new_ctx);
if (other.size == self.size)
break;
}
}
return other;
}
/// 将映射置为空状态,使反初始化变为空操作,
/// 并返回原映射的副本。
pub fn move(self: *Self) Self {
self.pointer_stability.assertUnlocked();
const result = self.*;
self.* = .empty;
return result;
}
/// 原地重新哈希映射。
///
/// 由于当前使用基于墓碑的实现,
/// 长期使用后,HashMap 可能因墓碑条目
/// 不断积累而产生碎片,过量探测
/// 导致性能下降。可能触发此情况的模式是
/// 长时间存在且反复插入、删除的 HashMap。
///
/// 调用此函数后,HashMap 中不再存在墓碑,
/// 所有条目均重新哈希,且任何已有的
/// 指向 HashMap 内键或值的指针均失效。
pub fn rehash(self: *Self, ctx: anytype) void {
const mask = self.capacity() - 1;
var metadata = self.metadata.?;
var keys_ptr = self.keys();
var values_ptr = self.values();
var curr: Size = 0;
// 重新哈希各槽位时,使用指纹将
// 已使用的桶标记为已使用,并进一步标记为 free
// (需要重新哈希)或 tombstone(已重新哈希)。
while (curr < self.capacity()) : (curr += 1) {
metadata[curr].fingerprint = Metadata.free;
}
// 现在遍历所有桶,重新计算其哈希
curr = 0;
while (curr < self.capacity()) {
if (!metadata[curr].isUsed()) {
assert(metadata[curr].isFree());
curr += 1;
continue;
}
const hash = ctx.hash(keys_ptr[curr]);
const fingerprint = Metadata.takeFingerprint(hash);
var idx = @as(usize, @truncate(hash & mask));
// 将每个桶重新哈希到某个索引:
// 1) 游标之前,探测到空闲槽位;或
// 2) 等于游标,无需移动;或
// 3) 游标之后,探测时跨过已重新哈希的条目。
while ((idx < curr and metadata[idx].isUsed()) or
(idx > curr and metadata[idx].fingerprint == Metadata.tombstone))
{
idx = (idx + 1) & mask;
}
if (idx < curr) {
assert(metadata[idx].isFree());
metadata[idx].fill(fingerprint);
keys_ptr[idx] = keys_ptr[curr];
values_ptr[idx] = values_ptr[curr];
metadata[curr].used = 0;
assert(metadata[curr].isFree());
keys_ptr[curr] = undefined;
values_ptr[curr] = undefined;
curr += 1;
} else if (idx == curr) {
metadata[idx].fingerprint = fingerprint;
curr += 1;
} else {
assert(metadata[idx].fingerprint != Metadata.tombstone);
metadata[idx].fingerprint = Metadata.tombstone;
if (metadata[idx].isUsed()) {
std.mem.swap(K, &keys_ptr[curr], &keys_ptr[idx]);
std.mem.swap(V, &values_ptr[curr], &values_ptr[idx]);
} else {
metadata[idx].used = 1;
keys_ptr[idx] = keys_ptr[curr];
values_ptr[idx] = values_ptr[curr];
metadata[curr].fingerprint = Metadata.free;
metadata[curr].used = 0;
keys_ptr[curr] = undefined;
values_ptr[curr] = undefined;
curr += 1;
}
}
}
}
fn grow(self: *Self, allocator: Allocator, new_capacity: Size, ctx: Context) Allocator.Error!void {
@branchHint(.cold);
const new_cap = @max(new_capacity, minimal_capacity);
assert(new_cap > self.capacity());
assert(std.math.isPowerOfTwo(new_cap));
var map: Self = .{};
try map.allocate(allocator, new_cap);
errdefer comptime unreachable;
map.pointer_stability.lock();
map.initMetadatas();
map.available = @truncate((new_cap * max_load_percentage) / 100);
if (self.size != 0) {
const old_capacity = self.capacity();
for (
self.metadata.?[0..old_capacity],
self.keys()[0..old_capacity],
self.values()[0..old_capacity],
) |m, k, v| {
if (!m.isUsed()) continue;
map.putAssumeCapacityNoClobberContext(k, v, ctx);
if (map.size == self.size) break;
}
}
self.size = 0;
self.pointer_stability = .{};
std.mem.swap(Self, self, &map);
map.deinit(allocator);
}
fn allocate(self: *Self, allocator: Allocator, new_capacity: Size) Allocator.Error!void {
const header_align = @alignOf(Header);
const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K);
const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V);
const max_align: Alignment = comptime .fromByteUnits(@max(header_align, key_align, val_align));
const new_cap: usize = new_capacity;
const meta_size = @sizeOf(Header) + new_cap * @sizeOf(Metadata);
comptime assert(@alignOf(Metadata) == 1);
const keys_start = std.mem.alignForward(usize, meta_size, key_align);
const keys_end = keys_start + new_cap * @sizeOf(K);
const vals_start = std.mem.alignForward(usize, keys_end, val_align);
const vals_end = vals_start + new_cap * @sizeOf(V);
const total_size = max_align.forward(vals_end);
const slice = try allocator.alignedAlloc(u8, max_align, total_size);
const ptr: [*]u8 = @ptrCast(slice.ptr);
const metadata = ptr + @sizeOf(Header);
const hdr = @as(*Header, @ptrCast(@alignCast(ptr)));
if (@sizeOf([*]V) != 0) {
hdr.values = @ptrCast(@alignCast((ptr + vals_start)));
}
if (@sizeOf([*]K) != 0) {
hdr.keys = @ptrCast(@alignCast((ptr + keys_start)));
}
hdr.capacity = new_capacity;
self.metadata = @ptrCast(@alignCast(metadata));
}
fn deallocate(self: *Self, allocator: Allocator) void {
if (self.metadata == null) return;
const header_align = @alignOf(Header);
const key_align = if (@sizeOf(K) == 0) 1 else @alignOf(K);
const val_align = if (@sizeOf(V) == 0) 1 else @alignOf(V);
const max_align = comptime @max(header_align, key_align, val_align);
const cap: usize = self.capacity();
const meta_size = @sizeOf(Header) + cap * @sizeOf(Metadata);
comptime assert(@alignOf(Metadata) == 1);
const keys_start = std.mem.alignForward(usize, meta_size, key_align);
const keys_end = keys_start + cap * @sizeOf(K);
const vals_start = std.mem.alignForward(usize, keys_end, val_align);
const vals_end = vals_start + cap * @sizeOf(V);
const total_size = std.mem.alignForward(usize, vals_end, max_align);
const slice = @as([*]align(max_align) u8, @ptrCast(@alignCast(self.header())))[0..total_size];
allocator.free(slice);
self.metadata = null;
self.available = 0;
}
/// lib/lldb/ 中的调试器美化格式化器使用此函数获取头部类型,以便为该类型提供格式化调试输出。
///
fn dbHelper(self: *Self, hdr: *Header, entry: *Entry) void {
_ = self;
_ = hdr;
_ = entry;
}
comptime {
if (!builtin.strip_debug_info) switch (builtin.zig_backend) {
.stage2_llvm => _ = &dbHelper,
.stage2_x86_64 => _ = @as(KV, undefined),
else => {},
};
}
};
}
const testing = std.testing;
const expect = std.testing.expect;
const expectEqual = std.testing.expectEqual;
test "basic usage" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
const count = 5;
var i: u32 = 0;
var total: u32 = 0;
while (i < count) : (i += 1) {
try map.put(i, i);
total += i;
}
var sum: u32 = 0;
var it = map.iterator();
while (it.next()) |kv| {
sum += kv.key_ptr.*;
}
try expectEqual(total, sum);
i = 0;
sum = 0;
while (i < count) : (i += 1) {
try expectEqual(i, map.get(i).?);
sum += map.get(i).?;
}
try expectEqual(total, sum);
}
test "ensureTotalCapacity" {
var map = AutoHashMap(i32, i32).init(std.testing.allocator);
defer map.deinit();
try map.ensureTotalCapacity(20);
const initial_capacity = map.capacity();
try testing.expect(initial_capacity >= 20);
var i: i32 = 0;
while (i < 20) : (i += 1) {
try testing.expect(map.fetchPutAssumeCapacity(i, i + 10) == null);
}
// putAssumeCapacity 不应调整大小
try testing.expect(initial_capacity == map.capacity());
}
test "ensureUnusedCapacity with tombstones" {
var map = AutoHashMap(i32, i32).init(std.testing.allocator);
defer map.deinit();
var i: i32 = 0;
while (i < 100) : (i += 1) {
try map.ensureUnusedCapacity(1);
map.putAssumeCapacity(i, i);
_ = map.remove(i);
}
}
test "clearRetainingCapacity" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
map.clearRetainingCapacity();
try map.put(1, 1);
try expectEqual(map.get(1).?, 1);
try expectEqual(map.count(), 1);
map.clearRetainingCapacity();
map.putAssumeCapacity(1, 1);
try expectEqual(map.get(1).?, 1);
try expectEqual(map.count(), 1);
const cap = map.capacity();
try expect(cap > 0);
map.clearRetainingCapacity();
map.clearRetainingCapacity();
try expectEqual(map.count(), 0);
try expectEqual(map.capacity(), cap);
try expect(!map.contains(1));
}
test "grow" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
const growTo = 12456;
var i: u32 = 0;
while (i < growTo) : (i += 1) {
try map.put(i, i);
}
try expectEqual(map.count(), growTo);
i = 0;
var it = map.iterator();
while (it.next()) |kv| {
try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
i += 1;
}
try expectEqual(i, growTo);
i = 0;
while (i < growTo) : (i += 1) {
try expectEqual(map.get(i).?, i);
}
}
test "clone" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
var a = try map.clone();
defer a.deinit();
try expectEqual(a.count(), 0);
try a.put(1, 1);
try a.put(2, 2);
try a.put(3, 3);
var b = try a.clone();
defer b.deinit();
try expectEqual(b.count(), 3);
try expectEqual(b.get(1).?, 1);
try expectEqual(b.get(2).?, 2);
try expectEqual(b.get(3).?, 3);
var original = AutoHashMap(i32, i32).init(std.testing.allocator);
defer original.deinit();
var i: u8 = 0;
while (i < 10) : (i += 1) {
try original.putNoClobber(i, i * 10);
}
var copy = try original.clone();
defer copy.deinit();
i = 0;
while (i < 10) : (i += 1) {
try testing.expect(copy.get(i).? == i * 10);
}
}
test "ensureTotalCapacity with existing elements" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
try map.put(0, 0);
try expectEqual(map.count(), 1);
try expectEqual(map.capacity(), @TypeOf(map).Unmanaged.minimal_capacity);
try map.ensureTotalCapacity(65);
try expectEqual(map.count(), 1);
try expectEqual(map.capacity(), 128);
}
test "ensureTotalCapacity satisfies max load factor" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
try map.ensureTotalCapacity(127);
try expectEqual(map.capacity(), 256);
}
test "remove" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
var i: u32 = 0;
while (i < 16) : (i += 1) {
try map.put(i, i);
}
i = 0;
while (i < 16) : (i += 1) {
if (i % 3 == 0) {
_ = map.remove(i);
}
}
try expectEqual(map.count(), 10);
var it = map.iterator();
while (it.next()) |kv| {
try expectEqual(kv.key_ptr.*, kv.value_ptr.*);
try expect(kv.key_ptr.* % 3 != 0);
}
i = 0;
while (i < 16) : (i += 1) {
if (i % 3 == 0) {
try expect(!map.contains(i));
} else {
try expectEqual(map.get(i).?, i);
}
}
}
test "reverse removes" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
var i: u32 = 0;
while (i < 16) : (i += 1) {
try map.putNoClobber(i, i);
}
i = 16;
while (i > 0) : (i -= 1) {
_ = map.remove(i - 1);
try expect(!map.contains(i - 1));
var j: u32 = 0;
while (j < i - 1) : (j += 1) {
try expectEqual(map.get(j).?, j);
}
}
try expectEqual(map.count(), 0);
}
test "multiple removes on same metadata" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
var i: u32 = 0;
while (i < 16) : (i += 1) {
try map.put(i, i);
}
_ = map.remove(7);
_ = map.remove(15);
_ = map.remove(14);
_ = map.remove(13);
try expect(!map.contains(7));
try expect(!map.contains(15));
try expect(!map.contains(14));
try expect(!map.contains(13));
i = 0;
while (i < 13) : (i += 1) {
if (i == 7) {
try expect(!map.contains(i));
} else {
try expectEqual(map.get(i).?, i);
}
}
try map.put(15, 15);
try map.put(13, 13);
try map.put(14, 14);
try map.put(7, 7);
i = 0;
while (i < 16) : (i += 1) {
try expectEqual(map.get(i).?, i);
}
}
test "put and remove loop in random order" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
var keys = std.array_list.Managed(u32).init(std.testing.allocator);
defer keys.deinit();
const size = 32;
const iterations = 100;
var i: u32 = 0;
while (i < size) : (i += 1) {
try keys.append(i);
}
var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
const random = prng.random();
while (i < iterations) : (i += 1) {
random.shuffle(u32, keys.items);
for (keys.items) |key| {
try map.put(key, key);
}
try expectEqual(map.count(), size);
for (keys.items) |key| {
_ = map.remove(key);
}
try expectEqual(map.count(), 0);
}
}
test "remove many elements in random order" {
const Map = AutoHashMap(u32, u32);
const n = 1000 * 100;
var map = Map.init(std.heap.page_allocator);
defer map.deinit();
var keys = std.array_list.Managed(u32).init(std.heap.page_allocator);
defer keys.deinit();
var i: u32 = 0;
while (i < n) : (i += 1) {
keys.append(i) catch unreachable;
}
var prng = std.Random.DefaultPrng.init(std.testing.random_seed);
const random = prng.random();
random.shuffle(u32, keys.items);
for (keys.items) |key| {
map.put(key, key) catch unreachable;
}
random.shuffle(u32, keys.items);
i = 0;
while (i < n) : (i += 1) {
const key = keys.items[i];
_ = map.remove(key);
}
}
test "put" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
var i: u32 = 0;
while (i < 16) : (i += 1) {
try map.put(i, i);
}
i = 0;
while (i < 16) : (i += 1) {
try expectEqual(map.get(i).?, i);
}
i = 0;
while (i < 16) : (i += 1) {
try map.put(i, i * 16 + 1);
}
i = 0;
while (i < 16) : (i += 1) {
try expectEqual(map.get(i).?, i * 16 + 1);
}
}
test "putAssumeCapacity" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
try map.ensureTotalCapacity(20);
var i: u32 = 0;
while (i < 20) : (i += 1) {
map.putAssumeCapacityNoClobber(i, i);
}
i = 0;
var sum = i;
while (i < 20) : (i += 1) {
sum += map.getPtr(i).?.*;
}
try expectEqual(sum, 190);
i = 0;
while (i < 20) : (i += 1) {
map.putAssumeCapacity(i, 1);
}
i = 0;
sum = i;
while (i < 20) : (i += 1) {
sum += map.get(i).?;
}
try expectEqual(sum, 20);
}
test "repeat putAssumeCapacity/remove" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
try map.ensureTotalCapacity(20);
const limit = map.unmanaged.available;
var i: u32 = 0;
while (i < limit) : (i += 1) {
map.putAssumeCapacityNoClobber(i, i);
}
// 在不调整映射大小的情况下,反复删除/插入条目。
// 放入不同的键,以免条目落入刚释放的槽位。
i = 0;
while (i < 10 * limit) : (i += 1) {
try testing.expect(map.remove(i));
if (i % 2 == 0) {
map.putAssumeCapacityNoClobber(limit + i, i);
} else {
map.putAssumeCapacity(limit + i, i);
}
}
i = 9 * limit;
while (i < 10 * limit) : (i += 1) {
try expectEqual(map.get(limit + i), i);
}
try expectEqual(map.unmanaged.available, 0);
try expectEqual(map.unmanaged.count(), limit);
}
test "getOrPut" {
var map = AutoHashMap(u32, u32).init(std.testing.allocator);
defer map.deinit();
var i: u32 = 0;
while (i < 10) : (i += 1) {
try map.put(i * 2, 2);
}
i = 0;
while (i < 20) : (i += 1) {
_ = try map.getOrPutValue(i, 1);
}
i = 0;
var sum = i;
while (i < 20) : (i += 1) {
sum += map.get(i).?;
}
try expectEqual(sum, 30);
}
test "basic hash map usage" {
var map = AutoHashMap(i32, i32).init(std.testing.allocator);
defer map.deinit();
try testing.expect((try map.fetchPut(1, 11)) == null);
try testing.expect((try map.fetchPut(2, 22)) == null);
try testing.expect((try map.fetchPut(3, 33)) == null);
try testing.expect((try map.fetchPut(4, 44)) == null);
try map.putNoClobber(5, 55);
try testing.expect((try map.fetchPut(5, 66)).?.value == 55);
try testing.expect((try map.fetchPut(5, 55)).?.value == 66);
const gop1 = try map.getOrPut(5);
try testing.expect(gop1.found_existing == true);
try testing.expect(gop1.value_ptr.* == 55);
gop1.value_ptr.* = 77;
try testing.expect(map.getEntry(5).?.value_ptr.* == 77);
const gop2 = try map.getOrPut(99);
try testing.expect(gop2.found_existing == false);
gop2.value_ptr.* = 42;
try testing.expect(map.getEntry(99).?.value_ptr.* == 42);
const gop3 = try map.getOrPutValue(5, 5);
try testing.expect(gop3.value_ptr.* == 77);
const gop4 = try map.getOrPutValue(100, 41);
try testing.expect(gop4.value_ptr.* == 41);
try testing.expect(map.contains(2));
try testing.expect(map.getEntry(2).?.value_ptr.* == 22);
try testing.expect(map.get(2).? == 22);
const rmv1 = map.fetchRemove(2);
try testing.expect(rmv1.?.key == 2);
try testing.expect(rmv1.?.value == 22);
try testing.expect(map.fetchRemove(2) == null);
try testing.expect(map.remove(2) == false);
try testing.expect(map.getEntry(2) == null);
try testing.expect(map.get(2) == null);
try testing.expect(map.remove(3) == true);
}
test "getOrPutAdapted" {
const AdaptedContext = struct {
fn eql(self: @This(), adapted_key: []const u8, test_key: u64) bool {
_ = self;
return std.fmt.parseInt(u64, adapted_key, 10) catch unreachable == test_key;
}
fn hash(self: @This(), adapted_key: []const u8) u64 {
_ = self;
const key = std.fmt.parseInt(u64, adapted_key, 10) catch unreachable;
return (AutoContext(u64){}).hash(key);
}
};
var map = AutoHashMap(u64, u64).init(testing.allocator);
defer map.deinit();
const keys = [_][]const u8{
"1231",
"4564",
"7894",
"1132",
"65235",
"95462",
"0112305",
"00658",
"0",
"2",
};
var real_keys: [keys.len]u64 = undefined;
inline for (keys, 0..) |key_str, i| {
const result = try map.getOrPutAdapted(key_str, AdaptedContext{});
try testing.expect(!result.found_existing);
real_keys[i] = std.fmt.parseInt(u64, key_str, 10) catch unreachable;
result.key_ptr.* = real_keys[i];
result.value_ptr.* = i * 2;
}
try testing.expectEqual(map.count(), keys.len);
inline for (keys, 0..) |key_str, i| {
const result = map.getOrPutAssumeCapacityAdapted(key_str, AdaptedContext{});
try testing.expect(result.found_existing);
try testing.expectEqual(real_keys[i], result.key_ptr.*);
try testing.expectEqual(@as(u64, i) * 2, result.value_ptr.*);
try testing.expectEqual(real_keys[i], map.getKeyAdapted(key_str, AdaptedContext{}).?);
}
}
test "ensureUnusedCapacity" {
var map = AutoHashMap(u64, u64).init(testing.allocator);
defer map.deinit();
try map.ensureUnusedCapacity(32);
const capacity = map.capacity();
try map.ensureUnusedCapacity(32);
// 连续调用 ensureUnusedCapacity(),期间未插入元素时,
// 不应改变容量。
try testing.expectEqual(capacity, map.capacity());
}
test "removeByPtr" {
var map = AutoHashMap(i32, u64).init(testing.allocator);
defer map.deinit();
var i: i32 = undefined;
i = 0;
while (i < 10) : (i += 1) {
try map.put(i, 0);
}
try testing.expect(map.count() == 10);
i = 0;
while (i < 10) : (i += 1) {
const key_ptr = map.getKeyPtr(i);
try testing.expect(key_ptr != null);
if (key_ptr) |ptr| {
map.removeByPtr(ptr);
}
}
try testing.expect(map.count() == 0);
}
test "removeByPtr 0 sized key" {
var map = AutoHashMap(u0, u64).init(testing.allocator);
defer map.deinit();
try map.put(0, 0);
try testing.expect(map.count() == 1);
const key_ptr = map.getKeyPtr(0);
try testing.expect(key_ptr != null);
if (key_ptr) |ptr| {
map.removeByPtr(ptr);
}
try testing.expect(map.count() == 0);
}
test "repeat fetchRemove" {
var map: AutoHashMapUnmanaged(u64, void) = .empty;
defer map.deinit(testing.allocator);
try map.ensureTotalCapacity(testing.allocator, 4);
map.putAssumeCapacity(0, {});
map.putAssumeCapacity(1, {});
map.putAssumeCapacity(2, {});
map.putAssumeCapacity(3, {});
// fetchRemove() 应使槽位可用。
var i: usize = 0;
while (i < 10) : (i += 1) {
try testing.expect(map.fetchRemove(3) != null);
map.putAssumeCapacity(3, {});
}
try testing.expect(map.get(0) != null);
try testing.expect(map.get(1) != null);
try testing.expect(map.get(2) != null);
try testing.expect(map.get(3) != null);
}
test "getOrPut allocation failure" {
var map: std.StringHashMapUnmanaged(void) = .empty;
try testing.expectError(error.OutOfMemory, map.getOrPut(std.testing.failing_allocator, "hello"));
}
test "rehash" {
var map = AutoHashMap(usize, usize).init(std.testing.allocator);
defer map.deinit();
var prng = std.Random.DefaultPrng.init(0);
const random = prng.random();
const count = 4 * random.intRangeLessThan(u32, 100_000, 500_000);
for (0..count) |i| {
try map.put(i, i);
if (i % 3 == 0) {
try expectEqual(map.remove(i), true);
}
}
map.rehash();
try expectEqual(map.count(), count * 2 / 3);
for (0..count) |i| {
if (i % 3 == 0) {
try expectEqual(map.get(i), null);
} else {
try expectEqual(map.get(i).?, i);
}
}
}
test "removeByPtr, key is array" {
const gpa = testing.allocator;
var map: AutoHashMapUnmanaged([2]u32, u32) = .empty;
defer map.deinit(gpa);
const key: [2]u32 = .{ 1, 2 };
try map.put(gpa, key, 3);
try expectEqual(1, map.count());
try expectEqual(3, map.get(key));
const key_ptr = map.getKeyPtr(key).?;
map.removeByPtr(key_ptr);
try expectEqual(0, map.count());
try expectEqual(null, map.get(key));
}