本文授權轉載，作者：漢斯哈哈哈（簡書）

繼第一篇，本文分析YYMemoryCache實現原理：

YYMemoryCache是內存緩存，所以存取速度非常快，主要用到兩種數據結構的LRU淘汰算法

1.LRU

Cache的容量是有限的，當Cache的空間都被占滿後，如果再次發生緩存失效，就必須選擇一個緩存塊來替換掉.LRU法是依據各塊使用的情況， 總是選擇那個最長時間未被使用的塊替換。這種方法比較好地反映了程序局部性規律

2.LRU主要采用兩種數據結構實現

• 雙向鏈表（Doubly Linked List）

• 哈希表（Dictionary）

3.對一個Cache的操作無非三種：插入、替換、查找

• 插入：當Cache未滿時，新的數據項只需插到雙鏈表頭部即可

• 替換：當Cache已滿時，將新的數據項插到雙鏈表頭部，並刪除雙鏈表的尾結點即可

• 查找：每次數據項被查詢到時，都將此數據項移動到鏈表頭部

4.分析圖(分析源碼時可以對照該圖)

5.YYMemoryCache.m裡的兩個分類

鏈表節點_YYLinkedMapNode：

@interface _YYLinkedMapNode : NSObject {
@package
// 指向前一個節點
__unsafe_unretained _YYLinkedMapNode *_prev; // retained by dic
// 指向後一個節點
__unsafe_unretained _YYLinkedMapNode *_next; // retained by dic
// 緩存key
id _key;
// 緩存對象
id _value;
// 當前緩存內存開銷
NSUInteger _cost;
// 緩存時間
NSTimeInterval _time;
}
@end

鏈表_YYLinkedMap：

@interface _YYLinkedMap : NSObject {
@package
// 用字典保存所有節點_YYLinkedMapNode (為什麼不用oc字典?因為用CFMutableDictionaryRef效率高，畢竟基於c)
CFMutableDictionaryRef _dic;
// 總緩存開銷
NSUInteger _totalCost;
// 總緩存數量
NSUInteger _totalCount;
// 鏈表頭節點
_YYLinkedMapNode *_head;
// 鏈表尾節點
_YYLinkedMapNode *_tail;
// 是否在主線程上，異步釋放 _YYLinkedMapNode對象
BOOL _releaseOnMainThread;
// 是否異步釋放 _YYLinkedMapNode對象
BOOL _releaseAsynchronously;
}
// 添加節點到鏈表頭節點
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node;
// 移動當前節點到鏈表頭節點
- (void)bringNodeToHead:(_YYLinkedMapNode *)node;
// 移除鏈表節點
- (void)removeNode:(_YYLinkedMapNode *)node;
// 移除鏈表尾節點(如果存在)
- (_YYLinkedMapNode *)removeTailNode;
// 移除所有緩存
- (void)removeAll;
@end

方法插入、替換、查找方法實現：

// 添加節點到鏈表頭節點
- (void)insertNodeAtHead:(_YYLinkedMapNode *)node {
// 字典保存鏈表節點node
CFDictionarySetValue(_dic, (__bridge const void *)(node->_key), (__bridge const void *)(node));
// 疊加該緩存開銷到總內存開銷
_totalCost += node->_cost;
// 總緩存數+1
_totalCount++;
if (_head) {
// 存在鏈表頭，取代當前表頭
node->_next = _head;
_head->_prev = node;
// 重新賦值鏈表表頭臨時變量_head
_head = node;
} else {
// 不存在鏈表頭
_head = _tail = node;
}
}

存在表頭情況圖形分析(其他情況不用圖分析,自己想象吧，呵呵)

// 移動當前節點到鏈表頭節點
- (void)bringNodeToHead:(_YYLinkedMapNode *)node {
// 當前節點已是鏈表頭節點
if (_head == node) return;
if (_tail == node) {
//**如果node是鏈表尾節點**
// 把node指向的上一個節點賦值給鏈表尾節點
_tail = node->_prev;
// 把鏈表尾節點指向的下一個節點賦值nil
_tail->_next = nil;
} else {
//**如果node是非鏈表尾節點和鏈表頭節點**
// 把node指向的上一個節點賦值給node指向的下一個節點node指向的上一個節點
node->_next->_prev = node->_prev;
// 把node指向的下一個節點賦值給node指向的上一個節點node指向的下一個節點
node->_prev->_next = node->_next;
}
// 把鏈表頭節點賦值給node指向的下一個節點
node->_next = _head;
// 把node指向的上一個節點賦值nil
node->_prev = nil;
// 把節點賦值給鏈表頭節點的指向的上一個節點
_head->_prev = node;
_head = node;
}

如果node是非鏈表尾節點和鏈表頭節點情況圖形分析(其他情況不用圖分析,自己想象吧，呵呵)

// 移除節點
- (void)removeNode:(_YYLinkedMapNode *)node {
// 從字典中移除node
CFDictionaryRemoveValue(_dic, (__bridge const void *)(node->_key));
// 減掉總內存消耗
_totalCost -= node->_cost;
// // 總緩存數-1
_totalCount--;
// 重新連接鏈表(看圖分析吧)
if (node->_next) node->_next->_prev = node->_prev;
if (node->_prev) node->_prev->_next = node->_next;
if (_head == node) _head = node->_next;
if (_tail == node) _tail = node->_prev;
}
// 移除尾節點(如果存在)
- (_YYLinkedMapNode *)removeTailNode {
if (!_tail) return nil;
// 拷貝一份要刪除的尾節點指針
_YYLinkedMapNode *tail = _tail;
// 移除鏈表尾節點
CFDictionaryRemoveValue(_dic, (__bridge const void *)(_tail->_key));
// 減掉總內存消耗
_totalCost -= _tail->_cost;
// 總緩存數-1
_totalCount--;
if (_head == _tail) {
// 清除節點，鏈表上已無節點了
_head = _tail = nil;
} else {
// 設倒數第二個節點為鏈表尾節點
_tail = _tail->_prev;
_tail->_next = nil;
}
// 返回完tail後_tail將會釋放
return tail;
}
// 移除所有緩存
- (void)removeAll {
// 清空內存開銷與緩存數量
_totalCost = 0;
_totalCount = 0;
// 清空頭尾節點
_head = nil;
_tail = nil;
if (CFDictionaryGetCount(_dic) > 0) {
// 拷貝一份字典
CFMutableDictionaryRef holder = _dic;
// 重新分配新的空間
_dic = CFDictionaryCreateMutable(CFAllocatorGetDefault(), 0, &kCFTypeDictionaryKeyCallBacks, &kCFTypeDictionaryValueCallBacks);
if (_releaseAsynchronously) {
// 異步釋放緩存
dispatch_queue_t queue = _releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
CFRelease(holder); // hold and release in specified queue
});
} else if (_releaseOnMainThread && !pthread_main_np()) {
// 主線程上釋放緩存
dispatch_async(dispatch_get_main_queue(), ^{
CFRelease(holder); // hold and release in specified queue
});
} else {
// 同步釋放緩存
CFRelease(holder);
}
}
}

YYMemoryCache.m實現分析(如果上面弄清楚，接下來就簡單多了)，增刪改都是調用上面的方法，下面分析查找與添加緩存方法實現

// 查找緩存
- (id)objectForKey:(id)key {
if (!key) return nil;
// 加鎖，防止資源競爭
// OSSpinLock 自旋鎖，性能最高的鎖。原理很簡單，就是一直 do while 忙等。它的缺點是當等待時會消耗大量 CPU 資源，所以它不適用於較長時間的任務。對於內存緩存的存取來說，它非常合適。
pthread_mutex_lock(&_lock);
// _lru為鏈表_YYLinkedMap，全部節點存在_lru->_dic中
// 獲取節點
_YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
if (node) {
//** 有對應緩存 **
// 重新更新緩存時間
node->_time = CACurrentMediaTime();
// 把當前node移到鏈表表頭(為什麼移到表頭？根據LRU淘汰算法:Cache的容量是有限的，當Cache的空間都被占滿後，如果再次發生緩存失效，就必須選擇一個緩存塊來替換掉.LRU法是依據各塊使用的情況， 總是選擇那個最長時間未被使用的塊替換。這種方法比較好地反映了程序局部性規律)
[_lru bringNodeToHead:node];
}
// 解鎖
pthread_mutex_unlock(&_lock);
// 有緩存則返回緩存值
return node ? node->_value : nil;
}
// 添加緩存
- (void)setObject:(id)object forKey:(id)key withCost:(NSUInteger)cost {
if (!key) return;
if (!object) {
// ** 緩存對象為空，移除緩存 **
[self removeObjectForKey:key];
return;
}
// 加鎖
pthread_mutex_lock(&_lock);
// 查找緩存
_YYLinkedMapNode *node = CFDictionaryGetValue(_lru->_dic, (__bridge const void *)(key));
// 當前時間
NSTimeInterval now = CACurrentMediaTime();
if (node) {
//** 之前有緩存，更新舊緩存 **
// 更新值
_lru->_totalCost -= node->_cost;
_lru->_totalCost += cost;
node->_cost = cost;
node->_time = now;
node->_value = object;
// 移動節點到鏈表表頭
[_lru bringNodeToHead:node];
} else {
//** 之前未有緩存，添加新緩存 **
// 新建節點
node = [_YYLinkedMapNode new];
node->_cost = cost;
node->_time = now;
node->_key = key;
node->_value = object;
// 添加節點到表頭
[_lru insertNodeAtHead:node];
}
if (_lru->_totalCost > _costLimit) {
// ** 總緩存開銷大於設定的開銷 **
// 異步清理最久未使用的緩存
dispatch_async(_queue, ^{
[self trimToCost:_costLimit];
});
}
if (_lru->_totalCount > _countLimit) {
// ** 總緩存數量大於設定的數量 **
// 移除鏈表尾節點(最久未訪問的緩存)
_YYLinkedMapNode *node = [_lru removeTailNode];
if (_lru->_releaseAsynchronously) {
dispatch_queue_t queue = _lru->_releaseOnMainThread ? dispatch_get_main_queue() : YYMemoryCacheGetReleaseQueue();
dispatch_async(queue, ^{
[node class]; //  and release in queue
});
} else if (_lru->_releaseOnMainThread && !pthread_main_np()) {
dispatch_async(dispatch_get_main_queue(), ^{
[node class]; //hold and release in queue
});
}
}
pthread_mutex_unlock(&_lock);
}

接下來會分析YYDiskCache實現原理