Swift-14：Array與Dictionary

LazySequence

先看一下下面代碼

image.png

從打印結(jié)果我們可以看到，首先Lazy的方式其實(shí)就是保存當(dāng)前集合和對(duì)應(yīng)的操作，然后在訪(fǎng)問(wèn)具體元素的時(shí)候，執(zhí)行對(duì)應(yīng)的操作。
LazyMapSequence<Array<Int>, Int>(_base: [1, 2, 3, 4], _transform: (Function))這是個(gè)什么東東呢？很明顯這是一個(gè)初始化的結(jié)構(gòu)體
我們看看源碼是不是這個(gè)東西呢？
image.png

<Base: Sequence, Element> 這是類(lèi)型約束，這里不太明白的童鞋可以看我Swift-12：泛型講的泛型以及類(lèi)型約束，初始化中保存當(dāng)前集合_base和對(duì)應(yīng)的操作_transform
當(dāng)我們?cè)L問(wèn)元素的時(shí)候，本質(zhì)上，繼承了Sequence協(xié)議，通過(guò)訪(fǎng)問(wèn)自身迭代器_base.next()迭代當(dāng)前的元素,然后對(duì)單個(gè)元素進(jìn)行map(_transform)操作，就得來(lái)了map之后的元素

image.png

應(yīng)用：一般我們數(shù)組數(shù)據(jù)特別大的時(shí)候我們使用lazy關(guān)鍵字。
比如Array(0...10000)

Array

源碼比較多，我摘要一下Array的內(nèi)存布局
Struct Array------> Struct _ContiguousArrayBuffer----->Class __ContiguousArrayStorageBase------>包含了?個(gè)屬性 Struct ArrayBody ------ > 包含了?個(gè)屬性 struct _SwiftArrayBodyStorage -------> 包含了兩個(gè)屬性 count & _capacityAndFlags
類(lèi)里面存的分別是 metaData、refCount、count、 _capacityAndFlags、firstElementAddress
結(jié)構(gòu)體包含結(jié)構(gòu)體，結(jié)構(gòu)體中包含類(lèi)，類(lèi)中在包含結(jié)構(gòu)體成員
我們來(lái)調(diào)試驗(yàn)證一下


image.png

append

image.png
image.png

如果是多個(gè)引用計(jì)數(shù)，就會(huì)createNewBuffer，這也就是所謂的寫(xiě)時(shí)復(fù)制
這里補(bǔ)充一下：當(dāng)值類(lèi)型包含引用類(lèi)型時(shí)，值類(lèi)型copy也會(huì)對(duì)內(nèi)部的引用類(lèi)型進(jìn)行+1，驗(yàn)證一下：


image.png

注意自定義的結(jié)構(gòu)體是沒(méi)有寫(xiě)時(shí)賦值功能的，這是集合等類(lèi)型swift底層實(shí)現(xiàn)的，我們接下來(lái)看看是如何實(shí)現(xiàn)的


image.png

image.png

  1. 判斷引用計(jì)數(shù)，>1 重新分配內(nèi)存空間返回newBuffer，為了寫(xiě)時(shí)復(fù)制
    2.如果加一之后>buffer的容量capacity也會(huì)從新開(kāi)辟內(nèi)存空間，將原有的element拼接到新的內(nèi)存空間中


    image.png

    image.png

    斷點(diǎn)驗(yàn)證

ar numbers = [1,2,3,4,5,6]
numbers.append(7)
print("end")
image.png

寫(xiě)時(shí)復(fù)制總結(jié)

看了大部分網(wǎng)上關(guān)于寫(xiě)時(shí)復(fù)制的說(shuō)法，其實(shí)不夠準(zhǔn)確。

Array，Dictionary 和 Set 這樣的集合類(lèi)型是通過(guò)一種叫做寫(xiě)時(shí)復(fù)制 (copy-on-write) 的技術(shù)實(shí)現(xiàn)的，在內(nèi)部，這些 Array 結(jié)構(gòu)體含有指向某個(gè)內(nèi)存的引用，也就是前面的__ContiguousArrayStorageBase引用類(lèi)型的地址，這地址指向的內(nèi)存就是數(shù)組中元素所存儲(chǔ)的位置。賦值時(shí)，兩個(gè)數(shù)組的引用指向的是內(nèi)存中同一個(gè)位置，這兩個(gè)數(shù)組共享了它們的存儲(chǔ)部分。不過(guò)，當(dāng)我 們改變 其中一個(gè)數(shù)組的時(shí)候，這個(gè)共享會(huì)被檢測(cè)到，內(nèi)存將會(huì)被復(fù)制。這樣一來(lái)，我們得以獨(dú)立地改變兩個(gè) 變量。昂貴的元素復(fù)制操作只在必要的時(shí)候發(fā)生，也就是我們改變這兩個(gè)變量的時(shí)候發(fā)生復(fù)制

這種行為就被稱(chēng)為寫(xiě)時(shí)復(fù)制。它的工作方式是，每當(dāng)數(shù)組被改變，它首先檢查它對(duì)存儲(chǔ)緩沖區(qū) 的引用是否是唯一的，或者說(shuō)，檢查數(shù)組本身是不是這塊緩沖區(qū)的唯一擁有者。如果是，那么 緩沖區(qū)可以進(jìn)行原地變更;也不會(huì)有復(fù)制被進(jìn)行。不過(guò)，如果緩沖區(qū)有一個(gè)以上的持有者 (如本 例中)，那么數(shù)組就需要先進(jìn)行復(fù)制，然后對(duì)復(fù)制的值進(jìn)行變化，而保持其他的持有者不受影響。

Dictionary

我們知道字典是通過(guò)hash表的，那么什么是哈希表呢？

哈希表：

哈希表（hash table 也叫散列表），根據(jù)關(guān)鍵字(key value)直接訪(fǎng)問(wèn)在內(nèi)存中存儲(chǔ)位置的數(shù)據(jù)結(jié)構(gòu)，利用數(shù)組可以直接通過(guò)下標(biāo)訪(fǎng)問(wèn)數(shù)據(jù)的特性，通過(guò)哈希函數(shù)找到下標(biāo)，返回值，存放記錄的數(shù)組稱(chēng)作散列表

哈希函數(shù)

設(shè)計(jì)一個(gè)哈希函數(shù)主要有下面幾種方法

  1. 直接尋址法 hash(key) = a*k + b 之類(lèi)的線(xiàn)性函數(shù)
  2. 數(shù)字分析法 取關(guān)鍵字的若干位作為哈希地址
  3. 平方取中法 平方去中間的幾位作為哈希地址
  4. 折疊法 將key分割成位數(shù)相同的幾個(gè)部分 去這幾個(gè)部分的疊加和作為哈希地址
  5. 隨機(jī)數(shù)法
  6. 除留余數(shù)法 k%x 除在iOS中一般取2^n ,當(dāng)然x需要是2的倍數(shù)，然后>> n ,k &(x-1) 與運(yùn)算替換模運(yùn)算提升效率

哈希沖突

如何解決哈希沖突

  1. 開(kāi)放尋址法
    當(dāng)存儲(chǔ)數(shù)據(jù)的時(shí)候，當(dāng)前下標(biāo)有數(shù)據(jù)，我們進(jìn)行存儲(chǔ)下標(biāo)+1或-1的位置，依次類(lèi)推
  2. 拉鏈法
    即通過(guò)鏈表的形式也就是哈希拉鏈表，如果當(dāng)前下標(biāo)中有數(shù)據(jù)，遍歷當(dāng)前鏈表，插到尾結(jié)點(diǎn)。

負(fù)載因子

填?表中的元素個(gè)數(shù) / 散列表的?度
一般超過(guò)3/4也就是0.75的時(shí)候就要對(duì)散列表擴(kuò)容。

回到Dictionary中,以字面量創(chuàng)建的字典源碼

  public init(dictionaryLiteral elements: (Key, Value)...) {
//初始化一個(gè)結(jié)構(gòu)體
    let native = _NativeDictionary<Key, Value>(capacity: elements.count)
    for (key, value) in elements {
  //判斷key是否存在
      let (bucket, found) = native.find(key)
      //若找到了key，則報(bào)錯(cuò)，也就是創(chuàng)建時(shí)不能有相同的key否則崩潰
      _precondition(!found, "Dictionary literal contains duplicate keys")
    //插入
      native._insert(at: bucket, key: key, value: value)
    }
    self.init(_native: native)
  }
}

_NativeDictionary是什么？

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 {
// allcocate 說(shuō)明_DictionaryStroage是一個(gè)類(lèi)
      self._storage = _DictionaryStorage<Key, Value>.allocate(capacity: capacity)
    }
  }
}

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

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

  1. Dictionary----->包含關(guān)聯(lián)值枚舉屬性_variant初始化的關(guān)聯(lián)值是_NativeDictionary
  2. _NativeDictionary是一個(gè)結(jié)構(gòu)體包含屬性 _storage，類(lèi)型是__RawDictionaryStorage,為Class
  3. __RawDictionaryStorage是一個(gè)類(lèi)型，初始化_storage的時(shí)候使用的是子類(lèi)_DictionaryStorage
image.png

自定義實(shí)現(xiàn)HashTable

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

    var count = 0
    init(capacity: Int) {
        buckets = Array<bucket>(repeating: bucket(), count: capacity)
    }
    //哈希函數(shù)
    func index(key: Key) -> Int {
        
        return abs(key.hashValue) % buckets.count
    }
    //dic[0]支持下標(biāo)訪(fǎng)問(wèn)需要自己實(shí)現(xiàn)subscript
    subscript(key: Key) -> Value? {
        get {
            return getValue(key: key)
        }
        set {
            if let value = newValue {
                //更新
                updateValue(value, key)
            } else {
                //沒(méi)有移除
                removeValue(key: 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 {
                buckets[index][i] = (key: key, value: value)
                count += 1
                return element.value
            }
        }
        buckets[index].append((key: key, value: value))
        count += 1
        return nil
    }
    
    mutating func removeValue(key : Key) -> Value? {
        let index = self.index(key: key)
        for (i,element) in buckets[index].enumerated() {
            if  element.key == key {
                buckets[index].remove(at: i)
                count -= 1
                return element.value
            }
        }
        return nil
    }
    
}

var b = HashTable<String, String>(capacity: 4)

b["a"] = "鳥(niǎo)"
print(b["a"])
b["a"] = "貓"
print(b["a"])
b["a"] = nil
print(b["a"])

b.updateValue("虎", "b")
b.updateValue("虎", "c")
b.updateValue("虎", "d")
print(b.getValue(key: "b"))
print(b.getValue(key: "c"))
print(b.getValue(key: "d"))
b.updateValue("超了", "e")
print(b.getValue(key: "e"))
最后編輯于 ：
?著作權(quán)歸作者所有,轉(zhuǎn)載或內(nèi)容合作請(qǐng)聯(lián)系作者
【社區(qū)內(nèi)容提示】社區(qū)部分內(nèi)容疑似由AI輔助生成，瀏覽時(shí)請(qǐng)結(jié)合常識(shí)與多方信息審慎甄別。
平臺(tái)聲明：文章內(nèi)容（如有圖片或視頻亦包括在內(nèi)）由作者上傳并發(fā)布，文章內(nèi)容僅代表作者本人觀(guān)點(diǎn)，簡(jiǎn)書(shū)系信息發(fā)布平臺(tái)，僅提供信息存儲(chǔ)服務(wù)。

相關(guān)閱讀更多精彩內(nèi)容

友情鏈接更多精彩內(nèi)容