使用位移避免冲突的Swift哈希算法

Question

给定一个具有name和surname字符串属性的Person结构体，我想编写一个高效且避免可互换姓名和姓氏（例如Lara Ray和Ray Lara）的碰撞的哈希算法。

我已经知道在Swift中避免使用字符串拼接，所以我想通过对两个变量进行XOR运算并位移其中一个变量来解决可互换问题。这样做有什么问题吗？

struct Person {
    let name: String
    let surname: String

    var hashValue: Int {
        return surname.hashValue << 1 ^ name.hashValue
    }
}

- cescofry

---

我认为一个好的起点是创建一个正则表达式子类。我会研究一下。 - jlmurph

在这里查看哈希组合函数：https://codereview.stackexchange.com/a/148777/73433 - JAL

Answer 1

马丁R慷慨地为我在旧的代码审查帖子这里中提供了Boost的hash_combine函数的Swift翻译。

我们可以在您的结构体中使用此函数：

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的示例）。

您可以在此处阅读有关“黄金比例”的更多信息：boost :: hash_combine中的魔术数字。

我仍在测试中，但我想这应该比仅将位移1提供更少的冲突。

- JAL