js 簡單實作 LRU

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

<code>/* ======================================== LRU 最近最少使用 ======================================== */</code>

<code>function</code> <code>LRUCache(limit){</code>

<code>    </code><code>limit = limit||10;</code>

<code>    </code><code>var</code> <code>_store = [];</code>

<code>    </code><code>var</code> <code>index = {};</code>

<code>    </code><code>this</code><code>.get = </code><code>function</code><code>(key){</code>

<code>        </code><code>var</code> <code>ind = index[key];</code>

<code>        </code> 

<code>        </code><code>if</code><code>(_store[ind]==</code><code>null</code><code>){ </code><code>// 未命中</code>

<code>            </code><code>return</code> <code>null</code><code>;</code>

<code>        </code><code>}          </code>

<code>            </code> 

<code>        </code><code>var</code> <code>newArr = _store.splice(0,ind+1);</code>

<code>        </code><code>var</code> <code>result = newArr.pop();</code>

<code>        </code><code>_store = newArr.concat(_store);</code>

<code>        </code><code>_store.unshift(result);</code>

<code>        </code><code>for</code><code>(</code><code>var</code> <code>k </code><code>in</code> <code>index){</code>

<code>            </code><code>var</code> <code>i = index[k];</code>

<code>            </code><code>if</code><code>(i==ind){</code>

<code>                </code><code>index[k] = 0;</code>

<code>            </code><code>}</code><code>else</code> <code>if</code><code>(i&lt;ind){</code>

<code>                </code><code>index[k] = ++index[k];</code>

<code>            </code><code>}</code>

<code>        </code><code>}</code>

<code>        </code><code>return</code> <code>result;</code>

<code>    </code><code>};</code>

<code>    </code> 

<code>    </code><code>this</code><code>.set = </code><code>function</code><code>(key,value){</code>

<code>        </code><code>if</code><code>(_store.length&gt;=limit){</code>

<code>            </code><code>_store.pop();      </code>

<code>            </code><code>index[k] = index[k]+1;</code>

<code>        </code><code>_store.unshift(value);</code>

<code>        </code><code>index[key] = 0;;</code>

<code>    </code><code>this</code><code>.list = </code><code>function</code><code>(){</code>

<code>        </code><code>console.log(_store);</code>

<code>    </code><code>};     </code>

<code>}</code>

 本文轉自 antlove 51CTO部落格，原文連結:http://blog.51cto.com/antlove/1978115