如何在 Swift 中为 Int 数组（自定义字符串结构）实现 Hashable Protocol

Question

我正在制作一个类似于 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 Protocol。我以为我可以做这样的事情：

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 arrays 没有 hashValue。

我读了什么

文章 Strategies for Implementing the Hashable Protocol in Swift 有很多很棒的想法，但我没有看到任何在这种情况下看起来会很好的想法。具体来说，

对象属性（数组没有hashValue）
ID 属性（不知道怎么实现）
公式（似乎任何用于 32 位整数字符串的公式都会占用大量处理器资源，并且有很多整数溢出）
ObjectIdentifier（我使用的是结构，而不是 class）
继承自 NSObject（我使用的是结构，而不是 class）

这是我读到的一些其他内容：

Implementing Swift's Hashable Protocol
Swift Comparison Protocols
Perfect hash function
Membership of custom objects in Swift Arrays and Dictionaries
How to implement Hashable for your custom class
Writing a good Hashable implementation in Swift

问题

Swift 字符串有一个 hashValue 属性，所以我知道这是可以做到的。

如何为我的自定义结构创建 hashValue？

更新

更新 1： 我想做一些不涉及转换为 String 然后使用 String 的 hashValue .我制作自己的结构的全部目的是为了避免进行大量 String 转换。 String 从某处获取 hashValue。看来我可以用同样的方法得到它。

更新 2： 我一直在研究其他上下文中字符串哈希码算法的实现。不过，我很难知道哪个是最好的并用 Swift 来表达它们。

Java hashCode algorithm
C algorithms
hash function for string（C 中的 SO 问题和答案）
Hashing tutorial（弗吉尼亚理工大学算法可视化研究组）
General Purpose Hash Function Algorithms

更新 3

我宁愿不导入任何外部框架，除非这是完成这些事情的推荐方法。

我提交了一个使用 DJB 哈希函数的可能解决方案。

Answer 1

一个建议 - 由于您正在为 String 建模，将 [UInt32] 数组转换为 String 并使用 String 的 hashValue?像这样：

var hashValue : Int {
    get {
        return String(self.scalarArray.map { UnicodeScalar([=10=]) }).hashValue
    }
}

这也可以让您方便地将自定义 struct 与 String 进行比较，尽管这是否是个好主意取决于您尝试做什么...

另请注意，使用这种方法，如果 String 的表示在规范上等价，ScalarString 的实例将具有相同的 hashValue，这可能是您想要的，也可能不是您想要的.

所以我想如果您希望 hashValue 代表唯一的 String，我的方法会很好。如果您希望 hashValue 代表一个唯一的 UInt32 值序列，@Kametrixom 的答案就是要走的路...

Answer 2

这不是一个非常优雅的解决方案，但效果很好：

"\(scalarArray)".hashValue

或

scalarArray.description.hashValue

它只使用文本表示作为哈希源

Answer 3

编辑（2017 年 5 月 31 日）：请参阅已接受的答案。这个答案 几乎只是关于如何使用 CommonCrypto 框架

的演示

好的，我继续使用 CommonCrypto 框架中的 SHA-256 散列算法，使用 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]
    }
}

编辑（2017 年 5 月 31 日）：不要这样做，即使 SHA256 几乎没有散列冲突，但通过散列相等性定义相等性是错误的想法

public func ==<T>(lhs: [T], rhs: [T]) -> Bool {
    return lhs.hashValue == rhs.hashValue
}

这与 CommonCrypto 一样好。它很丑，但速度很快，而且不多肯定几乎没有哈希冲突

编辑（2015 年 7 月 15 日）：我刚刚做了一些速度测试：

大小为 n 的随机填充 Int 数组平均运行超过 1000 次

n      -> time
1000   -> 0.000037 s
10000  -> 0.000379 s
100000 -> 0.003402 s

而使用字符串散列方法：

n      -> time
1000   -> 0.001359 s
10000  -> 0.011036 s
100000 -> 0.122177 s

所以 SHA-256 方式比字符串方式快 33 倍左右。我并不是说使用字符串是一个很好的解决方案，但这是我们现在唯一可以比较的解决方案

Answer 4

更新

马丁 writes:

As of Swift 4.1, the compiler can synthesize Equatable and Hashable for types conformance automatically, if all members conform to Equatable/Hashable (SE0185). And as of Swift 4.2, a high-quality hash combiner is built-in into the Swift standard library (SE-0206).

Therefore there is no need anymore to define your own hashing function, it suffices to declare the conformance:
struct ScalarString: Hashable, ... {

    private var scalarArray: [UInt32] = []

    // ... }

因此，下面的答案需要重写（再次）。在此之前，请参考上面 link 中 Martin R 的回答。

旧答案：

这个答案在提交我的 original answer to code review 后被完全重写了。

如何实现 Hashable 协议

Hashable protocol 允许您使用自定义 class 或结构作为字典键。为了实施此协议，您需要

实现Equatable protocol（Hashable继承自Equatable）
Return 一个计算 hashValue

这些要点来自文档中给出的公理：

x == y implies x.hashValue == y.hashValue

其中 x 和 y 是某些类型的值。

实施 Equatable 协议

为了实现 Equatable 协议，您定义您的类型如何使用 ==（等价）运算符。在您的示例中，可以这样确定等效性：

func ==(left: ScalarString, right: ScalarString) -> Bool {
    return left.scalarArray == right.scalarArray
}

== 函数是全局函数，因此它超出了您的 class 或结构。

Return 一个计算的 `hashValue`

您的自定义 class 或结构还必须具有计算的 hashValue 变量。一个好的散列算法会提供范围广泛的散列值。但是需要注意的是，你不需要保证哈希值都是唯一的。当两个不同的值具有相同的散列值时，这称为散列冲突。当发生碰撞时它需要一些额外的工作（这就是为什么需要良好的分布），但一些碰撞是可以预料的。据我了解， == 函数完成了额外的工作。 (更新:)

计算散列值的方法有很多种。例如，您可以做一些简单的事情，例如返回数组中的元素数。

var hashValue: Int {
    return self.scalarArray.count
}

每当两个数组具有相同数量的元素但不同的值时，这将导致散列冲突。 NSArray 显然使用了这种方法。

DJB 哈希函数

处理字符串的常见哈希函数是 DJB 哈希函数。这是我将要使用的，但请查看其他一些 here。

Swift 实现 provided by @MartinR 如下：

var hashValue: Int {
    return self.scalarArray.reduce(5381) {
        ([=13=] << 5) &+ [=13=] &+ Int()
    }
}

这是我最初实现的改进版本，但让我也包括旧的扩展形式，这对于不熟悉 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 溢出并重新开始。

大图

我们已经查看了各个部分，但现在让我展示与 Hashable 协议相关的整个示例代码。 ScalarString 是问题中的自定义类型。当然，这对不同的人来说会有所不同。

// 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) {
            ([=15=] << 5) &+ [=15=] &+ Int()
        }
    }
}

// required function for the Equatable protocol, which Hashable inheirits from
func ==(left: ScalarString, right: ScalarString) -> Bool {
    return left.scalarArray == right.scalarArray
}

其他有帮助的读物

Which hashing algorithm is best for uniqueness and speed?
Overflow Operators
Why are 5381 and 33 so important in the djb2 algorithm?

学分

非常感谢代码审查中的 Martin R。我的重写主要基于 his answer。如果觉得有帮助，请给他点个赞。

更新

Swift 现在是开源的，所以可以从 source code 中看到 hashValue 是如何为 String 实现的。它似乎比我在这里给出的答案更复杂，我没有花时间对其进行全面分析。随意自己做。

如何在 Swift 中为 Int 数组（自定义字符串结构）实现 Hashable Protocol

How to implement the Hashable Protocol in Swift for an Int array (a custom string struct)

ios

arrays

string

swift

hashtable

我想做什么

问题

我读了什么

问题

更新

更新

旧答案：

如何实现 Hashable 协议

实施 Equatable 协议

Return 一个计算的 `hashValue`

大图

其他有帮助的读物

学分

更新

如何在 Swift 中为 Int 数组（自定义字符串结构）实现 Hashable Protocol

How to implement the Hashable Protocol in Swift for an Int array (a custom string struct)

ios

arrays

string

swift

hashtable

我想做什么

问题

我读了什么

问题

更新

更新

旧答案：

如何实现 Hashable 协议

实施 Equatable 协议

Return 一个计算的 hashValue

大图

其他有帮助的读物

学分

更新

Return 一个计算的 `hashValue`