Swift: Overriding NSObject hash Without Overflow C

Question

Using Swift 3, I have some NSObject subclasses that I am overriding the hash property and isEqual() functions for. (I want the classes to be able to be used as keys in a dictionary, and I want an array of them to be able to be sorted, but it doesn't really matter why I'm overriding them.)

Harkening back to my old C++/Java days, I recalled that a "proper" hash involved prime numbers and the hashes of the object's properties. These questions talk about this style. Something like this:

override public var hash: Int {
    var hash = 1
    hash = hash * 17 + label.hash
    hash = hash * 31 + number.hash
    hash = hash * 13 + (ext?.hash ?? 0)
    return hash
}

At least, that's what I thought. While running my code, I saw a very peculiar crash in my hash override:

EXC_BAD_INSTRUCTION (code=EXC_I386_INVOP, subcode=0x0)

Looking here at StackOverflow, I saw a lot of these crashes being asked about, and the answer was usually that nil is being implicitly unwrapped, causing a crash. But there are no optionals in my hash. After playing around in lldb, I realized that the problem was integer overflow. If you do this in a playground, you'll see it causes an error:

`9485749857432985 * 39847239847239` // arithmetic operation '9485749857432985 * 39847239847239' (on type 'Int') results in an overflow

Well, I do a lot of addition and multiplication in my hash overrides. (It's hard to see in a playground, but in lldb it was obvious that overflow was causing my crash.) Reading about Swift crashes due to Int overflow, I found that you can use &* and &+ to prevent overflow. I'm not sure how well the hashes work, but this wouldn't crash, for example:

override public var hash: Int {
    var hash = 1
    hash = hash &* 17 &+ label.hash
    hash = hash &* 31 &+ number.hash
    hash = hash &* 13 &+ (ext?.hash ?? 0)
    return hash
}

Here's my question: what is the "proper" way to write this sort of hash override, without the potential for overflow, and in a way that actually provides good hashing?

Here is an example you can pop into a playground to try out. I think this would definitely lead to the EXC_BAD_INSTRUCTION for anybody:

class DateClass: NSObject {
    let date1: Date
    let date2: Date
    let date3: Date

    init(date1: Date, date2: Date, date3: Date) {
        self.date1 = date1
        self.date2 = date2
        self.date3 = date3
    }

    override var hash: Int {
        var hash = 1
        hash = hash + 17 + date1.hashValue
        hash = hash + 31 + date2.hashValue
        hash = hash + 13 + date3.hashValue
        return hash
    }

    override public func isEqual(_ object: Any?) -> Bool {
        guard let rhs = object as? DateClass else {
            return false
        }
        let lhs = self

        return lhs.date1 == rhs.date1 &&
            lhs.date2 == rhs.date2 &&
            lhs.date3 == rhs.date3
    }
}

let dateA = Date()
let dateB = Date().addingTimeInterval(10)
let dateC = Date().addingTimeInterval(20)
let dateD = Date().addingTimeInterval(30)
let dateE = Date().addingTimeInterval(40)

let class1 = DateClass(date1: dateA, date2: dateB, date3: dateC)
let class2 = DateClass(date1: dateB, date2: dateC, date3: dateD)
let class3 = DateClass(date1: dateC, date2: dateD, date3: dateE)

var dict = [DateClass: String]()
dict[class1] = "one"
dict[class2] = "two"
dict[class3] = "three"

Bonus question: is there a proper way to handle making the hash value, when a property on your class uses hashValue instead? I've been using them pretty interchangeably but I'm not sure if that's correct.

Answer 1

hashValue (or hash) can really be anything. As long as two objects that return true for isEqual also have the same hash value.

You don't really need to worry about coming up with some magic value based on all properties.

Your hash could simply return the hash of a single property. This will avoid any sort of overflow. Or your could do some bit manipulation of the hash values of multiple properties. Some combination of "or", "and", and "xor".

As for your bonus question, there is no problem calling hashValue on some Swift data types when calculating the result of the NSObject hash method. Both return Int.