有备无患：浏览器端缓存（基于 jQuery）

最近在翻《Ajax 设计模式》，所以想把其中的一部分模式实现出来练手 jQuery，今天写了一个简单的引入 LRU 算法的浏览器端缓存（Browser Side Cache）。

浏览器端缓存用来保留服务器返回的查询结果。这种缓存是一个 Javascript 里类似映射的对象，存储成对的查询结果；查询是缓存的键（Key），服务器返回的结果是缓存的值（Value）。因此，每当浏览器需要查询服务器时，先检查缓存。如果该查询是缓存中的一个键，则与键对应的值将被当作结果，而不必再向服务器查询。

LRU （Least Recently Used）是将存储在缓存中的自上一次获取之后，最长时间未被使用的项目（Item）丢弃的一种算法。可以用两个数组（Array）来实现，其一是用来存储查询结果的键值对（Key-Value Pairs），其二是一个先进先出（FIFO）的队列，每一个新项目被塞入队列的尾部，并随着后续项目的跟进，逐渐逼近队列的头部。当队列全满时，每次向尾部塞入一个新项目，就要从头部弹出一个旧项目。而每当一个项目被缓存查询时，它会被送回到队列的尾部，这样可以确保最长时间未被使用的项目总是在开头处。

另外，还有一种常用的缓存算法，LFU （Least Frequently Used），它将自上一次获取后最少被使用的项目丢弃。

顺便一说，下面贴出的代码是由代码发芽网生产的纯 HTML。代码发芽网是一个“无需插件支持 Blog 代码高亮，支持近百种编程语言，多种配色主题支持，代码版本管理”的代码片段管理网站。因为不是由 Javascript 脚本来高亮处理，所以在 feed 里也一样可以看到效果，这一点很赞。不过，由于用处不大的 id 和 class 也包含在生成的 HTML 里，所以体积偏大。比如说下面这段代码，在删除了多余的 id 和 class，套上代码专用的 pre 和 code 标签，并将   还原成空格之后，体积可以缩小一半仅17KB（原来35KB），更适合 blog 来贴代码。

cache.js

01 function Cache(size) {
02     /* A browser side LRU cache 
03      * Author: Wu Yuntao <http://luliban.com/blog/>
04      * License: GPLv3
05      *
06      * Usage:
07      * var cache = new Cache(10);   // create a new cache object
08      * cache.put('w', 'wiki');      // put an item into cache
09      * cache.get('w');              // get the value of item with key
10      * cache.remove('w');           // remove an item with specified key
11      * cache.initialize()           // re-initialize the cache
12      * cache.size(10)               // resize the cache
13      */
14     this.initialize(size);
15 }
16 
17 Cache.prototype = {
18     initialize: function(size) {
19         /* Initialize cache.
20          * ``size`` is the number of maxmium items this cache should hold.
21          * Default is maxium integer.
22          */
23         this._keys = new Array();
24         this._items = new Array();
25         this._size = size || this._size || Number.MAX_VALUE;
26     },
27 
28     is_empty: function() {
29         /* Check if cache is empty
30          */
31         return (this._keys.length == 0 && this._items.length == 0);
32     },
33 
34     size: function(size) {
35         /* Resize cache if ``size`` is specified, or return accual size of cache.
36          */
37         if (typeof size == 'undefined') return this._keys.length;
38         return this._size = size;
39     },
40 
41     put: function(key, value) {
42         /* Put a new item into cache, if the size of cache reaches limit,
43          * cache will remove the least recently used (LRU) automatically.
44          * ``key`` of an item should be a string.
45          * ``value`` of an item could be anything, string, array or object.
46          * If ``value`` is not defined, returns null.
47          */
48         if (typeof value != 'undefined') {
49             this._keys.push(key);
50             this._items[key] = value;
51 
52             if (this._keys.length > this._size) {
53                 this.remove_least();
54             }
55         }
56         return value;
57     },
58 
59     get: function(key) {
60         /* Retrieve an item by its key and move it to the tail of cache.
61          * If the item of ``key`` does not exist, returns null.
62          */
63         if (typeof this._items[key] == 'undefined') return null;
64         var used_key = this._remove_key(key);
65         this._keys.push(used_key);
66         return this._items[key];
67     },
68 
69     remove_least: function() {
70         /* Manually remove the least recently used item. */
71         if (!this.is_empty()) this.remove(this._keys[0]);
72     },
73 
74     remove: function(key) {
75         /* Remove an item by its key.
76          * If the item of ``key`` does not exist, returns null.
77          */
78         if (typeof this._items[key] == 'undefined') return null;
79         this._remove_key(key);
80         return this._remove_value(key);
81     },
82 
83     _remove_key: function(key) {
84         /* Remove the ``key`` in ``this._keys``.
85          */
86         var i = $.inArray(key, this._keys);
87         return this._keys.splice(i, 1);
88     },
89 
90     _remove_value: function(key) {
91         /* Remove the item in ``this._items``. */
92         var value = this._items[key];
93         delete this._items[key];
94         return value;
95     }
96 
97 };