1:HL["/_next/static/css/275839517c59c532.css",{"as":"style"}]
2:HL["/_next/static/css/bdb880d990e879b6.css",{"as":"style"}]
0:[[["",{"children":["post",{"children":[["slug","lru-lfu-cache","d"],{"children":["__PAGE__?{\"slug\":\"lru-lfu-cache\"}",{}]}]}]},"$undefined","$undefined",true],"$L3",[[["$","link","0",{"rel":"stylesheet","href":"/_next/static/css/275839517c59c532.css","precedence":"next"}],["$","link","1",{"rel":"stylesheet","href":"/_next/static/css/bdb880d990e879b6.css","precedence":"next"}]],["$L4",null]]]]
5:HL["/_next/static/css/95c7fb627fba8423.css",{"as":"style"}]
6:HL["/_next/static/css/477df780fc5cb593.css",{"as":"style"}]
7:HL["/_next/static/css/c40a92e7f996f910.css",{"as":"style"}]
3:["$L8",null]
4:[["$","meta","0",{"charSet":"utf-8"}],["$","title","1",{"children":"缓存替换算法 LRU LFU"}],["$","meta","2",{"name":"description","content":"缓存替换算法 LRU LFU"}],["$","link","3",{"rel":"manifest","href":"/manifest.json"}],["$","meta","4",{"name":"generator","content":"Hexo.js & Next.js"}],["$","meta","5",{"name":"viewport","content":"width=device-width, initial-scale=1"}],["$","meta","6",{"property":"og:title","content":"缓存替换算法 LRU LFU"}],["$","meta","7",{"property":"og:description","content":"缓存替换算法 LRU LFU"}],["$","meta","8",{"name":"twitter:card","content":"summary"}],["$","meta","9",{"name":"twitter:title","content":"缓存替换算法 LRU LFU"}],["$","meta","10",{"name":"twitter:description","content":"缓存替换算法 LRU LFU"}]]
9:I{"id":"7477","chunks":["194:static/chunks/194-26e3c21be498c0ce.js","859:static/chunks/859-ea023633456a13f8.js","355:static/chunks/app/tags/[slug]/page-257dc97429efd72a.js"],"name":"","async":false}
a:I{"id":"92","chunks":["194:static/chunks/194-26e3c21be498c0ce.js","92:static/chunks/92-371a458fbe090447.js","284:static/chunks/284-b1d21b691d3eabee.js","605:static/chunks/app/post/[slug]/page-0339b76e369b6af8.js"],"name":"","async":false}
b:I{"id":"2449","chunks":["194:static/chunks/194-26e3c21be498c0ce.js","92:static/chunks/92-371a458fbe090447.js","185:static/chunks/app/layout-4eab34e1c4d9af8d.js"],"name":"","async":false}
c:I{"id":"3211","chunks":["272:static/chunks/webpack-7471fa70de6bdb29.js","253:static/chunks/bce60fc1-2413e66000a5dd8f.js","769:static/chunks/769-2bf088c0a421e73d.js"],"name":"","async":false}
d:I{"id":"5767","chunks":["272:static/chunks/webpack-7471fa70de6bdb29.js","253:static/chunks/bce60fc1-2413e66000a5dd8f.js","769:static/chunks/769-2bf088c0a421e73d.js"],"name":"","async":false}
f:I{"id":"6424","chunks":["194:static/chunks/194-26e3c21be498c0ce.js","92:static/chunks/92-371a458fbe090447.js","185:static/chunks/app/layout-4eab34e1c4d9af8d.js"],"name":"GaLite","async":false}
10:I{"id":"9869","chunks":["194:static/chunks/194-26e3c21be498c0ce.js","92:static/chunks/92-371a458fbe090447.js","185:static/chunks/app/layout-4eab34e1c4d9af8d.js"],"name":"SpeedInsights","async":false}
11:I{"id":"7148","chunks":["194:static/chunks/194-26e3c21be498c0ce.js","92:static/chunks/92-371a458fbe090447.js","185:static/chunks/app/layout-4eab34e1c4d9af8d.js"],"name":"Analytics","async":false}
8:["$","html",null,{"lang":"zh-CN","children":[["$","link",null,{"rel":"icon","href":"/images/icons/icon-72x72.png","type":"image/x-icon"}],["$","link",null,{"rel":"preconnect","href":"https://vip2.loli.io"}],["$","link",null,{"rel":"dns-prefetch","href":"https://vip2.loli.io"}],["$","link",null,{"rel":"alternate","type":"application/atom+xml","href":"/atom.xml"}],["$","body",null,{"children":["$","div",null,{"className":"kbCXHY jdraHW eqrBPF kEFtPS bNzOWQ juexza kXMrYr ","children":[["$","header",null,{"className":"doNOqr WhAZY cRUUAa cwMEsi dpJmjl bsTuZj iRietU JCsMI fONtwf eEsPgn gWUoqV kazZiE fsKTUV dkPCxO gdGTeM ","children":[["$","div",null,{"className":"doNOqr WhAZY hrtgtE iYRJzs iJGxaV jlwzhw ","children":[["$","$L9",null,{"className":"icyDkI gSBWlu foGVKH IVbXa kooHYa JxWnH cVJMrm hyoqRt jlijat kUpitc gdtkYW iDPWLw kayxZK hCkclF cneMsd gYPNzh ","href":"/","children":[["$","div",null,{"className":"eSltVp cpOcAb caItCN cyerGB dSxtaa lbEyiT kUPESX Pmecg ldtSOY ","children":["$","$La",null,{"src":"https://vip2.loli.io/2023/03/09/2tAMcy694lE3IZX.jpg","blurDataURL":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAUAAAAFCAIAAAACDbGyAAAACXBIWXMAAAsTAAALEwEAmpwYAAAAW0lEQVR4nAFQAK//AAAAAA0MCD08JoiyXkqWNQBPSDHtwYf/86ehuWNAeS4Aep9O+bt9/9aWxbtzETMSAClqHld9MqambcuqdgMOAwBCaS1Mdzd/hFE4PCMEEAS4ex049PWXOAAAAABJRU5ErkJggg==","alt":"avatar","width":200,"height":200,"layout":"responsive","className":"jWjrEQ eKtERL BRobm iovjFN ","placeholder":"blur","priority":true}]}],["$","h1",null,{"className":"evYdWj cpOcAb XEVlt huiurs ","children":"fengkx's Blog"}]]}],["$","h2",null,{"id":"name","className":"hrtgtE fcXWHl ","children":"fengkx"}],["$","h3",null,{"id":"title","className":"hrtgtE fcXWHl ","children":"Student & Coder"}],["$","div",null,{"className":"fONtwf fcXWHl foGVKH IVbXa dPVLzs fkrGAA cvCecb jJGIjV ","children":[["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","children":["$undefined",[["$","path","0",{"d":"M21 10c0 7-9 13-9 13s-9-6-9-13a9 9 0 0 1 18 0z","children":"$undefined"}],["$","circle","1",{"cx":"12","cy":"10","r":"3","children":"$undefined"}]]],"className":"$undefined","style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}],["$","span",null,{"className":"gUpJEt ","children":"Guangzhou, China"}]]}],["$","nav",null,{"className":"hrtgtE jlwzhw gSBWlu IVbXa kKRHCo jzaqKj ehqwGF ","children":[["$","div",null,{"className":"kooHYa ","children":["$","$L9",null,{"className":"gSBWlu foGVKH fPWmiY JxWnH cVJMrm OqOoD jJbtJp ihIJmy bgUfpT AsNjI kwISoH gdPTUr eLDTYY dmKgnC dPFrWx bmQfsF krqYva kXurrt ","href":"/","children":[["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","className":"jJhMtm fcXWHl gdPTUr dCiVRS TTRIX ","children":["$undefined",[["$","path","0",{"d":"M3 9l9-7 9 7v11a2 2 0 0 1-2 2H5a2 2 0 0 1-2-2z","children":"$undefined"}],["$","polyline","1",{"points":"9 22 9 12 15 12 15 22","children":"$undefined"}]]],"style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}],["$","span",null,{"className":"","children":"首页"}]]}]}],["$","div",null,{"className":"kooHYa ","children":["$","$L9",null,{"className":"gSBWlu foGVKH fPWmiY JxWnH cVJMrm OqOoD jJbtJp ihIJmy bgUfpT AsNjI kwISoH gdPTUr eLDTYY dmKgnC dPFrWx bmQfsF krqYva kXurrt ","href":"/archives","children":[["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","className":"jJhMtm fcXWHl gdPTUr dCiVRS TTRIX ","children":["$undefined",[["$","polyline","0",{"points":"21 8 21 21 3 21 3 8","children":"$undefined"}],["$","rect","1",{"x":"1","y":"3","width":"22","height":"5","children":"$undefined"}],["$","line","2",{"x1":"10","y1":"12","x2":"14","y2":"12","children":"$undefined"}]]],"style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}],["$","span",null,{"className":"","children":"归档"}]]}]}],["$","div",null,{"className":"kooHYa ","children":["$","$L9",null,{"className":"gSBWlu foGVKH fPWmiY JxWnH cVJMrm OqOoD jJbtJp ihIJmy bgUfpT AsNjI kwISoH gdPTUr eLDTYY dmKgnC dPFrWx bmQfsF krqYva kXurrt ","href":"/tags","children":[["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","className":"jJhMtm fcXWHl gdPTUr dCiVRS TTRIX ","children":["$undefined",[["$","path","0",{"d":"M20.59 13.41l-7.17 7.17a2 2 0 0 1-2.83 0L2 12V2h10l8.59 8.59a2 2 0 0 1 0 2.82z","children":"$undefined"}],["$","line","1",{"x1":"7","y1":"7","x2":"7.01","y2":"7","children":"$undefined"}]]],"style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}],["$","span",null,{"className":"","children":"标签"}]]}]}],["$","div",null,{"className":"kooHYa ","children":["$","$L9",null,{"className":"gSBWlu foGVKH fPWmiY JxWnH cVJMrm OqOoD jJbtJp ihIJmy bgUfpT AsNjI kwISoH gdPTUr eLDTYY dmKgnC dPFrWx bmQfsF krqYva kXurrt ","href":"/links","children":[["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","className":"jJhMtm fcXWHl gdPTUr dCiVRS TTRIX ","children":["$undefined",[["$","path","0",{"d":"M17 21v-2a4 4 0 0 0-4-4H5a4 4 0 0 0-4 4v2","children":"$undefined"}],["$","circle","1",{"cx":"9","cy":"7","r":"4","children":"$undefined"}],["$","path","2",{"d":"M23 21v-2a4 4 0 0 0-3-3.87","children":"$undefined"}],["$","path","3",{"d":"M16 3.13a4 4 0 0 1 0 7.75","children":"$undefined"}]]],"style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}],["$","span",null,{"className":"","children":"友链"}]]}]}],["$","div",null,{"className":"kooHYa ","children":["$","$L9",null,{"className":"gSBWlu foGVKH fPWmiY JxWnH cVJMrm OqOoD jJbtJp ihIJmy bgUfpT AsNjI kwISoH gdPTUr eLDTYY dmKgnC dPFrWx bmQfsF krqYva kXurrt ","href":"/about","children":[["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","className":"jJhMtm fcXWHl gdPTUr dCiVRS TTRIX ","children":["$undefined",[["$","path","0",{"d":"M18 8h1a4 4 0 0 1 0 8h-1","children":"$undefined"}],["$","path","1",{"d":"M2 8h16v9a4 4 0 0 1-4 4H6a4 4 0 0 1-4-4V8z","children":"$undefined"}],["$","line","2",{"x1":"6","y1":"1","x2":"6","y2":"4","children":"$undefined"}],["$","line","3",{"x1":"10","y1":"1","x2":"10","y2":"4","children":"$undefined"}],["$","line","4",{"x1":"14","y1":"1","x2":"14","y2":"4","children":"$undefined"}]]],"style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}],["$","span",null,{"className":"","children":"关于"}]]}]}],["$","div",null,{"className":"kooHYa ","children":["$","$L9",null,{"className":"gSBWlu foGVKH fPWmiY JxWnH cVJMrm OqOoD jJbtJp ihIJmy bgUfpT AsNjI kwISoH gdPTUr eLDTYY dmKgnC dPFrWx bmQfsF krqYva kXurrt ","href":"/search","children":[["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","className":"cpOcAb gdPTUr dCiVRS TTRIX ","children":["$undefined",[["$","circle","0",{"cx":"11","cy":"11","r":"8","children":"$undefined"}],["$","line","1",{"x1":"21","y1":"21","x2":"16.65","y2":"16.65","children":"$undefined"}]]],"style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}],["$","span",null,{"className":"jJhMtm fcXWHl ","children":"搜索"}]]}]}],["$","div",null,{"className":"kooHYa evYdWj ","children":["$","$L9",null,{"className":"gSBWlu foGVKH fPWmiY JxWnH cVJMrm OqOoD jJbtJp ihIJmy bgUfpT AsNjI kwISoH gdPTUr eLDTYY dmKgnC dPFrWx bmQfsF krqYva kXurrt ","href":"/atom.xml","prefetch":false,"children":[["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","className":"cpOcAb gdPTUr dCiVRS TTRIX ","children":["$undefined",[["$","path","0",{"d":"M4 11a9 9 0 0 1 9 9","children":"$undefined"}],["$","path","1",{"d":"M4 4a16 16 0 0 1 16 16","children":"$undefined"}],["$","circle","2",{"cx":"5","cy":"19","r":"1","children":"$undefined"}]]],"style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}],["$","span",null,{"className":"jJhMtm fcXWHl ","children":"RSS"}]]}]}]]}]]}],["$","div",null,{"className":"doNOqr hrtgtE fcXWHl iigETV bMSzLf XEVlt jmezSN izetJs kdrTtD bLIxaN ","children":[["$","div",null,{"className":"iLYBKc gSBWlu zEGrF evYWGf hDdCaA ","children":[["$","$L9",null,{"title":"fengkx's GitHub","href":"https://github.com/fengkx","prefetch":false,"children":["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","children":["$undefined",[["$","path","0",{"d":"M9 19c-5 1.5-5-2.5-7-3m14 6v-3.87a3.37 3.37 0 0 0-.94-2.61c3.14-.35 6.44-1.54 6.44-7A5.44 5.44 0 0 0 20 4.77 5.07 5.07 0 0 0 19.91 1S18.73.65 16 2.48a13.38 13.38 0 0 0-7 0C6.27.65 5.09 1 5.09 1A5.07 5.07 0 0 0 5 4.77a5.44 5.44 0 0 0-1.5 3.78c0 5.42 3.3 6.61 6.44 7A3.37 3.37 0 0 0 9 18.13V22","children":"$undefined"}]]],"className":"$undefined","style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}]}],["$","$L9",null,{"title":"fengkx's Telegram","href":"https://t.me/fengkx","prefetch":false,"children":["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","children":["$undefined",[["$","line","0",{"x1":"22","y1":"2","x2":"11","y2":"13","children":"$undefined"}],["$","polygon","1",{"points":"22 2 15 22 11 13 2 9 22 2","children":"$undefined"}]]],"className":"$undefined","style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}]}],["$","$L9",null,{"href":"https://mstdn.social/@fengkx","rel":"me","prefetch":false,"children":["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","children":["$undefined",[["$","path","0",{"stroke":"none","d":"M0 0h24v24H0z","fill":"none","children":"$undefined"}],["$","path","1",{"d":"M18.648 15.254c-1.816 1.763 -6.648 1.626 -6.648 1.626a18.262 18.262 0 0 1 -3.288 -.256c1.127 1.985 4.12 2.81 8.982 2.475c-1.945 2.013 -13.598 5.257 -13.668 -7.636l-.026 -1.154c0 -3.036 .023 -4.115 1.352 -5.633c1.671 -1.91 6.648 -1.666 6.648 -1.666s4.977 -.243 6.648 1.667c1.329 1.518 1.352 2.597 1.352 5.633s-.456 4.074 -1.352 4.944z","children":"$undefined"}],["$","path","2",{"d":"M12 11.204v-2.926c0 -1.258 -.895 -2.278 -2 -2.278s-2 1.02 -2 2.278v4.722m4 -4.722c0 -1.258 .895 -2.278 2 -2.278s2 1.02 2 2.278v4.722","children":"$undefined"}]]],"className":"$undefined","style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}]}],["$","$L9",null,{"title":"RSS feed","href":"/atom.xml","prefetch":false,"children":["$","svg",null,{"stroke":"currentColor","fill":"none","strokeWidth":"2","viewBox":"0 0 24 24","strokeLinecap":"round","strokeLinejoin":"round","children":["$undefined",[["$","path","0",{"d":"M4 11a9 9 0 0 1 9 9","children":"$undefined"}],["$","path","1",{"d":"M4 4a16 16 0 0 1 16 16","children":"$undefined"}],["$","circle","2",{"cx":"5","cy":"19","r":"1","children":"$undefined"}]]],"className":"$undefined","style":{"color":"$undefined"},"height":"1em","width":"1em","xmlns":"http://www.w3.org/2000/svg"}]}]]}],["$","div",null,{"className":"hrtgtE fcXWHl cyerGB kKRHCo ","children":["Build with ",["$","$L9",null,{"title":"Hexo official site","rel":"noopener noreferrer external nofollow","href":"https://hexo.io","children":"Hexo"}]," ","and"," ",["$","$L9",null,{"title":"Next.js official site","href":"https://nextjs.org","rel":"noopener noreferrer external nofollow","children":"Next.js"}]]}]]}]]}],["$","$Lb",null,{"children":["$","$Lc",null,{"parallelRouterKey":"children","segmentPath":["children"],"error":"$undefined","errorStyles":"$undefined","loading":"$undefined","loadingStyles":"$undefined","hasLoading":false,"template":["$","$Ld",null,{}],"templateStyles":"$undefined","notFound":"$undefined","notFoundStyles":"$undefined","childProp":{"current":["$","$Lc",null,{"parallelRouterKey":"children","segmentPath":["children","post","children"],"error":"$undefined","errorStyles":"$undefined","loading":"$undefined","loadingStyles":"$undefined","hasLoading":false,"template":["$","$Ld",null,{}],"templateStyles":"$undefined","notFound":"$undefined","notFoundStyles":"$undefined","childProp":{"current":["$","$Lc",null,{"parallelRouterKey":"children","segmentPath":["children","post","children",["slug","lru-lfu-cache","d"],"children"],"error":"$undefined","errorStyles":"$undefined","loading":"$undefined","loadingStyles":"$undefined","hasLoading":false,"template":["$","$Ld",null,{}],"templateStyles":"$undefined","notFound":"$undefined","notFoundStyles":"$undefined","childProp":{"current":["$Le",null],"segment":"__PAGE__?{\"slug\":\"lru-lfu-cache\"}"},"styles":[["$","link","0",{"rel":"stylesheet","href":"/_next/static/css/275839517c59c532.css","precedence":"next"}],["$","link","1",{"rel":"stylesheet","href":"/_next/static/css/95c7fb627fba8423.css","precedence":"next"}],["$","link","2",{"rel":"stylesheet","href":"/_next/static/css/477df780fc5cb593.css","precedence":"next"}],["$","link","3",{"rel":"stylesheet","href":"/_next/static/css/c40a92e7f996f910.css","precedence":"next"}]]}],"segment":["slug","lru-lfu-cache","d"]},"styles":[]}],"segment":"post"},"styles":[]}]}],["$","$Lf",null,{"uaId":"UA-103237573-1"}],["$","$L10",null,{}],["$","$L11",null,{}]]}]}]]}]
13:I{"id":"5307","chunks":["194:static/chunks/194-26e3c21be498c0ce.js","92:static/chunks/92-371a458fbe090447.js","284:static/chunks/284-b1d21b691d3eabee.js","605:static/chunks/app/post/[slug]/page-0339b76e369b6af8.js"],"name":"TocTitle","async":false}
e:[false,["$","main",null,{"className":"prose eUUCKp kTeytq jmezSN cjScYX eqrBPF jdraHW cRUUAa DOWJl hgvoZN iZwowi jGHqUK kwISoH AsNjI","children":[["$","h1",null,{"className":"EKhXX ","children":"缓存替换算法 LRU LFU"}],"$L12"]}],["$","aside",null,{"className":"cwMEsi dpJmjl gWUoqV kazZiE fsKTUV dkPCxO fcXWHl hrtgtE icKiSN eeREmo fZMRmg hRjOno ","children":["$","div",null,{"className":"doNOqr gepZXl  AsideContainer_asideContainer___FNWl","children":["$","div",null,{"className":"bKqOie lkcNSa doNOqr dNtEOi ","children":[["$","div",null,{"className":"hlBtvm ckBWJI XEVlt ","children":"文章目录"}],["$","div",null,{"className":"$undefined","children":["$","ol",null,{"className":"jOeduE ","children":[["$","li",null,{"children":[["$","$L13",null,{"id":"缓存替换算法","text":"缓存替换算法"}],false]}],["$","li",null,{"children":[["$","$L13",null,{"id":"LRU","text":"LRU"}],["$","ol",null,{"className":"jOeduE  iDuqPI ","children":[["$","li",null,{"children":[["$","$L13",null,{"id":"实现","text":"实现"}],false]}]]}]]}],["$","li",null,{"children":[["$","$L13",null,{"id":"hashlru","text":"hashlru"}],false]}],["$","li",null,{"children":[["$","$L13",null,{"id":"LFU","text":"LFU"}],["$","ol",null,{"className":"jOeduE  iDuqPI ","children":[["$","li",null,{"children":[["$","$L13",null,{"id":"实现-2","text":"实现"}],false]}]]}]]}],["$","li",null,{"children":[["$","$L13",null,{"id":"ARC","text":"ARC"}],false]}],["$","li",null,{"children":[["$","$L13",null,{"id":"参考文章","text":"参考文章"}],false]}]]}]}]]}]}]}]]
14:I{"id":"4998","chunks":["194:static/chunks/194-26e3c21be498c0ce.js","92:static/chunks/92-371a458fbe090447.js","284:static/chunks/284-b1d21b691d3eabee.js","605:static/chunks/app/post/[slug]/page-0339b76e369b6af8.js"],"name":"ArticleContentClient","async":false}
15:I{"id":"7974","chunks":["194:static/chunks/194-26e3c21be498c0ce.js","92:static/chunks/92-371a458fbe090447.js","284:static/chunks/284-b1d21b691d3eabee.js","605:static/chunks/app/post/[slug]/page-0339b76e369b6af8.js"],"name":"H1","async":false}
17:I{"id":"7974","chunks":["194:static/chunks/194-26e3c21be498c0ce.js","92:static/chunks/92-371a458fbe090447.js","284:static/chunks/284-b1d21b691d3eabee.js","605:static/chunks/app/post/[slug]/page-0339b76e369b6af8.js"],"name":"H2","async":false}
12:["$","$L14",null,{"permalink":"https://www.fengkx.top/post/lru-lfu-cache/","dateString":"2020-02-22","comments":true,"aplayer":false,"showCopyright":true,"children":[["$","$L15","3179",{"id":"缓存替换算法","children":["缓存替换算法"]}],"\n",["$","p","3182",{"children":["缓存替换算法决定了在有限的容量的缓存中，有新的项进入的时候选择哪一项被剔除的问题。",["$","br","3180",{}],"\n","$L16"]}],"\n",["$","p","3187",{"children":["假如我们以",["$","strong","3183",{"children":["K-V"]}],"形式的缓存为例。通常 KV 形式的缓存为了有",["$","code","3184",{"children":["O(1)"]}],"的读取速度都会维护一个",["$","code","3185",{"children":["HashMap"]}],["$","br","3186",{}],"\n那么不同的算法的其中一个不同之处就是保存替换时决策所需要的信息而产生的额外的数据结构了。"]}],"\n",["$","$L15","3188",{"id":"LRU","children":["LRU"]}],"\n",["$","p","3189",{"children":["LRU (Least recently used) 最近最少使用，实际上就是缓存中最久未被使用的项会被优先剔除。"]}],"\n",["$","p","3190",{"children":["它的思想是如果一个项很久都没被使用了，那么它应该被剔除缓存。"]}],"\n",["$","p","3191",{"children":["但是当缓存的访问是循环的顺序遍历，而且缓存容量不足以容纳遍历的项时，缓存项就会频繁进出影响效率。"]}],"\n",["$","$L17","3192",{"id":"实现","children":["实现"]}],"\n",["$","p","3194",{"children":["$L18"]}],"\n",["$","p","3196",{"children":["为了知道最近最少访问的信息通常 LRU 的实现会采用双链表保存缓存项。因为缓存的数量会动态变化，所以会选择链表。而且会有不少的删除节点操作，为了达到",["$","code","3195",{"children":["O(1)"]}],"的删除操作所以会用双链表。"]}],"\n",["$","pre","3249",{"className":"shiki github-light","style":{"backgroundColor":"#fff","color":"#24292e"},"tabindex":"0","children":[["$","code","3248",{"className":"language-go","children":[["$","span","3201",{"className":"line","children":[["$","span","3197",{"style":{"color":"#D73A49"},"children":["type"]}],["$","span","3198",{"style":{"color":"#6F42C1"},"children":[" CacheNode"]}],["$","span","3199",{"style":{"color":"#D73A49"},"children":[" struct"]}],["$","span","3200",{"style":{"color":"#24292E"},"children":[" {"]}]]}],"\n",["$","span","3204",{"className":"line","children":[["$","span","3202",{"style":{"color":"#24292E"},"children":["\tkey   "]}],["$","span","3203",{"style":{"color":"#D73A49"},"children":["int"]}]]}],"\n",["$","span","3207",{"className":"line","children":[["$","span","3205",{"style":{"color":"#24292E"},"children":["\tvalue "]}],["$","span","3206",{"style":{"color":"#D73A49"},"children":["int"]}]]}],"\n",["$","span","3211",{"className":"line","children":[["$","span","3208",{"style":{"color":"#24292E"},"children":["\tprev  "]}],["$","span","3209",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3210",{"style":{"color":"#6F42C1"},"children":["CacheNode"]}]]}],"\n",["$","span","3215",{"className":"line","children":[["$","span","3212",{"style":{"color":"#24292E"},"children":["\tnext  "]}],["$","span","3213",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3214",{"style":{"color":"#6F42C1"},"children":["CacheNode"]}]]}],"\n",["$","span","3217",{"className":"line","children":[["$","span","3216",{"style":{"color":"#24292E"},"children":["}"]}]]}],"\n",["$","span","3218",{"className":"line","children":[]}],"\n",["$","span","3223",{"className":"line","children":[["$","span","3219",{"style":{"color":"#D73A49"},"children":["type"]}],["$","span","3220",{"style":{"color":"#6F42C1"},"children":[" LRUCache"]}],["$","span","3221",{"style":{"color":"#D73A49"},"children":[" struct"]}],["$","span","3222",{"style":{"color":"#24292E"},"children":[" {"]}]]}],"\n",["$","span","3226",{"className":"line","children":[["$","span","3224",{"style":{"color":"#24292E"},"children":["\tsize     "]}],["$","span","3225",{"style":{"color":"#D73A49"},"children":["int"]}]]}],"\n",["$","span","3229",{"className":"line","children":[["$","span","3227",{"style":{"color":"#24292E"},"children":["\tcapacity "]}],["$","span","3228",{"style":{"color":"#D73A49"},"children":["int"]}]]}],"\n",["$","span","3233",{"className":"line","children":[["$","span","3230",{"style":{"color":"#24292E"},"children":["\thead     "]}],["$","span","3231",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3232",{"style":{"color":"#6F42C1"},"children":["CacheNode"]}]]}],"\n",["$","span","3237",{"className":"line","children":[["$","span","3234",{"style":{"color":"#24292E"},"children":["\ttail     "]}],["$","span","3235",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3236",{"style":{"color":"#6F42C1"},"children":["CacheNode"]}]]}],"\n",["$","span","3245",{"className":"line","children":[["$","span","3238",{"style":{"color":"#24292E"},"children":["\tcache    "]}],["$","span","3239",{"style":{"color":"#D73A49"},"children":["map"]}],["$","span","3240",{"style":{"color":"#24292E"},"children":["["]}],["$","span","3241",{"style":{"color":"#D73A49"},"children":["int"]}],["$","span","3242",{"style":{"color":"#24292E"},"children":["]"]}],["$","span","3243",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3244",{"style":{"color":"#6F42C1"},"children":["CacheNode"]}]]}],"\n",["$","span","3247",{"className":"line","children":[["$","span","3246",{"style":{"color":"#24292E"},"children":["}"]}]]}]]}]]}],"\n",["$","p","3251",{"children":["我们保存链表的尾指针，每当有缓存项的访问或者新项都将对应的节点移到链表的头。头插入和删除节点的操作都是",["$","code","3250",{"children":["O(1)"]}]]}],"\n",["$","p","3253",{"children":["$L19"]}],"\n",["$","$L17","3254",{"id":"hashlru","children":["hashlru"]}],"\n",["$","p","3259",{"children":["还有一种近似的 LRU 算法","$L1a","通过两个",["$","code","3256",{"children":["HashMap"]}],"的交换实现",["$","code","3257",{"children":["O(1)"]}],"的复杂度，在实际的","$L1b","中的表现也很好。"]}],"\n",["$","$L15","3260",{"id":"LFU","children":["LFU"]}],"\n",["$","p","3261",{"children":["LFU (Least Frequently Used) 最近最不频繁使用，缓存中被使用的次数最少的项会被优先剔除。它认为被用的越少的项越应该移除。"]}],"\n",["$","p","3262",{"children":["LFU 克服了 LRU 在大规模遍历时的缺点。但是容易导致旧数据的积累。同时新数据因为使用次数少容易反复被移出缓存导致长期无法积累跟大的使用次数。"]}],"\n",["$","$L17","3263",{"id":"实现-2","children":["实现"]}],"\n",["$","p","3267",{"children":["$L1c",["$","br","3265",{}],"\n为了维护相关的访问频次信息需要额外的数据结构。一种各操作 (增删查) 都为",["$","code","3266",{"children":["O(1)"]}],"的形式是使用两个双链表。其中一个保存访问频次，另一个用于保存某频次对应的节点。因为频次链表会经常有增删操作所以使用双链表。而保存某频次对应节点的链表也可以使用 HashMap 或者动态表。"]}],"\n",["$","pre","3347",{"className":"shiki github-light","style":{"backgroundColor":"#fff","color":"#24292e"},"tabindex":"0","children":[["$","code","3346",{"className":"language-go","children":[["$","span","3272",{"className":"line","children":[["$","span","3268",{"style":{"color":"#D73A49"},"children":["type"]}],["$","span","3269",{"style":{"color":"#6F42C1"},"children":[" CacheNode"]}],["$","span","3270",{"style":{"color":"#D73A49"},"children":[" struct"]}],["$","span","3271",{"style":{"color":"#24292E"},"children":[" {"]}]]}],"\n",["$","span","3275",{"className":"line","children":[["$","span","3273",{"style":{"color":"#24292E"},"children":["\tkey    "]}],["$","span","3274",{"style":{"color":"#D73A49"},"children":["int"]}]]}],"\n",["$","span","3278",{"className":"line","children":[["$","span","3276",{"style":{"color":"#24292E"},"children":["\tvalue  "]}],["$","span","3277",{"style":{"color":"#D73A49"},"children":["int"]}]]}],"\n",["$","span","3282",{"className":"line","children":[["$","span","3279",{"style":{"color":"#24292E"},"children":["\tprev   "]}],["$","span","3280",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3281",{"style":{"color":"#6F42C1"},"children":["CacheNode"]}]]}],"\n",["$","span","3286",{"className":"line","children":[["$","span","3283",{"style":{"color":"#24292E"},"children":["\tnext   "]}],["$","span","3284",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3285",{"style":{"color":"#6F42C1"},"children":["CacheNode"]}]]}],"\n",["$","span","3290",{"className":"line","children":[["$","span","3287",{"style":{"color":"#24292E"},"children":["\tparent "]}],["$","span","3288",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3289",{"style":{"color":"#6F42C1"},"children":["FreqNode"]}]]}],"\n",["$","span","3292",{"className":"line","children":[["$","span","3291",{"style":{"color":"#24292E"},"children":["}"]}]]}],"\n",["$","span","3293",{"className":"line","children":[]}],"\n",["$","span","3298",{"className":"line","children":[["$","span","3294",{"style":{"color":"#D73A49"},"children":["type"]}],["$","span","3295",{"style":{"color":"#6F42C1"},"children":[" FreqNode"]}],["$","span","3296",{"style":{"color":"#D73A49"},"children":[" struct"]}],["$","span","3297",{"style":{"color":"#24292E"},"children":[" {"]}]]}],"\n",["$","span","3301",{"className":"line","children":[["$","span","3299",{"style":{"color":"#24292E"},"children":["\tfreq "]}],["$","span","3300",{"style":{"color":"#D73A49"},"children":["int"]}]]}],"\n",["$","span","3305",{"className":"line","children":[["$","span","3302",{"style":{"color":"#24292E"},"children":["\thead "]}],["$","span","3303",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3304",{"style":{"color":"#6F42C1"},"children":["CacheNode"]}]]}],"\n",["$","span","3309",{"className":"line","children":[["$","span","3306",{"style":{"color":"#24292E"},"children":["\ttail "]}],["$","span","3307",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3308",{"style":{"color":"#6F42C1"},"children":["CacheNode"]}]]}],"\n",["$","span","3313",{"className":"line","children":[["$","span","3310",{"style":{"color":"#24292E"},"children":["\tprev "]}],["$","span","3311",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3312",{"style":{"color":"#6F42C1"},"children":["FreqNode"]}]]}],"\n",["$","span","3317",{"className":"line","children":[["$","span","3314",{"style":{"color":"#24292E"},"children":["\tnext "]}],["$","span","3315",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3316",{"style":{"color":"#6F42C1"},"children":["FreqNode"]}]]}],"\n",["$","span","3319",{"className":"line","children":[["$","span","3318",{"style":{"color":"#24292E"},"children":["}"]}]]}],"\n",["$","span","3320",{"className":"line","children":[]}],"\n",["$","span","3325",{"className":"line","children":[["$","span","3321",{"style":{"color":"#D73A49"},"children":["type"]}],["$","span","3322",{"style":{"color":"#6F42C1"},"children":[" LFUCache"]}],["$","span","3323",{"style":{"color":"#D73A49"},"children":[" struct"]}],["$","span","3324",{"style":{"color":"#24292E"},"children":[" {"]}]]}],"\n",["$","span","3328",{"className":"line","children":[["$","span","3326",{"style":{"color":"#24292E"},"children":["\tsize "]}],["$","span","3327",{"style":{"color":"#D73A49"},"children":["int"]}]]}],"\n",["$","span","3331",{"className":"line","children":[["$","span","3329",{"style":{"color":"#24292E"},"children":["\tcapacity "]}],["$","span","3330",{"style":{"color":"#D73A49"},"children":["int"]}]]}],"\n",["$","span","3339",{"className":"line","children":[["$","span","3332",{"style":{"color":"#24292E"},"children":["\tcache "]}],["$","span","3333",{"style":{"color":"#D73A49"},"children":["map"]}],["$","span","3334",{"style":{"color":"#24292E"},"children":["["]}],["$","span","3335",{"style":{"color":"#D73A49"},"children":["int"]}],["$","span","3336",{"style":{"color":"#24292E"},"children":["]"]}],["$","span","3337",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3338",{"style":{"color":"#6F42C1"},"children":["CacheNode"]}]]}],"\n",["$","span","3343",{"className":"line","children":[["$","span","3340",{"style":{"color":"#24292E"},"children":["\tlfuHead "]}],["$","span","3341",{"style":{"color":"#D73A49"},"children":["*"]}],["$","span","3342",{"style":{"color":"#6F42C1"},"children":["FreqNode"]}]]}],"\n",["$","span","3345",{"className":"line","children":[["$","span","3344",{"style":{"color":"#24292E"},"children":["}"]}]]}]]}]]}],"\n",["$","p","3349",{"children":[["$","$La",null,{"className":"m-img","id":"$undefined","alt":"lfu","style":"$undefined","loading":"lazy","src":"https://vip2.loli.io/2023/03/08/gI31FS8z5jx2CWp.png","width":956,"height":519,"placeholder":"blur","blurDataURL":"data:image/png;base64,iVBORw0KGgoAAAANSUhEUgAAAAUAAAADCAIAAADUVFKvAAAACXBIWXMAABJ0AAASdAHeZh94AAAAN0lEQVR4nGOIiYkRBQM+Pj5ra2uG////NzQ0+Pn5rVu3bvny5Qzfv39ft27d/Pnzr1279v//fwCqWhgfsDAWMwAAAABJRU5ErkJggg=="}]]}],"\n",["$","p","3351",{"children":["缓存保存一个使用次数为 0 的频次节点的指针。新项加入时，头插入到次数为 1 的频次节点，时间复杂度为",["$","code","3350",{"children":["O(1)"]}],"。"]}],"\n",["$","p","3352",{"children":["当某一个频次的节点 (除 0 以外) 所持有的缓存项个数为 0 时，该频次节点就会被移除。这样保证了 0 频次节点的下一个节点总是缓存中使用次数最少的。"]}],"\n",["$","p","3354",{"children":["此时，只要在频次节点中维护缓存项链表的尾指针，就知道了缓存中使用此是最少最老旧的缓存项。此番操作 (lfuHead.next.head) 的时间复杂度也是",["$","code","3353",{"children":["O(1)"]}]]}],"\n",["$","p","3356",{"children":["$L1d"]}],"\n",["$","$L15","3357",{"id":"ARC","children":["ARC"]}],"\n",["$","p","3361",{"children":["ARC (Adaptive replacement cache) 同时使用 LRU 和 LFU。通过动态调整 LRU，LFU 的容量达到自适应的效果。",["$","br","3358",{}],"\n缓存中除了 LRU 和 LFU 所需的数据结构外，额外增加了两条链表 LRU 和 LFU 各一个称为 Ghost List。",["$","br","3359",{}],"\n开始时缓存容量被平分 LRU 和 LFU 两部分。当新项加入时，先加入到 LRU 中。当缓存项被访问而 LFU 中没有时，加入到 LFU 中。",["$","br","3360",{}],"\n如果缓存项被移除则将它的 Key 加入到对应的 Ghost List 中。每当缓存不命中时，都会检查 Ghost List。假如 Ghost List 中含有当前不命中的 Key 则该 Ghost List 对应的缓存的容量应该增加。"]}],"\n",["$","$L15","3362",{"id":"参考文章","children":["参考文章"]}],"\n",["$","ul","3372",{"children":["\n",["$","li","3364",{"children":["$L1e"]}],"\n",["$","li","3366",{"children":["$L1f"]}],"\n",["$","li","3368",{"children":["$L20"]}],"\n",["$","li","3370",{"children":["$L21"]}],"\n",["$","li","3371",{"children":["Leetcode discuss"]}],"\n"]}],"\n"]}]
16:["$","a",null,{"href":"https://en.wikipedia.org/wiki/Cache_replacement_policies","children":["缓存算法有很多"],"target":"_blank","rel":"noopener noreferrer external nofollow"}]
18:["$","a",null,{"href":"https://leetcode.com/problems/lru-cache/","children":["Leetcode 上有 LRU Cache 的题目"],"target":"_blank","rel":"noopener noreferrer external nofollow"}]
19:["$","a",null,{"href":"https://github.com/fengkx/leetcode/blob/master/lru_cache/lru_cache.go","children":["完整实现"],"target":"_blank","rel":"noopener noreferrer external nofollow"}]
1a:["$","a",null,{"href":"https://github.com/dominictarr/hashlru#algorithm","children":["HashLRU"],"target":"_blank","rel":"noopener noreferrer external nofollow"}]
1b:["$","a",null,{"href":"https://github.com/dominictarr/bench-lru","children":["Benchmark"],"target":"_blank","rel":"noopener noreferrer external nofollow"}]
1c:["$","a",null,{"href":"https://leetcode.com/problems/lfu-cache/","children":["Leetcode 上有 LFU Cache 的题目"],"target":"_blank","rel":"noopener noreferrer external nofollow"}]
1d:["$","a",null,{"href":"https://github.com/fengkx/leetcode/blob/master/lfu_cache/lfu_cache.go","children":["完整实现"],"target":"_blank","rel":"noopener noreferrer external nofollow"}]
1e:["$","a",null,{"href":"https://en.wikipedia.org/wiki/Cache_replacement_policies","children":["Cache Replacement Policy Wiki"],"target":"_blank","rel":"noopener noreferrer external nofollow"}]
1f:["$","a",null,{"href":"https://github.com/dominictarr/hashlru#algorithm","children":["LFU Cache Wiki"],"target":"_blank","rel":"noopener noreferrer external nofollow"}]
20:["$","a",null,{"href":"http://dhruvbird.com/lfu.pdf","children":["An O(1) algorithm for implementing the LFU cache eviction scheme"],"target":"_blank","rel":"noopener noreferrer external nofollow"}]
21:["$","a",null,{"href":"https://github.com/dominictarr/hashlru#algorithm","children":["Hash LRU"],"target":"_blank","rel":"noopener noreferrer external nofollow"}]