LazySequence
先看一下下面代码
从打印结果我们可以看到，首先Lazy的方式其实就是保存当前集合和对应的操作，然后在访问具体元素的时候，执行对应的操作。
LazyMapSequence<Array<Int>, Int>(_base: [1, 2, 3, 4], _transform: (Function))这是个什么东东呢？很明显这是一个初始化的结构体我们看看源码是不是这个东西呢？
<Base: Sequence, Element> 这是类型约束，这里不太明白的童鞋可以看我Swift-12：泛型讲的泛型以及类型约束，初始化中保存当前集合_base和对应的操作_transform
当我们访问元素的时候，本质上，继承了Sequence协议，通过访问自身迭代器_base.next()迭代当前的元素,然后对单个元素进行map(_transform)操作，就得来了map之后的元素
应用：一般我们数组数据特别大的时候我们使用lazy关键字。
比如Array(0...10000)
Array
源码比较多，我摘要一下Array的内存布局
Struct Array------> Struct _ContiguousArrayBuffer----->Class __ContiguousArrayStorageBase------>包含了⼀个属性 Struct ArrayBody ------ > 包含了⼀个属性 struct _SwiftArrayBodyStorage -------> 包含了两个属性 count & _capacityAndFlags
类里面存的分别是 metaData、refCount、count、 _capacityAndFlags、firstElementAddress
结构体包含结构体，结构体中包含类，类中在包含结构体成员
我们来调试验证一下
append
如果是多个引用计数，就会createNewBuffer，这也就是所谓的写时复制
这里补充一下：当值类型包含引用类型时，值类型copy也会对内部的引用类型进行+1，验证一下：
注意自定义的结构体是没有写时赋值功能的，这是集合等类型swift底层实现的，我们接下来看看是如何实现的
-
判断引用计数，>1 重新分配内存空间返回newBuffer，为了写时复制
2.如果加一之后>buffer的容量capacity也会从新开辟内存空间，将原有的element拼接到新的内存空间中
image.png
image.png
断点验证
ar numbers = [1,2,3,4,5,6]
numbers.append(7)
print("end")
写时复制总结
看了大部分网上关于写时复制的说法，其实不够准确。
Array，Dictionary 和 Set 这样的集合类型是通过一种叫做写时复制 (copy-on-write) 的技术实现的，在内部，这些 Array 结构体含有指向某个内存的引用，也就是前面的__ContiguousArrayStorageBase引用类型的地址，这地址指向的内存就是数组中元素所存储的位置。赋值时，两个数组的引用指向的是内存中同一个位置，这两个数组共享了它们的存储部分。不过，当我 们改变 其中一个数组的时候，这个共享会被检测到，内存将会被复制。这样一来，我们得以独立地改变两个 变量。昂贵的元素复制操作只在必要的时候发生，也就是我们改变这两个变量的时候发生复制
这种行为就被称为写时复制。它的工作方式是，每当数组被改变，它首先检查它对存储缓冲区 的引用是否是唯一的，或者说，检查数组本身是不是这块缓冲区的唯一拥有者。如果是，那么 缓冲区可以进行原地变更;也不会有复制被进行。不过，如果缓冲区有一个以上的持有者 (如本 例中)，那么数组就需要先进行复制，然后对复制的值进行变化，而保持其他的持有者不受影响。
Dictionary
我们知道字典是通过hash表的，那么什么是哈希表呢？
哈希表：
哈希表（hash table 也叫散列表），根据关键字(key value)直接访问在内存中存储位置的数据结构，利用数组可以直接通过下标访问数据的特性，通过哈希函数找到下标，返回值，存放记录的数组称作散列表
哈希函数
设计一个哈希函数主要有下面几种方法
- 直接寻址法 hash(key) = a*k + b 之类的线性函数
- 数字分析法 取关键字的若干位作为哈希地址
- 平方取中法 平方去中间的几位作为哈希地址
- 折叠法 将key分割成位数相同的几个部分 去这几个部分的叠加和作为哈希地址
- 随机数法
- 除留余数法 k%x 除在iOS中一般取2^n ,当然x需要是2的倍数，然后>> n ,k &(x-1) 与运算替换模运算提升效率
哈希冲突
如何解决哈希冲突
- 开放寻址法
当存储数据的时候，当前下标有数据，我们进行存储下标+1或-1的位置，依次类推 - 拉链法
即通过链表的形式也就是哈希拉链表，如果当前下标中有数据，遍历当前链表，插到尾结点。
负载因子
填⼊表中的元素个数 / 散列表的⻓度
一般超过3/4也就是0.75的时候就要对散列表扩容。
回到Dictionary中,以字面量创建的字典源码
public init(dictionaryLiteral elements: (Key, Value)...) {
//初始化一个结构体
let native = _NativeDictionary<Key, Value>(capacity: elements.count)
for (key, value) in elements {
//判断key是否存在
let (bucket, found) = native.find(key)
//若找到了key，则报错，也就是创建时不能有相同的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 说明_DictionaryStroage是一个类
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)
}
}
}
}
经过上面的分析我们可以得到如下的结论，在纯Swift 的字典中其内存结构如下：
- Dictionary----->包含关联值枚举属性_variant初始化的关联值是_NativeDictionary
- _NativeDictionary是一个结构体包含属性 _storage，类型是__RawDictionaryStorage,为Class
- __RawDictionaryStorage是一个类型，初始化_storage的时候使用的是子类_DictionaryStorage
自定义实现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)
}
//哈希函数
func index(key: Key) -> Int {
return abs(key.hashValue) % buckets.count
}
//dic[0]支持下标访问需要自己实现subscript
subscript(key: Key) -> Value? {
get {
return getValue(key: key)
}
set {
if let value = newValue {
//更新
updateValue(value, key)
} else {
//没有移除
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"] = "鸟"
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"))
