lucene-java-3.5.0/lucene/contrib/facet/src/java/org/apache/lucene/util/collections/LRUHashMap.java

   1 package org.apache.lucene.util.collections;
   2
   3 import java.util.LinkedHashMap;
   4 import java.util.Map;
   5
   6 /**
   7  * Licensed to the Apache Software Foundation (ASF) under one or more
   8  * contributor license agreements.  See the NOTICE file distributed with
   9  * this work for additional information regarding copyright ownership.
  10  * The ASF licenses this file to You under the Apache License, Version 2.0
  11  * (the "License"); you may not use this file except in compliance with
  12  * the License.  You may obtain a copy of the License at
  13  *
  14  *     http://www.apache.org/licenses/LICENSE-2.0
  15  *
  16  * Unless required by applicable law or agreed to in writing, software
  17  * distributed under the License is distributed on an "AS IS" BASIS,
  18  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
  19  * See the License for the specific language governing permissions and
  20  * limitations under the License.
  21  */
  22
  23 /**
  24  * LRUHashMap is an extension of Java's HashMap, which has a bounded size();
  25  * When it reaches that size, each time a new element is added, the least
  26  * recently used (LRU) entry is removed.
  27  * <p>
  28  * Java makes it very easy to implement LRUHashMap - all its functionality is
  29  * already available from {@link java.util.LinkedHashMap}, and we just need to
  30  * configure that properly.
  31  * <p>
  32  * Note that like HashMap, LRUHashMap is unsynchronized, and the user MUST
  33  * synchronize the access to it if used from several threads. Moreover, while
  34  * with HashMap this is only a concern if one of the threads is modifies the
  35  * map, with LURHashMap every read is a modification (because the LRU order
  36  * needs to be remembered) so proper synchronization is always necessary.
  37  * <p>
  38  * With the usual synchronization mechanisms available to the user, this
  39  * unfortunately means that LRUHashMap will probably perform sub-optimally under
  40  * heavy contention: while one thread uses the hash table (reads or writes), any
  41  * other thread will be blocked from using it - or even just starting to use it
  42  * (e.g., calculating the hash function). A more efficient approach would be not
  43  * to use LinkedHashMap at all, but rather to use a non-locking (as much as
  44  * possible) thread-safe solution, something along the lines of
  45  * java.util.concurrent.ConcurrentHashMap (though that particular class does not
  46  * support the additional LRU semantics, which will need to be added separately
  47  * using a concurrent linked list or additional storage of timestamps (in an
  48  * array or inside the entry objects), or whatever).
  49  *
  50  * @lucene.experimental
  51  */
  52 public class LRUHashMap<K,V> extends LinkedHashMap<K,V> {
  53
  54   private int maxSize;
  55
  56   /**
  57    * Create a new hash map with a bounded size and with least recently
  58    * used entries removed.
  59    * @param maxSize
  60    *     the maximum size (in number of entries) to which the map can grow
  61    *     before the least recently used entries start being removed.<BR>
  62    *      Setting maxSize to a very large value, like
  63    *      {@link Integer#MAX_VALUE} is allowed, but is less efficient than
  64    *      using {@link java.util.HashMap} because our class needs
  65    *      to keep track of the use order (via an additional doubly-linked
  66    *      list) which is not used when the map's size is always below the
  67    *      maximum size.
  68    */
  69   public LRUHashMap(int maxSize) {
  70     super(16, 0.75f, true);
  71     this.maxSize = maxSize;
  72   }
  73
  74   /**
  75    * Return the max size
  76    */
  77   public int getMaxSize() {
  78     return maxSize;
  79   }
  80
  81   /**
  82    * setMaxSize() allows changing the map's maximal number of elements
  83    * which was defined at construction time.
  84    * <P>
  85    * Note that if the map is already larger than maxSize, the current
  86    * implementation does not shrink it (by removing the oldest elements);
  87    * Rather, the map remains in its current size as new elements are
  88    * added, and will only start shrinking (until settling again on the
  89    * give maxSize) if existing elements are explicitly deleted.
  90    */
  91   public void setMaxSize(int maxSize) {
  92     this.maxSize = maxSize;
  93   }
  94
  95   // We override LinkedHashMap's removeEldestEntry() method. This method
  96   // is called every time a new entry is added, and if we return true
  97   // here, the eldest element will be deleted automatically. In our case,
  98   // we return true if the size of the map grew beyond our limit - ignoring
  99   // what is that eldest element that we'll be deleting.
 100   @Override
 101   protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
 102     return size() > maxSize;
 103   }
 104
 105 }