前言
在APP需求開發(fā)中，經常會有一些本地存儲一些信息的功能，對于本地保存的瀏覽歷史記錄，大多需要根據幾個維度進行約束：時間、數量、增刪改查的時間復雜度、用戶瀏覽順序等
例如：在簡書APP推薦列表中，對用戶瀏覽過的文章進行了置灰。
抽象成需求：在商品列表中，對用戶瀏覽過的商品卡片進行置灰
需求的要求：
1、 用戶瀏覽的順序需要記錄，如果用戶瀏覽的是同一個商品，則需要更新商品的瀏覽時間為用戶最后一次瀏覽時間
2、超時的歷史記錄進行刪除：對于瀏覽時間落后當前時間X天的歷史數據，則需要刪除
3、歷史記錄需要存到磁盤
思考過程
一、 讀取的時間復雜度
面對這樣一個需求，首要考慮的是讀取數據的時間復雜度。
數組儲存： 每個列表卡片都需要循環(huán)數組才能知道這個商品用戶是否已經瀏覽。而列表因為有上拉加載功能，卡片是無限的，這無疑造成了資源的浪費。而且如果用戶點擊的是同一個商品卡片，則需要先移除數組中的歷史記錄，再添加到數組的末尾，這又是一比消耗
字典存儲：讀取速度是O(1)， 而且每個商品的唯一標識我們肯定是知道的，那么我們使用商品的唯一標識作為Key，把一些必要數據包裝成Mode為字典的Value。所以字典存儲是可行的。而且如果用戶點擊的是同一個商品卡片，不需要做刪除與插入操作
二、 存儲的最大長度
在產品迭代中，肯定會新增一些信息一起存儲到用戶瀏覽記錄里，如果個數不加以限制，則會造成空間浪費
還是兩種存儲方式：
數組存儲： 數組有序，從而知道用戶的瀏覽順序，所以對于如果用戶瀏覽超出了最大長度的限制，則只需要刪除數組前部分數據即可（時間復雜度O(n)）
字典儲存：字典無需，但是我們可以把字典變得有序，比如我們在字典中儲存的是一個鏈表（以下把Mode稱為Node）。并記錄鏈表的head與end，這樣我們就可以實現快速的刪除操作（時間復雜度O(1)）。
三、超時的歷史記錄進行刪除
刪除超時的歷史記錄，就是查找超時歷史記錄的范圍
數組存儲： 因為數組在瀏覽時間上是有序的，所以我們可以使用二分查找來查找最后一個過期的歷史記錄（查找的時間復雜度O(log2n)，刪除的時間復雜度為O(n)）
字典儲存： 我們可以從鏈表的heade來逐個查找（查找時間復雜度為O(n)，刪除的時間復雜度為O(1)）
由于對于超時歷史記錄的刪除，對于實時性并沒那么敏感，所以或許我們可以在APP啟動、或者第一次使用到歷史記錄數據的時候進行查找刪除
四、儲存到磁盤
儲存到磁盤的操作是非常耗時的，所以應該盡量減少存儲次數。
好在iOS在APP退出、切換到后臺時都會發(fā)出通知：UIApplicationDidEnterBackgroundNotification，所以我們可以接收到通知時進行存儲
工具類VisitManager結構
對比數組、字典存儲，我們選擇了字典存儲鏈表來進行存儲。并把鏈表設計成雙向鏈表結構
為了避免刪除的Node需要手動釋放內存，我們可以讓Node的Next指針指向下一個Node在字典中的唯一標識Key，prev指針指向上一個Node在字典中的唯一標識Key
于是我們最終方案的結構如下：
一、Node：
Node中儲存了單個的房源瀏覽歷史
| 名稱 | 類型 | 含義 |
|---|---|---|
| prevNodeKey | NSString | 上一次瀏覽的房源的Node的CurrentNodeKey |
| data | id | 用于儲存數據的擴展字段 |
| timeInterval | NSTimeInterval（double） | 加入到 NodeDic中的時間戳 |
| currentNodeKey | NSString | 當前節(jié)點在NodeDic中所在的key |
| nextNodeKey | NSString | 下一次瀏覽的房源的Node的CurrentNodeKey |
二、 VisitManager
VisitManager是一個單利類，里面儲存了一些關鍵信息：
| 名稱 | 類型 | 含義 |
|---|---|---|
| NodeDic | 字典 | 儲存了所有的node數據 |
| HeadNode | Node | 鏈表頭, （prevNodeKey指向的nil） |
| EndNode | Node | 鏈表尾 （nextNodeKey指向的nil） |
| NodeDicMaxCount | Int | 鏈表儲存的最大長度 |
VisitManager數據操作流程
一、插入數據
在進入到房源詳情頁時、會嘗試生成一條該房源的唯一標識Key，根據這個Key來嘗試插入一條node
1、 查看瀏覽的房源A生成的Key，在NodeDic中是否有Node存在，如果存在，則說明之前瀏覽過房源
1.1、如果存在，則把之前的NodeA從鏈表中刪除（下面詳細敘述）
1.2、如果不存在，則創(chuàng)建NodeA，并查看NodeDIc.count 是否大于 NodeDicMaxCount-1， 超出了則刪除 headNode
1.3、插入NodeA到鏈表末尾，并賦值NodeA的TimeInterval的值為當前的手機時間
1.4、賦值 manager的 endNode
二、 刪除鏈表中的Node
1、 刪除鏈表中的NodeB
1.1、 根據NodeB.prevNodeKey 從manager 的NodeDic中獲取 NodeB的左節(jié)點，NodeA
1.2、 根據NodeB.nextNodeKey 從manager 的NodeDic中獲取 NodeB的左節(jié)點，NodeC
1.3、 NodeA.nextNodeKey = NodeC.currentNodeKey
1.4、NodeC.prevNodeKey = NodeA.currentNodeKey
15、NodeB.nextNodeKey = nil， NodeB.prevNodeKey = nil
2、 真正的刪除內存中的NodeB
把manager 的NodeDic字典中的NodeB刪除:
NodeDic[NodB.currentNodeKey?:@""] = nil;
三、校驗與存儲到磁盤
在用戶瀏覽房源卡片列表時，創(chuàng)建visitManager，并且解檔NodeDic、headeNode
當APP 退出后臺，或者殺死APP時，會把manager中的NodeDic、headeNode、EndNode歸檔到沙河中
demo
demo地址： https://github.com/LiPengYue/VisitManager.git
最大緩存數為：5個
最大超時時間為20秒
