如何实现在斯威夫特一个int数组的哈希协议（自定义字符串结构） [英] How to implement the Hashable Protocol in Swift for an Int array (a custom string struct)

问题描述

我在做一个行为像字符串的结构，但它仅与统一code UTF-32标值的交易。因此， UInt32的的数组。 （请参见这个问题了解背景。）

I am making a structure that acts like a String, except that it only deals with Unicode UTF-32 scalar values. Thus, it is an array of UInt32. (See this question for more background.)

我希望能够用我的自定义 ScalarString 结构作为在字典中的关键。例如：

I want to be able to use my custom ScalarString struct as a key in a dictionary. For example:

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 需要实现<一个href=\"https://developer.apple.com/library/$p$prelease/ios/documentation/Swift/Reference/Swift_Hashable_Protocol/index.html\">Hashable协议。我想我能够做这样的事情：

Problem

In order to do that, ScalarString needs to implement the Hashable Protocol. I thought I would be able to do something like this:

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
}

但后来我发现，<一个href=\"https://developer.apple.com/library/$p$prelease/ios/documentation/Swift/Reference/Swift_Array_Structure/index.html\">Swift数组没有一个散列值 。

文章<一个href=\"http://letvargo.mooo.com/strategies-for-implementing-the-hashable-protocol-in-swift/\">Strategies为实现在斯威夫特的哈希协议有很多伟大的想法，但我没有看到任何这似乎是他们会在这种情况下很好地工作。具体来说，

The article Strategies for Implementing the Hashable Protocol in Swift had a lot of great ideas, but I didn't see any that seemed like they would work well in this case. Specifically,

• 的对象属性的（数组是没有散列值）


• 的 ID属性的（不知道如何实现这一点的好）


• 的公式的（似乎是为32位整数的字符串的任何公式将是沉重的处理器，并有大量的整数溢出的）


• 的为ObjectIdentifier 的（我使用一个结构，而不是一类）


• 的从NSObject的继承的（我使用一个结构，而不是一类）

• Object property (array is does not have hashValue)
• ID property (not sure how this could be implemented well)
• Formula (seems like any formula for a string of 32 bit integers would be processor heavy and have lots of integer overflow)
• ObjectIdentifier (I'm using a struct, not a class)
• Inheriting from NSObject (I'm using a struct, not a class)

下面是一些其他的东西我读

Here are some other things I read:

• 实施斯威夫特的哈希协议


• 雨燕比较协议


• 完善哈希函数


• Membership在斯威夫特数组和字典
自定义对象

• How实现哈希的自定义类


• Writing在斯威夫特
一个好的哈希执行

• 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

斯威夫特字符串有一个<一个href=\"https://developer.apple.com/library/$p$prelease/ios/documentation/Swift/Reference/Swift_String_Structure/index.html#//apple_ref/swift/structp/String/s:vSS9hashValueSi\"><$c$c>hashValue财产，所以我知道这是可以做到的。

Swift Strings have a hashValue property, so I know it is possible to do.

我将如何创建一个散列值为我的自定义结构？

How would I create a hashValue for my custom structure?

更新1：我愿做一些事情，不涉及转换为字符串，然后用字符串的散列值。我整点使我自己的结构是这样我就能避免做大量的字符串转换。 字符串得到它的散列值从某处。好像我可以用同样的方法得到它。

Update 1: I would like to do something that does not involve converting to String and then using String's hashValue. My whole point for making my own structure was so that I could avoid doing lots of String conversions. String gets it's hashValue from somewhere. It seems like I could get it using the same method.

更新2：我一直在寻找到的来自其他上下文字符串哈希codeS算法的实现。我有一点困难知道哪个是最好的，当然pressing他们斯威夫特，虽然。

Update 2: I've been looking into the implementation of string hash codes algorithms from other contexts. I'm having a little difficulty knowing which is best and expressing them in Swift, though.

• 的Java 哈希code 算法


• ç算法


• （SO问题及答案在C）href=\"http://stackoverflow.com/questions/7666509/hash-function-for-string\">哈希函数


• 散列教程（弗吉尼亚理工大学算法可视化研究集团）


• 通用Hash函数算法

• Java hashCode algorithm
• C algorithms
• hash function for string (SO question and answers in C)
• Hashing tutorial (Virginia Tech Algorithm Visualization Research Group)
• General Purpose Hash Function Algorithms

更新3

我想preFER不进口任何外部框架，除非是去为这些事情的推荐方式。

I would prefer not to import any external frameworks unless that is the recommended way to go for these things.

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

I submitted a possible solution using the DJB Hash Function.

推荐答案

这个答案已经被完全填满后改写我的<一个href=\"http://$c$creview.stackexchange.com/questions/111545/implementing-the-hashable-protocol-in-swift-with-the-djb-hash-function\">original回答code检讨。

This answer has been completely rewritten after submitting my original answer to code review.

的<一个href=\"https://developer.apple.com/library/ios//documentation/Swift/Reference/Swift_Hashable_Protocol/index.html\">Hashable协议允许您使用您的自定义类或结构作为字典键。为了实现此协议需要

The Hashable protocol allows you to use your custom class or struct as a dictionary key. In order to implement this protocol you need to

1. 实施<一个href=\"https://developer.apple.com/library/ios//documentation/Swift/Reference/Swift_Equatable_Protocol/index.html#//apple_ref/swift/intf/s:PSs9Equatable\">Equatable协议（哈希从Equatable继承）


2. 返回一个计算散列值

1. Implement the Equatable protocol (Hashable inherits from Equatable)
2. Return a computed hashValue

这点从文档中给出​​的公理如下：

These points follow from the axiom given in the documentation:

X ==是意味着 x.hashValue == y.hashValue

其中， X 和是有一些类型的值。

where x and y are values of some Type.

为了实现Equatable协议，您可以定义你的类型如何使用 == （等效）操作符。在你的榜样，等价可确定是这样的：

In order to implement the Equatable protocol, you define how your type uses the == (equivalence) operator. In your example, equivalence can be determined like this:

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

的 == 的功能是全球如此这般类或结构之外。

The == function is global so it goes outside of your class or struct.

您的自定义类或结构还必须有一个计算散列值变量。好的哈希算法将提供广泛的散列值。然而，应该指出的是，不需要保证哈希值都是唯一的。当两个不同的值具有相同的散列值，这被称为散列冲突。它需要一些额外的工作时，有一个碰撞（这就是为什么良好分布是希望的），但有些碰撞是可以预料的。据我了解，在 == 函数做额外的工作。

Your custom class or struct must also have a computed hashValue variable. A good hash algorithm will provide a wide range of hash values. However, it should be noted that you do not need to guarantee that the hash values are all unique. When two different values have identical hash values, this is called a hash collision. It requires some extra work when there is a collision (which is why a good distribution is desirable), but some collisions are to be expected. As I understand it, the == function does that extra work.

有多种方式来计算散列值。例如，你可以做一些简单的数组中的元素返回的数量。

There are a number of ways to calculate the hash value. For example, you could do something as simple as returning the number of elements in the array.

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

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

This would give a hash collision every time two arrays had the same number of elements but different values. NSArray apparently uses this approach.

DJB Hash函数

这与字符串工作的通用散列函数是DJB哈希函数。这就是我将要使用的一个，但这里检查出一些其他的。

A common hash function that works with strings is the DJB hash function. This is the one I will be using, but check out some others here.

由@MartinR提供迅速实现 如下：

A Swift implementation provided by @MartinR follows:

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

这是我最初实现的改进版本，但我还包括旧的扩展形式，这可能是人们不熟悉的<一个更可读href=\"https://www.weheartswift.com/higher-order-functions-map-filter-reduce-and-more/\"><$c$c>reduce.这相当于，我相信：

This is an improved version of my original implementation, but let me also include the older expanded form, which may be more readable for people not familiar with reduce. This is equivalent, I believe:

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 &+ operator allows Int to overflow and start over again for long strings.

我们已经看了看片，但现在让我显示整个例如code，因为它涉及到哈希协议。 ScalarString 是问题的自定义类型。这将是不同的人有不同的，当然。

We have looked at the pieces, but let me now show the whole example code as it relates to the Hashable protocol. ScalarString is the custom type from the question. This will be different for different people, of course.

// 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散列算法是最好的独特性和速度？


• Overflow操作符


• Why是5381和33的djb2算法如此重要？


• 如何哈希冲突如何处理？



Other helpful reading

• 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?

非常感谢马丁·R经由在code审查。我的改写主要是基于他的回答。如果你发现这是很有帮助的话，请给他一个给予好评。

A big thanks to Martin R over in Code Review. My rewrite is largely based on his answer. If you found this helpful, then please give him an upvote.

雨燕是开源的，现在这样就可以看到散列值是字符串从<一实施HREF =htt​​ps://github.com/apple/swift/blob/master/stdlib/public/core/String.swift>来源$ C ​​$ C 。这似乎是比我这里给出的答案比较复杂，我没有花时间去全面分析它。随意这样做你自己。

Swift is open source now so it is possible to see how hashValue is implemented for String from the source code. It appears to be more complex than the answer I have given here, and I have not taken the time to analyze it fully. Feel free to do so yourself.

这篇关于如何实现在斯威夫特一个int数组的哈希协议（自定义字符串结构）的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！