Swift协议Hashable中hashValue的性能考虑

Question

除了唯一的整数，选择在Swift中实现Hashable协议时是否有任何性能考虑？例如，我选择的整数值的大小会影响后台数组的大小吗？也就是说，如果我将一个hashValue分配为4000，并将其插入到一个Set中，那么后台数组的长度是否需要至少为4000？请注意，本文中的HTML标签不做修改。

- gloo

---

这里的“backing array”是什么意思以及为什么hashValue会与之有任何关系并不清楚。（我猜答案是否定的，但我真的不理解问题。） - Rob Napier

我特别考虑了 Set。抱歉之前没有提到。 - gloo

我猜你认为集合是作为哈希值为索引的数组实现的？但这不是它们的实现方式。它们是哈希表。https://en.wikipedia.org/wiki/Hash_table。哈希值本身并不重要。理想情况下，它在整个Int空间中是随机的，因此没有冲突，并且表是平衡的（我记不清他们是否使用二叉树了；你可以在这里查看：https://github.com/apple/swift/blob/master/stdlib/public/core/HashedCollections.swift.gyb） - Rob Napier

但是散列表不需要动态支持数组吗？也许我对散列表的工作方式有误解。维基百科文章使用散列值索引到“存储桶”，我假设这是一个数组。 - gloo

在一天结束时，所有的计算机内存都是一个长数组，所以当然，大多数数据结构都有某种自由索引的内存，但深入了解哈希表的构建方式。它与返回哈希值的大小无关。 - Rob Napier

Answer 1

hashValue 不一定是唯一的。在绝大多数情况下，它不能是唯一的（任何比64位更大的类型都必然具有比其哈希更多的可能状态）。您无法选择整数的大小。它将始终为 Int（即机器字大小）。

hashValue 应该快速，并且理想情况下应为 O(1)。它经常用于优化相等检查（这可能非常缓慢）。

hashValue 的最简单实现如下：

var hashValue: Int { return 1 }

这是一个完全有效的哈希值。它不是特别好的哈希值，但它满足所有要求。它计算速度快，所有相等的对象将具有相等的哈希值（这是一个要求; 相反的情况不需要：相等的哈希值可能不意味着相等的对象）。

- Rob Napier