Swift Set type performance inconsistently when inserting data

Question

Created Aug ’20

Replies 1

Boosts 0

Participants 2

This code will generate different result when RoadmapCardChain implement Hashable and Equatable protocol

Code Block struct RoadmapCardChain: Codable, Hashable, Equatable {
		let start: String
		let end: String
		let styles: String
		
		static func == (lhs: RoadmapCardChain, rhs: RoadmapCardChain) -> Bool {
				let isStyleSame = lhs.styles == rhs.styles
				let isEndSame = lhs.start == rhs.start && lhs.end == rhs.end
				let isToggleEndSame = lhs.start == rhs.end && lhs.end == rhs.start
				print(lhs)
				print(rhs)
				print("result is \(isStyleSame && ( isEndSame  isToggleEndSame ))")
				return isStyleSame && ( isEndSame  isToggleEndSame )
		}
}
let a = RoadmapCardChain(start: "Cafeteria", end: "Payment BIZ", styles: "AECC5C")
let b = RoadmapCardChain(start: "Payment BIZ", end: "Cafeteria", styles: "AECC5C")
var chains: Set<RoadmapCardChain> = []
print(a.hashValue)
print(b.hashValue)
chains.insert(a)
if chains.contains(b) {
		print("contains is true")
} else {
		chains.insert(b)
}
print(chains)

sometime result is :

Code Block 785027920194053578
6404817261741129101
RoadmapCardChain(start: "Cafeteria", end: "Payment BIZ", styles: "AECC5C")
RoadmapCardChain(start: "Payment BIZ", end: "Cafeteria", styles: "AECC5C")
result is true
contains is true
[__lldb_expr_19.RoadmapCardChain(start: "Cafeteria", end: "Payment BIZ", styles: "AECC5C")]

but sometime result is :

Code Block 491382166321900052
7275567105868021174
[lldb_expr_21.RoadmapCardChain(start: "Cafeteria", end: "Payment BIZ", styles: "AECC5C"), lldb_expr_21.RoadmapCardChain(start: "Payment BIZ", end: "Cafeteria", styles: "AECC5C")]

I don't know why same codes has different performance

I still don't understand why sometimes == be called and sometimes it doesn't be called。According to my understanding Set only need hashvalue when insert or contains function, don't need to call ==

Answered by OOPer in 627830022

According to my understanding Set only need hashvalue when insert or contains function, don't need to call ==

Seems your understanding is wrong.
hashValue for different (meaning not ==) values may have the same value. So Set needs to call == in some cases, including when inserting or checking contained.
When a.hashValue ≠ b.hashValue, it is guaranteed that a ≠ b, so Set has no need to call ==. But when a.hashValue == b.hashValue, Set needs to call == to check if a == b or not.

That means, hashValue and == need to be consistent, which is represented by a simple axiom:

When a == b, a.hashValue must be equal to b.hashValue.

Your current implementation does not fulfill this axiom.

Please try this:

Code Block struct RoadmapCardChain: Codable, Hashable, Equatable {
		let start: String
		let end: String
		let styles: String
		
		static func == (lhs: RoadmapCardChain, rhs: RoadmapCardChain) -> Bool {
				let isStyleSame = lhs.styles == rhs.styles
				let isEndSame = lhs.start == rhs.start && lhs.end == rhs.end
				let isToggleEndSame = lhs.start == rhs.end && lhs.end == rhs.start
				print(lhs)
				print(rhs)
				print("result is \(isStyleSame && ( isEndSame ‖ isToggleEndSame ))")
				return isStyleSame && ( isEndSame ‖ isToggleEndSame )
		}
		
		//To make `hashValue` consistent with `==` above
		func hash(into hasher: inout Hasher) {
				styles.hash(into: &hasher)
				if start <= end {
						start.hash(into: &hasher)
						end.hash(into: &hasher)
				} else {
						end.hash(into: &hasher)
						start.hash(into: &hasher)
				}
		}
}

(Seems this site removes from inside code blocks. I have replaced to U+2016 ‖. If you want to use my code above, you need to replace U+2016 ‖ to ||.)

Boost

Answer 1

OOPer OP

Aug ’20

Accepted Answer