首页 文章

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

提问于
浏览 次
40

我正在创建一个类似于 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继承（我使用的是结构，而不是类）

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

问题

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

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

更新

Update 1: 我想做一些不涉及转换为 String 然后使用 String 的 hashValue 的事情 . 我制作自己的结构的全部意义在于我可以避免做很多 String 转换 . String 从某处得到它 hashValue . 好像我可以用同样的方法得到它 .

Update 2: 我知道哪个最好并且在Swift中表达它们有点困难 .

Update 3

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

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

ios arrays string swift hashtable

4 回答

  • 4

    更新

    马丁R writes：

    从Swift 4.1开始，如果所有成员都符合Equatable / Hashable（SE0185），编译器可以自动为类型一致性合成Equatable和Hashable . 从Swift 4.2开始，Swift标准库（SE-0206）内置了一个高质量的哈希合并器 . 因此，不再需要定义自己的散列函数，只需声明一致性：struct ScalarString：Hashable，... {

    private var scalarArray：[UInt32] = []

    // ...}

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

    旧答案：

    提交original answer to code review后，此答案已完全重写 .

    如何实现Hashable协议

    Hashable protocol允许您将自定义类或结构用作字典键 . 为了实现此协议，您需要

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

    x == y表示x.hashValue == y.hashValue

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

    实现Equatable协议

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

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

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

    返回计算出的hashValue

    您的自定义类或结构也必须具有计算的 hashValue 变量 . 良好的散列算法将提供各种散列值 . 但是，应该注意，您不需要保证哈希值都是唯一的 . 当两个不同的值具有相同的哈希值时，这称为哈希冲突 . 当发生碰撞时需要一些额外的工作（这就是为什么需要良好的分布），但是可能会发生一些碰撞 . 据我了解， == 函数可以完成额外的工作 . （ Update ：It looks like == may do all the work.）

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

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

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

    DJB Hash Function

    与字符串一起使用的常见哈希函数是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协议相关的整个示例代码 . 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
}

    其他有用的阅读

    学分

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

    更新

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

    回复于
  • 4

    它不是一个非常优雅的解决方案，但它很好地工作：

    "\(scalarArray)".hashValue

    要么

    scalarArray.description.hashValue

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

    回复于
  • 45

    编辑（17年5月31日）：请参阅接受的答案 . 这个答案是 pretty much just a demonstration on how to use the CommonCrypto Framework

    好的，我通过使用CommonCrypto框架中的SHA-256哈希算法，使用 Hashable 协议扩展了所有阵列 . 你必须把

    #import <CommonCrypto/CommonDigest.h>

    进入你的桥接 Headers ，以便工作 . 遗憾的是，必须使用指针：

    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]
    }
}

    编辑（5月31日'17): Don' t这样做，即使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倍 . 我不是说使用字符串是一个非常好的解决方案，但它是我们现在唯一可以比较它的方法

    回复于
  • 3

    一个建议 - 因为你正在建模一个 String ，它是否可以将你的 [UInt32] 数组转换为 String 并使用 String 的 hashValue ？像这样：

    var hashValue : Int {
    get {
        return String(self.scalarArray.map { UnicodeScalar($0) }).hashValue
    }
}

    这可以方便地让你比较你的自定义 struct 与 String ，虽然这是否是一个好主意取决于你想要做什么...

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

    所以我想如果你想让 hashValue 代表一个独特的 String ，我的方法会很好 . 如果你想让 hashValue 代表一个独特的 UInt32 值序列，那么@ Kametrixom的答案是要走的路......

    回复于

相关问题