golang 内置映射和字符串键的哈希冲突？

Question

我编写了这个函数来为我的测试用例生成随机唯一 ID：

func uuid(t *testing.T) string {
    uidCounterLock.Lock()
    defer uidCounterLock.Unlock()

    uidCounter++
    //return "[" + t.Name() + "|" + strconv.FormatInt(uidCounter, 10) + "]"
    return "[" + t.Name() + "|" + string(uidCounter) + "]"
}

var uidCounter int64 = 1
var uidCounterLock sync.Mutex

为了测试它，我在不同的 goroutine 中从中生成了一堆值，将它们发送到主线程，主线程通过执行 map[v] = map[v] + 1 将结果放入 map[string]int。没有对此地图的并发访问，它是主线程私有的。

var seen = make(map[string]int)
for v := range ch {
    seen[v] = seen[v] + 1
    if count := seen[v]; count > 1 {
        fmt.Printf("Generated the same uuid %d times: %#v\n", count, v)
    }
}

当我将 uidCounter 转换为一个字符串时，我在一个键上遇到了大量的冲突。当我使用 strconv.FormatInt 时，我根本没有遇到任何冲突。

当我说一吨时，我的意思是我刚刚在 2227980 生成的值中得到 1115919 值 [TestUuidIsUnique|�] 的冲突，即 50% 的值在相同的值上发生冲突钥匙。值不相等。对于相同的源代码，我总是会得到相同数量的冲突，所以至少它在某种程度上是确定性的，即可能与竞争条件无关。

我并不惊讶 rune 中的整数溢出会成为一个问题，但我离 2^31 还很远，这无法解释为什么地图认为 50% 的值有同一个键。另外，我不希望哈希冲突影响正确性，只会影响性能，因为我可以遍历映射中的键，所以值存储在那里的某个地方。

在输出中，所有打印的符文都是0xEFBFBD。它与最高有效 unicode 代码点的位数相同，但两者都不匹配。

Generated the same uuid 2 times: "[TestUuidIsUnique|�]"
Generated the same uuid 3 times: "[TestUuidIsUnique|�]"
Generated the same uuid 4 times: "[TestUuidIsUnique|�]"
Generated the same uuid 5 times: "[TestUuidIsUnique|�]"
...
Generated the same uuid 2047 times: "[TestUuidIsUnique|�]"
Generated the same uuid 2048 times: "[TestUuidIsUnique|�]"
Generated the same uuid 2049 times: "[TestUuidIsUnique|�]"
...

这是怎么回事？ go 作者是否假设 hash(a) == hash(b) 意味着 a == b 用于字符串？或者我只是想念一些愚蠢的东西？ go test -race 也没有抱怨。

我在 macOS 10.13.2 和 go version go1.9.2 darwin/amd64。

Answer 1

无效符文的字符串转换returns 包含 unicode 替换字符的字符串：“�”。

使用 strconv 包将整数转换为文本。

golang 内置映射和字符串键的哈希冲突？

Hash collisions for golang built-in map and string keys?

concurrency

hash

dictionary

go

goroutine