ios - 如何在 Swift 中为 Int 数组(自定义字符串结构)实现 Hashable 协议(protocol)

Question

我正在制作一个类似于 String 的结构，只是它只处理 Unicode UTF-32 标量值。因此，它是一个 UInt32 数组。 (有关更多背景信息，请参阅 this question。)

我想做什么

我希望能够使用我的自定义 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(我使用的是结构，而不是类)
• 继承自 NSObject(我使用的是结构，而不是类)

以下是我读到的一些其他内容:

• 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属性(property)，所以我知道这是可能的。

如何为我的自定义结构创建一个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

更新

马丁 R 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] = []

    // ... }

因此，下面的答案需要重写(再次)。在此之前，请引用上面链接中 Martin R 的回答。

---

旧答案:

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

如何实现Hashable协议(protocol)

Hashable protocol允许您使用自定义类或结构作为字典键。为了实现这个协议(protocol)，你需要

1. 实现Equatable protocol (Hashable 继承自 Equatable)
2. 返回计算的hashValue

这些要点遵循文档中给出的公理:

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

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

实现 Equatable 协议(protocol)

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

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

== 函数是全局函数，因此它在您的类或结构之外。

返回计算的hashValue

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

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

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

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

DJB 哈希函数

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

Swift 实现 provided by @MartinR如下:

var hashValue: Int {
    return self.scalarArray.reduce(5381) {
        ($0 << 5) &+ $0 &+ Int($1)
    }
}

这是我原始实现的改进版本，但让我也包括旧的扩展形式，这对于不熟悉 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 协议(protocol)相关的整个示例代码。 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) {
            ($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
}

其他有帮助的读物

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

致谢

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

更新

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