Jacob Parker Jacob Parker - 3 months ago 7
Swift Question

Swift Set of Structure Types

Say I have a

struct
, which could be anything:

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


How do I then create a
Set
of these points, such that there will be no two objects with the same properties?

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


But it’s not immediately obvious how to implement hashable. From what I read, I need to make a hash function, but that doesn’t look easily possible with the amount of properties I have in the struct.

Answer

First of all, Hashable extends Equatable, so you must implement a == operator which compares two values, using all properties which uniquely identify a cube:

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

The Hashable protocol only requires that

x == y implies x.hashValue == y.hashValue

so

var hashValue: Int {
    return 0
}

would be a valid (and working) implementation. However, this would put all objects in the same hash bucket of a set (or dictionary), which is not effective. A better implementation is for example

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

Here the "XOR" operator ^ is chosen because it cannot overflow. You could also use the "overflow operator" &+.

More sophisticated hash functions would be able to distinguish different values better, so that the set operations become faster. On the other hand, the computation of the hash function itself would be slower. Therefore I would look for a "better" hash function only if the set operations turn out to be a performance bottleneck in your program.

Comments