Do swift hashable protocol hash functions need to return unique values?

Question

I am working through an iOS swift Tetris tutorial* and have it completed and working. But I am puzzled about one particular aspect - the Hashable protocol. The function:

class Block: Hashable, Printable {
    [...]    
    var hashValue: Int { return self.column ^ self.row }

Rows go 0..9, and Columns 0..20. The notes says of this function "We return the exclusive-or of our row and column properties to generate a unique integer for each Block.". But my understanding is that 0^1 would be the same as 1^0, etc... I would like to know if it is a problem if the Hash function is not unique like this, or are collisions are generally OK? As I say, the application appears to work fine...

*https://www.bloc.io/tutorials/swiftris-build-your-first-ios-game-with-swift#!/chapters/681

Chanticleer

Answer 1

Collisions are not "generally OK". The underlying assumption is that the hash value of x is the hash value of y if and only if x == y. If you consider column 2, row 1 the same as column 1, row 2, then fine. But I don't think you do! The application may appear to work, but presumably you have done nothing that requires hashability - yet.

Reconstructionism

That is what I thought. I'm thinking perhaps the code works because the functions that require the hash just effect a single row or column at a time. Thanks for the help. -D – Chanticleer

The question is what would happen if you had, say, a Dictionary whose keys are Blocks. They wouldn't work correctly because the hash value is used to locate the key - and it wouldn't be unique. – Reconstructionism

Dictionary keys CAN have collisions, and actual equivalence is checked (==) before returning the value. In fact, you can just flat return 0 and Dictionary will work just fine. That's not guaranteed to be fine for all code that uses hashValue, but hashValue is not required to guarantee uniqueness. You could hash a string based on the first letter, for instance. hashValue is not a substitute for == which is why Hashable requires Equatable – Pent

-1. Hash collisions should never cause bugs, as hash functions (generally) don't guarantee perfect hashing. The only guarantee that a hash function h gives is that h(x) != h(y) implies that x != y. – Odometer

@Reconstructionism Could you confirm whether Swift requires hash function to be perfect? I guess 'the underlying assumption' is a bit vague: this 'assumption' exists in Java to make dictionary lookup O(1) , but doesn't require the hash code to be perfect. – Swarm

Answer 2

The application is working because it also implements the Equatable protocol:

func ==(lhs: Block, rhs: Block) -> Bool {
    return lhs.column == rhs.column && lhs.row == rhs.row && lhs.color.rawValue == rhs.color.rawValue
}

Collusive