Set如何解决散列冲突？

-1

基于此问题中接受的答案：How does Set ensure equatability in Swift?
hashValue用于唯一性的第一个测试。如果hashValue与另一个元素的hashValue匹配，则==用作备份测试。Set如何解决散列冲突？

但是，在场景后面，Set必须存储每个元素的唯一标识符。考虑一下这个例子：

struct Country { 
    let name: String 
    let capital: String 
} 

extension Country: Hashable { 
    static func == (lhs: Country, rhs: Country) -> Bool { 
     return lhs.name == rhs.name && lhs.capital == rhs.capital 
    } 

    var hashValue: Int { 
     return name.hashValue^capital.hashValue 
    } 
} 

let singapore = Country(name: "Singapore", capital: "Singapore") 
let monaco = Country(name: "Monaco", capital: "Monaco") 
singapore.hashValue // returns 0 
monaco.hashValue // returns 0 


var countries: Set<Country> = [] 
countries.insert(singapore) 
countries.insert(monaco) 

countries // Contains both singapore and monaco

正如你所看到的，一些国家和它们的首都有相同的名字。这会产生hashValue的碰撞。该集合将运行更昂贵的==以确定其独特性，其可能不是O(1)。但是在做这个比较之后，Set必须生成这个元素的唯一标识符以存储在场景后面。

问题： set如何为这样的碰撞元素生成唯一标识符？

来源

2017-08-11 Edward Anthony

打印单个String成员的hash值时会发生什么？ – Carlos

可供查看的源代码：https://github.com/apple/swift-corelibs-foundation/tree/19249417b01573bd6aa32b9a24cc42273315a48b/Foundation – Scroog1

这种情况被称为“散列冲突”。在那种情况下，相反og只有一个hashValue对象，将创建另一个集合，如内部Set，并将对象存储在那里。 –