SWIFT可变集：找到重复元素 [英] Swift mutable set: Duplicate element found

问题描述

我的应用程序使用可变的自定义元素集。有一次我崩溃了，错误是"在集合中找到重复的元素。元素可能在插入后发生了变化。"

寻找解释，发现this post，我不完全理解。
我的印象是，不应该修改集合的元素，因为这也会修改集合的哈希值，因此进一步的访问可能会失败。

我的问题：

• 是否允许修改可变集的元素，或者允许哪些修改(如果有)？
• 如果没有，我是否必须首先从集合中删除元素，然后对其进行修改，然后再将其插入？

编辑：

换一种说法：修改可变集的自定义元素的属性而不修改集本身是否安全？

推荐答案

SWIFT集的实现类似于字典的实现，Exploring Swift Dictionary's Implementation对此有很好的描述。具体地说，元素存储是一个"桶"列表，每个桶都可以被占用或不被占用。当一个新元素被插入到集合中时，其散列值被用来确定初始存储桶。如果该桶被占用，则完成对下一个空闲桶的线性搜索。类似地，当搜索集合中的元素时，使用散列值来确定初始存储桶，然后进行线性搜索，直到找到该元素(或未占用的存储桶)。

(详细信息可以在开放源码实现中找到，最相关的源文件是 Set.swift、NativeSet.swift、SetStorage.swift和HashTable.swift。)

更改插入元素的散列值会破坏集合存储实现的不变量：通过元素的初始存储桶定位元素不再起作用。而变异其他影响相等性的属性可能会导致同一个遗愿列表中有多个"相等"的元素。

因此，我认为可以肯定地说

将引用类型的实例插入集合后，不得以影响其哈希值或测试相等性的方式修改该实例的属性。

示例

首先，这只是引用类型的集合的问题。值类型的集合包含值的独立副本，在插入后修改该值的属性不会影响集合：

struct Foo: Hashable {
    var x: Int
}

var set = Set<Foo>()
var foo = Foo(x: 1)
set.insert(foo)
print(set.map { $0.x })   // [1]
foo.x = 2
print(set.map { $0.x })   // [1]
set.insert(foo)
print(set.map { $0.x })   // [1, 2]

引用类型的实例是指向实际对象存储的"指针"，修改该实例的属性不会改变引用。因此，可以在将实例插入到集合中后修改其属性：

class Bar: Hashable {
    var x : Int

    init(x: Int) { self.x = x }

    static func == (lhs: Bar, rhs: Bar) -> Bool { return lhs.x == rhs.x }

    func hash(into hasher: inout Hasher) { hasher.combine(x) }
}

var set = Set<Bar>()
let bar = Bar(x: 1)
set.insert(bar)
print(set.map { $0.x })   // [1]
bar.x = 2
print(set.map { $0.x })   // [2]

但是，这很容易导致崩溃，例如，如果我们再次插入相同的引用：

set.insert(bar)

Fatal error: Duplicate elements of type 'Bar' were found in a Set.
This usually means either that the type violates Hashable's requirements, or
that members of such a set were mutated after insertion.

这里是另一个示例，其中所有实例的哈希值都相同，但修改用于相等性测试的属性会导致一组两个相等的实例：

class Baz: Hashable {
    var x : Int

    init(x: Int) { self.x = x }

    static func == (lhs: Baz, rhs: Baz) -> Bool { return lhs.x == rhs.x }

    func hash(into hasher: inout Hasher) { }
}

var set = Set<Baz>()
let baz1 = Baz(x: 1)
set.insert(baz1)
let baz2 = Baz(x: 2)
set.insert(baz2)
baz1.x = 2

print(set.map { $0.x })   // [2, 2]
print(set.count)             // 2
print(Set(Array(set)).count) // 1 😲

这篇关于SWIFT可变集：找到重复元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！