给定一个具有 name
和 surname
字符串属性的 Person
结构,我想编写一个高效且避免冲突的哈希算法对于名字和姓氏可以互换的人(例如 Lara Ray 和 Ray Lara)。
我已经知道要摆脱 Swift 中的字符串连接,所以理想情况下,我正在考虑对 2 个变量进行 XOR
并对其中一个变量进行位移以解决可互换的问题。
这有什么问题吗?
struct Person {
let name: String
let surname: String
var hashValue: Int {
return surname.hashValue << 1 ^ name.hashValue
}
}
最佳答案
Martin R 慷慨地提供了 Boost 的 hash_combine 的 Swift 翻译在我的旧代码审查帖子中使用函数 here .
我们可以在你的结构中使用这个函数:
func hash_combine(seed: inout UInt, value: UInt) {
let tmp = value &+ 0x9e3779b9 &+ (seed << 6) &+ (seed >> 2)
seed ^= tmp
}
struct Person {
let name: String
let surname: String
var hashValue: Int {
var seed = UInt(0)
hash_combine(seed: &seed, value: UInt(bitPattern: name.hashValue))
hash_combine(seed: &seed, value: UInt(bitPattern: surname.hashValue))
return Int(bitPattern: seed)
}
}
Person(name: "Joe", surname: "Smith").hashValue // -5143836311621647467
Person(name: "Smith", surname: "Joe").hashValue // -5146825509308597586
虽然不完美,但这应该可以减少大量样本集中的碰撞次数(请参阅带有 CGPoint
的示例的链接帖子)。
您可以在此处阅读有关“黄金比例”的更多信息:Magic number in boost::hash_combine
我仍在对此进行测试,但我想这将提供比仅位移 1 更少的碰撞。
关于Swift Hashing 算法使用位移来避免冲突,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/45577996/