时间戳

首页 > 解决方案 > Swift：使用 Set.insert() 的间歇性、不一致、意外行为

swift - Swift：使用 Set.insert() 的间歇性、不一致、意外行为

问题描述

编辑：我从没想过在删除派生数据后重新启动 Xcode。现在一切都按预期工作。

我的应用程序遇到间歇性故障。我已经把它缩小到了一些奇怪的地方Set.insert()。有时插入会导致调用我的==函数，有时则不会，原因不明。这是我能想到的最好的精简样本；它在操场上运行。

// Results are the same whether I use Equatable or not
struct ID: Hashable, Equatable {
    let idNumber: Int

    // Results are the same whether I implement this or not
    func hash(into hasher: inout Hasher) {
        hasher.combine(idNumber)
    }

    // Always return true; it doesn't matter. What matters
    // is that sometimes the Set.insert() doesn't even
    // call this function.
    static func == (_ lhs: ID, _ rhs: ID) -> Bool {
        print("(eq)", terminator: ""); return true
    }
}

let id0 = ID(idNumber: 0)
let id1 = ID(idNumber: 1)

var uniqueIDs = Set<ID>()

print("a", terminator: "")
uniqueIDs.insert(id0)
print("b", terminator: "")
uniqueIDs.insert(id1)
print("c", terminator: "")

如果我在操场上运行十次，大约一半的时间会eq在输出中看到，一半的时间不会。也就是说，在尝试插入之前，大约有一半的时间Set.insert()没有打电话给我。==

我阅读了 Swift 套装，但没有找到任何可以说明问题的东西。我有点想，如果这是预期的行为，它会被记录下来，并附上一个大的警告标志。缺少此类警告表明我在滥用Sets，但我不知道我做错了什么。我错过了什么文档或哪个答案？

标签： swiftset

解决方案

Set==如果没有值冲突，则没有理由调用您的类型。我这是一个红鲱鱼。

Set调用hash(into hasher: inout Hasher)你的值，然后取集合内部数组大小的模数。结果是值（如果它已经存在于集合中）应该在的索引。自然地，这个过程使得多个值在散列和取模之后可以在同一个数组槽中结束。

为了弥补这一点，不是将元素直接存储在数组槽中，而是通过链表存储。从概念上讲，同一槽中的项目称为“桶”。查找元素时Set使用哈希值找到正确的桶，但需要遍历链表才能找到确切的元素。此时，散列不再用于标识元素，因此Set使用==检查直到找到正确的匹配项。这通常非常有效，因为Set应该使数组足够大，使得桶很小并且包含很少的冲突。

因为在桶中找到一个元素是O(N)，如果你可以强制许多哈希冲突，那么你可以强制Set的O(1)插入/删除/检查操作退化为O(N)对整个元素的遍历Set（因为你可以使所有元素映射到一个桶。为了应对 DOS 漏洞，现代关联数据结构使用每次运行应用程序时随机选择的“种子”，并使用它来打乱哈希值。这样，制作具有相同哈希值的有效负载变得非常困难（这会导致存储桶过大的问题。）这就是您的不确定性的来源。请参阅PSA：stdlib 现在使用随机播种的哈希值。

从根本上说，Set<T>实际上只是一个Dictionary类型[T: Void]。因此，如果您了解基于散列的关联数据结构（其他常见名称为字典、散列、散列映射等）的工作原理，大部分内容都适用。

推荐阅读