為什么散列表和鏈表經(jīng)常會(huì)一起使用？
- 散列表這種數(shù)據(jù)結(jié)構(gòu)雖然支持非常高效的數(shù)據(jù)插入帅韧、刪除里初、查找操作，但是散列表中的數(shù)據(jù)都是通過散列函數(shù)打亂之后無規(guī)律存儲(chǔ)的忽舟。也就說双妨，它無法支持按照某種順序快速地遍歷數(shù)據(jù)。如果希望按照順序遍歷散列表中的數(shù)據(jù)萧诫，那我們需要將散列表中的數(shù)據(jù)拷貝到數(shù)組中斥难，然后排序，再遍歷帘饶。
- 因?yàn)樯⒘斜硎莿?dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)哑诊，不停地有數(shù)據(jù)的插入、刪除及刻，所以每當(dāng)我們希望按順序遍歷散列表中的數(shù)據(jù)的時(shí)候镀裤，都需要先排序竞阐，那效率勢必會(huì)很低。為了解決這個(gè)問題暑劝，我們將散列表和鏈表（或者跳表）結(jié)合在一起使用骆莹。
LRU 緩存淘汰算法
當(dāng)要緩存某個(gè)數(shù)據(jù)的時(shí)候，先在鏈表中查找這個(gè)數(shù)據(jù)担猛。如果沒有找到幕垦，則直接將數(shù)據(jù)放到鏈表的尾部；如果找到了傅联，我們就把它移動(dòng)到鏈表的尾部先改。因?yàn)椴檎覕?shù)據(jù)需要遍歷鏈表，所以單純用鏈表實(shí)現(xiàn)的 LRU 緩存淘汰算法的時(shí)間復(fù)雜很高蒸走，是 O(n)仇奶。
總結(jié)一下，一個(gè)緩存（cache）系統(tǒng)主要包含下面這幾個(gè)操作：
- 往緩存中添加一個(gè)數(shù)據(jù)比驻；
- 從緩存中刪除一個(gè)數(shù)據(jù)该溯；
- 在緩存中查找一個(gè)數(shù)據(jù)。
