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，並將對象存儲在那裏。 –