Swift - Dictionary

[TOC]

前言

Dictionary是一種無序的集合，它存儲的是鍵值對之間的關(guān)系，其所有鍵的值需要是相同的類型，所有值的類型也需要相同。每個值（value）都關(guān)聯(lián)唯一的鍵（key），鍵作為字典中這個值數(shù)據(jù)的標(biāo)識符。和數(shù)組中的數(shù)據(jù)項不同，字典中的數(shù)據(jù)項并沒有什么具體順序。你在需要通過標(biāo)識符（鍵）訪問數(shù)據(jù)的時候使用字典，這種方法很大程度上和現(xiàn)實世界中使用字典查字義的方法一樣。

本問不介紹字典的用法，如果你需要了解更多關(guān)于字典的用法請查看Swift.gg 字典

注意
Swift 的 Dictionary類型被橋接到Foundation的NSDictionary類

更多關(guān)于在Foundation和Cocoa中使用Dictionary類型的信息，參見Bridging Between Dictionary and NSDictionary

哈希表

首先我們先了解一下哈希表：

哈希表，也叫Hash Table或者散列表，是根據(jù)關(guān)鍵字（Key value）而直接訪問在內(nèi)存存儲位置的數(shù)據(jù)結(jié)構(gòu)。也就是說，它通過計算一個關(guān)于鍵值的函數(shù)，將所需查詢的數(shù)據(jù)映射到表中一個位置來訪問記錄，這加快了查找速度。這個映射函數(shù)稱做散列函數(shù)，存放記錄的數(shù)組稱做散列表。

哈希函數(shù)（散列函數(shù)）

• 直接尋址法
• 數(shù)字分析法
• 平方取中法
• 折疊法
• 隨機數(shù)法
• 除留余數(shù)法

哈希沖突

• 開放定址法
• 拉鏈法

負載因子

填入表中的元素個數(shù) / 散列表的長度

1. Dictionary 的內(nèi)存結(jié)構(gòu)

首先我們初始化一個字典：

var dict = ["key1" : "value1", "key2" : "value2", "key3" : "value3"]

-w762

1.1 dictionaryLiteral

查看一下sil代碼可以發(fā)現(xiàn)是調(diào)用的Dictionary.init(dictionaryLiteral:)方法，其實不看sil也能知道是調(diào)用了Literal方法，因為這是一個通過字面量初始化的字典。下面我們來到Swift源碼中的Dictionary.swift文件中來查找一下dictionaryLiteral方法。

-w583

首先我們可以看到Dictionary是一個結(jié)構(gòu)體。這里的Key需要遵循Hashable協(xié)議，也就是Key必須是可哈希的。

-w651

這個字面量的方法是遵循ExpressibleByDictionaryLiteral協(xié)議的。方法內(nèi)部流程如下：

• 首先創(chuàng)建一個_NativeDictionary類型的實例
• 然后循環(huán)向里面插入數(shù)據(jù)，如果存在重復(fù)的key就會報錯
• 最后調(diào)用Dictionary的init方法進行初始化

1.2 _NativeDictionary

下面我們就來看看_NativeDictionary是什么？在NativeDictionary.swift文件中。

-w641

我們可以看到_NativeDictionary是對__RawDictionaryStorage的包裝，用于實現(xiàn)字典的大部分功能。

-w664

再看一下init(capacity:)方法，這里區(qū)分了字典在初始化的時候是空的還是不空的。所以我們主要看不空的情況。

1.3 _DictionaryStorage

下面我們看看_DictionaryStorage：

-w603

可以看到_DictionaryStorage是一個類，繼承自__RawDictionaryStorage 和_NSDictionaryCore。

1.4 __RawDictionaryStorage

下面我們看看__RawDictionaryStorage，在DictionaryStorage.swift文件中：

-w789

我們可以看到__RawDictionaryStorage是一個類，繼承自__SwiftNativeNSDictionary，定義了如下屬性：

1.5 __SwiftNativeNSDictionary

-w535

在Runtime.swift中我們可以找到__SwiftNativeNSDictionary的定義，如上圖。

1.6 _NSDictionaryCore

在ShadowProtocols.swift文件中我們可以找到_NSDictionaryCore的定義：

-w618

_NSDictionaryCore是一個協(xié)議，這也是我們上面提到的，Swift 的 Dictionary類型被橋接到Foundation的NSDictionary類，這就是與NSDictionary橋接的接口。

/// A shadow for the "core operations" of NSDictionary.
///
/// Covers a set of operations everyone needs to implement in order to
/// be a useful `NSDictionary` subclass.
@objc
internal protocol _NSDictionaryCore: _NSCopying, _NSFastEnumeration {
  // The following methods should be overridden when implementing an
  // NSDictionary subclass.

  // The designated initializer of `NSDictionary`.
  init(
    objects: UnsafePointer<AnyObject?>,
    forKeys: UnsafeRawPointer, count: Int)

  var count: Int { get }

  @objc(objectForKey:)
  func object(forKey aKey: AnyObject) -> AnyObject?

  func keyEnumerator() -> _NSEnumerator

  // We also override the following methods for efficiency.

  @objc(copyWithZone:)
  override func copy(with zone: _SwiftNSZone?) -> AnyObject

  @objc(getObjects:andKeys:count:)
  func getObjects(
    _ objects: UnsafeMutablePointer<AnyObject>?,
    andKeys keys: UnsafeMutablePointer<AnyObject>?,
    count: Int
  )

  @objc(countByEnumeratingWithState:objects:count:)
  override func countByEnumerating(
    with state: UnsafeMutablePointer<_SwiftNSFastEnumerationState>,
    objects: UnsafeMutablePointer<AnyObject>?, count: Int
  ) -> Int
}

1.7 Dictionary init

下面我們回到Dictionary的init方法。

在字面量初始化的時候是這么調(diào)用的self.init(_native: native)

-w576

1.8 _Variant

-w639

在Dictionary.swift文件中經(jīng)過一番查找，可以看到_Variant是一個具有關(guān)聯(lián)值的枚舉類型。

1.9 Dictionary內(nèi)存結(jié)構(gòu)總結(jié)

經(jīng)過上面的分析我們可以得到如下的結(jié)論，在純Swift 的字典中其內(nèi)存結(jié)構(gòu)如下：

• Dictionary----->包含關(guān)聯(lián)值枚舉屬性_variant初始化的關(guān)聯(lián)值是_NativeDictionary
• _NativeDictionary是一個結(jié)構(gòu)體包含屬性 _storage，類型是__RawDictionaryStorage
• __RawDictionaryStorage是一個類型，初始化_storage的時候使用的是子類_DictionaryStorage

所以我們可以得到Dictionary的內(nèi)存結(jié)構(gòu)如下：

-w742

1.10 _DictionaryStorage<Key, Value>.allocate(capacity:)

根據(jù)上面的總結(jié)的內(nèi)存結(jié)構(gòu)我們可以知道，這里面重要的額就是_DictionaryStorage，它在初始化的時候調(diào)用的是allocate(capacity:)方法，下面我們看看這個方法都做了什么在DictionaryStorage.swift文件中可以看到如下代碼：

  @usableFromInline
  @_effects(releasenone)
  static internal func allocate(capacity: Int) -> _DictionaryStorage {
    let scale = _HashTable.scale(forCapacity: capacity)
    return allocate(scale: scale, age: nil, seed: nil)
  }

可以看到這里面有一個_HashTable，下面我們看看這個_HashTable是什么。

1.11 _HashTable

在HashTable.swift文件中可以找到_HashTable的定義。

-w571

在_HashTable中可以發(fā)現(xiàn)兩個屬性：

• words這是一個二進制位，用于標(biāo)記當(dāng)前位置是否存儲了元素
• 掩碼，bucketCount - 1 也就是2^n - 1，n的值來自scale

下面我們在看看_HashTable.scale(forCapacity:）方法：

  internal static func scale(forCapacity capacity: Int) -> Int8 {
    let capacity = Swift.max(capacity, 1)
    // Calculate the minimum number of entries we need to allocate to satisfy
    // the maximum load factor. `capacity + 1` below ensures that we always
    // leave at least one hole.
    let minimumEntries = Swift.max(
      Int((Double(capacity) / maxLoadFactor).rounded(.up)),
      capacity + 1)
    // The actual number of entries we need to allocate is the lowest power of
    // two greater than or equal to the minimum entry count. Calculate its
    // exponent.
    let exponent = (Swift.max(minimumEntries, 2) - 1)._binaryLogarithm() + 1
    _internalInvariant(exponent >= 0 && exponent < Int.bitWidth)
    // The scale is the exponent corresponding to the bucket count.
    let scale = Int8(truncatingIfNeeded: exponent)
    _internalInvariant(self.capacity(forScale: scale) >= capacity)
    return scale
  }

這里就是計算scale的，通過傳入的capacity，這里是這樣的，scale指數(shù)的冪，為了方便通過哈希計算出元素的位置，這里面看過看過Objective-C或者Swift底層源碼的同學(xué)都知道，蘋果在底層經(jīng)常會用到一個叫做mask的值，也就是掩碼。在objc_msgSend查找緩存的時候，計算index通過sel & mask= index。下面我們就要知道這個mask的值是如何取得的。

通常情況下mask的取值范圍是2^n - 1。

所以有這么一個表達式：x % y = x & (y - 1)，其中y的取值是2^n，一個數(shù)對2^n取模相當(dāng)于一個數(shù)和2^n - 1做按位與運算。

舉個例子:
3 % 4 = 3 & 3
5 % 4 = 5 & 3

為了方便計算位置，我們可以通過與運算的方式來計算index。那么我們就要在初始化的時候，通過計算得到一個稍大的與想要的大小最接近的2^n的容量。

舉個例子，如果要存儲3個元素，就要開辟4個空間，2^scale = 4，所以scale = 2。所以scale(forCapacity:)方法的作用就是計算這個scale的。當(dāng)然，看注釋還有很多細節(jié)，這里就不過多介紹了。

1.12 _DictionaryStorage.allocate(scale:, age:, seed:)

知道如何計算scale后，我們回到_DictionaryStorage中看看它的_DictionaryStorage.allocate(scale:, age:, seed:)

static internal func allocate(
    scale: Int8,
    age: Int32?,
    seed: Int?
  ) -> _DictionaryStorage {
    // The entry count must be representable by an Int value; hence the scale's
    // peculiar upper bound.
    _internalInvariant(scale >= 0 && scale < Int.bitWidth - 1)

    let bucketCount = (1 as Int) &<< scale
    let wordCount = _UnsafeBitset.wordCount(forCapacity: bucketCount)
    let storage = Builtin.allocWithTailElems_3(
      _DictionaryStorage<Key, Value>.self,
      wordCount._builtinWordValue, _HashTable.Word.self,
      bucketCount._builtinWordValue, Key.self,
      bucketCount._builtinWordValue, Value.self)

    let metadataAddr = Builtin.projectTailElems(storage, _HashTable.Word.self)
    let keysAddr = Builtin.getTailAddr_Word(
      metadataAddr, wordCount._builtinWordValue, _HashTable.Word.self,
      Key.self)
    let valuesAddr = Builtin.getTailAddr_Word(
      keysAddr, bucketCount._builtinWordValue, Key.self,
      Value.self)
    storage._count = 0
    storage._capacity = _HashTable.capacity(forScale: scale)
    storage._scale = scale
    storage._reservedScale = 0
    storage._extra = 0

    if let age = age {
      storage._age = age
    } else {
      // The default mutation count is simply a scrambled version of the storage
      // address.
      storage._age = Int32(
        truncatingIfNeeded: ObjectIdentifier(storage).hashValue)
    }

    storage._seed = seed ?? _HashTable.hashSeed(for: storage, scale: scale)
    storage._rawKeys = UnsafeMutableRawPointer(keysAddr)
    storage._rawValues = UnsafeMutableRawPointer(valuesAddr)

    // Initialize hash table metadata.
    storage._hashTable.clear()
    return storage
  }

-w688

我們可以看到這里初始化了_DictionaryStorage對應(yīng)的屬性。

1.13 lldb 驗證內(nèi)存結(jié)構(gòu)

編寫一段簡單的代碼：

var dict = ["1" : "a", "2" : "b", "3" : "c", "4" : "d"]

-w899

看圖吧。

這里的capacity為什么是6呢？看了源碼就知道了：

storage._capacity = _HashTable.capacity(forScale: scale)

extension _HashTable {
  /// The inverse of the maximum hash table load factor.
  private static var maxLoadFactor: Double {
    @inline(__always) get { return 3 / 4 }
  }

  internal static func capacity(forScale scale: Int8) -> Int {
    let bucketCount = (1 as Int) &<< scale
    return Int(Double(bucketCount) * maxLoadFactor)
  }
}

這里面取3/4，所以就是8 * 3/4 = 6。8是2^{3，因為初始化的4個鍵值對，為了保證一定有空間，比4大的最小的2}n是8，所以scale為3。

2. get & set

這里我們通過下標(biāo)來入手，首先找到subscript方法：

  @inlinable
  public subscript(key: Key) -> Value? {
    get {
      return _variant.lookup(key)
    }
    set(newValue) {
      if let x = newValue {
        _variant.setValue(x, forKey: key)
      } else {
        removeValue(forKey: key)
      }
    }
    _modify {
      defer { _fixLifetime(self) }
      yield &_variant[key]
    }
  }
}

2.1 get

2.1.1 lookup

在subscript方法中我們可以看到get中會調(diào)用一個lookup方法，_variant是個關(guān)聯(lián)值枚舉，關(guān)聯(lián)值類型是_NativeDictionary，所以在_NativeDictionary找到lookup如下：

  @inlinable
  @inline(__always)
  func lookup(_ key: Key) -> Value? {
    if count == 0 {
      // Fast path that avoids computing the hash of the key.
      return nil
    }
    let (bucket, found) = self.find(key)
    guard found else { return nil }
    return self.uncheckedValue(at: bucket)
  }

• 這里面主要是調(diào)用find方法。
• 如果沒找到就返回nil
• 找到了就調(diào)用uncheckedValue去根據(jù)下標(biāo)查找，然后返回

  @inlinable
  @inline(__always)
  internal func uncheckedValue(at bucket: Bucket) -> Value {
    defer { _fixLifetime(self) }
    _internalInvariant(hashTable.isOccupied(bucket))
    return _values[bucket.offset]
  }

2.1.2 _NativeDictionary find

find方法代碼如下：

  @inlinable
  @inline(__always)
  internal func find(_ key: Key) -> (bucket: Bucket, found: Bool) {
    return _storage.find(key)
  }

這里面調(diào)用的是_storage.find

2.1.2 __RawDictionaryStorage.find

代碼如下：

internal final func find<Key: Hashable>(_ key: Key) -> (bucket: _HashTable.Bucket, found: Bool) {
    return find(key, hashValue: key._rawHashValue(seed: _seed))
  }

里面又調(diào)用了另一個find方法，代碼如下：

  @_alwaysEmitIntoClient
  @inline(never)
  internal final func find<Key: Hashable>(_ key: Key, hashValue: Int) -> (bucket: _HashTable.Bucket, found: Bool) {
      let hashTable = _hashTable
      var bucket = hashTable.idealBucket(forHashValue: hashValue)
      while hashTable._isOccupied(bucket) {
        if uncheckedKey(at: bucket) == key {
          return (bucket, true)
        }
        bucket = hashTable.bucket(wrappedAfter: bucket)
      }
      return (bucket, false)
  }

_hashTable為一個計算屬性，代碼如下：

  // The _HashTable struct contains pointers into tail-allocated storage, so
  // this is unsafe and needs `_fixLifetime` calls in the caller.
  @inlinable
  @nonobjc
  internal final var _hashTable: _HashTable {
    @inline(__always) get {
      return _HashTable(words: _metadata, bucketCount: _bucketCount)
}

這里就是初始化了一個_HashTable

idealBucket方法的代碼如下：

@inlinable
  @inline(__always)
  internal func idealBucket(forHashValue hashValue: Int) -> Bucket {
    return Bucket(offset: hashValue & bucketMask)
  }

idealBucket是返回了一個Bucket，將hashValue & bucketMask得到對應(yīng)的index

_isOccupied源碼如下：

@inlinable
  @inline(__always)
  internal func _isOccupied(_ bucket: Bucket) -> Bool {
    _internalInvariant(isValid(bucket))
    return words[bucket.word].uncheckedContains(bucket.bit)
  }

_isOccupied返回當(dāng)前二進制位標(biāo)記的是否有元素。

所以通過上述一系列操作，最終會判斷是否找到當(dāng)前的key，如果找到就返回，找不到就下一個，直到?jīng)]有下一個返回一個元組，內(nèi)容為當(dāng)前bucket和是否找到。

接下來就需要回到lookup里面分析了，在上面有提到，回去再看看就行。這里面就使用了開放尋址法。

2.2 set

下面我們在看看set，如果有值就調(diào)用_variant.setValue，沒值就removeValue。

我們先看看有值的情況：

2.2.1 setValue

在_NativeDictionary找到setValue如下：

  @inlinable
  internal mutating func setValue(
    _ value: __owned Value,
    forKey key: Key,
    isUnique: Bool
  ) {
    let (bucket, found) = mutatingFind(key, isUnique: isUnique)
    if found {
      (_values + bucket.offset).pointee = value
    } else {
      _insert(at: bucket, key: key, value: value)
    }
  }

其實也很簡單，還是先去查找，如果找到了就覆蓋，沒找到就插入。

2.2.2 mutatingFind

代碼如下：

  @inlinable
  internal mutating func mutatingFind(
    _ key: Key,
    isUnique: Bool
  ) -> (bucket: Bucket, found: Bool) {
    let (bucket, found) = find(key)

    // Prepare storage.
    // If `key` isn't in the dictionary yet, assume that this access will end
    // up inserting it. (If we guess wrong, we might needlessly expand
    // storage; that's fine.) Otherwise this can only be a removal or an
    // in-place mutation.
    let rehashed = ensureUnique(
      isUnique: isUnique,
      capacity: count + (found ? 0 : 1))
    guard rehashed else { return (bucket, found) }
    let (b, f) = find(key)
    if f != found {
      KEY_TYPE_OF_DICTIONARY_VIOLATES_HASHABLE_REQUIREMENTS(Key.self)
    }
    return (b, found)
  }

這里面還是調(diào)用find(key)去查找，詳細分析看上面的get，如果沒找到則說明要插入，這里我們會嘗試去開辟空間（擴容），最后還是返回一個元組。

2.2.3 _insert

如果沒找到就是插入，代碼如下：

  @inlinable
  internal func _insert(
    at bucket: Bucket,
    key: __owned Key,
    value: __owned Value) {
    _internalInvariant(count < capacity)
    hashTable.insert(bucket)
    uncheckedInitialize(at: bucket, toKey: key, value: value)
    _storage._count += 1
  }

插入就簡單了：

• 首先判斷容量夠不夠，不夠應(yīng)該擴容，這個方法沒仔細找
• 然后插入數(shù)據(jù)
• 調(diào)用uncheckedInitialize
• count + 1

2.2.4 removeValue

下面我們再來看看removeValue，代碼如下：

  @inlinable
  @discardableResult
  public mutating func removeValue(forKey key: Key) -> Value? {
    return _variant.removeValue(forKey: key)
  }

2.2.5 _variant.removeValue

這個是通過斷點找到的，在DictionaryVariant.swift文件中：

extension Dictionary._Variant {
  @inlinable
  internal mutating func removeValue(forKey key: Key) -> Value? {
#if _runtime(_ObjC)
    guard isNative else {
      let cocoaKey = _bridgeAnythingToObjectiveC(key)
      let cocoa = asCocoa
      guard cocoa.lookup(cocoaKey) != nil else { return nil }
      var native = _NativeDictionary<Key, Value>(cocoa)
      let (bucket, found) = native.find(key)
      _precondition(found, "Bridging did not preserve equality")
      let old = native.uncheckedRemove(at: bucket, isUnique: true).value
      self = .init(native: native)
      return old
    }
#endif
    let (bucket, found) = asNative.find(key)
    guard found else { return nil }
    let isUnique = isUniquelyReferenced()
    return asNative.uncheckedRemove(at: bucket, isUnique: isUnique).value
  }
}

是通過擴展Dictionary._Variant的一個方法。

• 首先是判斷了是不是與objc交互
• 如果不是則通過find查找，這里跟上面也是一樣的
• 如果沒找到就返回nil
• 找到了則調(diào)用uncheckedRemove清空

2.2.6 uncheckedRemove

這個就是_NativeDictionary中的方法了：

  @inlinable
  @_semantics("optimize.sil.specialize.generic.size.never")
  internal mutating func uncheckedRemove(
    at bucket: Bucket,
    isUnique: Bool
  ) -> Element {
    _internalInvariant(hashTable.isOccupied(bucket))
    let rehashed = ensureUnique(isUnique: isUnique, capacity: capacity)
    _internalInvariant(!rehashed)
    let oldKey = (_keys + bucket.offset).move()
    let oldValue = (_values + bucket.offset).move()
    _delete(at: bucket)
    return (oldKey, oldValue)
  }

關(guān)于里面的調(diào)用就不具體分析了，感興趣的去源碼中再仔細看看吧