從HashMap中刪除最舊的對象以達到一定的大小？

Question

我有一個Java中的hashmap，我需要限制的大小（50000的順序）。但我應該只刪除最舊的項目。該項目的時間戳存儲在輸入對象的字段：

Map<String, MyModel> snapshot = new HashMap<>(); 

和

public class MyModel { 
    private ZonedDateTime createdAt; 
    // other fields... 
} 

我也該時間戳將它們插入到地圖中的順序。

什麼是最有效的方法來完成這種刪除最舊的條目？請注意，時間的「閾值」是未知的，只有Map所需的最終大小。

Answer 1

HashMap沒有「最老」的任何一個列表更好，它沒有「第一」，它有no order。

在另一方面，一個LinkedHashMap是專爲正是這一點，它維護的條目之間的雙向鏈表所以讓他們在插入順序，它也提供了一個removeEldestEntry方法：

public static void main(final String args[]) throws Exception { 
    final int maxSize = 4; 
    final LinkedHashMap<String, String> cache = new LinkedHashMap<String, String>() { 
     @Override 
     protected boolean removeEldestEntry(final Map.Entry eldest) { 
      return size() > maxSize; 
     } 
    }; 

    cache.put("A", "A"); 
    System.out.println(cache); 
    cache.put("B", "A"); 
    System.out.println(cache); 
    cache.put("C", "A"); 
    System.out.println(cache); 
    cache.put("D", "A"); 
    System.out.println(cache); 
    cache.put("E", "A"); 
    System.out.println(cache); 
    cache.put("F", "A"); 
    System.out.println(cache); 
    cache.put("G", "A"); 
} 

輸出：

{A=A} 
{A=A, B=A} 
{A=A, B=A, C=A} 
{A=A, B=A, C=A, D=A} 
{B=A, C=A, D=A, E=A} 
{C=A, D=A, E=A, F=A} 

---

大打擂臺

請注意，此實現不是​​。如果多個線程同時訪問鏈接的哈希映射，並且至少有一個線程在結構上修改了映射，則它必須是​​。這一般通過synchronizing在一些自然地封裝地圖的對象上實現。如果不存在這樣的對象，則應使用Collections.synchronizedMap方法「映射」地圖。這是在創建時，這樣做可以防止意外的不同步訪問地圖：

Map m = Collections.synchronizedMap(new LinkedHashMap(...));

_{LinkedHashMap JavaDoc}

Answer 2

簡單地說：那麼一個HashMap不會。除了顯而易見的：你已經迭代所有的值，檢查屬性;然後決定您打算刪除哪些鍵。

換句話說：一個HashMap只有那個一個責任：將鍵映射到值。它不關心插入順序，插入時間或訪問密鑰的頻率。從這個意義上說：你應該考慮使用其他類型的Map接口的實現。

一種替代方法是使用TreeSet和客戶比較器，它們根據這些時間戳自動排序。

但要記住：只有2米在計算機科學堅硬的東西：

1. 命名
2. 緩存失效

Answer 3

這可能是最簡單的只是字符串對象添加到一個列表，只要你把東西放在地圖上。那麼你可以這樣做：

while(map.size()>50000){ 
    map.remove(list.get(0)) 
    list.remove(0); 
} 

這是有效的，因爲你實際上並不關心時間，只是順序。

隊列會比在這方面，你並不需要比接近和移出第一要素

Answer 4

我已經修改了LruCache類，從Android框架，這樣做。

這裏是完整的代碼。

import java.util.LinkedHashMap; 
import java.util.Map; 

public class RemoveOldHashMap<K, V> { 
    private final LinkedHashMap<K, V> map; 
    /** Size of this cache in units. Not necessarily the number of elements. */ 
    private int size; 
    private int maxSize; 
    private int putCount; 
    private int createCount; 
    private int evictionCount; 
    private int hitCount; 
    private int missCount; 
    /** 
    * @param maxSize for caches that do not override {@link #sizeOf}, this is 
    *  the maximum number of entries in the cache. For all other caches, 
    *  this is the maximum sum of the sizes of the entries in this cache. 
    */ 
    public RemoveOldHashMap(int maxSize) { 
     if (maxSize <= 0) { 
      throw new IllegalArgumentException("maxSize <= 0"); 
     } 
     this.maxSize = maxSize; 
     this.map = new LinkedHashMap<K, V>(0, 0.75f, false); // false for "interaction order" 
    } 
    /** 
    * Returns the value for {@code key} if it exists in the cache or can be 
    * created by {@code #create}. If a value was returned, it is moved to the 
    * head of the queue. This returns null if a value is not cached and cannot 
    * be created. 
    */ 
    public synchronized final V get(K key) { 
     if (key == null) { 
      throw new NullPointerException("key == null"); 
     } 

     for (K k : map.keySet()) { 
      System.out.println("k = " + k); 
     } 

     V result = map.get(key); 

     for (K k : map.keySet()) { 
      System.out.println("k = " + k); 
     } 

     if (result != null) { 
      hitCount++; 
      return result; 
     } 
     missCount++; 
     // TODO: release the lock while calling this potentially slow user code 
     result = create(key); 
     if (result != null) { 
      createCount++; 
      size += safeSizeOf(key, result); 
      map.put(key, result); 
      trimToSize(maxSize); 
     } 
     return result; 
    } 
    /** 
    * Caches {@code value} for {@code key}. The value is moved to the head of 
    * the queue. 
    * 
    * @return the previous value mapped by {@code key}. Although that entry is 
    *  no longer cached, it has not been passed to {@link #entryEvicted}. 
    */ 
    public synchronized final V put(K key, V value) { 
     if (key == null || value == null) { 
      throw new NullPointerException("key == null || value == null"); 
     } 
     putCount++; 
     size += safeSizeOf(key, value); 
     V previous = map.put(key, value); 
     if (previous != null) { 
      size -= safeSizeOf(key, previous); 
     } 
     trimToSize(maxSize); 
     return previous; 
    } 
    private void trimToSize(int maxSize) { 
     while (size > maxSize && !map.isEmpty()) { 
      Map.Entry<K, V> toEvict = map.entrySet().iterator().next(); 
      if (toEvict == null) { 
       break; // map is empty; if size is not 0 then throw an error below 
      } 
      K key = toEvict.getKey(); 
      V value = toEvict.getValue(); 
      map.remove(key); 
      size -= safeSizeOf(key, value); 
      evictionCount++; 
      // TODO: release the lock while calling this potentially slow user code 
      entryEvicted(key, value); 
     } 
     if (size < 0 || (map.isEmpty() && size != 0)) { 
      throw new IllegalStateException(getClass().getName() 
        + ".sizeOf() is reporting inconsistent results!"); 
     } 
    } 
    /** 
    * Removes the entry for {@code key} if it exists. 
    * 
    * @return the previous value mapped by {@code key}. Although that entry is 
    *  no longer cached, it has not been passed to {@link #entryEvicted}. 
    */ 
    public synchronized final V remove(K key) { 
     if (key == null) { 
      throw new NullPointerException("key == null"); 
     } 
     V previous = map.remove(key); 
     if (previous != null) { 
      size -= safeSizeOf(key, previous); 
     } 
     return previous; 
    } 
    /** 
    * Called for entries that have reached the tail of the least recently used 
    * queue and are be removed. The default implementation does nothing. 
    */ 
    protected void entryEvicted(K key, V value) {} 
    /** 
    * Called after a cache miss to compute a value for the corresponding key. 
    * Returns the computed value or null if no value can be computed. The 
    * default implementation returns null. 
    */ 
    protected V create(K key) { 
     return null; 
    } 
    private int safeSizeOf(K key, V value) { 
     int result = sizeOf(key, value); 
     if (result < 0) { 
      throw new IllegalStateException("Negative size: " + key + "=" + value); 
     } 
     return result; 
    } 
    /** 
    * Returns the size of the entry for {@code key} and {@code value} in 
    * user-defined units. The default implementation returns 1 so that size 
    * is the number of entries and max size is the maximum number of entries. 
    * 
    * <p>An entry's size must not change while it is in the cache. 
    */ 
    protected int sizeOf(K key, V value) { 
     return 1; 
    } 
    /** 
    * Clear the cache, calling {@link #entryEvicted} on each removed entry. 
    */ 
    public synchronized final void evictAll() { 
     trimToSize(-1); // -1 will evict 0-sized elements 
    } 
    /** 
    * For caches that do not override {@link #sizeOf}, this returns the number 
    * of entries in the cache. For all other caches, this returns the sum of 
    * the sizes of the entries in this cache. 
    */ 
    public synchronized final int size() { 
     return size; 
    } 
    /** 
    * For caches that do not override {@link #sizeOf}, this returns the maximum 
    * number of entries in the cache. For all other caches, this returns the 
    * maximum sum of the sizes of the entries in this cache. 
    */ 
    public synchronized final int maxSize() { 
     return maxSize; 
    } 
    /** 
    * Returns the number of times {@link #get} returned a value. 
    */ 
    public synchronized final int hitCount() { 
     return hitCount; 
    } 
    /** 
    * Returns the number of times {@link #get} returned null or required a new 
    * value to be created. 
    */ 
    public synchronized final int missCount() { 
     return missCount; 
    } 
    /** 
    * Returns the number of times {@link #create(Object)} returned a value. 
    */ 
    public synchronized final int createCount() { 
     return createCount; 
    } 
    /** 
    * Returns the number of times {@link #put} was called. 
    */ 
    public synchronized final int putCount() { 
     return putCount; 
    } 
    /** 
    * Returns the number of values that have been evicted. 
    */ 
    public synchronized final int evictionCount() { 
     return evictionCount; 
    } 
    /** 
    * Returns a copy of the current contents of the cache, ordered from least 
    * recently accessed to most recently accessed. 
    */ 
    public synchronized final Map<K, V> snapshot() { 
     return new LinkedHashMap<K, V>(map); 
    } 
    @Override public synchronized final String toString() { 
     int accesses = hitCount + missCount; 
     int hitPercent = accesses != 0 ? (100 * hitCount/accesses) : 0; 
     return String.format("LruCache[maxSize=%d,hits=%d,misses=%d,hitRate=%d%%]", 
       maxSize, hitCount, missCount, hitPercent); 
    } 
} 

如何使用 在我的例子，我會在整數密鑰字符串對象映射。限制是2個對象，但你應該改變以實現你的目標。

RemoveOldHashMap<Integer, String> hash = new RemoveOldHashMap<Integer, String>(2 /* here is max value that the internal counter reaches */) { 
    // Override to tell how your object is measured 
    @Override 
    protected int sizeOf(Integer key, String value) { 
     return 1; // the size of your object 
    } 
}; 

參考：LruCache