转载

LinkedHashMap实现原理

HashMap存放是无序的，当以一定顺序put时候，HashMap是以key的hash值顺序保存的，迭代器遍历时是无序的，有时候我们需要一款以插入顺序返回的map,于是LinkedHashMap应运而生。

实现原理

LinkedHashMap基于HashMap的实现，只不过在table之外，额外维护了一个双向链表。实现newNode，afterNodeRemoval等方法方法，put及remove时候维护链表的增减其内部子类实现Iterator接口，返回链表数据内部逻辑图如下

LruCache与LinkedHashMap

利用LinkedHashMap特性实现lru队列很简单，当队列缓存满了，会有限淘汰头部节点，每次get请求会将该节点放置到队列尾，那么头节点就是不经常使用的数据了，利用removeEldestEntry 方法，在put时候判断并淘汰数据。代码如下 public class MyLruCache<K,V> { private static final float hashTableLoadFactor = 0.75f; private LinkedHashMap<K, V> map; private int cacheSize;

public MyLruCache(int cacheSize) {
    this.cacheSize = cacheSize;
    int hashTableCapacity= (int) (Math.ceil(cacheSize/hashTableLoadFactor)+1);
    map=new LinkedHashMap<K,V>(hashTableCapacity,hashTableLoadFactor,true){
      
        @Override
        protected boolean removeEldestEntry(Map.Entry<K, V> eldest) {
            return size() > MyLruCache.this.cacheSize;
        }
    };
}

public V get(K key){
    return map.get(key);
}
public void put(K key,V value){
    map.put(key,value);
}
public synchronized int usedEntries() {
    return map.size();
}
public synchronized void clear() {
    map.clear();
}
public synchronized Collection<Map.Entry<K, V>> getAll() {
    return new ArrayList<Map.Entry<K, V>>(map.entrySet());
}
}
复制代码

本文参考https://juejin.im/post/5a4b433b6fb9a0451705916f 如果侵权，告知马上处理

原文 https://juejin.im/post/5d3c4180e51d454f6f16ece7

正文到此结束