京公网安备11010502063487号哈希表要防的是“有人故意构造一批碰撞的键把它拖垮”,办法就是让哈希函数带一个随机种子,攻击者事先算不出来。hash/maphash 把 Go 内置 map 用的这种做法开放成了公共包。这篇看它的种子怎么随进程变化、分布够不够均匀、速度怎么样。
maphash.String(seed1, "hello") 进程 1:0ae496e7eaa7f835 进程 2:46fa68a0a0c0d61e 进程 3:6df89d1f6f5ae8ad
同一个进程里再算一次 进程 1:0ae496e7eaa7f835 进程 2:46fa68a0a0c0d61e 进程 3:6df89d1f6f5ae8ad
maphash.String(seed2, "hello")(同一进程里的另一个种子) 进程 1:32e473bff57e28f9 进程 2:7c432ecef34c9ce4 进程 3:6409fa17acd38561
maphash.Hash 分两段写入 "he" + "llo"(seed1) 进程 1:0ae496e7eaa7f835 进程 2:46fa68a0a0c0d61e 进程 3:6df89d1f6f5ae8ad
maphash.Comparable(seed1, key{1,"x"}) 进程 1:a7ca6d3e4bdf0e53 进程 2:980100820e1111c6 进程 3:7b6e52001acd6d95
同一个值再算一次 进程 1:a7ca6d3e4bdf0e53 进程 2:980100820e1111c6 进程 3:7b6e52001acd6d95
maphash.Comparable(seed1, key{2,"x"})(不同的值) 进程 1:b7e81071bc8eed0e 进程 2:3ff15aaa094853a0 进程 3:2a8d2379a9791f34
FNV-1a 64 位 "hello" 进程 1:a430d84680aabd0b 进程 2:a430d84680aabd0b 进程 3:a430d84680aabd0bmaphash.MakeSeed() 每次都生成新的随机种子,同一个字符串在三个进程里的哈希值完全不同;同一进程内同一个种子、同一输入则稳定。FNV-1a 这类固定算法在任何进程里都是 a430d84680aabd0b,所以攻击者可以离线算出一批碰撞的键。因此 maphash 的值不能持久化、不能跨进程比较。
maphash 每个桶最少 9900、最多 10132;FNV-1a 每个桶最少 9948、最多 10052(理想值 10000)
16 万个连续编号的键落进 16 个桶,maphash 每桶 9900 到 10132 个,FNV-1a 是 9948 到 10052,都很均匀。速度上 16 字节输入三者差不多(4–7 ns);1 KiB 时 maphash.String 77 ns,FNV-1a 1176 ns,差约 15 倍。
16 字节输入:maphash.String 4 ns(4000 MB/s);FNV-1a 64 7 ns(2286 MB/s);CRC32-C 4 ns(4000 MB/s) 1024 字节输入:maphash.String 77 ns(13299 MB/s);FNV-1a 64 1176 ns(871 MB/s);CRC32-C 104 ns(9846 MB/s)
文档建议每个哈希表或数据结构实例用自己的种子;它不是密码学安全的。maphash.Comparable 可以直接哈希可比较的值(本文试了一个含 int 和 string 的结构体)。
两个键完全相同的 map 的遍历顺序:[6 7 0 1 2 3 4 5] | [1 2 3 4 5 6 7 0] 两个键完全相同的 map 的遍历顺序:[2 3 4 5 6 7 0 1] | [0 1 2 3 4 5 6 7]
内置 map 同样有随机化:两个键完全相同的 map,遍历的起点也不同(这里的小 map 是环形轮转)。这说明遍历顺序不能依赖,前面“map 遍历顺序”一篇已经单独讨论过。
Package maphash provides hash functions on byte sequences and comparable values. It also defines Hasher, the interface between a hash function and a hash table. These hash functions are intended to be used to implement hash tables, Bloom filters, and other data structures that need to map arbitrary strings or byte sequences to a uniform distribution on unsigned 64-bit integers. Each different instance of a hash table or data structure should use its own Seed. The hash functions are not cryptographically secure. (See crypto/sha256 and crypto/sha512 for cryptographic use.)
文档还定义了 Hasher 接口(哈希函数和哈希表之间的接口),本文没有使用。