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

Question

我正在创建一个类似于a的结构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.

我读了什么

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

• 对象属性(数组没有hashValue)
• ID属性(不确定如何实现这一点)
• 公式(看起来像32位整数字符串的任何公式将是处理器繁重并且有很多整数溢出)
• ObjectIdentifier(我使用的是结构,而不是类)
• 继承自NSObject(我使用的是结构,而不是类)

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

• 实现Swift的Hashable协议
• 快速比较协议
• 完美的哈希函数
• Swift Arrays和Dictionaries中自定义对象的成员身份
• 如何为您的自定义类实现Hashable
• 在Swift中编写一个好的Hashable实现

题

Swift Strings有一个hashValue属性,所以我知道它可以做到.

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

更新

更新1:我想做一些不涉及转换String然后使用String的东西hashValue.我制作自己的结构的全部意义在于我可以避免进行大量的String转换.String得到它hashValue来自某个地方.好像我可以用同样的方法得到它.

更新2:我一直在研究其他上下文中字符串哈希码算法的实现.我知道哪个最好并且在Swift中表达它们有点困难.

• Java hashCode算法
• C算法
• 字符串的哈希函数(SO中的问题和答案)
• 哈希教程(弗吉尼亚理工大学算法可视化研究组)
• 通用散列函数算法

更新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的答案.

旧答案:

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

如何实现Hashable协议

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

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

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

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

where x和y是某些Type的值.

实现Equatable协议

为了实现Equatable协议,您可以定义类型使用==(等价)运算符的方式.在您的示例中,等价可以像这样确定:

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

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

返回计算 hashValue

您的自定义类或结构也必须具有计算hashValue变量.良好的散列算法将提供各种散列值.但是,应该注意,您不需要保证哈希值都是唯一的.当两个不同的值具有相同的哈希值时,这称为哈希冲突.当发生碰撞时需要一些额外的工作(这就是为什么需要良好的分布),但是可能会发生一些碰撞.据我了解,该==功能可以完成额外的工作.(更新:看起来==可能会完成所有工作.)

有许多方法可以计算哈希值.例如,您可以执行一些简单的操作,即返回数组中的元素数.

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

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

DJB Hash功能

与字符串一起使用的常见哈希函数是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溢出和长串重新开始.

大图

我们已经查看过各个部分,但现在让我展示与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算法中如此重要？
• 哈希冲突是如何处理的？

积分

非常感谢Martin R在Code Review中的表现.我的重写主要基于他的回答.如果你觉得这很有帮助,那么请给他一个upvote.

更新

Swift现在是开源的,因此可以从源代码中看到如何hashValue实现.它似乎比我在这里给出的答案更复杂,我没有花时间对它进行全面分析.随意自己做.String

Answer 2

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

好的，我Hashable通过使用来自 CommonCrypto 框架的 SHA-256 散列算法提前使用该协议扩展了所有数组。你必须把

#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. 这是丑陋的，但速度快，没有多少几乎没有哈希冲突肯定

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

Int大小为 n 的随机填充数组平均运行 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倍。我并不是说使用字符串是一个很好的解决方案，但它是我们现在唯一可以比较的方法