Change Dir

先知cd——热爱生活是一切艺术的开始

统计

留言簿(18)

积分与排名

“牛”们的博客

各个公司技术

我的链接

淘宝技术

阅读排行榜

评论排行榜

分享一个LRUMap的实现——来自apache common-collections框架

今天主要分享一个LRUmap的实现。我们经常会用到需要使用map来保存数据的时候,由于map本身的映射高效,最适合做随机读取的存储结构。当然LRU算法是在有限大小的存储集合下的一种调度算法,即最近最少使用。对于一个给定大小限制的容器,如何分配资源就涉及到调度,而LRU就是一种经典的调度了,在容器中定义一个最后使用时间,当容器满时,再来新的元素,那么淘汰最近最少使用的元素,把新的元素替换之,这是最直接的思想。

apache common-collections框架里有一个LRUMap的实现,其继承自抽象的linkedmap和抽象的hashmap。下面给出一段测试代码,来看看LRU的直观效果:

   1: public static void main(String[] args) {
   2:         // TODO Auto-generated method stub
   3:         LRUMap map = new LRUMap(3);
   4:         map.put("1", 1);
   5:         map.put("2", 2);
   6:         //map.get("1");
   7:         map.put("3", 3);
   8:         map.put("4", 4);
   9:         
  10:         for(Iterator it = map.entrySet().iterator();it.hasNext();){
  11:             System.out.println(it.next());
  12:         }
  13:     }

使用的版本是common-collections3.2.1,直接执行,结果会显示

2=2

3=3

4=4

如果把第6行的注释打开,那么执行结果会是

1=1

3=3

4=4

这样就符合了LRU的原理,在调用了一次get后,1对应的数据不再是最近最少使用。

具体实现也颇有趣,LRUmap继承linkedmap,维护了一个linked list来保存内部数据

   1: /** Header in the linked list */
   2:     protected transient LinkEntry header;

linkentry又是一个循环双向的链表,且继承了hashentry,hashentry虽然也是commons框架自己实现,但是与jdk的实现同理,也是利用链接桶来预防冲突

   1: protected static class LinkEntry extends HashEntry {
   2:         /** The entry before this one in the order */
   3:         protected LinkEntry before;
   4:         /** The entry after this one in the order */
   5:         protected LinkEntry after;
   6:         
   7:         /**
   8:          * Constructs a new entry.
   9:          * 
  10:          * @param next  the next entry in the hash bucket sequence
  11:          * @param hashCode  the hash code
  12:          * @param key  the key
  13:          * @param value  the value
  14:          */
  15:         protected LinkEntry(HashEntry next, int hashCode, Object key, Object value) {
  16:             super(next, hashCode, key, value);
  17:         }
  18:     }

当进行put操作时,LRUMap会调用abstracthashmap的put方法,与传统一样,计算hashcode,在对应的hashcode桶定位index,然后做一个addmapping操作。本来在抽象类中的addmapping是传统的,等同于jdk中hashmap的addentry,但是LRUMap这里重写了addmapping,主要进行了map是否已满的判断,如果map未满,那么直接插入,否则,LRU将会定位到将被替换掉的entry的位置,然后做一个reuseMapping的操作,将该替换掉的entryremove,将新加进来的entry放到队尾。这样就完成了put操作。

进行get操作时,首先依据hashmap的原则找到entry,在返回value之前进行了LRU调整moveToMRU操作。该操作判断这个entry是否是队尾,如果是,那么什么都不用干,它就是最近被使用的,如果不是,那么调整它到队尾。

全部的源码见下:

   1: /*
   2:  *  Licensed to the Apache Software Foundation (ASF) under one or more
   3:  *  contributor license agreements.  See the NOTICE file distributed with
   4:  *  this work for additional information regarding copyright ownership.
   5:  *  The ASF licenses this file to You under the Apache License, Version 2.0
   6:  *  (the "License"); you may not use this file except in compliance with
   7:  *  the License.  You may obtain a copy of the License at
   8:  *
   9:  *      http://www.apache.org/licenses/LICENSE-2.0
  10:  *
  11:  *  Unless required by applicable law or agreed to in writing, software
  12:  *  distributed under the License is distributed on an "AS IS" BASIS,
  13:  *  WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  14:  *  See the License for the specific language governing permissions and
  15:  *  limitations under the License.
  16:  */
  17: package org.apache.commons.collections.map;
  18:  
  19: import java.io.IOException;
  20: import java.io.ObjectInputStream;
  21: import java.io.ObjectOutputStream;
  22: import java.io.Serializable;
  23: import java.util.Map;
  24:  
  25: import org.apache.commons.collections.BoundedMap;
  26:  
  27: /**
  28:  * A <code>Map</code> implementation with a fixed maximum size which removes
  29:  * the least recently used entry if an entry is added when full.
  30:  * <p>
  31:  * The least recently used algorithm works on the get and put operations only.
  32:  * Iteration of any kind, including setting the value by iteration, does not
  33:  * change the order. Queries such as containsKey and containsValue or access
  34:  * via views also do not change the order.
  35:  * <p>
  36:  * The map implements <code>OrderedMap</code> and entries may be queried using
  37:  * the bidirectional <code>OrderedMapIterator</code>. The order returned is
  38:  * least recently used to most recently used. Iterators from map views can 
  39:  * also be cast to <code>OrderedIterator</code> if required.
  40:  * <p>
  41:  * All the available iterators can be reset back to the start by casting to
  42:  * <code>ResettableIterator</code> and calling <code>reset()</code>.
  43:  * <p>
  44:  * <strong>Note that LRUMap is not synchronized and is not thread-safe.</strong>
  45:  * If you wish to use this map from multiple threads concurrently, you must use
  46:  * appropriate synchronization. The simplest approach is to wrap this map
  47:  * using {@link java.util.Collections#synchronizedMap(Map)}. This class may throw 
  48:  * <code>NullPointerException</code>'s when accessed by concurrent threads.
  49:  *
  50:  * @since Commons Collections 3.0 (previously in main package v1.0)
  51:  * @version $Revision: 646777 $ $Date: 2008-04-10 13:33:15 +0100 (Thu, 10 Apr 2008) $
  52:  *
  53:  * @author James Strachan
  54:  * @author Morgan Delagrange
  55:  * @author Stephen Colebourne
  56:  * @author Mike Pettypiece
  57:  * @author Mario Ivankovits
  58:  */
  59: public class LRUMap
  60:         extends AbstractLinkedMap implements BoundedMap, Serializable, Cloneable {
  61:     
  62:     /** Serialisation version */
  63:     private static final long serialVersionUID = -612114643488955218L;
  64:     /** Default maximum size */
  65:     protected static final int DEFAULT_MAX_SIZE = 100;
  66:     
  67:     /** Maximum size */
  68:     private transient int maxSize;
  69:     /** Scan behaviour */
  70:     private boolean scanUntilRemovable;
  71:  
  72:     /**
  73:      * Constructs a new empty map with a maximum size of 100.
  74:      */
  75:     public LRUMap() {
  76:         this(DEFAULT_MAX_SIZE, DEFAULT_LOAD_FACTOR, false);
  77:     }
  78:  
  79:     /**
  80:      * Constructs a new, empty map with the specified maximum size.
  81:      *
  82:      * @param maxSize  the maximum size of the map
  83:      * @throws IllegalArgumentException if the maximum size is less than one
  84:      */
  85:     public LRUMap(int maxSize) {
  86:         this(maxSize, DEFAULT_LOAD_FACTOR);
  87:     }
  88:  
  89:     /**
  90:      * Constructs a new, empty map with the specified maximum size.
  91:      *
  92:      * @param maxSize  the maximum size of the map
  93:      * @param scanUntilRemovable  scan until a removeable entry is found, default false
  94:      * @throws IllegalArgumentException if the maximum size is less than one
  95:      * @since Commons Collections 3.1
  96:      */
  97:     public LRUMap(int maxSize, boolean scanUntilRemovable) {
  98:         this(maxSize, DEFAULT_LOAD_FACTOR, scanUntilRemovable);
  99:     }
 100:  
 101:     /**
 102:      * Constructs a new, empty map with the specified initial capacity and
 103:      * load factor. 
 104:      *
 105:      * @param maxSize  the maximum size of the map, -1 for no limit,
 106:      * @param loadFactor  the load factor
 107:      * @throws IllegalArgumentException if the maximum size is less than one
 108:      * @throws IllegalArgumentException if the load factor is less than zero
 109:      */
 110:     public LRUMap(int maxSize, float loadFactor) {
 111:         this(maxSize, loadFactor, false);
 112:     }
 113:  
 114:     /**
 115:      * Constructs a new, empty map with the specified initial capacity and
 116:      * load factor.
 117:      *
 118:      * @param maxSize  the maximum size of the map, -1 for no limit,
 119:      * @param loadFactor  the load factor
 120:      * @param scanUntilRemovable  scan until a removeable entry is found, default false
 121:      * @throws IllegalArgumentException if the maximum size is less than one
 122:      * @throws IllegalArgumentException if the load factor is less than zero
 123:      * @since Commons Collections 3.1
 124:      */
 125:     public LRUMap(int maxSize, float loadFactor, boolean scanUntilRemovable) {
 126:         super((maxSize < 1 ? DEFAULT_CAPACITY : maxSize), loadFactor);
 127:         if (maxSize < 1) {
 128:             throw new IllegalArgumentException("LRUMap max size must be greater than 0");
 129:         }
 130:         this.maxSize = maxSize;
 131:         this.scanUntilRemovable = scanUntilRemovable;
 132:     }
 133:  
 134:     /**
 135:      * Constructor copying elements from another map.
 136:      * <p>
 137:      * The maximum size is set from the map's size.
 138:      *
 139:      * @param map  the map to copy
 140:      * @throws NullPointerException if the map is null
 141:      * @throws IllegalArgumentException if the map is empty
 142:      */
 143:     public LRUMap(Map map) {
 144:         this(map, false);
 145:     }
 146:  
 147:     /**
 148:      * Constructor copying elements from another map.
 149:      * <p/>
 150:      * The maximum size is set from the map's size.
 151:      *
 152:      * @param map  the map to copy
 153:      * @param scanUntilRemovable  scan until a removeable entry is found, default false
 154:      * @throws NullPointerException if the map is null
 155:      * @throws IllegalArgumentException if the map is empty
 156:      * @since Commons Collections 3.1
 157:      */
 158:     public LRUMap(Map map, boolean scanUntilRemovable) {
 159:         this(map.size(), DEFAULT_LOAD_FACTOR, scanUntilRemovable);
 160:         putAll(map);
 161:     }
 162:  
 163:     //-----------------------------------------------------------------------
 164:     /**
 165:      * Gets the value mapped to the key specified.
 166:      * <p>
 167:      * This operation changes the position of the key in the map to the
 168:      * most recently used position (first).
 169:      * 
 170:      * @param key  the key
 171:      * @return the mapped value, null if no match
 172:      */
 173:     public Object get(Object key) {
 174:         LinkEntry entry = (LinkEntry) getEntry(key);
 175:         if (entry == null) {
 176:             return null;
 177:         }
 178:         moveToMRU(entry);
 179:         return entry.getValue();
 180:     }
 181:  
 182:     //-----------------------------------------------------------------------
 183:     /**
 184:      * Moves an entry to the MRU position at the end of the list.
 185:      * <p>
 186:      * This implementation moves the updated entry to the end of the list.
 187:      * 
 188:      * @param entry  the entry to update
 189:      */
 190:     protected void moveToMRU(LinkEntry entry) {
 191:         if (entry.after != header) {
 192:             modCount++;
 193:             // remove
 194:             entry.before.after = entry.after;
 195:             entry.after.before = entry.before;
 196:             // add first
 197:             entry.after = header;
 198:             entry.before = header.before;
 199:             header.before.after = entry;
 200:             header.before = entry;
 201:         } else if (entry == header) {
 202:             throw new IllegalStateException("Can't move header to MRU" +
 203:                 " (please report this to commons-dev@jakarta.apache.org)");
 204:         }
 205:     }
 206:     
 207:     /**
 208:      * Updates an existing key-value mapping.
 209:      * <p>
 210:      * This implementation moves the updated entry to the top of the list
 211:      * using {@link #moveToMRU(AbstractLinkedMap.LinkEntry)}.
 212:      * 
 213:      * @param entry  the entry to update
 214:      * @param newValue  the new value to store
 215:      */
 216:     protected void updateEntry(HashEntry entry, Object newValue) {
 217:         moveToMRU((LinkEntry) entry);  // handles modCount
 218:         entry.setValue(newValue);
 219:     }
 220:     
 221:     /**
 222:      * Adds a new key-value mapping into this map.
 223:      * <p>
 224:      * This implementation checks the LRU size and determines whether to
 225:      * discard an entry or not using {@link #removeLRU(AbstractLinkedMap.LinkEntry)}.
 226:      * <p>
 227:      * From Commons Collections 3.1 this method uses {@link #isFull()} rather
 228:      * than accessing <code>size</code> and <code>maxSize</code> directly.
 229:      * It also handles the scanUntilRemovable functionality.
 230:      * 
 231:      * @param hashIndex  the index into the data array to store at
 232:      * @param hashCode  the hash code of the key to add
 233:      * @param key  the key to add
 234:      * @param value  the value to add
 235:      */
 236:     protected void addMapping(int hashIndex, int hashCode, Object key, Object value) {
 237:         if (isFull()) {
 238:             LinkEntry reuse = header.after;
 239:             boolean removeLRUEntry = false;
 240:             if (scanUntilRemovable) {
 241:                 while (reuse != header && reuse != null) {
 242:                     if (removeLRU(reuse)) {
 243:                         removeLRUEntry = true;
 244:                         break;
 245:                     }
 246:                     reuse = reuse.after;
 247:                 }
 248:                 if (reuse == null) {
 249:                     throw new IllegalStateException(
 250:                         "Entry.after=null, header.after" + header.after + " header.before" + header.before +
 251:                         " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
 252:                         " Please check that your keys are immutable, and that you have used synchronization properly." +
 253:                         " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
 254:                 }
 255:             } else {
 256:                 removeLRUEntry = removeLRU(reuse);
 257:             }
 258:             
 259:             if (removeLRUEntry) {
 260:                 if (reuse == null) {
 261:                     throw new IllegalStateException(
 262:                         "reuse=null, header.after=" + header.after + " header.before" + header.before +
 263:                         " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
 264:                         " Please check that your keys are immutable, and that you have used synchronization properly." +
 265:                         " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
 266:                 }
 267:                 reuseMapping(reuse, hashIndex, hashCode, key, value);
 268:             } else {
 269:                 super.addMapping(hashIndex, hashCode, key, value);
 270:             }
 271:         } else {
 272:             super.addMapping(hashIndex, hashCode, key, value);
 273:         }
 274:     }
 275:     
 276:     /**
 277:      * Reuses an entry by removing it and moving it to a new place in the map.
 278:      * <p>
 279:      * This method uses {@link #removeEntry}, {@link #reuseEntry} and {@link #addEntry}.
 280:      * 
 281:      * @param entry  the entry to reuse
 282:      * @param hashIndex  the index into the data array to store at
 283:      * @param hashCode  the hash code of the key to add
 284:      * @param key  the key to add
 285:      * @param value  the value to add
 286:      */
 287:     protected void reuseMapping(LinkEntry entry, int hashIndex, int hashCode, Object key, Object value) {
 288:         // find the entry before the entry specified in the hash table
 289:         // remember that the parameters (except the first) refer to the new entry,
 290:         // not the old one
 291:         try {
 292:             int removeIndex = hashIndex(entry.hashCode, data.length);
 293:             HashEntry[] tmp = data;  // may protect against some sync issues
 294:             HashEntry loop = tmp[removeIndex];
 295:             HashEntry previous = null;
 296:             while (loop != entry && loop != null) {
 297:                 previous = loop;
 298:                 loop = loop.next;
 299:             }
 300:             if (loop == null) {
 301:                 throw new IllegalStateException(
 302:                     "Entry.next=null, data[removeIndex]=" + data[removeIndex] + " previous=" + previous +
 303:                     " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
 304:                     " Please check that your keys are immutable, and that you have used synchronization properly." +
 305:                     " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
 306:             }
 307:             
 308:             // reuse the entry
 309:             modCount++;
 310:             removeEntry(entry, removeIndex, previous);
 311:             reuseEntry(entry, hashIndex, hashCode, key, value);
 312:             addEntry(entry, hashIndex);
 313:         } catch (NullPointerException ex) {
 314:             throw new IllegalStateException(
 315:                     "NPE, entry=" + entry + " entryIsHeader=" + (entry==header) +
 316:                     " key=" + key + " value=" + value + " size=" + size + " maxSize=" + maxSize +
 317:                     " Please check that your keys are immutable, and that you have used synchronization properly." +
 318:                     " If so, then please report this to commons-dev@jakarta.apache.org as a bug.");
 319:         }
 320:     }
 321:     
 322:     /**
 323:      * Subclass method to control removal of the least recently used entry from the map.
 324:      * <p>
 325:      * This method exists for subclasses to override. A subclass may wish to
 326:      * provide cleanup of resources when an entry is removed. For example:
 327:      * <pre>
 328:      * protected boolean removeLRU(LinkEntry entry) {
 329:      *   releaseResources(entry.getValue());  // release resources held by entry
 330:      *   return true;  // actually delete entry
 331:      * }
 332:      * </pre>
 333:      * <p>
 334:      * Alternatively, a subclass may choose to not remove the entry or selectively
 335:      * keep certain LRU entries. For example:
 336:      * <pre>
 337:      * protected boolean removeLRU(LinkEntry entry) {
 338:      *   if (entry.getKey().toString().startsWith("System.")) {
 339:      *     return false;  // entry not removed from LRUMap
 340:      *   } else {
 341:      *     return true;  // actually delete entry
 342:      *   }
 343:      * }
 344:      * </pre>
 345:      * The effect of returning false is dependent on the scanUntilRemovable flag.
 346:      * If the flag is true, the next LRU entry will be passed to this method and so on
 347:      * until one returns false and is removed, or every entry in the map has been passed.
 348:      * If the scanUntilRemovable flag is false, the map will exceed the maximum size.
 349:      * <p>
 350:      * NOTE: Commons Collections 3.0 passed the wrong entry to this method.
 351:      * This is fixed in version 3.1 onwards.
 352:      * 
 353:      * @param entry  the entry to be removed
 354:      */
 355:     protected boolean removeLRU(LinkEntry entry) {
 356:         return true;
 357:     }
 358:  
 359:     //-----------------------------------------------------------------------
 360:     /**
 361:      * Returns true if this map is full and no new mappings can be added.
 362:      *
 363:      * @return <code>true</code> if the map is full
 364:      */
 365:     public boolean isFull() {
 366:         return (size >= maxSize);
 367:     }
 368:  
 369:     /**
 370:      * Gets the maximum size of the map (the bound).
 371:      *
 372:      * @return the maximum number of elements the map can hold
 373:      */
 374:     public int maxSize() {
 375:         return maxSize;
 376:     }
 377:  
 378:     /**
 379:      * Whether this LRUMap will scan until a removable entry is found when the
 380:      * map is full.
 381:      *
 382:      * @return true if this map scans
 383:      * @since Commons Collections 3.1
 384:      */
 385:     public boolean isScanUntilRemovable() {
 386:         return scanUntilRemovable;
 387:     }
 388:  
 389:     //-----------------------------------------------------------------------
 390:     /**
 391:      * Clones the map without cloning the keys or values.
 392:      *
 393:      * @return a shallow clone
 394:      */
 395:     public Object clone() {
 396:         return super.clone();
 397:     }
 398:     
 399:     /**
 400:      * Write the map out using a custom routine.
 401:      */
 402:     private void writeObject(ObjectOutputStream out) throws IOException {
 403:         out.defaultWriteObject();
 404:         doWriteObject(out);
 405:     }
 406:  
 407:     /**
 408:      * Read the map in using a custom routine.
 409:      */
 410:     private void readObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 411:         in.defaultReadObject();
 412:         doReadObject(in);
 413:     }
 414:     
 415:     /**
 416:      * Writes the data necessary for <code>put()</code> to work in deserialization.
 417:      */
 418:     protected void doWriteObject(ObjectOutputStream out) throws IOException {
 419:         out.writeInt(maxSize);
 420:         super.doWriteObject(out);
 421:     }
 422:  
 423:     /**
 424:      * Reads the data necessary for <code>put()</code> to work in the superclass.
 425:      */
 426:     protected void doReadObject(ObjectInputStream in) throws IOException, ClassNotFoundException {
 427:         maxSize = in.readInt();
 428:         super.doReadObject(in);
 429:     }
 430:     
 431: }

部分操作需要追溯其父类代码,这里就不贴了,有兴趣的朋友可以直接到源码阅读。

LRUMap对于构建缓存或者连接池之类的技术经常用到,common-collections框架给了现成的实现,大家在不需要修改的情况下,完全可以不必reinvent the wheel,直接用,好用且稳定。

posted on 2012-05-31 13:16 changedi 阅读(2627) 评论(1)  编辑  收藏 所属分类: Java技术好代码分享

评论

# re: 分享一个LRUMap的实现&mdash;&mdash;来自apache common-collections框架 2012-06-02 10:53 工业辅料

网页设计也涉及到框架的哈  回复  更多评论   


只有注册用户登录后才能发表评论。


网站导航: