如何在Swift中为Int数组实现Hashable协议（自定义string结构）
我做了一个像String一样的结构，只是它只处理Unicode UTF-32标量值。 因此，它是一个UInt32的数组。 （有关更多背景，请参阅此问题 。）
我想做的事
我希望能够使用我的自定义ScalarString结构作为字典中的键。 例如：
var suffixDictionary = [ScalarString: ScalarString]() // Unicode key, rendered glyph value // populate dictionary suffixDictionary[keyScalarString] = valueScalarString // ... // check if dictionary contains Unicode scalar string key if let renderedSuffix = suffixDictionary[unicodeScalarString] { // do something with value }
问题
为了做到这一点， ScalarString需要实现Hashable协议 。 我以为我可以做这样的事情：
struct ScalarString: Hashable { private var scalarArray: [UInt32] = [] var hashValue : Int { get { return self.scalarArray.hashValue // error } } } func ==(left: ScalarString, right: ScalarString) -> Bool { return left.hashValue == right.hashValue }
但后来我发现， Swift数组没有hashValue 。
我读过的
在Swift中实现哈希协议的策略有很多伟大的想法，但我没有看到任何在这种情况下运行的好像。 特别，
- 对象属性 （数组是没有
hashValue） - ID属性 （不知道如何实现这个）
- 公式 （似乎任何一个32位整数string的公式将是处理器沉重，并有很多整数溢出）
- ObjectIdentifier （我正在使用一个结构，而不是一个类）
- 从NSObjectinheritance （我正在使用一个结构，而不是一个类）
这里是我读的其他一些东西：
- 实现Swift的Hashable协议
- Swift比较协议
- 完美的散列函数
- Swift数组和字典中的自定义对象的成员资格
- 如何为自定义类实现Hashable
- 在Swift中编写一个好的Hashable实现
题
Swiftstring有一个hashValue属性，所以我知道这是可以做到的。
我将如何为我的自定义结构创build一个hashValue ？
更新
更新1：我想做一些不涉及转换为String ，然后使用String的hashValue 。 我制作自己的结构的目的是为了避免大量的String转换。 String从某处获取它的hashValue 。 我似乎可以用同样的方法得到它。
更新2：我一直在研究从其他上下文的string哈希码algorithm的实现。 不过，我知道哪一个是最好的，并且在Swift中expression出来有点困难。
- Java的
hashCodealgorithm - Calgorithm
- string散列函数 （在C中的问题和答案）
- 散列教程 （弗吉尼亚理工大学algorithm可视化研究小组）
- 通用散列函数algorithm
更新3
我不想导入任何外部框架，除非这是推荐的方法。
我使用DJB Hash函数提交了一个可能的解决scheme。
提交我的原始答案代码审查后，这个答案已经完全重写。
如何实现到Hashable协议
Hashable协议允许您使用自定义类或结构作为字典键。 为了实现这个协议你需要
- 实现Equatable协议 （Hashable从Equatableinheritance）
- 返回一个计算
hashValue
这些观点来自文献中给出的公理：
x == y意味着x.hashValue == y.hashValue
其中x和y是某些Type的值。
实施可衡量的协议
为了实现可衡量协议，您可以定义types如何使用== （等价）运算符。 在你的例子中，可以这样来确定等价：
func ==(left: ScalarString, right: ScalarString) -> Bool { return left.scalarArray == right.scalarArray }
==函数是全局的，所以它不在你的类或结构之内。
返回一个计算hashValue
您的自定义类或结构也必须具有计算的hashValuevariables。 一个好的散列algorithm将提供大范围的散列值。 但是，应该注意的是，您不需要保证散列值都是唯一的。 当两个不同的值具有相同的散列值时，这被称为散列冲突。 碰撞时需要一些额外的工作（这就是为什么一个好的分配是可取的），但一些碰撞是可以预料的。 据我了解， ==function做了额外的工作。 （ 更新 ： 它看起来像==可能会做所有的工作。 ）
有很多方法可以计算散列值。 例如，你可以做一些简单的事情，例如返回数组中的元素数量。
var hashValue: Int { return self.scalarArray.count }
每次两个数组具有相同数量的元素但是不同的值时，这将会产生散列冲突。 NSArray显然使用这种方法。
DJB哈希函数
与string一起使用的常用散列函数是DJB散列函数。 这是我将使用的，但在这里检查一些其他人。
@MartinR提供的 Swift实现如下：
var hashValue: Int { return self.scalarArray.reduce(5381) { ($0 << 5) &+ $0 &+ Int($1) } }
这是我的原始实现的改进版本，但让我也包括旧的扩展forms，这可能是更多的人不熟悉reduce可读性。 我相信这相当于：
var hashValue: Int { // DJB Hash Function var hash = 5381 for(var i = 0; i < self.scalarArray.count; i++) { hash = ((hash << 5) &+ hash) &+ Int(self.scalarArray[i]) } return hash }
&+运算符允许Int溢出并重新开始长string。
大图片
我们已经看过这些部分，但是现在让我来展示整个示例代码，因为它与Hashable协议有关。 ScalarString是问题的自定义types。 当然，这对于不同的人会有所不同。
// Include the Hashable keyword after the class/struct name struct ScalarString: Hashable { private var scalarArray: [UInt32] = [] // required var for the Hashable protocol var hashValue: Int { // DJB hash function return self.scalarArray.reduce(5381) { ($0 << 5) &+ $0 &+ Int($1) } } } // required function for the Equatable protocol, which Hashable inheirits from func ==(left: ScalarString, right: ScalarString) -> Bool { return left.scalarArray == right.scalarArray }
其他有用的阅读
- 哪种哈希algorithm最适合独特性和速度？
- 溢出操作符
- 为什么5381和33在djb2algorithm中如此重要？
- 如何处理散列冲突？
积分
非常感谢Code Review的Martin R。 我的重写主要是基于他的回答 。 如果你发现这有帮助，那么请给他一个upvote。
更新
Swift现在是开源的，因此可以从源代码中看到如何为String实现hashValue 。 这似乎比我在这里给出的答案更为复杂，我没有花时间来充分分析。 随意自己这样做。
一个build议 – 因为你正在build模一个String ，它会工作将你的[UInt32]数组转换为一个String并使用String的hashValue ？ 喜欢这个：
var hashValue : Int { get { return String(self.scalarArray.map { UnicodeScalar($0) }).hashValue } }
这可以方便地让你比较你的自定义struct与String ，以及是否这是一个好主意取决于你想要做什么…
还要注意的是，使用这种方法，如果ScalarString实例的String表示是正则等价的，那么它们将具有相同的hashValue ，这可能是也可能不是你想要的。
所以我想，如果你想hashValue来表示一个唯一的String ，我的方法是好的。 如果你想hashValue表示一个独特的UInt32值序列，@ Kametrixom的答案是要走的路…
编辑（17五月'17）：请参阅接受的答案。 这个答案几乎就是如何使用CommonCrypto框架的一个演示
好吧，通过使用CommonCrypto框架中的SHA-256哈希algorithm，我获得了Hashable ，并使用Hashable协议扩展了所有数组。 你必须放
#import <CommonCrypto/CommonDigest.h>
进入您的桥接头为此工作。 这是一个耻辱，指针必须使用，虽然：
extension Array : Hashable, Equatable { public var hashValue : Int { var hash = [Int](count: Int(CC_SHA256_DIGEST_LENGTH) / sizeof(Int), repeatedValue: 0) withUnsafeBufferPointer { ptr in hash.withUnsafeMutableBufferPointer { (inout hPtr: UnsafeMutableBufferPointer<Int>) -> Void in CC_SHA256(UnsafePointer<Void>(ptr.baseAddress), CC_LONG(count * sizeof(Element)), UnsafeMutablePointer<UInt8>(hPtr.baseAddress)) } } return hash[0] } }
编辑（17五月'17）：不要这样做，即使SHA256几乎没有哈希冲突，这是一个错误的想法，通过哈希相等定义相等
public func ==<T>(lhs: [T], rhs: [T]) -> Bool { return lhs.hashValue == rhs.hashValue }
这与CommonCrypto一样好。 这是丑陋的，但很快， 没有多less肯定没有哈希碰撞
编辑（15年15月15日）：我只是做了一些速度testing：
随机填充的大小为n的Int数组平均需要超过1000次运行
n -> time 1000 -> 0.000037 s 10000 -> 0.000379 s 100000 -> 0.003402 s
而用string哈希方法：
n -> time 1000 -> 0.001359 s 10000 -> 0.011036 s 100000 -> 0.122177 s
所以SHA-256的方式比string快33倍。 我并不是说使用string是一个很好的解决scheme，但是现在我们只能把它与之比较
这不是一个非常优雅的解决scheme，但它很好地工作：
"\(scalarArray)".hashValue
要么
scalarArray.description.hashValue
它只是使用文本表示作为散列源
