我正在制作一个结构，其作用就像String，不同之处在于它仅处理 Unicode UTF-32 标量值。因此，它是一个数组UInt32. (See 这个问题了解更多背景。）

我想做的事

我希望能够使用我的自定义ScalarStringstruct 作为字典中的键。例如：

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
}

Problem

为了做到这一点，ScalarString需要实施可哈希协议。我想我可以做这样的事情：

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
}

但后来我发现斯威夫特数组没有hashValue.

我读到了什么

文章在 Swift 中实现 Hashable 协议的策略有很多很棒的想法，但我没有看到任何在这种情况下可以很好地发挥作用的想法。具体来说，

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

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

• 实现 Swift 的 Hashable 协议
• Swift 比较协议
• 完美的哈希函数
• Swift 数组和字典中自定义对象的成员资格
• 如何为您的自定义类实现 Hashable
• 在 Swift 中编写良好的 Hashable 实现

Question

Swift Strings 有一个hashValue财产，所以我知道这是可能做到的。

我将如何创建一个hashValue对于我的自定义结构？

Updates

更新1：我想做一些不涉及转换的事情String然后使用String's hashValue。我制作自己的结构的全部目的是为了避免做很多事情String转换。String得到它的hashValue从某个地方。看来我可以用同样的方法得到它。

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

• Java hashCode算法
• C 算法
• 字符串的哈希函数（所以C中的问题和答案）
• 哈希教程（弗吉尼亚理工大学算法可视化研究小组）
• 通用哈希函数算法

Update 3

我不想导入任何外部框架，除非这是推荐的方法。

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

Update

马丁·Rwrites:

As of 斯威夫特 4.1，编译器可以综合Equatable and Hashable如果所有成员都符合，则自动实现类型一致性 Equatable/Hashable (SE0185)。并且截至斯威夫特 4.2，高质量的哈希 组合器内置于 Swift 标准库（SE-0206）中。

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

struct ScalarString: Hashable, ... {

    private var scalarArray: [UInt32] = []

    // ... }

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

旧答案：

提交我的答案后，这个答案已被完全重写代码审查的原始答案.

如何实现Hashable协议

The 可哈希协议允许您使用自定义类或结构作为字典键。为了实现这个协议，你需要

1. 实施等值协议（Hashable继承自Equatable）
2. 返回一个计算出来的hashValue

这些要点是根据文档中给出的公理得出的：

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

where x and y是某种类型的值。

实施 Equatable 协议

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

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

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

返回一个计算出来的hashValue

您的自定义类或结构还必须有一个计算的hashValue多变的。一个好的哈希算法将提供广泛的哈希值。但需要注意的是，您不需要保证哈希值都是唯一的。当两个不同的值具有相同的哈希值时，这称为哈希冲突。当发生碰撞时，它需要一些额外的工作（这就是为什么需要良好的分布），但有些碰撞是可以预料的。据我了解，==函数做了额外的工作。 （Update: 看起来像== may do all工作。)

有多种计算哈希值的方法。例如，您可以执行一些简单的操作，例如返回数组中的元素数量。

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

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

DJB 哈希函数

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

快速实现由@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
} 

The &+运营商允许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) {
            ($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
}

其他有帮助的阅读

• 哪种哈希算法最适合唯一性和速度？
• 溢出运算符
• 为什么 5381 和 33 在 djb2 算法中如此重要？
• 如何处理哈希冲突？

Credits

非常感谢 Code Review 中的 Martin R。我的重写很大程度上是基于他的回答。如果您觉得这有帮助，请给他点赞。

Update

Swift 现在是开源的，所以可以看看如何hashValue实施用于String来自源代码。它似乎比我在这里给出的答案更复杂，我没有花时间对其进行全面分析。您可以自己这样做。