std.hash.auto_hash.assert
别名
别名目标 std.debug.assert
std.hash.auto_hash.autoHash
函数
为所有符合条件的类型提供泛型哈希。
仅对 key 本身计算哈希,不跟随指针。
拒绝切片,以及包含切片的联合体和结构体,
避免对用户意图产生歧义。
pub fn autoHash(hasher: anytype, key: anytype) void
std.hash.auto_hash.hash
函数
为所有符合条件的类型提供泛型哈希。 通过所提供的策略决定是否跟随指针。
pub fn hash(hasher: anytype, key: anytype, comptime strat: HashStrategy) void
参数
strat: HashStrategy
std.hash.auto_hash.hashArray
函数
用于对数组或切片中一组连续对象进行哈希的辅助函数。
pub fn hashArray(hasher: anytype, key: anytype, comptime strat: HashStrategy) void
参数
strat: HashStrategy
std.hash.auto_hash.hashPointer
函数
用于对指针进行哈希,并按需修改策略的辅助函数。
pub fn hashPointer(hasher: anytype, key: anytype, comptime strat: HashStrategy) void
参数
strat: HashStrategy
std.hash.auto_hash.HashStrategy
容器
描述指针类型的哈希方式。
字段
Shallow不要跟随指针,只对其值进行哈希。
Deep跟随指针,对指向内容进行哈希。 仅解引用一级,即遇到指针类型时会转为 .Shallow。
DeepRecursive沿指针对所指内容进行哈希。 解引用遇到的所有指针。 假定不存在环。
std.hash.auto_hash.init
函数
pub fn init(allocator: mem.Allocator, a_: u32, b_: u16, c_: bool) !Self
参数
std.hash.auto_hash.mem
别名
别名目标 std.mem
std.hash.auto_hash.Self
别名
别名目标 std.hash.auto_hash
std.hash.auto_hash.std
别名
别名目标 std
std.hash.auto_hash.testHash
函数
fn testHash(key: anytype) u64
std.hash.auto_hash.testHashDeep
函数
fn testHashDeep(key: anytype) u64
std.hash.auto_hash.testHashDeepRecursive
函数
fn testHashDeepRecursive(key: anytype) u64
std.hash.auto_hash.testHashShallow
函数
fn testHashShallow(key: anytype) u64
std.hash.auto_hash.testing
别名
别名目标 std.testing
std.hash.auto_hash.typeContainsSlice
函数
inline fn typeContainsSlice(comptime K: type) bool
参数
K: type
std.hash.auto_hash.Wyhash
别名
别名目标 std.hash.Wyhash
源码
std/hash/auto_hash.zig
const std = @import("std");
const assert = std.debug.assert;
const mem = std.mem;
/// 描述指针类型的哈希方式。
pub const HashStrategy = enum {
/// 不要跟随指针,只对其值进行哈希。
Shallow,
/// 跟随指针,对指向内容进行哈希。
/// 仅解引用一级,即遇到指针类型时会转为 .Shallow。
///
Deep,
/// 沿指针对所指内容进行哈希。
/// 解引用遇到的所有指针。
/// 假定不存在环。
DeepRecursive,
};
/// 用于对指针进行哈希,并按需修改策略的辅助函数。
pub fn hashPointer(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
const info = @typeInfo(@TypeOf(key));
switch (info.pointer.size) {
.one => switch (strat) {
.Shallow => hash(hasher, @intFromPtr(key), .Shallow),
.Deep => hash(hasher, key.*, .Shallow),
.DeepRecursive => hash(hasher, key.*, .DeepRecursive),
},
.slice => {
switch (strat) {
.Shallow => {
hashPointer(hasher, key.ptr, .Shallow);
},
.Deep => hashArray(hasher, key, .Shallow),
.DeepRecursive => hashArray(hasher, key, .DeepRecursive),
}
hash(hasher, key.len, .Shallow);
},
.many,
.c,
=> switch (strat) {
.Shallow => hash(hasher, @intFromPtr(key), .Shallow),
else => @compileError(
\\ unknown-length pointers and C pointers cannot be hashed deeply.
\\ Consider providing your own hash function.
),
},
}
}
/// 用于对数组或切片中一组连续对象进行哈希的辅助函数。
pub fn hashArray(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
for (key) |element| {
hash(hasher, element, strat);
}
}
/// 为所有符合条件的类型提供泛型哈希。
/// 通过所提供的策略决定是否跟随指针。
pub fn hash(hasher: anytype, key: anytype, comptime strat: HashStrategy) void {
const Key = @TypeOf(key);
const Hasher = switch (@typeInfo(@TypeOf(hasher))) {
.pointer => |ptr| ptr.child,
else => @TypeOf(hasher),
};
if (strat == .Shallow and std.meta.hasUniqueRepresentation(Key)) {
@call(.always_inline, Hasher.update, .{ hasher, mem.asBytes(&key) });
return;
}
switch (@typeInfo(Key)) {
.noreturn,
.@"opaque",
.spirv,
.undefined,
.null,
.comptime_float,
.comptime_int,
.type,
.enum_literal,
.frame,
.float,
=> @compileError("unable to hash type " ++ @typeName(Key)),
.void => return,
// 通过内联帮助优化器识别整数哈希很简单。
// TODO: 检查 #561 解决后情况是否改善。
.int => |int| switch (int.signedness) {
.signed => hash(hasher, @as(@Int(.unsigned, int.bits), @bitCast(key)), strat),
.unsigned => {
if (std.meta.hasUniqueRepresentation(Key)) {
@call(.always_inline, Hasher.update, .{ hasher, std.mem.asBytes(&key) });
} else {
// 仅取包含键值的部分,其余
// 字节未定义,绝不可参与哈希!
const byte_size = @divCeil(@bitSizeOf(Key), 8);
@call(.always_inline, Hasher.update, .{ hasher, std.mem.asBytes(&key)[0..byte_size] });
}
},
},
.bool => hash(hasher, @intFromBool(key), strat),
.@"enum" => hash(hasher, @backingInt(key), strat),
.error_set => hash(hasher, @intFromError(key), strat),
.@"anyframe", .@"fn" => hash(hasher, @intFromPtr(key), strat),
.pointer => @call(.always_inline, hashPointer, .{ hasher, key, strat }),
.optional => if (key) |k| hash(hasher, k, strat),
.array => hashArray(hasher, key, strat),
.vector => |info| {
if (std.meta.hasUniqueRepresentation(Key)) {
hasher.update(mem.asBytes(&key));
} else {
comptime var i = 0;
inline while (i < info.len) : (i += 1) {
hash(hasher, key[i], strat);
}
}
},
.@"struct" => |info| {
inline for (info.field_names) |field_name| {
// 复用前一个字段的哈希作为
// 下一个字段的种子,使它们相互依赖。
hash(hasher, @field(key, field_name), strat);
}
},
.@"union" => |info| blk: {
if (info.tag_type) |tag_type| {
const tag = std.meta.activeTag(key);
hash(hasher, tag, strat);
inline for (info.field_names, info.field_types) |field_name, field_type| {
if (@field(tag_type, field_name) == tag) {
if (field_type != void) {
hash(hasher, @field(key, field_name), strat);
}
break :blk;
}
}
unreachable;
} else @compileError("cannot hash untagged union type: " ++ @typeName(Key) ++ ", provide your own hash function");
},
.error_union => blk: {
const payload = key catch |err| {
hash(hasher, err, strat);
break :blk;
};
hash(hasher, payload, strat);
},
}
}
inline fn typeContainsSlice(comptime K: type) bool {
return switch (@typeInfo(K)) {
.pointer => |info| info.size == .slice,
inline .@"struct", .@"union" => |info| {
inline for (info.field_types) |field_type| {
if (typeContainsSlice(field_type)) {
return true;
}
}
return false;
},
else => false,
};
}
/// 为所有符合条件的类型提供泛型哈希。
/// 仅对 `key` 本身计算哈希,不跟随指针。
/// 拒绝切片,以及包含切片的联合体和结构体,
/// 避免对用户意图产生歧义。
pub fn autoHash(hasher: anytype, key: anytype) void {
const Key = @TypeOf(key);
if (comptime typeContainsSlice(Key)) {
@compileError("std.hash.autoHash does not allow slices as well as unions and structs containing slices here (" ++ @typeName(Key) ++
") because the intent is unclear. Consider using std.hash.autoHashStrat or providing your own hash function instead.");
}
hash(hasher, key, .Shallow);
}
const testing = std.testing;
const Wyhash = std.hash.Wyhash;
fn testHash(key: anytype) u64 {
// 此处可使用任意哈希,以测试 autoHash。
var hasher = Wyhash.init(0);
hash(&hasher, key, .Shallow);
return hasher.final();
}
fn testHashShallow(key: anytype) u64 {
// 此处可使用任意哈希,以测试 autoHash。
var hasher = Wyhash.init(0);
hash(&hasher, key, .Shallow);
return hasher.final();
}
fn testHashDeep(key: anytype) u64 {
// 此处可使用任意哈希,以测试 autoHash。
var hasher = Wyhash.init(0);
hash(&hasher, key, .Deep);
return hasher.final();
}
fn testHashDeepRecursive(key: anytype) u64 {
// 此处可使用任意哈希,以测试 autoHash。
var hasher = Wyhash.init(0);
hash(&hasher, key, .DeepRecursive);
return hasher.final();
}
test "typeContainsSlice" {
comptime {
try testing.expect(!typeContainsSlice(std.meta.Tag(std.lang.Type)));
try testing.expect(typeContainsSlice([]const u8));
try testing.expect(!typeContainsSlice(u8));
const A = struct { x: []const u8 };
const B = struct { a: A };
const C = struct { b: B };
const D = struct { x: u8 };
try testing.expect(typeContainsSlice(A));
try testing.expect(typeContainsSlice(B));
try testing.expect(typeContainsSlice(C));
try testing.expect(!typeContainsSlice(D));
}
}
test "hash pointer" {
const array = [_]u32{ 123, 123, 123 };
const a = &array[0];
const b = &array[1];
const c = &array[2];
const d = a;
try testing.expect(testHashShallow(a) == testHashShallow(d));
try testing.expect(testHashShallow(a) != testHashShallow(c));
try testing.expect(testHashShallow(a) != testHashShallow(b));
try testing.expect(testHashDeep(a) == testHashDeep(a));
try testing.expect(testHashDeep(a) == testHashDeep(c));
try testing.expect(testHashDeep(a) == testHashDeep(b));
try testing.expect(testHashDeepRecursive(a) == testHashDeepRecursive(a));
try testing.expect(testHashDeepRecursive(a) == testHashDeepRecursive(c));
try testing.expect(testHashDeepRecursive(a) == testHashDeepRecursive(b));
}
test "hash slice shallow" {
// 动态分配其中一个数组,确保优化过程
// 不会将其与另一个数组合并。
const array1 = try std.testing.allocator.create([6]u32);
defer std.testing.allocator.destroy(array1);
array1.* = [_]u32{ 1, 2, 3, 4, 5, 6 };
const array2 = [_]u32{ 1, 2, 3, 4, 5, 6 };
// TODO 审查深层/浅层行为——对数组指针和切片的处理可能不正确
var runtime_zero: usize = 0;
_ = &runtime_zero;
const a = array1[runtime_zero..];
const b = array2[runtime_zero..];
const c = array1[runtime_zero..3];
try testing.expect(testHashShallow(a) == testHashShallow(a));
try testing.expect(testHashShallow(a) != testHashShallow(array1));
try testing.expect(testHashShallow(a) != testHashShallow(b));
try testing.expect(testHashShallow(a) != testHashShallow(c));
}
test "hash slice deep" {
// 动态分配其中一个数组,确保优化过程
// 不会将其与另一个数组合并。
const array1 = try std.testing.allocator.create([6]u32);
defer std.testing.allocator.destroy(array1);
array1.* = [_]u32{ 1, 2, 3, 4, 5, 6 };
const array2 = [_]u32{ 1, 2, 3, 4, 5, 6 };
const a = array1[0..];
const b = array2[0..];
const c = array1[0..3];
try testing.expect(testHashDeep(a) == testHashDeep(a));
try testing.expect(testHashDeep(a) == testHashDeep(array1));
try testing.expect(testHashDeep(a) == testHashDeep(b));
try testing.expect(testHashDeep(a) != testHashDeep(c));
}
test "hash struct deep" {
const Foo = struct {
a: u32,
b: u16,
c: *bool,
const Self = @This();
pub fn init(allocator: mem.Allocator, a_: u32, b_: u16, c_: bool) !Self {
const ptr = try allocator.create(bool);
ptr.* = c_;
return Self{ .a = a_, .b = b_, .c = ptr };
}
};
const allocator = std.testing.allocator;
const foo = try Foo.init(allocator, 123, 10, true);
const bar = try Foo.init(allocator, 123, 10, true);
const baz = try Foo.init(allocator, 123, 10, false);
defer allocator.destroy(foo.c);
defer allocator.destroy(bar.c);
defer allocator.destroy(baz.c);
try testing.expect(testHashDeep(foo) == testHashDeep(bar));
try testing.expect(testHashDeep(foo) != testHashDeep(baz));
try testing.expect(testHashDeep(bar) != testHashDeep(baz));
var hasher = Wyhash.init(0);
const h = testHashDeep(foo);
autoHash(&hasher, foo.a);
autoHash(&hasher, foo.b);
autoHash(&hasher, foo.c.*);
try testing.expectEqual(h, hasher.final());
const h2 = testHashDeepRecursive(&foo);
try testing.expect(h2 != testHashDeep(&foo));
try testing.expect(h2 == testHashDeep(foo));
}
test "testHash optional" {
const a: ?u32 = 123;
const b: ?u32 = null;
try testing.expectEqual(testHash(a), testHash(@as(u32, 123)));
try testing.expect(testHash(a) != testHash(b));
try testing.expectEqual(testHash(b), 0x409638ee2bde459); // wyhash 空输入的哈希
}
test "testHash array" {
const a = [_]u32{ 1, 2, 3 };
const h = testHash(a);
var hasher = Wyhash.init(0);
autoHash(&hasher, @as(u32, 1));
autoHash(&hasher, @as(u32, 2));
autoHash(&hasher, @as(u32, 3));
try testing.expectEqual(h, hasher.final());
}
test "testHash multi-dimensional array" {
const a = [_][]const u32{ &.{ 1, 2, 3 }, &.{ 4, 5 } };
const b = [_][]const u32{ &.{ 1, 2 }, &.{ 3, 4, 5 } };
try testing.expect(testHash(a) != testHash(b));
}
test "testHash struct" {
const Foo = struct {
a: u32 = 1,
b: u32 = 2,
c: u32 = 3,
};
const f = Foo{};
const h = testHash(f);
var hasher = Wyhash.init(0);
autoHash(&hasher, @as(u32, 1));
autoHash(&hasher, @as(u32, 2));
autoHash(&hasher, @as(u32, 3));
try testing.expectEqual(h, hasher.final());
}
test "testHash union" {
const Foo = union(enum) {
A: u32,
B: bool,
C: u32,
D: void,
};
const a = Foo{ .A = 18 };
var b = Foo{ .B = true };
const c = Foo{ .C = 18 };
const d: Foo = .D;
try testing.expect(testHash(a) == testHash(a));
try testing.expect(testHash(a) != testHash(b));
try testing.expect(testHash(a) != testHash(c));
try testing.expect(testHash(a) != testHash(d));
b = Foo{ .A = 18 };
try testing.expect(testHash(a) == testHash(b));
b = .D;
try testing.expect(testHash(d) == testHash(b));
}
test "testHash vector" {
const a: @Vector(4, u32) = [_]u32{ 1, 2, 3, 4 };
const b: @Vector(4, u32) = [_]u32{ 1, 2, 3, 5 };
try testing.expect(testHash(a) == testHash(a));
try testing.expect(testHash(a) != testHash(b));
const c: @Vector(4, u31) = [_]u31{ 1, 2, 3, 4 };
const d: @Vector(4, u31) = [_]u31{ 1, 2, 3, 5 };
try testing.expect(testHash(c) == testHash(c));
try testing.expect(testHash(c) != testHash(d));
}
test "testHash error union" {
const Errors = error{Test};
const Foo = struct {
a: u32 = 1,
b: u32 = 2,
c: u32 = 3,
};
const f = Foo{};
const g: Errors!Foo = Errors.Test;
try testing.expect(testHash(f) != testHash(g));
try testing.expect(testHash(f) == testHash(Foo{}));
try testing.expect(testHash(g) == testHash(Errors.Test));
}