在Java中使用LinkedHashMap进行缓存的hashmap

Question

我不熟悉使用哈希表结构。我正在使用LinkedHashMap（例如：cache = new LinkedHashMap<K,V>(...)）实现我自己的缓存。我有一系列关于此数据结构的问题：

1. 参数I表示存储桶中的项目数限制为100（例如，存储桶中的项目数I）。那么，如果我将一个新项目插入到这个缓存中（当缓存大小=100时），我认为将发生逐出策略的想法是否正确

2. 在我的实现中，键是复合对象，包括以下两项：

   class Key {
   
    public string a;
    public string b;
        @Override
        public int hashCode() {
           final int prime = 31;
            int result = 1;
            result = prime * result + ((a == null) ? 0 : a.hashCode());
            result = prime * result + ((b == null) ? 0 : b.hashCode());
            return result;
        }
    }
   

   使用这个hashcode()，假设这个bucket已经有100个项目。当我插入一个新项时，假设hashcode()返回一个与前一项重复的键，我的理解是linkedhashmap将使用逐出策略删除最旧的项，并使用linkedlist处理新项的冲突，因此bucket中的项数将为99。是这样吗

3. 有没有办法确定当前存储桶中的哪些条目包含用于处理冲突的链

Answer 1

答复第一个问题：

1. 您需要明确地覆盖方法removeEldest，以使逐出工作

默认实现返回false，因此不会删除任何元素：

protected boolean removeEldestEntry(Map.Entry<K,V> eldest) {
    return false;
}

1. 问题二：如果不重写方法removeEldest

2. 问题三：我认为没有办法处理这种情况

请阅读这篇有用的文章，以便更熟悉基于LinkedHahMap的eviciton算法：

http://javarticles.com/2012/06/lru-cache.html

对于补充讲座，请阅读关于LFU驱逐的内容：http://javarticles.com/2012/06/lfu-cache.html

Answer 2

容量不是固定的。它将根据地图使用情况动态变化

来自javadocs：

An instance of HashMap has two parameters that affect its performance: initial capacity and load factor. The capacity is the number of buckets in the hash table, and the initial capacity is simply the capacity at the time the hash table is created. The load factor is a measure of how full the hash table is allowed to get before its capacity is automatically increased. When the number of entries in the hash table exceeds the product of the load factor and the current capacity, the hash table is rehashed (that is, internal data structures are rebuilt) so that the hash table has approximately twice the number of buckets.

所以map不会根据条目的数量删除条目

要使用的Simple cache由guava图书馆提供

Answer 3

I set a parameter capcity = 100 (eg.), it means that number of items in bucket limit to 100. Then if I insert new item to this cache (when cache size = 100), the evict policy will happen,right?

不，capacity参数是对构造函数的一个提示，提示您希望映射的大小。它使用此选项试图避免在添加元素时不必要地调整贴图的大小。如果添加的容量超过了指定的容量，则只需调整贴图大小即可有效地容纳更多元素

when I insert new item, assuming that hashcode() return a duplicate key with one of previous items, then linkedhashmap will remove the eldest item as evict policy and use linkedlist to handle collision for new item, so the number items in bucket will be 99, is it right ?

不，如果用相同的哈希代码插入两个不相等的元素，它们将被简单地放在同一个bucket中，但它们仍然存在并且可以访问。当然，如果指定一个键等于映射中当前存在的键，该条目将被覆盖

Is there any way to identify which entries in the bucket current contain a chain for handle collision?

通常不会。你可以使用反射，但那最多也很难。你想完成什么，让你觉得你需要这样做

---

LinkedHashMap提供的缓存行为取决于扩展类和实现^{}。正如您在该方法的示例中所看到的，您可以添加一个检查，例如size() > MAX_ENTRIES，以指示映射在调用put()或putAll()时删除最旧的元素

如果你需要一个更强大的缓存，你可能会喜欢Guava's ^{} and ^{}类