Hash

Definition:

雜湊(英語:Hashing)是電腦科學中一種對資料的處理方法,通過某種特定的函式/演算法(稱為雜湊函式/演算法)將要檢索的項與用來檢索的索引(稱為雜湊,或者雜湊值)關聯起來,生成一種便於搜尋的資料結構(稱為雜湊表(Hash table))。 (from Wiki)

Hash function(雜湊函式):

又稱雜湊演算法,能把任意長度的data轉換成固定長度的值。hash function回傳的值稱為hash value(or hash code or digest)。
Note 1:

Hash有可能發生"collision“(i.e. 兩個不同的data,對應到同一個hash value)

Note 2:
Hash functions are related to (and often confused with) checksums, check digits, fingerprints, lossy compression, randomization functions, error-correcting codes, and ciphers.

Example:

此圖片來自Wiki – 由 David Göthberg, Sweden 創作

Hash table說明:

http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html

Collision Resolution

  1. Open Addressing
    • 發生collision時,找尋尚未被對應到的key,將data對應到找到的key
      • (p.s. 找到未使用key的方式有: linear probing, double hashing, and quadratic probing)
  2. Separate Chaining
    • 把對應到相同key的data,以linked list方式串連起來
  3. Cache-Conscious Collision Resolution

詳細說明請參考Wiki

Swift Hashable

//For a struct, all its stored properties must conform to Hashable.
//For an enum, all its associated values must conform to Hashable. (An enum without associated values has Hashable conformance even without the declaration.)

struct Location: Hashable {
    var x: Double
    var y: Double

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

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

Ref:

https://developer.apple.com/documentation/swift/hashable

http://alrightchiu.github.io/SecondRound/hash-tableintrojian-jie.html

https://zh.wikipedia.org/wiki/%E6%95%A3%E5%88%97%E5%87%BD%E6%95%B8

https://ithelp.ithome.com.tw/articles/10208884