• Swift字典用來(lái)存儲(chǔ)無(wú)序的相同類(lèi)型數(shù)據(jù)的集合，字典會(huì)強(qiáng)制檢測(cè)元素的類(lèi)型，如果類(lèi)型不同則會(huì)報(bào)錯(cuò)。
• Swift字典每個(gè)值（value）都關(guān)聯(lián)唯一的鍵（key），鍵作為字典中的這個(gè)值數(shù)據(jù)的標(biāo)識(shí)符。
• 和數(shù)組中的元素不同，字典中的元素并沒(méi)有具體順序，需要通過(guò)key訪問(wèn)到元素。
• 字典的key沒(méi)有類(lèi)型限制，可以是Int或String，但必須是唯一的。
• 如果創(chuàng)建一個(gè)字典，并賦值給一個(gè)變量，則創(chuàng)建的字典是可以修改的。這意味著在創(chuàng)建字典后，可以通過(guò)添加、刪除、修改的方式改變字典里的元素。
• 如果將一個(gè)字典賦值給常量，字典是不可修改的，并且字典的大小和內(nèi)容都不可以修改。

基本定義

Dictionary類(lèi)型的鍵值對(duì)必須遵循Hashable協(xié)議，因?yàn)樗褂玫木褪枪１?/p>

哈希表

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

散列函數(shù)

散列函數(shù)又稱(chēng)散列算法、哈希函數(shù)。它的目標(biāo)是計(jì)算key在數(shù)組中的下標(biāo)。

幾種常用的散列函數(shù)構(gòu)造方法：

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

哈希沖突

再優(yōu)秀的哈希算法永遠(yuǎn)無(wú)法避免出現(xiàn)哈希沖突。哈希沖突指的是兩個(gè)不同的key經(jīng)過(guò)哈希計(jì)算后得到的數(shù)組下標(biāo)是相同的。

哈希沖突幾種常用的解決方法：

• 開(kāi)放定址法
• 拉鏈法

負(fù)載因?

負(fù)載因子 = 填?表中的元素個(gè)數(shù) / 散列表的?度

一個(gè)非空散列表的負(fù)載因子是填?表中的元素個(gè)數(shù) / 散列表的?度。這是面臨再次散列或擴(kuò)容時(shí)的決策參數(shù)，有助于確定散列函數(shù)的效率。也就是說(shuō)，該參數(shù)指出了散列函數(shù)是否將關(guān)鍵字均勻分布。

內(nèi)存布局

Dictionary是否是連續(xù)的內(nèi)存地址空間？如果不是，當(dāng)前元素和元素之前的關(guān)系如何確定？如何計(jì)算?個(gè)元素的地址？

通過(guò)字?量方式創(chuàng)建?個(gè)字典：

var dic = ["1": "Kody", "2": "Hank", "3": "Cooci", "4" : "Cat"]

源碼分析

上述代碼，通過(guò)字?量方式創(chuàng)建Dictionary，在源碼中可以直接搜索literal

打開(kāi)Dictionary.swift文件，找到init(dictionaryLiteral elements:)的定義：

  @inlinable
  @_effects(readonly)
  @_semantics("optimize.sil.specialize.generic.size.never")
  public init(dictionaryLiteral elements: (Key, Value)...) {
    let native = _NativeDictionary<Key, Value>(capacity: elements.count)
    for (key, value) in elements {
      let (bucket, found) = native.find(key)
      _precondition(!found, "Dictionary literal contains duplicate keys")
      native._insert(at: bucket, key: key, value: value)
    }
    self.init(_native: native)
  }

• 創(chuàng)建了一個(gè)_NativeDictionary的實(shí)例對(duì)象
• 遍歷elements，通過(guò)實(shí)例對(duì)象的find方法，找到key值對(duì)應(yīng)的bucket
• bucket相當(dāng)于要插入的位置
• 將key、value循環(huán)插入到bucket中
• 最后調(diào)用init方法
• found：布爾類(lèi)型，如果字典初始化時(shí)，字面量里包含重復(fù)key值，運(yùn)行時(shí)報(bào)錯(cuò)Dictionary literal contains duplicate keys
  

打開(kāi)NativeDictionary.swift文件，找到_NativeDictionary的定義：

@usableFromInline
@frozen
internal struct _NativeDictionary<Key: Hashable, Value> {
  @usableFromInline
  internal typealias Element = (key: Key, value: Value)

  /// See this comments on __RawDictionaryStorage and its subclasses to
  /// understand why we store an untyped storage here.
  @usableFromInline
  internal var _storage: __RawDictionaryStorage

  /// Constructs an instance from the empty singleton.
  @inlinable
  internal init() {
    self._storage = __RawDictionaryStorage.empty
  }

  /// Constructs a dictionary adopting the given storage.
  @inlinable
  internal init(_ storage: __owned __RawDictionaryStorage) {
    self._storage = storage
  }

  @inlinable
  internal init(capacity: Int) {
    if capacity == 0 {
      self._storage = __RawDictionaryStorage.empty
    } else {
      self._storage = _DictionaryStorage<Key, Value>.allocate(capacity: capacity)
    }
  }

#if _runtime(_ObjC)
  @inlinable
  internal init(_ cocoa: __owned __CocoaDictionary) {
    self.init(cocoa, capacity: cocoa.count)
  }

  @inlinable
  internal init(_ cocoa: __owned __CocoaDictionary, capacity: Int) {
    if capacity == 0 {
      self._storage = __RawDictionaryStorage.empty
    } else {
      _internalInvariant(cocoa.count <= capacity)
      self._storage =
        _DictionaryStorage<Key, Value>.convert(cocoa, capacity: capacity)
      for (key, value) in cocoa {
        insertNew(
          key: _forceBridgeFromObjectiveC(key, Key.self),
          value: _forceBridgeFromObjectiveC(value, Value.self))
      }
    }
  }
#endif
}

• _NativeDictionary是一個(gè)結(jié)構(gòu)體
• 使用init(capacity:)方法初始化，如果capacity容量等于0，使用__RawDictionaryStorage.empty。否則使用_DictionaryStorage，通過(guò)allocate方法，按容量大小分配內(nèi)存空間

打開(kāi)DictionaryStorage.swift文件，找到_DictionaryStorage的定義：

@usableFromInline
final internal class _DictionaryStorage<Key: Hashable, Value>
  : __RawDictionaryStorage, _NSDictionaryCore {
  // This type is made with allocWithTailElems, so no init is ever called.
  // But we still need to have an init to satisfy the compiler.
  @nonobjc
  override internal init(_doNotCallMe: ()) {
    _internalInvariantFailure("This class cannot be directly initialized")
  }

  deinit {
    guard _count > 0 else { return }
    if !_isPOD(Key.self) {
      let keys = self._keys
      for bucket in _hashTable {
        (keys + bucket.offset).deinitialize(count: 1)
      }
    }
    if !_isPOD(Value.self) {
      let values = self._values
      for bucket in _hashTable {
        (values + bucket.offset).deinitialize(count: 1)
      }
    }
    _count = 0
    _fixLifetime(self)
  }

  @inlinable
  final internal var _keys: UnsafeMutablePointer<Key> {
    @inline(__always)
    get {
      return self._rawKeys.assumingMemoryBound(to: Key.self)
    }
  }

  @inlinable
  final internal var _values: UnsafeMutablePointer<Value> {
    @inline(__always)
    get {
      return self._rawValues.assumingMemoryBound(to: Value.self)
    }
  }

  internal var asNative: _NativeDictionary<Key, Value> {
    return _NativeDictionary(self)
  }

#if _runtime(_ObjC)
  @objc
  internal required init(
    objects: UnsafePointer<AnyObject?>,
    forKeys: UnsafeRawPointer,
    count: Int
  ) {
    _internalInvariantFailure("This class cannot be directly initialized")
  }

  @objc(copyWithZone:)
  internal func copy(with zone: _SwiftNSZone?) -> AnyObject {
    return self
  }

  @objc
  internal var count: Int {
    return _count
  }

  @objc(keyEnumerator)
  internal func keyEnumerator() -> _NSEnumerator {
    return _SwiftDictionaryNSEnumerator<Key, Value>(asNative)
  }

  @objc(countByEnumeratingWithState:objects:count:)
  internal func countByEnumerating(
    with state: UnsafeMutablePointer<_SwiftNSFastEnumerationState>,
    objects: UnsafeMutablePointer<AnyObject>?, count: Int
  ) -> Int {
    defer { _fixLifetime(self) }
    let hashTable = _hashTable

    var theState = state.pointee
    if theState.state == 0 {
      theState.state = 1 // Arbitrary non-zero value.
      theState.itemsPtr = AutoreleasingUnsafeMutablePointer(objects)
      theState.mutationsPtr = _fastEnumerationStorageMutationsPtr
      theState.extra.0 = CUnsignedLong(hashTable.startBucket.offset)
    }

    // Test 'objects' rather than 'count' because (a) this is very rare anyway,
    // and (b) the optimizer should then be able to optimize away the
    // unwrapping check below.
    if _slowPath(objects == nil) {
      return 0
    }

    let unmanagedObjects = _UnmanagedAnyObjectArray(objects!)
    var bucket = _HashTable.Bucket(offset: Int(theState.extra.0))
    let endBucket = hashTable.endBucket
    _precondition(bucket == endBucket || hashTable.isOccupied(bucket),
      "Invalid fast enumeration state")
    var stored = 0
    for i in 0..<count {
      if bucket == endBucket { break }

      let key = _keys[bucket.offset]
      unmanagedObjects[i] = _bridgeAnythingToObjectiveC(key)

      stored += 1
      bucket = hashTable.occupiedBucket(after: bucket)
    }
    theState.extra.0 = CUnsignedLong(bucket.offset)
    state.pointee = theState
    return stored
  }

  @objc(objectForKey:)
  internal func object(forKey aKey: AnyObject) -> AnyObject? {
    guard let nativeKey = _conditionallyBridgeFromObjectiveC(aKey, Key.self)
    else { return nil }

    let (bucket, found) = asNative.find(nativeKey)
    guard found else { return nil }
    let value = asNative.uncheckedValue(at: bucket)
    return _bridgeAnythingToObjectiveC(value)
  }

  @objc(getObjects:andKeys:count:)
  internal func getObjects(
    _ objects: UnsafeMutablePointer<AnyObject>?,
    andKeys keys: UnsafeMutablePointer<AnyObject>?,
    count: Int) {
    _precondition(count >= 0, "Invalid count")
    guard count > 0 else { return }
    var i = 0 // Current position in the output buffers
    switch (_UnmanagedAnyObjectArray(keys), _UnmanagedAnyObjectArray(objects)) {
    case (let unmanagedKeys?, let unmanagedObjects?):
      for (key, value) in asNative {
        unmanagedObjects[i] = _bridgeAnythingToObjectiveC(value)
        unmanagedKeys[i] = _bridgeAnythingToObjectiveC(key)
        i += 1
        guard i < count else { break }
      }
    case (let unmanagedKeys?, nil):
      for (key, _) in asNative {
        unmanagedKeys[i] = _bridgeAnythingToObjectiveC(key)
        i += 1
        guard i < count else { break }
      }
    case (nil, let unmanagedObjects?):
      for (_, value) in asNative {
        unmanagedObjects[i] = _bridgeAnythingToObjectiveC(value)
        i += 1
        guard i < count else { break }
      }
    case (nil, nil):
      // Do nothing.
      break
    }
  }
#endif
}

• _DictionaryStorage是一個(gè)類(lèi)，繼承自__RawDictionaryStorage，遵循_NSDictionaryCore協(xié)議
• _DictionaryStorage使用final關(guān)鍵字修飾，子類(lèi)不可重寫(xiě)

找到__RawDictionaryStorage的定義：

@_fixed_layout
@usableFromInline
@_objc_non_lazy_realization
internal class __RawDictionaryStorage: __SwiftNativeNSDictionary {
  // NOTE: The precise layout of this type is relied on in the runtime to
  // provide a statically allocated empty singleton.  See
  // stdlib/public/stubs/GlobalObjects.cpp for details.

  /// The current number of occupied entries in this dictionary.
  @usableFromInline
  @nonobjc
  internal final var _count: Int

  /// The maximum number of elements that can be inserted into this set without
  /// exceeding the hash table's maximum load factor.
  @usableFromInline
  @nonobjc
  internal final var _capacity: Int

  /// The scale of this dictionary. The number of buckets is 2 raised to the
  /// power of `scale`.
  @usableFromInline
  @nonobjc
  internal final var _scale: Int8

  /// The scale corresponding to the highest `reserveCapacity(_:)` call so far,
  /// or 0 if there were none. This may be used later to allow removals to
  /// resize storage.
  ///
  /// FIXME: <rdar://problem/18114559> Shrink storage on deletion
  @usableFromInline
  @nonobjc
  internal final var _reservedScale: Int8

  // Currently unused, set to zero.
  @nonobjc
  internal final var _extra: Int16

  /// A mutation count, enabling stricter index validation.
  @usableFromInline
  @nonobjc
  internal final var _age: Int32

  /// The hash seed used to hash elements in this dictionary instance.
  @usableFromInline
  internal final var _seed: Int

  /// A raw pointer to the start of the tail-allocated hash buffer holding keys.
  @usableFromInline
  @nonobjc
  internal final var _rawKeys: UnsafeMutableRawPointer

  /// A raw pointer to the start of the tail-allocated hash buffer holding
  /// values.
  @usableFromInline
  @nonobjc
  internal final var _rawValues: UnsafeMutableRawPointer

  // This type is made with allocWithTailElems, so no init is ever called.
  // But we still need to have an init to satisfy the compiler.
  @nonobjc
  internal init(_doNotCallMe: ()) {
    _internalInvariantFailure("This class cannot be directly initialized")
  }

  @inlinable
  @nonobjc
  internal final var _bucketCount: Int {
    @inline(__always) get { return 1 &<< _scale }
  }

  @inlinable
  @nonobjc
  internal final var _metadata: UnsafeMutablePointer<_HashTable.Word> {
    @inline(__always) get {
      let address = Builtin.projectTailElems(self, _HashTable.Word.self)
      return UnsafeMutablePointer(address)
    }
  }

  // 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)
    }
  }
}

• __RawDictionaryStorage類(lèi)，定義基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)，例如_count、_capacity
• 其中_scale為2的n次方數(shù)，參與計(jì)算_bucketCount
• _seed為哈希種子

找到allocate的定義：

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

• 調(diào)用_HashTable的scale方法，計(jì)算scale
• 調(diào)用allocate方法，傳入scale

打開(kāi)HashTable.swift文件，找到_HashTable的定義：

@usableFromInline
@frozen
internal struct _HashTable {
  @usableFromInline
  internal typealias Word = _UnsafeBitset.Word

  @usableFromInline
  internal var words: UnsafeMutablePointer<Word>

  @usableFromInline
  internal let bucketMask: Int

  @inlinable
  @inline(__always)
  internal init(words: UnsafeMutablePointer<Word>, bucketCount: Int) {
    _internalInvariant(bucketCount > 0 && bucketCount & (bucketCount - 1) == 0,
      "bucketCount must be a power of two")
    self.words = words
    // The bucket count is a power of two, so subtracting 1 will never overflow
    // and get us a nice mask.
    self.bucketMask = bucketCount &- 1
  }

  @inlinable
  internal var bucketCount: Int {
    @inline(__always) get {
      return bucketMask &+ 1
    }
  }

  @inlinable
  internal var wordCount: Int {
    @inline(__always) get {
      return _UnsafeBitset.wordCount(forCapacity: bucketCount)
    }
  }
}

• words可以理解為二進(jìn)制位，記錄當(dāng)前位置是否插入元素
• bucketMask等于bucketCount-1，而bucketCount是2的n次方數(shù)，所以bucketMask相當(dāng)于掩碼
• _HashTable并不直接存儲(chǔ)數(shù)據(jù)，而是存儲(chǔ)二進(jìn)制位

回到DictionaryStorage.swift文件，找到allocate的定義：

  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
  }

• 通過(guò)&運(yùn)算符計(jì)算bucketCount
• wordCount通過(guò)bucketCount計(jì)算要記錄的二進(jìn)制位
• allocWithTailElems_3在類(lèi)的后面分配連續(xù)的內(nèi)存空間，分別存儲(chǔ)Key和Value

Dictionary內(nèi)存布局

• Dictionary包含DictionaryStorage類(lèi)
• DictionaryStorage類(lèi)包含metaData、refCount、_count、_capacity
• 中間64位存儲(chǔ)_scale、_reservedScale、_extra、_age
• 接下來(lái)存儲(chǔ)的_seed、_rawKeys、_rawValues、metaAddr
• 其中_rawKeys、_rawValues存儲(chǔ)的是數(shù)組地址

通過(guò)LLDB調(diào)試來(lái)驗(yàn)證?下：

通過(guò)字?量方式創(chuàng)建?個(gè)字典：

var dic = ["1": "Kody", "2": "Hank", "3": "Cooci", "4" : "Cat"]

通過(guò)withUnsafePointer打印dic內(nèi)存地址

通過(guò)x/8g查看dic的內(nèi)存地址，里面包含了一個(gè)堆上的地址0x000000010067aed0

通過(guò)x/8g查看內(nèi)存地址0x000000010067aed0

• 0x00007fff99540800：metaData元類(lèi)型
• 0x0000000000000002：refCoutn引用計(jì)數(shù)
• 0x0000000000000004：_count
• 0x0000000000000006：_capacity
• 0xcf1ba4a800000003：64位連續(xù)內(nèi)存，包含_scale、_reservedScale、_extra、_age
• 0x000000010067aed0：_seed種子，以對(duì)象創(chuàng)建的地址作為隨機(jī)數(shù)的開(kāi)始
• 0x000000010067af18：_rawKeys
• 0x000000010067af98：_rawValues

通過(guò)x/16g查看_rawKeys內(nèi)存地址

• 連續(xù)內(nèi)存中并不是連續(xù)存儲(chǔ)的，0x0000000000000032轉(zhuǎn)為十進(jìn)制是50，對(duì)應(yīng)的是key值2的ASCII碼
• 后面的0xe100000000000000表示key值2的字符串長(zhǎng)度
• 同理后面的0x0000000000000033、0x0000000000000031、0x0000000000000034分別對(duì)應(yīng)的key值是3、1、4

通過(guò)x/16g查看_rawValues內(nèi)存地址

• 和_rawKeys同理，前面的0x000000006b6e6148、0x00000069636f6f43、0x0000000079646f4b、0x0000000000746143表示value值
• 后面的0xe400000000000000、0xe500000000000000、0xe400000000000000、0xe300000000000000表示value值的字符串長(zhǎng)度

Dictionary插??個(gè)值

var dic = ["1": "Kody", "2": "Hank", "3": "Cooci", "4" : "Cat"]
dic["5"] = "Swift"

打開(kāi)Dictionary.swift文件，找到subscript的定義：

  @inlinable
  public subscript(
    key: Key, default defaultValue: @autoclosure () -> Value
  ) -> Value {
    @inline(__always)
    get {
      return _variant.lookup(key) ?? defaultValue()
    }
    @inline(__always)
    _modify {
      let (bucket, found) = _variant.mutatingFind(key)
      let native = _variant.asNative
      if !found {
        let value = defaultValue()
        native._insert(at: bucket, key: key, value: value)
      }
      let address = native._values + bucket.offset
      defer { _fixLifetime(self) }
      yield &address.pointee
    }
  }

• get方法里，_variant是一個(gè)關(guān)聯(lián)值的枚舉類(lèi)型
• 通過(guò)_variant的lookup方法，找到key值是否存在

打開(kāi)NativeDictionary.swift文件，找到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)
  }

• 通過(guò)find方法，傳入key，找到bucket和found

找到find的定義：

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

調(diào)用_storage的find方法，傳入key值

打開(kāi)DictionaryStorage.swift文件，找到find的定義：

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

• 調(diào)用key的_rawHashValue方法，傳入_seed種子
• 本質(zhì)上就是通過(guò)key值得到hashValue
• 調(diào)用find方法，傳入key和hashValue

找到find(_ key:, hashValue:)的定義：

  @_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)
  }
}

• 調(diào)用hashTable的idealBucket方法，傳入hashValue，返回bucket
• 通過(guò)_isOccupied方法判斷bucket是否被占用

打開(kāi)HashTable.swift文件，找到idealBucket的定義：

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

hashValue和bucketMask進(jìn)行&運(yùn)算，計(jì)算index保存到bucket中

找到_isOccupied的定義：

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

• 與原有的二進(jìn)制位進(jìn)行計(jì)算，使用uncheckedContains返回0或1，查看是否包含當(dāng)前bucket

找到bucket(wrappedAfter bucket:)的定義：

  @inlinable
  @inline(__always)
  internal func bucket(wrappedAfter bucket: Bucket) -> Bucket {
    // The bucket is less than bucketCount, which is power of two less than
    // Int.max. Therefore adding 1 does not overflow.
    return Bucket(offset: (bucket.offset &+ 1) & bucketMask)
  }

• bucket.offset進(jìn)行+1操作，再和bucketMask進(jìn)行&運(yùn)算，然后重新構(gòu)建bucket

打開(kāi)NativeDictionary.swift文件，找到uncheckedValue的定義：

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

• _values是連續(xù)存儲(chǔ)的數(shù)組，直接通過(guò)bucket.offset作為index獲取指定位置的元素

找到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)
    }
  }

• 通過(guò)mutatingFind找到bucket和found
• 如果存在，使用_values加上bucket.offset，將value覆蓋
• 如果不存在，使用_insert方法，在當(dāng)前bucket位置插入key和value

Dictionary插??個(gè)值的過(guò)程：

• 通過(guò)key找到key. hashValue
• 通過(guò)key. hashValue和bucketMask進(jìn)行&運(yùn)算，計(jì)算出index
• 通過(guò)index查找是否有對(duì)應(yīng)key值，如果有采用開(kāi)放定址法查找下一個(gè)bucket是否為空，如果為空返回對(duì)應(yīng)元素
• 對(duì)于setValue也是一樣，通過(guò)key值先查找，再賦值

使用Swift代碼實(shí)現(xiàn)簡(jiǎn)單的HashTable

struct HashTable<Key: Hashable, Value> {
    
    typealias Element = (key: Key, value: Value)
    typealias Bucket = [Element]

    var buckets: [Bucket]
    var count = 0
    
    init(capacity: Int){
        buckets = Array<Bucket>(repeating: [Element](), count: capacity)
    }
    
    func index(key: Key) -> Int {
        return abs(key.hashValue) % buckets.count
    }
    
    subscript(key: Key) -> Value? {
        
        get {
            return getValue(key: key)
        }
        
        set {
            if let value = newValue {
                updateValue(value, key)
            }
            else{
                removeValue(key)
            }
        }
    }
    
    func getValue(key: Key) -> Value? {
        let index = self.index(key: key)
        
        for element in buckets[index] {
            
            if(element.key == key){
                return element.value
            }
        }
        
        return nil
    }
    
    mutating func updateValue(_ value: Value, _ key: Key) -> Value? {
        let index = self.index(key: key)
        
        for (i, element) in buckets[index].enumerated() {
            
            if(element.key == key){
                let originValue = element.value
                buckets[index][i].value = value
                return originValue
            }
        }
        
        buckets[index].append((key: key, value: value))
        count += 1
        
        return nil
    }
    
    mutating func removeValue(_ key: Key) {
        let index = self.index(key: key)
        
        for (i, element) in buckets[index].enumerated() {
            
            if(element.key == key){
                buckets[index].remove(at: i)
                count -= 1
            }
        }
    }
}

var ht = HashTable<String, String>(capacity: 5)
ht["1"] = "Kody"
print(ht["1"])

//輸出以下內(nèi)容：
//Optional("Kody")