鏈表這種數(shù)據(jù)結(jié)構(gòu)和數(shù)組一樣是線性表一罩。在我們開發(fā)中我們可能經(jīng)常會(huì)在不知不覺中使用它廊驼。是一種非秤糖郏基礎(chǔ)的數(shù)據(jù)結(jié)構(gòu)熙涤。與數(shù)組相比鏈表的優(yōu)點(diǎn)在于它不要求必須要連續(xù)的內(nèi)存空間阁苞。因此可以最大限度的利用內(nèi)存空間，因?yàn)椴恍枰B續(xù)的內(nèi)存空間鏈表的插入與刪除的時(shí)間復(fù)雜度都要優(yōu)與數(shù)組祠挫。那么怎么才能寫出最標(biāo)準(zhǔn)的鏈表了那槽？嘿嘿。蘋果官方有標(biāo)準(zhǔn)的參考哦等舔。
NSCache我們都使用過骚灸，它存儲(chǔ)數(shù)據(jù)的方式就是使用的雙向鏈表。github地址：https://github.com/apple/swift-corelibs-foundation/blob/main/Sources/Foundation/NSCache.swift
下面我也把蘋果官方NSCache的源碼貼出來慌植。并做簡單的源碼解析方便查看甚牲。打開github有時(shí)候確實(shí)有點(diǎn)慢。
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 是常見的雙向鏈表存儲(chǔ)結(jié)構(gòu)蝶柿，但是其中多了一個(gè)cost屬性丈钙，是為了為了在內(nèi)存達(dá)到預(yù)警時(shí)自動(dòng)刪除比對的。
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這個(gè)不用說交汤，用在存儲(chǔ)的key雏赦。
下面是NSCache的源碼。
在NSCache源碼中我們能看到它同時(shí)有_entries與_head。一個(gè)是字典另一個(gè)是鏈表的head星岗。為什么會(huì)同時(shí)用兩個(gè)了填大。這里是因?yàn)殒湵淼牟樵儠r(shí)間復(fù)雜度在o(n)但是字典作為hash表它的查詢復(fù)雜度是o(1)。并且NSCacheEntry是class 是引用類型伍茄。因此對內(nèi)存的增加也是很小的栋盹。_entries就是對緩存數(shù)據(jù)做的一層索引。
totalCostLimit與countLimit都是做淘汰算法使用的敷矫，在setObject方法中有使用。
open func object(forKey key: KeyType) 緩存讀取方法汉额，直接讀取_entries字典中的數(shù)據(jù)曹仗，時(shí)間復(fù)雜度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中查找是否已經(jīng)有當(dāng)前插入的元素怎茫，如果有在判斷cost是否有更新，如果有更新就更新鏈表中的數(shù)據(jù)妓灌。如果沒有更新直接插入到鏈表中轨蛤。
2.然后判斷purgeAmount。如果purgeAmount大于零就執(zhí)行淘汰算法虫埂，刪除鏈表中最先插入進(jìn)來的數(shù)據(jù)祥山。同時(shí)刪除_entries字典中的數(shù)據(jù)。調(diào)用回調(diào)方法掉伏。
3.然后判斷purgeCount缝呕。和purgeAmount一樣執(zhí)行同樣的淘汰機(jī)制。
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()
}
}
