链表这种数据结构和数组一样是线性表。在我们开发中我们可能经常会在不知不觉中使用它。是一种非常基础的数据结构。与数组相比链表的优点在于它不要求必须要连续的内存空间。因此可以最大限度的利用内存空间，因为不需要连续的内存空间链表的插入与删除的时间复杂度都要优与数组。那么怎么才能写出最标准的链表了？嘿嘿。苹果官方有标准的参考哦。
NSCache我们都使用过，它存储数据的方式就是使用的双向链表。github地址：https://github.com/apple/swift-corelibs-foundation/blob/main/Sources/Foundation/NSCache.swift
下面我也把苹果官方NSCache的源码贴出来。并做简单的源码解析方便查看。打开github有时候确实有点慢。
private class NSCacheEntry<KeyType : AnyObject, ObjectType : AnyObject> {
var key: KeyType
var value: ObjectType
var cost: Int
var prevByCost: NSCacheEntry?
var nextByCost: NSCacheEntry?
init(key: KeyType, value: ObjectType, cost: Int) {
self.key = key
self.value = value
self.cost = cost
}
}
NSCacheEntry 是常见的双向链表存储结构，但是其中多了一个cost属性，是为了为了在内存达到预警时自动删除比对的。
fileprivate class NSCacheKey: NSObject {
var value: AnyObject
init(_ value: AnyObject) {
self.value = value
super.init()
}
override var hash: Int {
switch self.value {
case let nsObject as NSObject:
return nsObject.hashValue
case let hashable as AnyHashable:
return hashable.hashValue
default: return 0
}
}
override func isEqual(_ object: Any?) -> Bool {
guard let other = (object as? NSCacheKey) else { return false }
if self.value === other.value {
return true
} else {
guard let left = self.value as? NSObject,
let right = other.value as? NSObject else { return false }
return left.isEqual(right)
}
}
}
NSCacheKey这个不用说，用在存储的key。
下面是NSCache的源码。
在NSCache源码中我们能看到它同时有_entries与_head。一个是字典另一个是链表的head。为什么会同时用两个了。这里是因为链表的查询时间复杂度在o(n)但是字典作为hash表它的查询复杂度是o(1)。并且NSCacheEntry是class 是引用类型。因此对内存的增加也是很小的。_entries就是对缓存数据做的一层索引。
totalCostLimit与countLimit都是做淘汰算法使用的，在setObject方法中有使用。
open func object(forKey key: KeyType) 缓存读取方法，直接读取_entries字典中的数据，时间复杂度o(1)
open func object(forKey key: KeyType) -> ObjectType? {
var object: ObjectType?
let key = NSCacheKey(key)
_lock.lock()
if let entry = _entries[key] {
object = entry.value
}
_lock.unlock()
return object
}
private func remove(_ entry: NSCacheEntry<KeyType, ObjectType>)与private func insert(_ entry: NSCacheEntry<KeyType, ObjectType>)是链表的插入与删除方法。
private func remove(_ entry: NSCacheEntry<KeyType, ObjectType>) {
let oldPrev = entry.prevByCost
let oldNext = entry.nextByCost
oldPrev?.nextByCost = oldNext
oldNext?.prevByCost = oldPrev
if entry === _head {
_head = oldNext
}
}
private func insert(_ entry: NSCacheEntry<KeyType, ObjectType>) {
guard var currentElement = _head else {
// The cache is empty
entry.prevByCost = nil
entry.nextByCost = nil
_head = entry
return
}
guard entry.cost > currentElement.cost else {
// Insert entry at the head
entry.prevByCost = nil
entry.nextByCost = currentElement
currentElement.prevByCost = entry
_head = entry
return
}
while let nextByCost = currentElement.nextByCost, nextByCost.cost < entry.cost {
currentElement = nextByCost
}
// Insert entry between currentElement and nextElement
let nextElement = currentElement.nextByCost
currentElement.nextByCost = entry
entry.prevByCost = currentElement
entry.nextByCost = nextElement
nextElement?.prevByCost = entry
}
setObject方法添加缓存对象到NSCache中。
1.首先从_entries中查找是否已经有当前插入的元素，如果有在判断cost是否有更新，如果有更新就更新链表中的数据。如果没有更新直接插入到链表中。
2.然后判断purgeAmount。如果purgeAmount大于零就执行淘汰算法，删除链表中最先插入进来的数据。同时删除_entries字典中的数据。调用回调方法。
3.然后判断purgeCount。和purgeAmount一样执行同样的淘汰机制。
open func setObject(_ obj: ObjectType, forKey key: KeyType, cost g: Int) {
let g = max(g, 0)
let keyRef = NSCacheKey(key)
_lock.lock()
let costDiff: Int
if let entry = _entries[keyRef] {
costDiff = g - entry.cost
entry.cost = g
entry.value = obj
if costDiff != 0 {
remove(entry)
insert(entry)
}
} else {
let entry = NSCacheEntry(key: key, value: obj, cost: g)
_entries[keyRef] = entry
insert(entry)
costDiff = g
}
_totalCost += costDiff
var purgeAmount = (totalCostLimit > 0) ? (_totalCost - totalCostLimit) : 0
while purgeAmount > 0 {
if let entry = _head {
delegate?.cache(unsafeDowncast(self, to:NSCache<AnyObject, AnyObject>.self), willEvictObject: entry.value)
_totalCost -= entry.cost
purgeAmount -= entry.cost
remove(entry) // _head will be changed to next entry in remove(_:)
_entries[NSCacheKey(entry.key)] = nil
} else {
break
}
}
var purgeCount = (countLimit > 0) ? (_entries.count - countLimit) : 0
while purgeCount > 0 {
if let entry = _head {
delegate?.cache(unsafeDowncast(self, to:NSCache<AnyObject, AnyObject>.self), willEvictObject: entry.value)
_totalCost -= entry.cost
purgeCount -= 1
remove(entry) // _head will be changed to next entry in remove(_:)
_entries[NSCacheKey(entry.key)] = nil
} else {
break
}
}
_lock.unlock()
}
下面是完整的NSCache源码。
private class NSCacheEntry<KeyType : AnyObject, ObjectType : AnyObject> {
var key: KeyType
var value: ObjectType
var cost: Int
var prevByCost: NSCacheEntry?
var nextByCost: NSCacheEntry?
init(key: KeyType, value: ObjectType, cost: Int) {
self.key = key
self.value = value
self.cost = cost
}
}
fileprivate class NSCacheKey: NSObject {
var value: AnyObject
init(_ value: AnyObject) {
self.value = value
super.init()
}
override var hash: Int {
switch self.value {
case let nsObject as NSObject:
return nsObject.hashValue
case let hashable as AnyHashable:
return hashable.hashValue
default: return 0
}
}
override func isEqual(_ object: Any?) -> Bool {
guard let other = (object as? NSCacheKey) else { return false }
if self.value === other.value {
return true
} else {
guard let left = self.value as? NSObject,
let right = other.value as? NSObject else { return false }
return left.isEqual(right)
}
}
}
open class NSCache<KeyType : AnyObject, ObjectType : AnyObject> : NSObject {
private var _entries = Dictionary<NSCacheKey, NSCacheEntry<KeyType, ObjectType>>()
private let _lock = NSLock()
private var _totalCost = 0
private var _head: NSCacheEntry<KeyType, ObjectType>?
open var name: String = ""
open var totalCostLimit: Int = 0 // limits are imprecise/not strict
open var countLimit: Int = 0 // limits are imprecise/not strict
open var evictsObjectsWithDiscardedContent: Bool = false
public override init() {}
open weak var delegate: NSCacheDelegate?
open func object(forKey key: KeyType) -> ObjectType? {
var object: ObjectType?
let key = NSCacheKey(key)
_lock.lock()
if let entry = _entries[key] {
object = entry.value
}
_lock.unlock()
return object
}
open func setObject(_ obj: ObjectType, forKey key: KeyType) {
setObject(obj, forKey: key, cost: 0)
}
private func remove(_ entry: NSCacheEntry<KeyType, ObjectType>) {
let oldPrev = entry.prevByCost
let oldNext = entry.nextByCost
oldPrev?.nextByCost = oldNext
oldNext?.prevByCost = oldPrev
if entry === _head {
_head = oldNext
}
}
private func insert(_ entry: NSCacheEntry<KeyType, ObjectType>) {
guard var currentElement = _head else {
// The cache is empty
entry.prevByCost = nil
entry.nextByCost = nil
_head = entry
return
}
guard entry.cost > currentElement.cost else {
// Insert entry at the head
entry.prevByCost = nil
entry.nextByCost = currentElement
currentElement.prevByCost = entry
_head = entry
return
}
while let nextByCost = currentElement.nextByCost, nextByCost.cost < entry.cost {
currentElement = nextByCost
}
// Insert entry between currentElement and nextElement
let nextElement = currentElement.nextByCost
currentElement.nextByCost = entry
entry.prevByCost = currentElement
entry.nextByCost = nextElement
nextElement?.prevByCost = entry
}
open func setObject(_ obj: ObjectType, forKey key: KeyType, cost g: Int) {
let g = max(g, 0)
let keyRef = NSCacheKey(key)
_lock.lock()
let costDiff: Int
if let entry = _entries[keyRef] {
costDiff = g - entry.cost
entry.cost = g
entry.value = obj
if costDiff != 0 {
remove(entry)
insert(entry)
}
} else {
let entry = NSCacheEntry(key: key, value: obj, cost: g)
_entries[keyRef] = entry
insert(entry)
costDiff = g
}
_totalCost += costDiff
var purgeAmount = (totalCostLimit > 0) ? (_totalCost - totalCostLimit) : 0
while purgeAmount > 0 {
if let entry = _head {
delegate?.cache(unsafeDowncast(self, to:NSCache<AnyObject, AnyObject>.self), willEvictObject: entry.value)
_totalCost -= entry.cost
purgeAmount -= entry.cost
remove(entry) // _head will be changed to next entry in remove(_:)
_entries[NSCacheKey(entry.key)] = nil
} else {
break
}
}
var purgeCount = (countLimit > 0) ? (_entries.count - countLimit) : 0
while purgeCount > 0 {
if let entry = _head {
delegate?.cache(unsafeDowncast(self, to:NSCache<AnyObject, AnyObject>.self), willEvictObject: entry.value)
_totalCost -= entry.cost
purgeCount -= 1
remove(entry) // _head will be changed to next entry in remove(_:)
_entries[NSCacheKey(entry.key)] = nil
} else {
break
}
}
_lock.unlock()
}
open func removeObject(forKey key: KeyType) {
let keyRef = NSCacheKey(key)
_lock.lock()
if let entry = _entries.removeValue(forKey: keyRef) {
_totalCost -= entry.cost
remove(entry)
}
_lock.unlock()
}
open func removeAllObjects() {
_lock.lock()
_entries.removeAll()
while let currentElement = _head {
let nextElement = currentElement.nextByCost
currentElement.prevByCost = nil
currentElement.nextByCost = nil
_head = nextElement
}
_totalCost = 0
_lock.unlock()
}
}
网友评论