干货|漫画算法：LRU从实现到应用层层剖析（第一讲）

今天为大家分享很出名的LRU算法，第一讲共包括4节。

• LRU概述
• LRU使用
• LRU实现
• Redis近LRU概述

第一部分：LRU概述

LRU是Least Recently UsedR B ] ; m的缩写，译为最近最少使用。它的理论基础为“最近使用的数据会在未来一段时期内仍然被使用，已c q L k经很久没有使用的数据大概率在未来很长一段时间仍然不会被使用”由于该思想非常契合业I h F p @ f { H务场景 ，并且可以解决很多实际开发中的问4 0 l K W Q |题，所以我们经常通过LRU的思想来作缓存，一般也将其称为LRU缓存机制。因为恰好leetcode上有这道题，所以我干脆把题目贴这里。但是对于LRU而言，希望大家不要局限于! ; 本题（大家不用担心学不会，我希望能做一个全网最简单的版本，希望可以坚持看下去！）下面，我们一起学习一T R B n A 1 @ L下。

题目：运用你所掌握的数据结构，设计和实现一个 LRU (最近最少使用) 缓存机制7 , & m u 8 l 1 w。它应该支持以下操作：获取数据 get 和 写入数据 put 。

获取数据 get(key) - 如果密钥 (key) 存在于缓存中，则获取密钥的值（总是正数），否则返回 -1。

写入数据 pT 9 kut(key, value) - 如果密钥不存在，则写入其数据值。当缓存容量达到上限时，它应该在写入新D F D数据之前删除最近最少使用的数据值，从而为新的数据值留出空间。

进阶:你是否可以在 O(1) 时间复杂度q u C q }内完成这两种操作？

示例:

LRUCache cach/ c _ [e = new LRUCache( 2 /* 缓存w ) T h 4 M T 3 T容量 */ );

cache.put(1, 1);

cache.put(2, 2);

cache.get, 4 8 z r z # / s(1); // 返回 1

cache.put(3, 3); // 该操作会使得密钥 2 作废

cache.get(2N e = e z); // 返回 -1 (未找到$ W 4 r r % 6 j 2)

cache.put(4, 4); // 该操作会使得密钥 1 作废

cache.get(1); // 返回 -1 (未找到)

cache.get(3); // 返回 3

cache.get(4); // 返回 4

第二部分：LRU使用

首先说一下LRUCu 8 c c 0 2ache的示例解释一下

• 第一步：我们申明一个LRU) D = SCachv v We，长度为2

• 第二步：我们分别向cache里边put(: X M ~ * l1,1)和put(2,2)，这里因为最近使用的是2（put也算作使用）( o / l 5 G所以2在前，1在后。

• 第三步：我们get(1)，也就是我们使用了1，所以需要将1移到前面。

• 第四步：此时我们put(3,3)，因为2是最近最少使用的，所以4 ; ^ V F u w我们需要将2进行作废。此时我们再get(2)，就会返回-1@ s 3 } 1。& d = G v

• 第五步：我们继续put(4,4)，同理我们将1作废。此时如果get(1)，也是返回-1。

• 第H u D k R e k H六步：此时我们get(3)，实际为调整3的位置H s = 4 T 3 B。

• 第七步：同理，get(4)，继续调整4的位置。

第三部分：L` K URU 实现（层层剖析）

通过上面的分析大家应该都能理解LRU的使用了。现在我们聊一下实现。LRU一般来讲，g N . P我们是使用双向链表实现。这里我要强调的是，其实在项目中，并不绝对是这样。比如Redis源码里，LRU的淘汰策略，就没有使用双向链表，而是使用一种模拟链表的方式。因为Redis大多是当内存在用（我知道可以持久化），如果再在内存N i N A Z d m中去维护一个链表，就平添了一些复杂性，同时也会多耗掉一些内存，后面我会单独拉出来Redis的源码给大家分析，这里不细说。

回到题目，为什么我们要选择双向链表来实现呢？看看上面的使用步骤图，大家会发现，在整个LRUCache的使用中，我们需要频繁的去调整首尾元素的位置。而双向链表的结构，刚好满足这一点（再啰嗦一下，前几天我刚好看了groupcache的源码，里边就是用双向链表来做的LRU，当然它里边做了一f B W /些改进。groupcache是memcar } h + ? $ wche作者实现的go版本，如果有go的读者，可以去看看源码，还是有一些收获。）

下面，我们采用hashmap+双向链表的方式进行实现。

首先，我们定义一个LinkNode，用以存储元素。因为是双向链表，自然我们要定义pre和next。同时，我们需要存储下元素的key和value。valo x $ / x A %大家应该都能理解，关键是为什么需要存储key？举个例s : w - 0 Z T U O子，比如当整个cache的元素满了，此时我们需要删除map中的数据，需要通过LinkNode中的key来 ) g J I e | F d进行查询，否则无法获取到key。

1type O h , oLRUCache struct {
2    m          map[int]*LinkNode
3&nb! ) ~ Y ; |spb G Q B D ; Z L ; : $ ; = L P : t U;  cap      &nbsI R t -p; int
4    R ^ A / Nhead, tail *LinkNode
5}

现在有了LinkNode，自然需要一个CaE n 8che来存储所有的Node。我们定义cap为cache的长度，m用来存储( J & =元素。head和tail作为Cache的首尾。

1type LRUCache struct {
2  K . 3  k  m  &n^  u m b Q d 0bsp;  &ng T l  8 j [ mbsN 0 : o C ! q 8p;&nO B g J @bsp;   map[int]*LinkNode
3  &nbsR 6 8 ( p Y V * (p; cap        int
4    head, tail D | ]*LinkNode
5}

接下来我们对整个Cache进行初始化。在初始化head和tail的时候将它们连接在一起。

1func Constructor(capacity int) LRUCache {
2    head := &LinkNode{0, 0, nil, nil}
3&nbsb , [ fp;   tai0 . l 0 {l := &Li d %nkNode{0, 0, nil, nil}
4    3  B m L 4 %head.next = tail
5    tail.pre = head
6    return LRUCache{make(map[int]*LinkNode), capacity, head, tail}
7}

大概是这样：

现在我们已经完成了CacB # 1 # $he的构造，剩下的就是添加它的o a 6 & I ( |API了。因为Get比较简单，我们先[ - x c完成Get方法。这里分两种情} 8 $ , 况考虑，如果没有找到元素，我们返回-1K i V b 0。如果@ p I _ ` . r t 0元素存在，我们需要把这个元素移动到首位置上去。

 1func (this 1 F N L g b q;*LRUCache) Get(L d t 8 2 1key int) int F = =;{
 2    head&nn j ; H I ~ dbsp;:= this_ } F *.head
 3    cache :=- x [ this.m
 4&nbY [ {sp;   if v, exist := cac8 ] X he[key]; exist {
 5      &no Y A e D lbsp; v.pre.next = v.next
 6        v.next.` ( ^pre =&nq q s i e Tbsp;v~ A o ; ~.pre
 7        v.next = head.next
 8        head, @ . 8 X p.next.pre4 ) 2 = v
 9  &nbsf j = g F | 6p;     v.pre = head
10        head.next = v
11        retuA ; / N | I | / wrn v.val
12    } else {
13        return -1
14    }
15}

大概就是下面这个样子（假若2是我们getx V O . B q的元素）

我们很容易想到这个方法后面还会用到，所以将其抽出。

 1func (this k N S d Y / = $;*LRUCache) moveToHead(node *LinkNode){
 2 &nb 2 ybsp; Q ] q P 7;&n& ` c @ bsp;    head := this.head
 3 a 9 S . z U; &nr X 5 f [bsp;     //从当前位置删除
 4 $ d B 1;       node.pre.next = node.next
 5        ; J a X E m s bnode.next.pre = k j b h | p Dnode.prO n , _e
 6    &nbE p b ysp;   //移动到首位置8 ^ n 1 Y X ] N
 7 &nbr I ( 2sp; &nb ] t N m Lsp;   &5 S = j I t fnbsp;node.next = head.next
 8        head.next.pre = node
 9 , R .;       _ z X S O A q;node.pre = head
10  &f & I H n j v i 6nbsp;     head.next& E ( s z Q G dnbsp;= node
11}
12
13funs A m s x cc (this *LRUg p #Cache) N & & , $ b Q 7Get(key int) int {
14    cache := this.m
15&nh ^ O q Z S Nbsp;   if v,&nbs- _ f ] *p;exist = N Y 0;:= cache[key]; exist&nA k l 9 b i absp;{
16        this.moveToHead(v)
17   &nbs7 K Q N `p;    return vn j U Z j o k Y.val
18    } else {
19    &nbj a b + n Z : Isp;   return -1
20    }
21}

现在我们开始完{ K 2 Q成Put。实现Put时，有两种情况需要考虑。假若元素存在，其实相当于做一个Get操作，也是移动到最前面（但是需要注意的是，这里多了O 8 , R Y . m Q Z一个更新值的0 1 N P步骤）。

 1func (this Y ] 0 *;*LR3 n ~ H 5 e 7 % ~UCache) Put(key int, value int$ { 2 0 s ? M o) {
 2    head := this.head
 3 &nb4 % 7 | A V h [ 8sp;  tail := 2 [ k K c / x Gthis.tail
 4    cache := this` _ z s ].m
 5  &@ H W Y Gnbsp; //假若元素存在
 6&&  } ` [nbsp;   if v, exist :=&n8 - ,bsp;cache[key]; ex, ~ 3ist {
 7 7 y L;&nbA x = & ] [ Ysp;     &^ n _nbsp;//1.更新值
 8  &n# y o p G N & u bsp;  &n9 e % p bsp;  6 q 7 [;v.val&nbs) # l [ $ O ) $ wp;=&nbL y w d T dsp;value
 9      D N N z; &@ ] Q 5 t 2 inbsp;//2.移动! ^ c ] p o j /到最前
10        this.moveToHead(v)
11  &n* c , . cbsp; } else {
12        //TODO
13    }
14}

假若元素不存在，我们将其插入到元素首，并把9 m 6 [ D 1 Z该元素值放入到map中。

 1func (this *LRUCache)&nbsF . ^p;Put(key int, value int) {
 2    head := this.head
 3    tail :=&# 1 L d [ g 5 %nbsp;this, C I ~ ` D _ l 9.tail
 4    cache :=&nbsN : 5 D & n T hp;this.m
 5    //存在
 6    if v,&nbs( H d  tp;exist := cache[key]; 7 , ( I { I 4 U Vexist {
 7&nbsW x Ap;       //1.V & { Z M更新值
 8        v.val = value
 9  &nbsA $ ~ 4 np; &nbsu n p sp;   //2.移动到最前
10        this.moveToHead(v)
11  # @ [ C Z x S;&n4 s M @ x 6 z fbspA n D; } else {
12        v := 5 D ; 9 % H V b&LinkNode{key, value, nil, nil}
13   &nh D T % 7 3 i - 8bsp; &ne * .bsp;  v.next = head.next
14        g + E I  ; lv.pre = head
15      &nbr z / k T a 8 usp; head.next.pre = v
16        head.next = v
17&nbs+ Q e j h H U yp;   i 9 5 | ] B { V    cache[key]&nb! d P / 3 O = nsp;= vT = + b 9 = | n m
18&n ) [ ) c N K c 8nbsp;  C # - B x 7 g Z E }
19}

但是我们漏掉了一种情况，如果恰好此时Cache中元素满了，需要删掉最后的元r L $ ^素。处理完毕，附上Put函数完整代码。

 1func (this *LRUCache) Put(key&R Y F Vnbsp;int, value int)&n` Y ) ;bsp;{
 2    head := this.head
 3    tas w kil :=&nbd _ N = nsp;this.tail
 4    c+ s r E [ache Q E R !:= this.m
 5    //存在
 6   &nbs9 B 3 Np;if v, exist := cache[key]; exist {
 7 &nbsY [ $ lp; k r 2 P { I O;     //1.更新值
 8        v.val = value
 9        //2.移动到最前
10  &a h H K V . %nbsp;    &O  G 7 ] Tnbsp;this.moveToHead(v)
11    } else {
12        v :=&nbsT g I &p;&LinkNode{key, value, nil, nil}
13        if len(cache) == this.cap {
14            //删除最后元素
15    &nbs` w c kp;       delete(cache, tail.pre.key)
16      _ i 4; 5 : Z + h , z  &nbw 5 g 0 m +  K esp;  tail.pre.pre.nextu t n X y L 3 c 2 = tu ` } 1ail
17    &R V C nbsp;      &nbs5 l 4 n Gp;t, c $ C iail.pre = tail.pre.pre
18        }
19        v.next&nba * T lsp;= head.next
20&A ! 9 v n X enbsp;  &nH 4 Y 2 l B w p Fbsp;   % ! B $; v.pre = i 8 / .;head
21        head.ne@ E 2 Nxt.pre =&nb@ . A Q Jsp;v
22        head.next = v
23        cache[key]&m ^ ]nbsp;= v
24    }
25}

最后，我们完成所有代码：

 1type LinkNode struct&nbq  ( @ 4 z Z k ksp;{
 2 &nbsc M z _ : 0 xp;  key, val  int
 3    pre, next *LinkNode
 4}
 5
 6type LRUCache st] - I W 5 Kruct {
 7    m  ( a /    U M ! J b , C #     map[int]*LinkNode
 8&e 4 ( R G d C : !nbsp;   c 3 * ~ { k ; | Nap &nbss & Y Op;      int
 9    head, tail *LinkNode
10}
11
12func CoS o M R { H I [nstrW ] U @ :uctor(capacity U I 1 _ -int)&nbs& % { a 9 i .p;LRy & 1 *UCache {
13    head := &LinkNode{0,&f m nnbsp;0, nil, nil}
14   &nbK I B F L Q - { /sp;tail := &LinkNode{0, 0, niW a @l,&6 z i :nbsp;nil}
15    hb 2 o O . Cead.nexZ l A M K 5 6 A ~t = tail
16    tail.pre = head
17    return LRUCac! x 0 she{make(map[int]*LinkNode), capacitY b ]y,4 ) n = x | b * T head, tail}
18}
19
20func (this *LRUCache) Gu C U w g ^et(key int)&/ t j j I Y :nbsp;int {
21    c1 X @ 7 : U M gache := this.m
22    if v,&^ [ knbsp;exist := cache[key]; exist {
23        this.movS K z ^ 7eToH; t ` * Uead(u * 4 4 e Uv)
24        return K a 6 w : r ^ e Bv.val
25 e L } S;   } else {
26&nbw 3 ! =sp;       return -1
27    }
28}
29
30func (this *LRUCache) moveToHead(node *LinkNode) . , N{
31    head := this.head
32    //从当前位置删除
33    node.pre.next = node.next
34    node.next.pre = e O Z q v $ 0 +node.pre
35    //移动到首位置
36 &nb2 v h  T K 9 1sp;  node.next = head.next
37 W [ K 6 h D;  &ni _ b Bbs4 Q q ? 3 [ r }p;head.next.pre = node
38   &n4 8 Ibsp;node.pre = head
39    head.next = node
40}
41
42func (this *LRUCache) Put(key int,&nbs3 S l ] a + $ 4 _p;value&nI 2 o 4 _ `bsp;int) {
43[ p # c l | Z b    head := n @ l G O $ ythis.head
44   &nbM ` O ( g {sp;tail :=3 l ) C h . P C this.tail
45    cache&| ,  i # O E r }nbsp;:= this.m
4x l s C + N  A6  &nb; U [ h 7 j . @sp; //存在
47  &D * _ ` u 4nbsp; if v, z r O;exist := cF l j V B j v W iache[key]; exist {
48    E & K #     //1.更新值
49  &nK u x | m ibsp;    &nl 0 ( 3bsp;v.val = k Y W w 8 H 6 }value
50    &nbsh V ( upR 7 2 r ] | U; &nB c G / / Dbsp; # | W X//2.移动到最前
51( o L I e (  ~  U ^ * L   &nbs& / $ 4p;  this.moveToHead(v)
52   &nbse z / r I R w = p;} else {
53    &nk H J ibsp;   v := &LinkNode{key, value, nil, nil}
54      &B i N } c = S # {nbsp; o 3 X T | ` )  Y;if _ { 0;len(cache) == tX + $ ^ . / Q Chis.cap {
55            //删除末尾元素
56    &nbP z r K c v sb P  F f z F  Fp;  + @ # * j T ~ t w     delete(cache, tail.pre.key)
57            tail.pre.pre.next =&e ~ Z r W ` Nnbsp;tail
58 &nB # r hbsp;      E 2 z X A    tail.pre = tail.pre` ! g.pre
59    &X 7 W I $ G tnbsp;  &nbk & 7 0 6 y U j 5sp;}
60  &n$ 1 l Absp;&n m bbsp; p @ 3 ; F ^ , 1;   v.next = head.next
61    &nbsJ e 2 Dp; = ? 1  v.pre = head3 o f = s n #  =
62    &nbsg V z B h W ) c Gp;  g ^ @ o [ head.nV ! M I ^ i z #ext.pre p { % i e @ w z %;= v
63      &nb, 1 ) : d Xsp; head.next = v
64    &nbs@ W ; k q ,p;   cache[key] = v
65    }
66}

优化后：

 1type&ni / ~ 3 A M #bsp;LinkNode| k z struct {
 2    key,&d e x ( H : z i anbsp;val  int
 3d M @   ] ~ $ l 4 O @ k Z; pre, neP A L c m T D ?xt *LinkNode
 4}
 5
 6type&nbS G n q A - ksb _ U D  i p;LRUCache struct {
 7 ` ~ G b Q 0 4   m    &nD N X G y Gbsp;     map[int]*LinkNode
 8    cap    W W ` b w x i t ?;    int
 9    hep c b 5 ` Jad, H ^ s 6 m % D *tail *LinkNode
10}
11
12func Constructor(capacity int) LRUCache {
13    head := &LinkNode{0, 0,&u F D = ,nbsp;nil, nil}
14 &nbs} 0 !p;  tailL ~ T n 7 l - 0 := &LinkNode{0,&( b z ? Q ! F tnbsp;0, nil, nil}
15    head.next = tail
16    tail.pz f Z = s _ S G *re = head
17    return&/ n : Q Y ~ h s Lnbsp;LR7 n ? 3 ! ?UCache{make(map[int]*LinkNode), capacity, head, tail}
18}
19
20funP [ % C $c (this *LRUCache) A i O;Get(key int) int {
21    cache :=&E A % . u b t dnbsp;this.m
22    if v, exist := cache[key]; exist {
23&nbW F t F ` S b usp;   S d : .;   &nbO k d ;sp;this.MoveToHead(v)
24    N O 6 &    return v.val
25&nV f * # + =bsp;&nbsU X B _ .p;  } else {
26      &; = y Q z : D h @nbsp; return -1
27    }
28}
29
30func _ 1 o H;(this *LRUCache) RemoveNode(no^ B Xde *LinkNode)&n$  b : r q n c ibsp;{
31 &nbj J q 8 Psp;  node.pre.next = node.next
32d c Z _ S I v * %    node.next.pre =d : y node.pre
33}
34
35func (this *LRUCache) AddNode(node *LinkNode) {
36  d C x . g ^ 2  l;  head := this.head
37    node.nex~ W 3 O B L F kt = head.next
3~ : 8    head.next.pre = node
39    node.pr) C 5 ] 1 je = head
40    head.next =&n6 + t o w ~ / z lbsp;node
41}
42
43func (this h E )*LRUCache) w ? g l R;MoveToHead(node *LinkNode) {
44    this.RemoveNode(node)
45  , J P ; : + ; . `;&nbN g (sp; thl / F ; &is.AddNode(node)
46}
47
48func 6 $ 7 :(this&nbv / p ; gsp;*LRUCache) Put(key&nbY h ^ nsp;@ h q N Q N c int, value int) {
49  &nbsE Z 3 c Z n H O yp; tail := this.tail
50    cache := this.m
51    if v, exist := cache[key]; exist {
52        v.val = value
53  E 0 5 f L ; r U q;      this.MoveToHead(v)
54    } else&nbsV x m C F T p;{
55        v := &LinkNode{key, value,&K ( A T A ~ W - nbsp;nil, nil}
56        if len(cache)&nbsc r Wp;== this.cap {
57            delete(cache, tail.pre.key)
58 4 8 K  3; &nb= Z 6 !sp;    &d K 0 ~ 8 & x ! +nbsc r } ap;    this.RemoveNode(tail.pre)
59   y  ` Z s U u x d   &n~ %  Y r i z E gbsp; }4 E = : p ) A O K
60   &nc X t d ~ 2 i g /bsp; &I f rnbsp;  this.AddNode(v)
61 &nbsX h K | xp;      cache[key] = v
6 J F * y o [2    }
63}

因为该算法过于重要，给一个Java版本的：

 1//java版本
 2public class LRUCache {
 3&nd 8 }bsp; class LinkedNode {
 4    int key;
 52 h ] R ~ S    int value;
 6    LinkedNode prev;
 7   &M J y ] Tnbsp;LinkedNode next;
 8  }
 9
10  privatG ^ & Q [e void addNode(Li] e / A ; q %nkedNode not a ; B 9 U 8 bde) g T W a S 3 $;{
11    node.prev&nbi _ G lsp;= head;
12 &q , 7 P # 4 t 4nbsp;  node.next = head.next;
13    head.next.pn U ?  / /rev = node;
14    head.next&nbw n G E 7 Dsp;= node;
15  }
16
17&Z @ E 5 u mnbsp; private void removeNode(LinkedNode5 9 ? node){
18  / U , ? C Q  LinkedNode prev =&nbT t 9 vsp;node.prev;
19  : g ! 3 q S k r ];  LinkedNode next = node.next;
20 &ny y h r i ] ~ 1 Bbsp;  prev.next = @ h i 0 3 T;next;
21    next.prev&W n Y mnbsp;= prev;
22  }
23
24  private void M d K d;moveToHead(LinkedNode node){
25    removeNode(node);
26    addNode(node);
27  }
28
29  private&2 V I O $ 0 @ e *nbsp;LinkedNode popTail() {
30 ; 5 O V S I c;   LinkedN! I : k c sode rr _ ~ a , i B S 4es = tail.prev;
31&$ ` : B #nbsp;   removeNode(res);
32    return res;
33 &nbm D U  P + ` ts~ u  a &p;}
34
35  prT ] Givate HashtabX - ) u g : f Wle<Integer, LinkedNode> cache 3 e * H n Y 0= P , u Q 1 B;new&nbsA j F K G m z ;p;Hashtable<Integer, LinkedNode>();
36  private int size;
37 f n ; private int capacity;
38  private LinkedNode&nbE K A n S asp;head, tail;
39
40  public LRUCache(int capacityk { M v P) {
41 &nB j o 8 , ) |bsp;  this.size = 0;
42a q h E G n 0 &nbsU } I O [ ,p;  this.capacity = capacityW $ Q J d E z l d;
43  &nbm v  H & [ 2 Gsp; head = new LinkedNode();
44  3 * = : L  tail&nbs| a B  Np;= ~ 1 Lnew LinkedNode();
45    head.next = tai! 0 v ml;
46   &nx @  Ibsp2 G F 2 r;tail.prev&nz u Sbsp;= head;
47 &~ i { M G Mnbsp;}
48
49  public int get(int T d d n - ckey) {
50    LinkedNode node = cache.get(key);
51   g - - K O / Y; if g I o z a(node == null) return -4 n J N ] 8 { b j1;
52    moveToHead(node);
53    return T v x d P .  K snode.value;
54 &nbsy a )  H 4p;}
55
56  N 4 :public void put(int key, int value) {
57    LinkedNoW G I u -de&nbsH J I ! M l % B gp;node = cache.get(key);
58
59   7 t k j m; if(nod( W 7 l } J A ^ ue == null) {
60      LinkedNode newNode = new LinkedNode();
6N 0 ^ * A Z d =1      newNode.key = key;
62      newNode.value = value;
63     G , *  U ~ e } a; cache.pT 5 uut(key, newNode);
6v 3 { 7 N4      addNode(newNode);
65  &nb2 W G E ] W 7 fsp;   ++size;
66      if(size&y , X 1 k { d y /nbsp;> capacity) {
67 &nbsg G ? D #p;   &r 3 dnbsp;  LinkedNode tail = popTail();
68&[ 3 1 k d E & m qnbsp;       cache.remove(tail.key);
69        --size;
70      }
71    } else {
72    | d % & h o;  } k ,;node.value = value;
73  b L i & R !; &i , g @ g W $nbsp;   moveToHead^ [ k C(node);
74    }
75  }
76}

第四部分：Redis 近LRU 介绍

上文完成了咱们自己的LRU实现，现在现在聊一聊RediR k 3 5 { T o C Os中的近似LRU。由于真实LRU需要过多的内存（在数据量比较大时），所以Redis是使用一种e 0 e D随_ u O 9 d X 5机抽样的方式，来实现一个近似LRU的& | .效果。说白了，LR8 ? ~ ) = ~U根本只是一个预测键访问顺序的模型。

在Redis中有一个参数，叫做 “maxmemory-samples”，是干嘛用的呢？

 # LRU and minimal H f t  N 8 2 ~ J;TTL algor~ J M / L t c -ithms are not precise algorithms but approm l W v j Sximated ? h ! ] I C U D O;
 # algorithms&7 w U ~ ynbsp;(in&nbs] C X Z F tp;order to save memory),/ A d W 2 y H q so you can tune it 0 # ^ ! r 2 X ?;for speed or 
 # accuracy. For default Redis will checku d P 6 = o q a five keys and pick the one that was 
 # I % A d e;used less recently, you can c( Z VhaA G J r j : g )nge the sample E 5 nsize using the following 
 # configuration direV K 9cg z 7 x u Ttive. 
 # 
 # The default of 5 produces good enouV t ) ; B &gh results. 10 Approximates very closely&nbB A [ o h , a M lsp;H / F a c
 # true LRU but&n% s O G gbsp;costs a bit more CPU. 3 is very fast bu) # i m Q kt&nQ _ a 1 ebsp;not very accurate. 
 # 
maxmemory-samples 5

上面我们说过了，近似LRU是用随机抽样的方式来实现一个近似的` m 3 . l k k Y iLRU效果。这个参数其实就是作者提供了一种方式，可以让我们人为干预样本数大小，将其设的越大，就越接近真` L % B [ g t Z )实L] z 8RU的效果，当然也就意味着越耗内存。（初始值为5? X f z k z是作者默认的最佳）

这个图解释一下，绿色的点是新增加的元素，深灰色的点是没有被删除的元素，浅t w h灰色的是被删除的元素。最下面的这张图，是真实LRU的效果，第二张图是默认该参数为5的效果，可以看到浅灰色部分和真实的契合还是不错的。第一张图是将该参数设置为10的效果，已经基本接近真实LRU的效果了。

由于时间关系本文基本就说到这里。那Redis中的近似LRU是如何实现的呢？请关P 9 j注下一期的内容~

文章来源：本文由小浩算法授权转载