三双的哈希值

Question

让对象保存三个双精度值。如果所有三个值在任何可能的组合中都相等，则两个对象相等。需要一个函数来确定数组中“唯一”对象的数量。我想从数组中创建 Set 并返回计数，但符合 Hashable 协议需要 hashValue 函数......在 Swift 上编码但任何语言（外星人除外）的算法将不胜感激:)

所以我需要三个双精度的 hashValue（值的顺序无关紧要）或任何其他确定数组中唯一对象数量的解决方案

更新： “独特”意味着不相等。正如我上面所说的，等于两个具有双精度值的对象（例如 a、b、c）等于任何可能组合中的所有三个值。例如：

obj1 = (a: 1, b: 2, c: 3)
obj2 = (a: 3, b: 2, c: 1)
// obj1 is equal obj2

Answer 1

这是创建一个包含 3 个双精度的类的示例，Hashable以便您可以使用它Set来确定数组中包含多少个唯一的双精度：

class Triple: Hashable {
    var a: Double
    var b: Double
    var c: Double

    // hashValue need only be the same for "equal" instances of the class,
    // so the hashValue of the smallest property will suffice        
    var hashValue: Int {
        return min(a, b, c).hashValue
    }

    init(a: Double, b: Double, c: Double) {
        self.a = a
        self.b = b
        self.c = c
    }
}

// Protocol Hashable includes Equatable, so implement == for type Triple:
// Compare sorted values to determine equality    
func ==(lhs: Triple, rhs: Triple) -> Bool {
    return [lhs.a, lhs.b, lhs.c].sorted() == [rhs.a, rhs.b, rhs.c].sorted()
}

let t1 = Triple(a: 3, b: 2, c: 1)
let t2 = Triple(a: 1, b: 2, c: 3)
let t3 = Triple(a: 1, b: 3, c: 2)
let t4 = Triple(a: 3, b: 3, c: 2)

let arr = [t1, t2, t3, t4]

// Find out how many unique Triples are in the array:    
let set = Set(arr)
print(set.count)  // 2

讨论：更好的哈希函数

正如@PatriciaShanahan 在评论中指出的那样，min在 的计算中使用hashValue有几个缺点：

1. min 可能很昂贵，因为它涉及比较。
2. 在计算hashValuefor时只考虑最小的项Triple会导致许多Triple具有相同hashValue. 例如，任何Triple值为0和 两个正值的值都将具有相同的hashValue。

我选择了min，因为我觉得这是很容易理解的是，min(a, b, c)会导致对所有排序相同的值a，b和c这意味着我们会得到相同的hashValue所有排序。这很重要，因为我们认为Triples 与 3 个值的排序无关，因此hashValue对于任何值的排序， 都必须相同，因为a == b意味着a.hashValue == b.hashValue。

我曾考虑过其他散列函数，例如：

• (a + b + c).hashValue
• (a * b * c).hashValue

但这些都是有缺陷的。从数学上讲，加法和乘法是可交换的，因此理论上hashValue无论a、b、 和的顺序如何，它们都会产生相同的结果c。但是，实际上，更改操作顺序可能会导致上溢或下溢。

考虑以下示例：

let a = Int.max
let b = Int.min
let c = 5

let t1 = (a + b) + c  // 4
let t2 = (a + c) + b  // Overflow!

一个理想的类散列函数是Triple：

1. 保证相同hashValue的所有排序a，b和c。
2. 计算速度快。
3. 会改变，如果任何的结果a，b或c改变。
4. 无法上溢或下溢。

组合数字的一种很好的数学运算是按位 OR函数^。它通过按位比较两个值并将结果位设置为0如果两个位相同以及1如果位不同来组合两个值。

 a    b    result
---  ---   ------
 0    0      0
 0    1      1
 1    0      1
 1    1      0

将此扩展为 3 个值：

 a    b    c    result
---  ---  ---   ------
 0    0    0      0
 0    0    1      1
 0    1    0      1
 0    1    1      0
 1    0    0      1
 1    0    1      0
 1    1    0      0
 1    1    1      1

如上表所示，XOR(0, 0, 0) = 0对于所有排序，XOR(1, 0, 0) = 1对于所有排序，XOR(1, 1, 0) = 0对于所有排序，XOR(1, 1, 1) = 1对于所有排序。因此，使用异或来组合这些值符合为所有排序提供相同结果的第一个标准。

异或是一种快速操作。它由单个汇编指令实现。因此它符合良好散列函数的第二个标准。

如果a、b、 或 中的任何一个c发生变化，则 的结果a ^ b ^ c将发生变化。因此，异或符合良好散列函数的第三个标准。

异或不能上溢或下溢，因为它只是设置位。因此它符合良好散列函数的第四个标准。

因此，更好的hashing函数是：

var hashValue: Int {
    return a.hashValue ^ b.hashValue ^ c.hashValue
}