写点什么

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

作者:zarmnosaj
  • 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); 删除头节点

用户头像

zarmnosaj

关注

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

成都后端混子

评论

发布
暂无评论
LinkedHashMap 源码分析-访问最少删除策略_5月月更_zarmnosaj_InfoQ写作社区