如何在Swift中为Int数组（自定义字符串结构）实现哈希协议

Question

我正在制作一个类似于的结构String，只是它只处理UnicodeUTF-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数组没有hashValue。

我读了什么

文章在斯威夫特实施哈希的协议策略有很多伟大的想法，但我没有看到任何这似乎是他们会在这种情况下很好地工作。特别，

• 对象属性 （数组没有hashValue）
• ID属性 （不确定如何很好地实现）
• 公式 （似乎任何32位整数字符串的公式都会占用大量处理器资源，并且有很多整数溢出）
• ObjectIdentifier （我使用的是结构，而不是类）
• 从NSObject继承 （我使用的是结构，而不是类）

这是我阅读的其他内容：

• 实现Swift的Hashable协议
• 快速比较协议
• 完善的哈希函数
• Swift数组和字典中的自定义对象的成员资格
• 如何为您的自定义类实现Hashable

题

Swift字符串具有一个hashValue属性，因此我知道可以做到。

如何hashValue为自定义结构创建一个？

更新

更新1：
我想做一些不涉及转换为String，然后使用String的的事情hashValue。建立我自己的结构的全部目的是为了避免进行大量String转换。从某个地方String得到它hashValue。看来我可以使用相同的方法来获得它。

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

• Java hashCode算法
• C算法
• 哈希教程（弗吉尼亚州技术算法可视化研究组）
• 通用哈希函数算法

更新3

我宁愿不导入任何外部框架，除非这是进行这些操作的推荐方法。

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

Answer 1

更新资料

马丁·R 写道：

从 Swift 4.1开始 ， 如果所有成员都符合Equatable /
Hashable（SE0185），则编译器可以自动进行合成Equatable并Hashable实现类型一致性。从 Swift 4.2开始
，Swift标准库（SE-0206）中内置了一个高质量的哈希组合器。

因此，不再需要定义自己的哈希函数，只需声明一致性即可：

struct ScalarString: Hashable, ... {

    private var scalarArray: [UInt32] = []

    // ... }

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

旧答案：

将我的原始答案提交给代码审查后，该答案已被完全重写。

如何实现到哈希协议

该哈希的协议允许您使用您的自定义类或结构作为字典键。为了实施此协议，您需要

1. 实现Equatable协议（Hashable继承自Equatable）
2. 返回计算结果 hashValue

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

x == y 暗示 x.hashValue == y.hashValue

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

实施平等协议

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

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

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

返回计算结果 hashValue

您的自定义类或结构还必须具有一个计算hashValue变量。一个好的哈希算法将提供广泛的哈希值。但是，应注意，您不必保证哈希值都是唯一的。当两个不同的值具有相同的哈希值时，这称为哈希冲突。发生冲突时，这需要一些额外的工作（这就是为什么需要良好的分布）的原因，但是某些冲突是可以预期的。据我了解，该==功能可以完成额外的工作。（

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

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

每当两个数组具有相同数量的元素但值不同时，就会产生哈希冲突。NSArray显然使用这种方法。

DJB哈希函数

DJB哈希函数是与字符串一起使用的常见哈希函数。这是我将要使用的那个，但是在这里请查看其他一些。

@MartinR提供的 Swift实现如下：

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溢出和长串重新开始。

大图景

我们已经研究了各个部分，但现在让我展示与哈希协议相关的整个示例代码。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
}

其他有用的阅读

• 哪种哈希算法最适合唯一性和速度？
• 溢出运算符

学分

非常感谢CodeReview中的MartinR。我的改写主要是基于他的回答。如果您觉得这有帮助，请给他点赞。

更新资料

Swift现在是开源的，因此可以从源代码中了解如何hashValue实现。它似乎比我在这里给出的答案更复杂，并且我还没有花时间对它进行全面分析。自己动手做。String