Swift结构类型集

Question

说我有一个struct,可能是任何东西:

struct Cube {
    var x: Int
    var y: Int
    var z: Int
    var width: Int
    // ...
}

然后我如何创建Set这些点,这样就不会有两个具有相同属性的对象？

let points: Set<Cube> = Set()
// Type ‘Cube’ does not conform to protocol ‘Hashable’

但是如何实现hashable并不是显而易见的.根据我的阅读,我需要创建一个哈希函数,但是在结构中我拥有的属性数量看起来并不容易.

Answer 1

首先,Hashable扩展Equatable,因此您必须==使用唯一标识多维数据集的所有属性来实现比较两个值的运算符:

func ==(lhs: Cube, rhs: Cube) -> Bool {
    return lhs.x == rhs.x && lhs.y == rhs.y && lhs.z == rhs.z && lhs.width == rhs.width
}

该Hashable协议只要求

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

所以

var hashValue: Int {
    return 0
}

将是一个有效(和工作)的实现.但是,这会将所有对象放在集合(或字典)的相同散列桶中,这是无效的.例如,更好的实现

struct Cube: Hashable {
    var x: Int
    var y: Int
    var z: Int
    var width: Int

    var hashValue: Int {
        return x.hashValue ^ y.hashValue ^ z.hashValue ^ width.hashValue
    }
}

这里选择"XOR"运算符^是因为它不能溢出.您也可以使用"溢出运算符" &+.

更复杂的散列函数将能够更好地区分不同的值,从而使集合操作变得更快.另一方面,散列函数本身的计算会更慢.因此,只有当设置操作成为程序中的性能瓶颈时,我才会寻找"更好"的哈希函数.

更新:从Swift 4.1(Xcode 9.4)开始,如果结构的所有成员都是,编译器可以合成==和hashValue方法 Equatable/Hashable.因此,足以声明一致性:

struct Cube: Hashable {
    var x: Int
    var y: Int
    var z: Int
    var width: Int
}

Answer 2

实现Hashable协议包含两件事.首先是实现hashValue,第二个是实现等于运算符.

工作Hashable协议的重要组成部分是等式运算符.它必须以仅返回true的方式实现,并且只有在两个结构包含相同值的情况下才能实现.

另一方面hashValue,只要相同的结构总是返回相同的值,您的实现就可以返回任何内容.

唯一hashValue影响的是代码的运行速度,因为当您添加或查找值时,首先运行的代码是hashValue.如果hashValue为两个结构返回相同的值,则它们之间的相等性将通过调用否则将被跳过的相等运算符来确定.

struct Cube: Hashable {

    // satisfy Hashable requirement
    var hashValue: Int {
        get {
            // you can return any integer here
            return x &+ y &+ z &+...
            // or even the same one for all structs
            return 0
        }
    }
}

// satisfy Equatable requirement
func ==(lhs: Cube, rhs: Cube) -> Bool {
    return lhs.x == rhs.x && lhs.y == rhs.y .....
}