LinkedHashMap 源码分析 - 访问最少删除策略

2022 年 5 月 26 日
本文字数：1914 字
阅读完需：约 6 分钟

LinkedHashMap 源码分析-访问最少删除策略

访问最少删除策略也叫做 LRU（Least recently used,最近最少使用），意思就是经常访问的元素会移动到队尾，不经常访问的数据会在队头的位置，然后可以通过设置的删除策略，比如当元素大于多少个时，把最少使用的元素进行删除。

元素访问与转移

如何实现在访问时，元素被移动到队尾？源码：

public V get(Object key) {    Node<K,V> e;    if ((e = getNode(hash(key), key)) == null)        return null;    if (accessOrder)        afterNodeAccess(e);    return e.value;}

复制代码

if ((e = getNode(hash(key), key)) == null) return null;调用了 HashMap 的 get 方法

if (accessOrder) afterNodeAccess(e);如果设置了 LRU 策略，则会把当前 key 移动到队列的尾部

主要是通过 afterNodeAccess 方法把当前访问节点移动到了队尾

具备相同性质的方法还有：

    public V getOrDefault(Object key, V defaultValue) {       Node<K,V> e;       if ((e = getNode(hash(key), key)) == null)           return defaultValue;       if (accessOrder)           afterNodeAccess(e);       return e.value;   }

复制代码

    default V computeIfAbsent(K key,            Function<? super K, ? extends V> mappingFunction) {        Objects.requireNonNull(mappingFunction);        V v;        if ((v = get(key)) == null) {            V newValue;            if ((newValue = mappingFunction.apply(key)) != null) {                put(key, newValue);                return newValue;            }        }
        return v;    }

复制代码

    public V compute(K key,                     BiFunction<? super K, ? super V, ? extends V> remappingFunction) {        if (remappingFunction == null)            throw new NullPointerException();        int hash = hash(key);        Node<K,V>[] tab; Node<K,V> first; int n, i;        int binCount = 0;        TreeNode<K,V> t = null;        Node<K,V> old = null;        if (size > threshold || (tab = table) == null ||            (n = tab.length) == 0)            n = (tab = resize()).length;        if ((first = tab[i = (n - 1) & hash]) != null) {            if (first instanceof TreeNode)                old = (t = (TreeNode<K,V>)first).getTreeNode(hash, key);            else {                Node<K,V> e = first; K k;                do {                    if (e.hash == hash &&                        ((k = e.key) == key || (key != null && key.equals(k)))) {                        old = e;                        break;                    }                    ++binCount;                } while ((e = e.next) != null);            }        }        V oldValue = (old == null) ? null : old.value;        V v = remappingFunction.apply(key, oldValue);        if (old != null) {            if (v != null) {                old.value = v;                afterNodeAccess(old);            }            else                removeNode(hash, key, null, false, true);        }        else if (v != null) {            if (t != null)                t.putTreeVal(this, tab, hash, key, v);            else {                tab[i] = newNode(hash, key, v, first);                if (binCount >= TREEIFY_THRESHOLD - 1)                    treeifyBin(tab, hash);            }            ++modCount;            ++size;            afterNodeInsertion(true);        }        return v;    }

复制代码

这些方法都是对于元素在访问时，不断的把访问的经常访问的节点移动到队尾，那么靠近队头的节点，自然就是很少被访问的元素了。

删除

void afterNodeInsertion(boolean evict) {     LinkedHashMap.Entry<K,V> first;    if (evict && (first = head) != null && removeEldestEntry(first)) {        K key = first.key;        removeNode(hash(key), key, null, false, true);    }}

复制代码

LinkedHashMap.Entry<K,V> first; 得到元素头节点

if (evict && (first = head) != null && removeEldestEntry(first)) removeEldestEntry()控制删除策略，如果队列不为空，并且删除策略允许删除的情况下，删除头节点

removeNode(hash(key), key, null, false, true); 删除头节点

发布于: 3 小时前阅读数: 6

zarmnosaj

关注

靡不有初，鲜克有终 2020.02.06 加入

成都后端混子

发布

暂无评论

创作场景

LinkedHashMap 源码分析 - 访问最少删除策略

LinkedHashMap 源码分析-访问最少删除策略

元素访问与转移

删除

zarmnosaj

评论