在 Swift 中實現字典

NevilleGent 8年前發布 | 11K 次閱讀 Swift Apple Swift開發

雖然 Swift 原生的字典類型實現的很復雜（毫無疑問是為了性能），但是我們可以利用 Swift 提供的工具寫出漂亮簡潔的實現。我們從一個簡單的實現開始，并且逐步添加功能。

我們簡要看一下字典的工作原理：它通過任意類型的關鍵字來設置和獲取值。這些值常常存儲在一個數組中，當然也可以存儲在樹型結構中。由于我還不太清楚以樹作為字典存儲結構的工作原理，所以這篇文章中我們主要探索一個由數組存儲值的字典。

由于我們字典中的值是由數組存儲，所以我們需要將給定的關鍵字轉換成整數，然后讓這個整數落在數組范圍內。這兩個方法一個是哈希函數，一個是取模操作。通過哈希函數，我們可以將關鍵字（通常是字符串，也可以是遵循 Hashable 協議的任意類型）轉換成一個數值，然后根據數組的長度，通過取模操作我們會得到一個固定位置(consistent slot)來設置和獲取值。

譯者注: 這里的 consistent slot 是指，字典的 key，通過這種 Hash 和取模運算，每次都會得到相同的數值，從而確保相同的 key 值，每次取得的 value 總是保持一致性。

我從 Mike Ash 的文章讓我們構建 NSMutableDictionary 獲取了一些靈感，特別是重新計算數組容量的規則。

讓我們開始吧。我們知道 Key 和 Value 都應該支持泛型，而且 Key 必須遵循 Hashable 協議。遵循 Hashable 協議的也一定同時遵循 Equatable 協議。(譯者注， Hashable 協議繼承自 Equatable 協議)

struct Dictionary<Key, Value where Key: Hashable> {
    private var storage = //some Array...

    subscript(key: Key) -> Value? {
        get {
            return nil
        }
        set {
        }
    }
}

這是我們類型的基本結構。我們知道我們的數組必須是支持泛型的，但是還不知道具體的值是什么。由于兩個不同的關鍵字經過哈希和取模操作后可能會指向數組的同一個位置，這樣就會造成沖突，因此每個占位對象需要支持存儲多個值。現在讓來我們設計 Placeholder ：

struct Placeholder<Key, Value where Key: Hashable> {
    var values: [(Key, Value)] = []
}

這個對象存儲很多經過哈希和取模操作后指向字典同一位置的鍵和值。如果我們很好的設計了字典，那么每個 Placeholder 包含的鍵值對將不會超過一個，但是超過一個的情況也會發生。一個比較好的實現是用一個鏈表來存儲 Placeholder 的屬性 values 。我將留作一個練習給讀者。

現在我們大體知道了 Placeholder 是什么樣的，接下來我們看看我們的存儲器是什么樣的。

private var storage = Array(count: 8, repeatedValue: Placeholder<Key, Value>())

初始時我們給數組一個隨機的大小。最好選擇 2 的整數冪，因為對 2 的冪取模要比其他數更快。除非我們實現如何重新計算數組容量，否則取多大都沒有關系。 Array(count:repeatedValue:) 構造方法使得數組中的每個位置都有一個可以添加值的占位對象。

為了設置字典的值，我們需要對鍵進行哈希（然后取絕對值，因為哈希有時會返回負值），然后根據數組大小進行取模操作。

set {
    let position = abs(key.hashValue) % storage.count
    //...
}

在真正給字典添加值之前，我們需要

a）確保新值(newValue)不為 nil

b）找到在 position 位置的占位對象

c）將鍵和值添加到占位對象中。

set {
    guard let value = newValue else { return }
    let position = abs(key.hashValue) % storage.count
    storage[position].values.append((key, value))
}

這就是基本滿足我們需求的設置方法的實現。（我忽略掉了一些小的細節，比如當你試著對同一個鍵設置兩次時會發生什么。我們很快會處理這種情況。）

取值的過程相當簡單。對鍵進行哈希，取絕對值，取模操作，然后我們獲取了在那個位置上的占位對象。我將會把從占位對象中獲取值的過程交給占位對象自己去做。

get {
    let position = abs(key.hashValue) % storage.count
    return storage[position].firstValue(matchingKey: key)
}

真正神奇的是在下面這個方法。我們需要找到第一個包含那個鍵的鍵值對。在 Swift 3 中我們可以使用 SequenceType 協議中的 first(where:) 方法來實現，但目前我們使用普通的寫法 lazy.filter( /* block */ ).first 來獲取鍵值對。

func firstValue(matchingKey key: Key) -> Value? {
    let matchingKeyValuePair = values.lazy.filter({ $0.0 == key }).first
    //...
}

一旦我們拿到表示鍵值對的元組，我們就可以直接調用 .1 獲取對應的值。

func firstValue(matchingKey key: Key) -> Value? {
    return values.lazy.filter({ $0.0 == key }).first?.1
}

這幾乎是 Dictionary 的基本實現了。23 行 Swift 代碼。所有代碼在這個 gist 中。

還有幾個有意思的事情還沒有實現。首先，需要有惰性求值的 generate() ，這樣的話 Dictionary 就遵循 SequenceType 協議了。

譯者注: 遵循 SequenceType 協議之后，就可以使用 for (key, value) in 的方式來遍歷字典了

extension Dictionary: SequenceType {
    typealias Generator = IndexingGenerator<[(Key, Value)]>
    func generate() -> Dictionary.Generator {
        return storage.flatMap({ $0.values }).generate()
    }
}

接下來是刪除鍵。首先，從占位對象中刪除：

extension Placeholder {
    mutating func removeValue(key key: Key) {
        values = values.filter({ $0.0 != key })
    }
}

然后從字典中刪除

extension Dictionary {
    mutating func remove(key key: Key) {
        let position = abs(key.hashValue) % storage.count
        storage[position].removeValue(key: key)
    }
}

在設置新值時先調用 remove(key:) 。這樣確保同一個鍵不會映射到不同的值上。

最后，我們來看看如何重新計算數組容量。當字典包含非常多對象時，它的實際存儲結構需要調整自身大小，可以把“非常多對象”看成一個大于2/3或者3/4的負載系數（對象數量除以數組長度）。我選擇 0.7。

extension Dictionary {
    private let maxLoadFactor = 0.7

    private var size: Int {
        return storage.count
    }

    var count: Int {
        return storage.flatMap({ $0.values }).count
    }

    var currentLoadFactor: Double {
        return Double(count) / Double(size)
    }
}

（ count 的實現還是懶求值。理想情況下， Dictionary 會記錄有多少對象被添加和被刪除，但實際上很難記錄）

mutating func resizeIfNeeded() {
    if currentLoadFactor > maxLoadFactor {
        //resize storage
    }
}

這就是 Swift 的值語法非常奇怪的地方。 Mike Ash 在構建NSMutableDictionary 文章中，創建了一個固定大小的字典，并且把它封裝成一個可變大小的字典。當需要調整大小時，他創建一個新的固定大小的字典（大小加倍），然后手動的把所有元素拷貝到新的字典當中。

在 Swift 中我們不必如此。Swift 中的結構體對象賦值給一個變量會進行一次完整拷貝。

let oldDictionary = self
//...

一旦我們拷貝完字典，我們可以重置 storage 變量為原先數組大小的兩倍。（大小加倍確保數組大小仍然是2的冪。）

//...
storage = Array<Placeholder<Key, Value>>(count: size*2, repeatedValue: Placeholder<Key, Value>())
//...

一旦設置完成，字典會變成空的，我們必須把 oldDictionary 的所有值拷貝到當前字典中：

//...
for (key, value) in oldDictionary {
    self[key] = value
}

這是完整的 resizeIfNeeded 函數：

mutating func resizeIfNeeded() {
    if Double(count) / Double(size) > maxLoadFactor {
        let oldDictionary = self
        storage = Array<Placeholder<Key, Value>>(count: size*2, repeatedValue: Placeholder<Key, Value>())
        for (key, value) in oldDictionary {
            self[key] = value
        }
    }
}

在 Swift 的結構體中， self 可以訪問當前類型的值和函數，但是它也是可變的。你可以對它設置新值，拷貝它，或者就把它當成另一個變量的引用。

兩周前我開玩笑說 Swift 是比 Objective-C ，Ruby 或者 Python 更動態的語言。因為你可以改變它的錯誤行為，但是這里有另一種情況，即你可以在 Swift 中修改一些在 Objective-C 中不能修改的東西： self 本身的引用。我們本可以在該方法中這樣寫 self = Dictionary(size: size*2) ，這在 Swift 是絕對有效的。對于那些覺得對象標識是最重要的面向對象開發者而言，這非常奇怪。

包含排序，刪除，調整數組大小的完整的實現可以在 gist 中找到。除了 count/generate() 懶求值的實現，我非常喜歡這個小工程的表達方式。

來自：http://swift.gg/2016/08/08/implementing-dictionary-in-swift/

本文由用戶 NevilleGent 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1470731573508.html

Swift Apple Swift開發

在 Swift 中實現字典

相關經驗

相關資訊

相關文檔

目錄